---

Problem 186

---

Connectedness of a network

Here are the records from a busy telephone system with one million users:

Rec Nr	Caller	Called
1	200007	100053
2	600183	500439
3	600863	701497
…	…	…

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 ≤ k ≤ 55, S_k = [100003 - 200003k + 300007k³] (modulo 1000000)
For 56 ≤ 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?

---

网络连通性

以下是一个有着一百万用户的忙碌电话系统的部分记录：

编号	呼叫	接听
1	200007	100053
2	600183	500439
3	600863	701497
…	…	…

编号为n的记录中，呼叫者的电话号码是Caller(n) = S_2n-1，接听者的电话号码是Called(n) = S_2n，其中S_1,2,3,…来自于所谓“延迟斐波那契随机数生成器”：

对于1 ≤ k ≤ 55，S_k = [100003 - 200003k + 300007k³] (modulo 1000000)
对于56 ≤ k，S_k = [S_k-24 + S_k-55] (modulo 1000000)

如果Caller(n) = Called(n)，那么我们认为呼叫者拨错了号码，呼叫失败；否则我们认为呼叫成功。

根据这份记录，如果X曾经呼叫过Y或者Y呼叫过X，则我们认为这两个电话用户X和Y是朋友。同样的，如果X是Y的朋友，Y是Z的朋友，那么我们说X是Z的朋友的朋友；我们可以同理组成更长的“朋友”链。

首相的电话号码是524287。在多少次呼叫成功（不计呼叫失败）之后，99%的用户（包括首相）将会成为首相的朋友，或是朋友的朋友，或是朋友的朋友的朋友……？

---