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.


Cevap: 9922545104535661
Python:

from array 
import array

def main():
    target = 1000000000000000
    start = rand = 14025256
    a = array('b')
    while rand != start or len(a) == 0:
        for c in str(rand):
            a.append(int(c))
        rand = rand * rand % 20300713

    max_sum = sum(a)
    a *= 2
    seen = array('b', '\0' * (max_sum + 1))
    num_seen = 0
    c = 0
    j = 0
    while num_seen <= max_sum:
        i = j
        n = a[i]
        while n <= max_sum:
            if not seen[n]:
                seen[n] = 1
                num_seen += 1
                c += (j + 1) * ((target - n) // max_sum + 1)
            i += 1
            n += a[i]
        j += 1
    print c

main()

C++:

#include 
#include 
#include 

Pascal:

const n=2000000000000000;
var s:QWord;
 t:array[0..100000000] of integer;
 ts:array[0..100000000] of 0..9;
 tr:array[1..10] of 0..9;
 i,su,k,j,l,sl:longint;
 
function ismiss():boolean;
var i:longint;
 flag:boolean;
begin
 flag:=false;
 for i:=0 to l do
  if t[i]=0 then flag:=true;
 ismiss:=flag;
end;

begin
 s:=14025256;
 i:=1;
 while (s<>14025256) or (i=1) do
 begin
  su:=s;
  j:=1;
  while su<>0 do
  begin
   tr[j]:=su mod 10;
   su:=su div 10;
   j:=j+1
  end;
  for k:=1 to j-1 do
   ts[i+k-1]:=tr[j-k];
  s:=s*s mod 20300713;
  i:=i+j-1;
 end;
 l:=i-1;
 ts[0]:=ts[l];
 
 sl:=0;
 for i:=1 to l do
  sl:=sl+ts[i];
 
 i:=0;
 while ismiss do
 begin
  i:=i+1;
  su:=ts[i];
  j:=i;
  while su<=sl do
  begin
   if t[su]=0 then t[su]:=i;
   j:=j+1;
   su:=su+ts[j mod l];
  end;
 end;
 
 s:=0;
 for i:=0 to sl do s:=s+t[i]*(1+trunc((n-i)/sl));
 writeln(s-3+170*trunc(n/sl));
 readln;
end.

C#:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.Drawing;
using System.IO;

using MathUtilities;

namespace MathProblems
{
    public class Problem238
    {
        /// 

        /// Problem238 - Infinite string tour
        /// 
        public void Run()
        {
            long limit = 2 * Utilities.Pow(10, 15);

            InitializePValues();

            Console.WriteLine("Sum p(k) for 0 < k <= {0} = {1}", limit, SumP(limit));
        }

        long SumP(long limit)
        {
            long numCycles = limit / sumAllBbsDigits;
            long total = cycleSum * numCycles;
            for (int k = 1; k <= limit % sumAllBbsDigits; k++)
                total += pValues[k];

            return total;
        }

        int[] pValues;

        long cycleSum;

        void InitializePValues()
        {
            InitializeBBSDigits();
            int limit = sumAllBbsDigits;
            pValues = new int[limit];
            cycleSum = 0;
            int numFilledIn = 0;

            for (int pos = 0; pos < limit; pos++)
            {
                int sum = 0;
                int idx = pos;
                while (numFilledIn < limit)
                {
                    sum += bbsDigits[idx % bbsDigits.Count];
                    if (sum >= limit)
                        break;
                    if (pValues[sum] == 0)
                    {
                        pValues[sum] = pos + 1;
                        cycleSum += pos + 1;
                        numFilledIn++;
                    }
                    idx++;
                }
            }

            // Adjust the sum to include p(sumAllBbsDigits) and exclude p(0)
            cycleSum += pValues[1] - pValues[0];
        }

        long randCurrent = 14025256;

        long Rand()
        {
            long result = randCurrent;
            randCurrent = (randCurrent * randCurrent) % 20300713;
            return result;
        }

        List bbsDigits = new List();

        int sumAllBbsDigits;

        void InitializeBBSDigits()
        {
            long initial = Rand();
            long current = initial;
            do
            {
                string s = current.ToString();
                for (int i = 0; i < s.Length; i++)
                    bbsDigits.Add((byte)(s[i] - '0'));
                current = Rand();
            }
            while (current != initial);

            sumAllBbsDigits = 0;
            for (int i = 0; i < bbsDigits.Count; i++)
                sumAllBbsDigits += bbsDigits[i];
        }
    }
}