---

Problem 238

---

Infinite string tour

Create a sequence of numbers using the “Blum Blum Shub” pseudo-random number generator:

$s\_0=14025256$ $s\_{n+1}=s\_n^2 \text{ mod }20300713$

Concatenate these numbers  s₀s₁s₂… to create a string w of infinite length.
Then, w = 14025256741014958470038053646…

For a positive integer k, if no substring of w exists with a sum of digits equal to k, p(k) is defined to be zero. If at least one substring of w exists with a sum of digits equal to k, we define p(k) = z, where z is the starting position of the earliest such substring.

For instance:

The substrings 1, 14, 1402, …
with respective sums of digits equal to 1, 5, 7, …
start at position 1, hence p(1) = p(5) = p(7) = … = 1.

The substrings 4, 402, 4025, …
with respective sums of digits equal to 4, 6, 11, …
start at position 2, hence p(4) = p(6) = p(11) = … = 2.

The substrings 02, 0252, …
with respective sums of digits equal to 2, 9, …
start at position 3, hence p(2) = p(9) = … = 3.

Note that substring 025 starting at position 3, has a sum of digits equal to 7, but there was an earlier substring (starting at position 1) with a sum of digits equal to 7, so p(7) = 1, not 3.

We can verify that, for 0 < k ≤ 10³, ∑ p(k) = 4742.

Find ∑ p(k), for 0 < k ≤ 2·10¹⁵.

---

无穷长字符串遍历

使用“布鲁姆-布鲁姆-舒布”伪随机数生成算法生成如下的数字序列：

$s\_0=14025256$ $s\_{n+1}=s\_n^2 \text{ mod }20300713$

将这些数s₀s₁s₂…连接起来组成一个无穷长的字符串w。
可知w = 14025256741014958470038053646…

对于正整数k，如果w不存在任意子串的各位数字和等于k，则p(k)被定义为0。如果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.

注意开始位置为3的子串025各位数字和是7，但由于存在更早出现的子串（开始位置为1）各位数字和为7，因此p(7) = 1，而不是 3。

我们可以验证，对于0 < k ≤ 10³，∑ p(k) = 4742。

对于0 < k ≤ 2·10¹⁵，求∑ p(k)。

---