186 : あるネットワークの連結性

100万人のユーザをもつ電話システムの通信記録がある。

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

$n$番目の記録の掛けた側と掛けられた側の電話番号は $\textrm{Caller}(n) = S_{2n-1}$ と $\textrm{Called}(n) = S_{2n}$ で与えられる。$S_1, S_2, \dots$は『ラグ付きフィボナッチ生成器』で定義される：

$1 ≤ k ≤ 55$については、$S_k = [(100003 - 200003k + 300007k^3) \bmod 1000000]$

$56 ≤ k$では、$S_k = [(S_{k-24} + S_{k-55}) \bmod 1000000]$である.

もし $\textrm{Caller}(n) = \textrm{Called}(n)$ であれば、ユーザは間違って電話を掛けたとされ通信は切断される。そうでない場合には、通信は成功している。

X が Y に電話を掛けるかその逆のときに、ユーザ X とユーザ Y が友達であると呼ぶ。同様に、X が Y の友達であるかつ Y が Z の友達であるとき、X が Z の友達の友達であると呼ぶ。同様にして長い連鎖が得られる。

首相の電話番号は524287である。首相自身も含めた全ユーザのうち99%が首相の友達、または友達の友達、…になるには、間違い電話を除いて何回電話を掛ける必要があるか？