Euler Projesi 238. Soru

Sonsuz Dizgi Turu

"Blum Blum Shub" sözde rasgele sayı üreteci kullanarak bir sayı dizgisi oluşturun:

s₀=14025256

s_n+1=s_n² mod 20300713

Sonsuz uzunlukta bir w dizgisi oluşturmak için s₀s₁s₂… sayılarını birleştirin. Bu durumda w = 14025256741014958470038053646... olur.

Pozitif bir tamsayı k için, eğer rakamları toplamı k'ya eşit olmayan w'nun bir alt dizgisi yoksa, p(k) sıfır olarak tanımlanır. Eğer rakamları toplamı k'ya eşit olan w'nun en az bir alt dizgisi varsa, p(k) = z'yi tanımlarız; burada z, ilk bu tür alt dizginin başlangıç konumudur.

Örneğin;

1, 14, 1402, … alt dizgilerinin
karşılıklı basamak toplamları 1, 5, 7, … olup
1 pozisyonundan başladığı için p(1) = p(5) = p(7) = … = 1.

4, 402, 4025, … alt dizgilerinin
karşılıklı basamak toplamları 4, 6, 11, … olup
2 pozisyonundan başladığı için p(4) = p(6) = p(11) = … = 2.

02, 0252, … alt dizgilerinin
karşılıklı basamak toplamları 2, 9, … olup
3 pozisyonundan başladığı için p(2) = p(9) = … = 3.

3 konumunda başlayan 025 alt dizgisinin 7'ye eşit bir rakam toplamına sahip olduğuna dikkat edin, ancak 7'ye eşit rakamları toplamı olan daha önce bir alt dizgi (konum 1'den başlayan) vardı, bu nedenle p(7) = 1 değil 3'tür.

0 < k ≤ 10³ için ∑ p(k) = 4742 olduğunu gösterebiliriz.

0 < k ≤ 2·10¹⁵ için ∑ p(k) değerini bulunuz.