RSS Feed
Precedenta

Problema 238

29 Martie 2009

Turul printr-un șir infinit


Creează un șir de numere folosind generatorul de numere pseudo-aleatorii "Blum Blum Shub":

s0 = 14025256
sn+1 = sn2 mod 20300713

Alătură aceste numere  s0s1s2… pentru a forma un șir w de lungime infinită.
Atunci, w = 14025256741014958470038053646…

Pentru un număr întreg pozitiv k, dacă nu există nici un subșir al lui w cu suma cifrelor egală cu k, p(k) e definit ca fiind zero. Dacă există cel puțin un subșir al lui w cu suma cifrelor egală cu k, o să zicem că p(k) = z, unde z e poziția de început a primei apariții a unui astfel de subșir.

De exemplu:

Subșirurile 1, 14, 1402, …
cu sumele cifrelor egale cu 1, 5, 7, …
încep la poziția 1, prin urmare p(1) = p(5) = p(7) = … = 1.

Subșirurile 4, 402, 4025, …
cu sumele cifrelor egale cu 4, 6, 11, …
încep la poziția 2, prin urmare p(4) = p(6) = p(11) = … = 2.

Subșirurile 02, 0252, …
cu sumele cifrelor egale cu 2, 9, …
încep la poziția 3, prin urmare p(2) = p(9) = … = 3.

Ține cont că subșirul 025 care începe la poziția 3, are o suma cifrelor egală cu 7, dar a existat un subșir înaintea lui (începând cu poziția 1) cu suma cifrelor de asemenea egală cu 7, deci p(7) = 1, nu 3.

Se poate verifica că, pentru 0 < k ≤ 103, ∑ p(k) = 4742.

Găsește ∑ p(k), pentru 0 < k ≤ 2·1015.


>> Vezi problema originală <<