Detailed mathematical approach

Problem Summary

There are \(N=1000000\) subscribers labeled \(0,1,\dots,999999\). The distinguished subscriber is the Prime Minister, whose number is \(524287\). Call attempts are generated by the deterministic sequence

$S_k=(100003-200003k+300007k^3)\bmod 1000000 \qquad (1\le k\le 55),$

$S_k=(S_{k-24}+S_{k-55})\bmod 1000000 \qquad (k\ge 56).$

The \(n\)-th call attempt uses the ordered pair \((S_{2n-1},S_{2n})\). If the two numbers are equal, the call is a misdial and does not count. Otherwise it is a successful call and creates an undirected connection between those two subscribers. The goal is to find the first successful-call count \(t\) for which the Prime Minister belongs to a connected component of size at least \(99\%\) of the network, namely \(990000\) subscribers.

Mathematical Approach

The graph only grows: successful calls add edges, and nothing ever removes one. Because of that, the problem is really about tracking a partition of the subscriber set into connected components, not about storing the whole history of calls.

The call stream is deterministic

Although the story describes a pseudo-random telephone log, the data are completely determined by the recurrence for \(S_k\). Once the first 55 values are fixed, every later value follows from the lagged relation \(S_{k-24}+S_{k-55}\). So the problem is not probabilistic after the sequence definition is given: it is a fixed graph process on the vertex set

$V=\{0,1,\dots,999999\}.$

Every call attempt is simply one more edge candidate produced by this stream.

Successful calls define a growing graph

Let \((u_t,v_t)\) be the \(t\)-th successful call, so \(u_t\ne v_t\). After \(t\) successful calls define

$G_t=(V,E_t),\qquad E_t=\bigl\{\{u_i,v_i\}:1\le i\le t\bigr\}.$

If the same pair appears again, or if a new call connects two subscribers that were already linked through earlier calls, the graph \(G_t\) does not gain a new connected component structure; only the successful-call counter increases. This distinction matters because the answer is the number of successful calls, not the number of component merges.

Write \(C_t(524287)\) for the connected component containing the Prime Minister after \(t\) successful calls. Since edges are only added, connected components can merge but never split, so the size \(\lvert C_t(524287)\rvert\) is monotone nondecreasing.

The key invariant: only the component partition matters

Initially every subscriber is isolated, so the graph has \(1000000\) singleton components. Now process the successful calls one by one.

If a successful call joins two different components, those two components merge into one. If it joins two subscribers that are already in the same component, connectivity does not change at all. Therefore the entire state of the problem can be represented by the current partition of \(V\) into connected components together with the size of each part.

This is exactly why disjoint-set union works. The inductive invariant is simple: after every processed successful call, the disjoint-set classes are exactly the connected components of \(G_t\).

The proof is immediate from the two cases above. Because the invariant is exact, there is no need for adjacency lists, breadth-first search, or repeated graph traversals.

Worked example: a successful call need not enlarge the PM component

Consider a toy network with subscribers \(\{0,1,2,3,4,5\}\) and suppose the Prime Minister were \(0\). Process the successful calls

$ (0,1),\ (2,3),\ (1,2),\ (0,3). $

After the first three successful calls, the PM component is already \(\{0,1,2,3\}\), so its size is \(4\). The fourth call is still successful because \(0\ne 3\), so the successful-call counter increases by one, but the connected components do not change at all because \(0\) and \(3\) were already connected. This is the exact behavior the implementation must capture: count every non-misdial call, but merge components only when the two endpoints currently have different representatives.

The stopping condition for Problem 186

For the actual Euler instance the target is

$\left\lfloor 0.99\cdot 1000000\right\rfloor=990000.$

So the required answer is

$\min\bigl\{t\ge 0:\lvert C_t(524287)\rvert\ge 990000\bigr\}.$

Because the component size is monotone, once this inequality becomes true it stays true, so a single left-to-right scan of the call stream is enough.

How the Code Works

Generating callers and callees

The C++, Python, and Java implementations all reproduce the same lagged Fibonacci stream and consume it two values at a time to form call attempts. The C++ implementation keeps only the last 55 values in a circular structure, which is sufficient for the recurrence. The Python and Java implementations instead grow a dynamic sequence as more values are requested. The C++ version also checks the published prefix \(200007,100053,600183,500439,600863,701497\) before starting the main computation.

Maintaining connectivity and the answer counter

All three implementations store, for each subscriber, a current representative and the size of the represented component. Path compression and union by size keep these operations fast. For each call attempt, a self-call is skipped immediately. Otherwise the successful-call counter is incremented, the two endpoints are merged if they belong to different components, and then the size of the component containing subscriber \(524287\) is tested against \(990000\). The first time the threshold is met, the current counter is the answer.

Complexity Analysis

Let \(A\) be the number of call attempts examined before the threshold is first reached, and let \(T\le A\) be the number of successful calls among them. Producing the sequence costs \(O(A)\). The connectivity maintenance costs \(O(T\,\alpha(N))\), where \(\alpha\) is the inverse Ackermann function and \(N=1000000\). In practice \(\alpha(N)\) is tiny, so the overall running time is effectively linear in the number of processed calls.

The dominant memory usage is the disjoint-set structure, which stores one parent and one component size for each subscriber, hence \(O(N)\) space. The C++ implementation needs only \(O(1)\) extra storage for the sequence generator, while the Python and Java implementations keep a growing generated prefix in addition to the \(O(N)\) connectivity arrays.

Footnotes and References

1. Project Euler problem page: Project Euler 186
2. Connected component: Wikipedia - Connected component
3. Disjoint-set data structure: Wikipedia - Disjoint-set data structure
4. Lagged Fibonacci generator: Wikipedia - Lagged Fibonacci generator
5. Inverse Ackermann function: Wikipedia - Inverse Ackermann function