Statement

The telephone number of the caller and the called number in record n are Caller(n) = S_2n-1 and Called(n) = S_2n where S_1,2,3,… come from the "Lagged Fibonacci Generator":

For 1 $\leq$ k $\leq$ 55, S_k = [100003 - 200003k + 300007k³] (modulo 1000000)
For 56 $\leq$ k, S_k = [S_k-24 + S_k-55] (modulo 1000000)

If Caller(n) = Called(n) then the user is assumed to have misdialled and the call fails; otherwise the call is successful.

From the start of the records, we say that any pair of users X and Y are friends if X calls Y or vice-versa. Similarly, X is a friend of a friend of Z if X is a friend of Y and Y is a friend of Z; and so on for longer chains.

The Prime Minister's phone number is 524287. After how many successful calls, not counting misdials, will 99% of the users (including the PM) be a friend, or a friend of a friend etc., of the Prime Minister?

Solution

The solution of this problem is quite straightforward. I will use a list which will hold sets, each of them will represent the nodes in a connected graph.

First of all a generator is needed in order to produce the caller and called of each phone call. For that I use a generator function implemented with the yield instruction.

The next thing to keep in mind is that once you know the caller and called how can you efficiently find in which connected graphs are they in. To accomplish this, the set's list will hold for position i the set where i is in or the position where it was moved to. If a number was moved several times you need to follow the chain of indexes until you find a set.

Having mentioned the two key techniques used it is easy to code the program that solves the problem. "While the connected graph that the president is in is less than 990000(99%): get the next phone call, find the graphs of each of the participants, if they differ then join both sets in one and in the other's position set the corresponding reference.".

from collections import deque
 
def generator():
    queue_55 = deque()
    queue_24 = deque()
    for k in range(1, 56):
        s_k = (100003 - 200003 * k + 300007 * (k ** 3)) % 1000000
        queue_55.append(s_k)
        if k >= 32:
            queue_24.append(s_k) 
        yield s_k
    while True:
        s_k = (queue_55.popleft() + queue_24.popleft()) % 1000000
        queue_55.append(s_k)
        queue_24.append(s_k) 
        yield s_k
 
graph_list = [set([i]) for i in range(1000000)]
 
def get_pos_of(i):
    while isinstance(graph_list[i], int):
        i = graph_list[i]
    return i
 
if __name__ == '__main__':
    gen = generator()
    res = 0
    while len(graph_list[get_pos_of(524287)]) < 990000:
        c1 = next(gen)
        c2 = next(gen)
        if c1 == c2:
            continue
        res += 1
        i1 = get_pos_of(c1)
        i2 = get_pos_of(c2)
        if i1 != i2:
            to_put_into = min(i1, i2)
            to_remove = max(i1, i2)
            graph_list[to_put_into] |= (graph_list[to_remove])
            graph_list[to_remove] = to_put_into        
    print("The result is:", res)

The Python file is available for download here.