Создайте последовательность чисел с помощью генератора псевдослучайных чисел "Blum Blum Shub":
| s0 | = | 14025256 |
| sn+1 | = | sn2 mod 20300713 |
Соедините эти числа s0s1s2… чтобы получить строку 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 ≤ 103, ∑ p(k) = 4742.
Найдите ∑ p(k) для 0 < k ≤ 2·1015.