Задача 186
Связанность сети

Вот несколько записей загруженной телефонной системы с миллионом пользователей:

CallerCalled
1200007100053
2600183500439
3600863701497
.........

В строке № n телефонный номер звонящего и вызываемый номер являются Caller(n) = S_(2n-1) и Called(n) = S_(2n) соответственно, где S_(1,2,3,...) образуются "Генератором Фибоначчи с задержкой":

При 1 ≤ k ≤ 55, S_(k) = [100003 - 200003k + 300007k^(3)] (modulo 1000000)
При 56 ≤ k, S_(k) = [S_(k-24) + S_(k-55)] (modulo 1000000)

Если Caller(n) = Called(n), то предполагается, что пользователь ошибся в наборе номера, и вызов не происходит. В противном случае вызов происходит успешно.

Оговорим, что начиная с первой строки, любая пара пользователей X и Y - друзья, если X звонит Y или наоборот. Аналогично, X будет другом друга Z, если X является другом Y, который, в свою очередь является другом Z; и так далее, с образованием более длинных цепочек.

Номер премьер-министра 524287. После скольких удачных звонков, не считая неправильный набор, 99% пользователей (включая самого премьер-министра), окажутся друзьями премьер-министра, друзьями его друзей и т.д.?

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net