Задача 238
Бесконечное путешествие по строке

Создайте последовательность чисел с помощью генератора псевдослучайных чисел "Blum Blum Shub":

s_(0) = 14025256
s_(n+1) = s_(n)^(2) mod 20300713

Соедините эти числа  s_(0)s_(1)s_(2)… чтобы получить строку w бесконечной длины.
Тогда, w = 14025256741014958470038053646…

Для положительного целого числа k, если не существует такой подстроки w, сумма чьих цифр равна k, p(k) определяется как равное нулю. Если существует хотя бы одна подстрока w, сумма чьих цифр равна k, мы определим p(k) = z, где z - начальная позиция первой такой подстроки.

Для примера:

Подстроки 1, 14, 1402, …
с суммами цифр 1, 5, 7, … соответственно
начинаются с позиции 1, посему p(1) = p(5) = p(7) = … = 1.

Подстроки 4, 402, 4025, …
с суммами цифр 4, 6, 11, … соответственно
начинаются с позиции 2, посему p(4) = p(6) = p(11) = … = 2.

Подстроки 02, 0252, …
с суммами цифр 2, 9, … соответственно
начинаются с позиции 3, посему p(2) = p(9) = … = 3.

Обратите внимание, что подстрока 025, начинающаяся с позиции 3, имеет сумму цифр, равную 7, однако существует подстрока до нее (начинающаяся с позиции 1) с суммой цифр, равной 7, поэтому p(7) = 1, а не 3.

Можно показать, что для 0 < k ≤ 10^(3), p(k) = 4742.

Найдите p(k) для 0 < k ≤ 2·10^(15).

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