题目238：无穷字符串之旅

欧拉计划

Infinite string tour

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

s₀ = 14025256
s_n+1 = s_n² 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&#8201;<&#8201;k&#8201;≤&#8201;10³, ∑&#8201;p(k) = 4742.

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

题目：

通过 "Blum Blum Shub" 伪随机数生成器产生一个数字序列：

s₀ = 14025256
s_n+1 = s_n² mod 20300713

连接这些数字 &#8201;s₀s₁s₂…  得到一个无穷长的字符串 w。
也就有，w =&#8201;14025256741014958470038053646…

对于一个正整数 k， 如果不存在一个 w 的子串使得其数字之和为 k，定义 p(k) 为 0。如果至少存在一个 w 的子串满足其数字之和为 k，定义 p(k)&#8201;=&#8201;z，其中 z 为第一个子串的起始位置。

例如：

子串 1, 14, 1402, …
各自的数字之和等于 1, 5, 7, …
起始位置为 1，因此 p(1)&#8201;=&#8201;p(5)&#8201;=&#8201;p(7)&#8201;=&#8201;…&#8201;=&#8201;1。

子串 4, 402, 4025, …
各自的数字之和等于 4, 6, 11, …
起始位置为 2，因此 p(4)&#8201;=&#8201;p(6)&#8201;=&#8201;p(11)&#8201;=&#8201;…&#8201;=&#8201;2。

子串 02, 0252, …
各自的数字之和等于 2, 9, …
起始位置为 3，因此 p(2)&#8201;=&#8201;p(9)&#8201;=&#8201;…&#8201;=&#8201;3。


注意子串 025 起始位置为 3，数字之和等于 7，但有更早出现的子串（起始位置为 1）数字之和等于 7，所以 p(7)&#8201;=&#8201;1，而不是  3。

我们已经得到，对于 0&#8201;<&#8201;k ≤&#8201;10³，∑&#8201;p(k) = 4742。

求 ∑&#8201;p(k)，其中 0&#8201;<&#8201;k ≤&#8201;2·10¹⁵。