Start with \(s_0=14025256\) and iterate
$$s_{n+1}=s_n^2 \pmod{20300713}.$$
Write the decimal expansions of \(s_0,s_1,s_2,\dots\) one after another to obtain an infinite digit string \(w=w_1w_2w_3\cdots\). For each positive integer \(k\), define \(p(k)\) to be the smallest starting position \(z\ge 1\) for which there exists an ending position \(y\ge z\) such that the digit sum of the block \(w_z w_{z+1}\dots w_y\) is exactly \(k\). The problem asks for
$$\sum_{k=1}^{2\cdot 10^{15}} p(k).$$
A direct attack is impossible: the outer summation is enormous, and the string itself is infinite. The solution used by the implementations turns the problem into finite data extracted from one period of the quadratic generator.
The key objects are the state cycle of the modular recurrence, the resulting periodic digit block, and the prefix sums of that block taken modulo one full-period digit sum.
The recurrence evolves in a finite state space, so some state must eventually repeat. Once a state repeats, the future trajectory repeats as well. In this problem the repetition is especially clean: the first repeated state is the initial seed itself, so there is no transient prefix before the cycle starts.
Therefore the sequence of generated integers is a pure cycle from \(s_0\) onward. Concatenating their decimal representations gives a digit block
$$d_1,d_2,\dots,d_L$$
that repeats forever. The implementations discover this period directly and obtain
$$L=18{,}886{,}117,\qquad S=\sum_{i=1}^{L} d_i = 80{,}846{,}691.$$
Here \(L\) is the number of digits in one full period, and \(S\) is the sum of the digits in that period.
Define the one-period prefix sums by
$$P_0=0,\qquad P_i=\sum_{t=1}^{i} d_t\quad (1\le i\le L).$$
Then \(P_L=S\). Because the digit block repeats, every prefix sum of the infinite string has the form
$$T_{mL+i}=mS+P_i,\qquad m\ge 0,\ 0\le i\le L,$$
where \(T_n=w_1+\cdots+w_n\) is the sum of the first \(n\) digits of the infinite string.
A block beginning at position \(z\) and ending at position \(y\) has digit sum \(k\) exactly when
$$T_y-T_{z-1}=k.$$
So \(p(k)\) is the smallest \(z\) for which this equation has at least one solution \(y\ge z\).
Write \(z-1=mL+b\) with \(0\le b<L\). Then
$$T_{z-1}=mS+P_b.$$
If we want a block of digit sum \(k\) starting at \(z\), we need
$$T_y=mS+P_b+k.$$
But every \(T_y\) is some \(qS+P_i\), so the existence of such a \(y\) is equivalent to the congruence
$$P_i\equiv P_b+k \pmod S$$
for at least one \(i\in\{0,1,\dots,L\}\). This leads to the residue set
$$R=\{P_i\bmod S:0\le i\le L\}.$$
Now the entire question “does position \(z\) work for target sum \(k\)?” becomes the finite test
$$\big(P_b+k\big)\bmod S\in R.$$
That is exactly the condition checked in the implementations. The infinite search over end positions is reduced to a residue lookup.
The validity test depends on \(k\) only through \(k\bmod S\). Therefore the set of starting positions that work for \(k\) is the same as the set of starting positions that work for \(k+S\), so
$$p(k+S)=p(k).$$
There is a second periodicity as well: the starting residue repeats every \(L\) digits, so whether position \(z\) works depends only on \((z-1)\bmod L\). Hence, whenever a target sum is attainable, its earliest valid start lies within the first period.
As a result, it is enough to compute \(p(1),p(2),\dots,p(S)\) once. If \(N=2\cdot10^{15}\), then
$$\sum_{k=1}^{N} p(k)=\left\lfloor\frac{N}{S}\right\rfloor\sum_{k=1}^{S}p(k)+\sum_{k=1}^{N\bmod S}p(k).$$
This is the central reduction in the problem: a huge outer range collapses to one finite period in \(k\).
The infinite string begins with the decimal expansions of \(14025256,7410149,5847003,\dots\), so its first digits are
$$1,4,0,2,5,2,5,6,7,4,1,0,1,4,9,\dots$$
The corresponding prefix sums begin
$$0,1,5,5,7,12,14,19,25,32,36,37,37,38,42,51,\dots$$
Take \(k=6\). Starting at \(z=1\) would require a later prefix sum equal to \(6\), but the running totals jump from \(5\) to \(7\), so no substring beginning at the first digit has digit sum \(6\).
Starting at \(z=2\), however, the starting prefix sum is \(1\), and \(1+6=7\) does appear later as a prefix sum. Therefore the block \(4,0,2\) has digit sum \(6\), so
$$p(6)=2.$$
This is a miniature version of the full method: subtract the prefix sum at the starting position, look for the shifted target among the visited prefix residues, and take the earliest start that succeeds.
The C++, Python, and Java implementations iterate the quadratic recurrence from the given seed, remember the first occurrence of each generated state, and stop when a state repeats. Because the repeated state is the seed, the collected decimal digits already form one complete period of the infinite string. The implementations then build the one-period prefix sums and the total digit sum \(S\).
Next, the implementation marks every residue \(P_i\bmod S\) in a dense membership table and also stores the repeating sequence of starting residues \(P_0,P_1,\dots,P_{L-1}\bmod S\). These two arrays encode the mathematical criterion above: for a candidate start position and a target \(k\), one modular addition and one table lookup decide whether that start position works.
For each \(k=1,2,\dots,S\), the implementation scans starting positions \(z=1,2,3,\dots\) until the residue condition succeeds, and records that first successful position as \(p(k)\). The C++ and Java implementations split the independent \(k\)-ranges across multiple threads; the Python implementation performs the same search serially. Once the table \(p(1),\dots,p(S)\) is available, the final answer is obtained from the block decomposition formula.
Let \(L\) be the number of digits in one period and \(S\) the digit sum of one period. Constructing the state cycle, the digit block, and the prefix sums costs \(O(L)\) time. Marking the residue set also costs \(O(L)\) time and uses \(O(S)\) memory for the membership table.
The dominant cost in these implementations is the direct search for each \(p(k)\). In the worst case, one value of \(k\) can scan up to one whole digit period before the first success, so the overall worst-case running time is \(O(SL)\). The memory usage is \(O(S+L)\). Parallel execution in the compiled implementations reduces wall-clock time, but the main mathematical gain comes from periodicity: instead of handling \(2\cdot10^{15}\) targets separately, the algorithm computes one finite period and reuses it.
Man startet mit \(s_0=14025256\) und iteriert
$$s_{n+1}=s_n^2 \pmod{20300713}.$$
Die Dezimaldarstellungen von \(s_0,s_1,s_2,\dots\) werden hintereinander geschrieben und ergeben so eine unendliche Ziffernfolge \(w=w_1w_2w_3\cdots\). Für jedes positive \(k\) sei \(p(k)\) die kleinste Startposition \(z\ge 1\), für die es eine Endposition \(y\ge z\) gibt, sodass die Ziffernsumme des Blocks \(w_z w_{z+1}\dots w_y\) genau \(k\) ist. Gesucht ist also
$$\sum_{k=1}^{2\cdot 10^{15}} p(k).$$
Der eigentliche Engpass ist nicht die Rekursion selbst, sondern die Größe des Problems: Die Summationsgrenze ist gigantisch, und die Ziffernfolge ist unendlich. Die Lösung reduziert deshalb alles auf eine endliche Periode des Generators.
Entscheidend sind der Zyklus der modularen Folge, der daraus entstehende periodische Ziffernblock und die Präfixsummen dieses Blocks modulo der Ziffernsumme einer ganzen Periode.
Die Rekursion läuft in einem endlichen Zustandsraum, also muss irgendwann ein Zustand erneut auftreten. Ab diesem Moment wiederholt sich die gesamte weitere Entwicklung. In diesem Problem ist die Situation besonders günstig: Der erste wiederholte Zustand ist bereits der Startwert selbst. Es gibt also keinen Vorlauf vor dem Zyklus.
Damit ist die Zahlenfolge von \(s_0\) an ein reiner Zyklus. Wenn man ihre Dezimaldarstellungen verknüpft, erhält man einen Ziffernblock
$$d_1,d_2,\dots,d_L$$
der sich unendlich oft wiederholt. Die Implementierungen bestimmen diese Periode direkt und erhalten
$$L=18{,}886{,}117,\qquad S=\sum_{i=1}^{L} d_i = 80{,}846{,}691.$$
Hier ist \(L\) die Anzahl der Ziffern einer vollständigen Periode und \(S\) die Ziffernsumme dieser Periode.
Definiere die Präfixsummen einer Periode durch
$$P_0=0,\qquad P_i=\sum_{t=1}^{i} d_t\quad (1\le i\le L).$$
Dann gilt \(P_L=S\). Wegen der Periodizität des Ziffernblocks hat jede Präfixsumme der unendlichen Folge die Form
$$T_{mL+i}=mS+P_i,\qquad m\ge 0,\ 0\le i\le L,$$
wobei \(T_n=w_1+\cdots+w_n\) die Summe der ersten \(n\) Ziffern bezeichnet.
Ein Block von Position \(z\) bis Position \(y\) hat genau dann Ziffernsumme \(k\), wenn
$$T_y-T_{z-1}=k.$$
Somit ist \(p(k)\) die kleinste Position \(z\), für die diese Gleichung mindestens eine Lösung \(y\ge z\) besitzt.
Schreibe \(z-1=mL+b\) mit \(0\le b<L\). Dann ist
$$T_{z-1}=mS+P_b.$$
Für einen Block mit Ziffernsumme \(k\), der bei \(z\) beginnt, brauchen wir daher
$$T_y=mS+P_b+k.$$
Da jede Präfixsumme \(T_y\) von der Form \(qS+P_i\) ist, ist die Existenz eines solchen \(y\) äquivalent dazu, dass für mindestens ein \(i\in\{0,1,\dots,L\}\)
$$P_i\equiv P_b+k \pmod S$$
gilt. Deshalb betrachtet man die Restklassenmenge
$$R=\{P_i\bmod S:0\le i\le L\}.$$
Die Frage, ob Position \(z\) für die Zielsumme \(k\) geeignet ist, reduziert sich damit auf den endlichen Test
$$\big(P_b+k\big)\bmod S\in R.$$
Genau diese Bedingung prüfen die Implementierungen. Die unendliche Suche nach Endpositionen wird zu einem Restklassentest.
Die Gültigkeitsbedingung hängt nur von \(k\bmod S\) ab. Daher ist die Menge der Startpositionen, die für \(k\) funktionieren, dieselbe wie für \(k+S\), also
$$p(k+S)=p(k).$$
Es gibt noch eine zweite Periodizität: Der Startrest wiederholt sich alle \(L\) Ziffern. Ob eine Position \(z\) funktioniert, hängt also nur von \((z-1)\bmod L\) ab. Sobald eine Zielsumme erreichbar ist, liegt ihre kleinste gültige Startposition deshalb innerhalb der ersten Periode.
Damit genügt es, \(p(1),p(2),\dots,p(S)\) genau einmal zu berechnen. Für \(N=2\cdot10^{15}\) folgt dann
$$\sum_{k=1}^{N} p(k)=\left\lfloor\frac{N}{S}\right\rfloor\sum_{k=1}^{S}p(k)+\sum_{k=1}^{N\bmod S}p(k).$$
Das ist die zentrale Reduktion: Ein astronomischer Summationsbereich wird auf eine einzige endliche \(k\)-Periode zurückgeführt.
Die unendliche Ziffernfolge beginnt mit den Dezimaldarstellungen von \(14025256,7410149,5847003,\dots\), also mit
$$1,4,0,2,5,2,5,6,7,4,1,0,1,4,9,\dots$$
Die zugehörigen Präfixsummen beginnen als
$$0,1,5,5,7,12,14,19,25,32,36,37,37,38,42,51,\dots$$
Betrachte \(k=6\). Für \(z=1\) müsste später eine Präfixsumme \(6\) auftreten, aber die laufenden Summen springen von \(5\) direkt auf \(7\). Also gibt es keinen Teilblock mit Start an der ersten Ziffer und Ziffernsumme \(6\).
Für \(z=2\) ist die Startpräfixsumme dagegen \(1\), und \(1+6=7\) tritt als spätere Präfixsumme auf. Daher hat der Block \(4,0,2\) die Ziffernsumme \(6\), also
$$p(6)=2.$$
Genau so funktioniert die allgemeine Methode: Startpräfixsumme abziehen, das verschobene Ziel unter den besuchten Restklassen suchen und die kleinste erfolgreiche Startposition wählen.
Die C++-, Python- und Java-Implementierungen iterieren die quadratische Rekursion vom vorgegebenen Startwert aus, merken sich die erste Position jedes erzeugten Zustands und stoppen beim ersten wiederholten Zustand. Da dieser wiederholte Zustand der Startwert ist, bilden die gesammelten Dezimalziffern bereits eine vollständige Periode der unendlichen Folge. Anschließend werden die Präfixsummen dieser Periode und die Gesamtziffernsumme \(S\) berechnet.
Danach markiert die Implementierung jede Restklasse \(P_i\bmod S\) in einer dichten Nachschlagetabelle und speichert außerdem die periodische Folge der Startreste \(P_0,P_1,\dots,P_{L-1}\bmod S\). Diese beiden Strukturen kodieren genau das mathematische Kriterium: Für eine Kandidatenposition und ein Ziel \(k\) genügen eine modulare Addition und eine Tabellenabfrage.
Für jedes \(k=1,2,\dots,S\) testet die Implementierung die Startpositionen \(z=1,2,3,\dots\), bis die Restbedingung erfüllt ist, und speichert dieses erste erfolgreiche \(z\) als \(p(k)\). Die C++- und Java-Versionen verteilen die unabhängigen \(k\)-Bereiche auf mehrere Threads; die Python-Version führt dieselbe Suche seriell aus. Ist die Tabelle \(p(1),\dots,p(S)\) einmal vorhanden, ergibt sich die Endsumme sofort aus der Blockzerlegung.
Sei \(L\) die Ziffernzahl einer Periode und \(S\) ihre Ziffernsumme. Das Erzeugen des Zustandszyklus, des Ziffernblocks und der Präfixsummen kostet \(O(L)\) Zeit. Auch das Markieren der Restklassen kostet \(O(L)\) Zeit und benötigt \(O(S)\) Speicher für die dichte Mitgliedschaftstabelle.
Der dominante Teil ist in diesen Implementierungen die direkte Suche nach jedem \(p(k)\). Im schlechtesten Fall kann ein einzelnes \(k\) bis zu eine ganze Ziffernperiode an Startpositionen prüfen, sodass die Gesamtlaufzeit im Worst Case \(O(SL)\) ist. Der Speicherbedarf beträgt \(O(S+L)\). Die Parallelisierung in den kompilierten Versionen verkürzt die Laufzeit, aber der eigentliche mathematische Gewinn stammt aus der Periodizität: Statt \(2\cdot10^{15}\) Werte einzeln zu behandeln, wird nur eine endliche Periode berechnet und wiederverwendet.
\(s_0=14025256\) ile başlayıp
$$s_{n+1}=s_n^2 \pmod{20300713}$$
özyinelemesini kuruyoruz. \(s_0,s_1,s_2,\dots\) sayılarının ondalık yazımları art arda eklenince \(w=w_1w_2w_3\cdots\) sonsuz rakam dizisi elde edilir. Her pozitif \(k\) için \(p(k)\), rakam toplamı tam olarak \(k\) olan bir ardışık bloğun başlayabildiği en küçük başlangıç konumu \(z\ge 1\) olarak tanımlanır. Yani \(y\ge z\) olacak şekilde \(w_z w_{z+1}\dots w_y\) bloğunun rakam toplamı \(k\) ise, bu başlangıç kabul edilir. İstenen büyüklük
$$\sum_{k=1}^{2\cdot 10^{15}} p(k)$$
toplamıdır. Zorluk, üretecin kendisinden çok iki farklı sonsuzluk görünümündedir: dizi sonsuzdur ve dış toplamın üst sınırı aşırı büyüktür. Çözüm, ikisini de tek bir periyoda indirir.
Bu problemde asıl nesneler, modüler karesel üretecin durum çevrimi, ondan doğan periyodik rakam bloğu ve bu bloğun bir periyot içindeki prefix toplamlarının \(S\) modundaki artık sınıflarıdır.
Özyineleme sonlu bir durum uzayında ilerlediği için bir noktada daha önce görülmüş bir değere dönmek zorundadır. Bir değer tekrarlandığı anda sonraki tüm davranış da tekrar eder. Bu problemde tekrar, başlangıç değerinin kendisinde gerçekleşir; yani herhangi bir geçici kuyruk yoktur.
Dolayısıyla \(s_0\)'dan itibaren üretilen sayılar saf bir çevrim oluşturur. Bu sayıların ondalık yazımlarını birleştirince
$$d_1,d_2,\dots,d_L$$
şeklinde bir rakam bloğu elde edilir ve bu blok sonsuza kadar tekrar eder. Uygulamalar bu periyodu doğrudan çıkarır ve
$$L=18{,}886{,}117,\qquad S=\sum_{i=1}^{L} d_i = 80{,}846{,}691$$
değerlerini bulur. Burada \(L\) bir periyottaki rakam sayısı, \(S\) ise aynı periyodun toplam rakam ağırlığıdır.
Bir periyot içindeki prefix toplamları
$$P_0=0,\qquad P_i=\sum_{t=1}^{i} d_t\quad (1\le i\le L)$$
şeklinde tanımlayalım. O zaman \(P_L=S\) olur. Rakam bloğu tekrar ettiği için sonsuz dizinin her prefix toplamı
$$T_{mL+i}=mS+P_i,\qquad m\ge 0,\ 0\le i\le L$$
biçimindedir; burada \(T_n\), ilk \(n\) rakamın toplamıdır.
\(z\) konumunda başlayıp \(y\) konumunda biten bir bloğun rakam toplamı tam olarak \(k\) ise
$$T_y-T_{z-1}=k$$
olmalıdır. Böylece \(p(k)\), bu denklemin en az bir \(y\ge z\) çözümü olduğu en küçük \(z\)'ye dönüşür.
\(z-1=mL+b\) ve \(0\le b<L\) yazalım. O zaman
$$T_{z-1}=mS+P_b$$
olur. Başlangıcı \(z\) olan ve toplamı \(k\) olan bir blok arıyorsak
$$T_y=mS+P_b+k$$
eşitliğini sağlamalıyız. Öte yandan her \(T_y\), \(qS+P_i\) biçimindedir. Demek ki böyle bir \(y\)'nin var olması, en az bir \(i\in\{0,1,\dots,L\}\) için
$$P_i\equiv P_b+k \pmod S$$
olmasına denktir. Bu yüzden
$$R=\{P_i\bmod S:0\le i\le L\}$$
kümesini kuruyoruz. Artık “\(z\) konumu \(k\) hedefi için geçerli mi?” sorusu
$$\big(P_b+k\big)\bmod S\in R$$
testine iner. Uygulamaların yaptığı kontrol tam olarak budur. Sonsuz bitiş konumu araması, sonlu bir üyelik sorgusuna dönüşür.
Geçerlilik koşulu yalnızca \(k\bmod S\)'ye bağlıdır. Bu nedenle \(k\) ve \(k+S\) için işe yarayan başlangıç konumları aynıdır ve
$$p(k+S)=p(k)$$
elde edilir. Bir ikinci periyodiklik daha vardır: başlangıç artık sınıfı her \(L\) rakamda tekrar eder. Yani bir konumun işe yarayıp yaramadığı sadece \((z-1)\bmod L\)'ye bağlıdır. Bu yüzden ulaşılabilir bir hedef toplamın en erken başlangıcı ilk periyot içinde bulunur.
Sonuç olarak yalnızca \(p(1),p(2),\dots,p(S)\) değerlerini bir kez hesaplamak yeterlidir. \(N=2\cdot10^{15}\) için
$$\sum_{k=1}^{N} p(k)=\left\lfloor\frac{N}{S}\right\rfloor\sum_{k=1}^{S}p(k)+\sum_{k=1}^{N\bmod S}p(k)$$
olur. Problemin asıl sıkıştırması budur: devasa bir dış toplam, \(k\) üzerinde tek bir sonlu periyoda iner.
Sonsuz dizi, \(14025256,7410149,5847003,\dots\) sayılarının ondalık yazımlarıyla başladığı için ilk rakamlar
$$1,4,0,2,5,2,5,6,7,4,1,0,1,4,9,\dots$$
şeklindedir. Buna karşılık gelen prefix toplamları da
$$0,1,5,5,7,12,14,19,25,32,36,37,37,38,42,51,\dots$$
diye başlar. \(k=6\) alalım. \(z=1\) için daha sonra \(6\) değerine eşit bir prefix toplamı gerekir; ancak toplamlar \(5\)'ten doğrudan \(7\)'ye sıçrıyor. Demek ki ilk rakamdan başlayan hiçbir blok toplamı \(6\) vermez.
\(z=2\) için başlangıç prefix toplamı \(1\)'dir ve \(1+6=7\) daha sonra gerçekten görülür. Dolayısıyla \(4,0,2\) bloğunun toplamı \(6\) olur ve
$$p(6)=2$$
elde edilir. Tam yöntemde de yapılan budur: başlangıç prefix toplamını çıkar, kaymış hedefi ziyaret edilen artık sınıflar arasında ara ve bunu sağlayan en erken başlangıcı al.
C++, Python ve Java uygulamaları verilen tohumdan başlayarak karesel özyinelemeyi iterasyonla üretir, görülen her durumun ilk konumunu kaydeder ve bir durum tekrarlandığında durur. Tekrar eden durum başlangıç değeri olduğu için toplanan ondalık rakamlar zaten sonsuz dizinin tam bir periyodudur. Ardından bu periyodun prefix toplamları ve toplam rakam ağırlığı \(S\) hesaplanır.
Sonraki aşamada uygulama her \(P_i\bmod S\) artık sınıfını sık bir üyelik tablosunda işaretler ve ayrıca periyodik başlangıç artıklarını, yani \(P_0,P_1,\dots,P_{L-1}\bmod S\) dizisini saklar. Matematiksel kriterin tamamı bu iki yapıdadır: aday bir başlangıç ve hedef \(k\) verildiğinde bir toplama, gerekirse tek bir çıkarma ve bir tablo bakışı yeterlidir.
Her \(k=1,2,\dots,S\) için uygulama başlangıç konumlarını \(z=1,2,3,\dots\) diye dener, artık sınıf testi ilk kez başarılı olduğunda o konumu \(p(k)\) olarak kaydeder. C++ ve Java sürümleri birbirinden bağımsız \(k\) aralıklarını çok iş parçacıklı biçimde dağıtır; Python sürümü aynı aramayı seri olarak yapar. \(p(1),\dots,p(S)\) tablosu hazır olduğunda son cevap, tam blok toplamı ile kalan blok toplamını birleştirerek elde edilir.
\(L\) bir periyottaki rakam sayısı, \(S\) de bir periyottaki rakam toplamı olsun. Durum çevrimini, rakam bloğunu ve prefix toplamları kurmak \(O(L)\) zaman alır. Artık sınıfları işaretlemek de \(O(L)\) zamandır ve üyelik tablosu için \(O(S)\) bellek gerektirir.
Bu uygulamalarda baskın maliyet, her \(p(k)\) için yapılan doğrudan aramadır. En kötü durumda tek bir \(k\), ilk başarıyı bulmak için neredeyse bir tam rakam periyodu kadar başlangıç deneyebilir; dolayısıyla en kötü durum çalışma süresi \(O(SL)\) olur. Toplam bellek kullanımı \(O(S+L)\)'dir. Derlenmiş sürümlerde paralelleştirme duvar saati süresini azaltır; ama asıl matematiksel kazanç, \(2\cdot10^{15}\) ayrı hedef yerine tek bir sonlu dönemin hesaplanıp tekrar kullanılabilmesidir.
Se empieza con \(s_0=14025256\) y se itera
$$s_{n+1}=s_n^2 \pmod{20300713}.$$
Las expansiones decimales de \(s_0,s_1,s_2,\dots\) se concatenan para formar una cadena infinita de dígitos \(w=w_1w_2w_3\cdots\). Para cada entero positivo \(k\), \(p(k)\) es la menor posición inicial \(z\ge 1\) para la cual existe una posición final \(y\ge z\) tal que la suma de los dígitos del bloque \(w_z w_{z+1}\dots w_y\) sea exactamente \(k\). Lo que se pide es
$$\sum_{k=1}^{2\cdot 10^{15}} p(k).$$
No se puede trabajar directamente con la definición: la cadena es infinita y el límite exterior es gigantesco. La solución que implementan los programas extrae una estructura periódica finita y la reutiliza.
Los objetos centrales son el ciclo de estados de la recurrencia modular, el bloque periódico de dígitos que produce y las sumas prefijo de ese bloque tomadas módulo la suma total de una vuelta completa.
La sucesión vive en un espacio finito de residuos, así que algún estado tiene que repetirse. Cuando un estado vuelve a aparecer, toda la evolución futura también se repite. En este problema ocurre algo mejor: el primer estado repetido es la propia semilla inicial, de modo que no existe una cola transitoria antes del ciclo.
Por tanto, desde \(s_0\) la sucesión numérica ya es cíclica. Al concatenar sus escrituras decimales obtenemos un bloque de dígitos
$$d_1,d_2,\dots,d_L$$
que se repite indefinidamente. Las implementaciones detectan ese período de forma explícita y obtienen
$$L=18{,}886{,}117,\qquad S=\sum_{i=1}^{L} d_i = 80{,}846{,}691.$$
Aquí \(L\) es la longitud en dígitos de un período completo y \(S\) es la suma de los dígitos de ese período.
Definimos las sumas prefijo de un período por
$$P_0=0,\qquad P_i=\sum_{t=1}^{i} d_t\quad (1\le i\le L).$$
Entonces \(P_L=S\). Como el bloque se repite, toda suma prefijo de la cadena infinita tiene la forma
$$T_{mL+i}=mS+P_i,\qquad m\ge 0,\ 0\le i\le L,$$
donde \(T_n=w_1+\cdots+w_n\) es la suma de los primeros \(n\) dígitos.
Un bloque que empieza en \(z\) y termina en \(y\) tiene suma \(k\) exactamente cuando
$$T_y-T_{z-1}=k.$$
Así, \(p(k)\) es la menor posición inicial \(z\) para la que esta ecuación admite al menos una solución \(y\ge z\).
Escribamos \(z-1=mL+b\) con \(0\le b<L\). Entonces
$$T_{z-1}=mS+P_b.$$
Si queremos que un bloque que empieza en \(z\) tenga suma \(k\), necesitamos
$$T_y=mS+P_b+k.$$
Pero todo \(T_y\) es de la forma \(qS+P_i\), así que la existencia de un tal \(y\) equivale a que para algún \(i\in\{0,1,\dots,L\}\) se cumpla
$$P_i\equiv P_b+k \pmod S.$$
Esto motiva el conjunto de residuos
$$R=\{P_i\bmod S:0\le i\le L\}.$$
Con él, la pregunta “¿sirve la posición \(z\) para la suma objetivo \(k\)?” se convierte en el criterio finito
$$\big(P_b+k\big)\bmod S\in R.$$
Ese es exactamente el test que realizan las implementaciones. La búsqueda infinita del extremo derecho del bloque queda reducida a una consulta de pertenencia.
La condición anterior depende de \(k\) solo a través de \(k\bmod S\). Por eso, el conjunto de posiciones iniciales válidas para \(k\) coincide con el de \(k+S\), y se obtiene
$$p(k+S)=p(k).$$
Además, el residuo de arranque se repite cada \(L\) dígitos. Por lo tanto, que una posición \(z\) funcione o no depende solo de \((z-1)\bmod L\). Cuando un objetivo es alcanzable, su primera posición válida aparece dentro del primer período.
En consecuencia basta con calcular \(p(1),p(2),\dots,p(S)\) una sola vez. Si \(N=2\cdot10^{15}\), entonces
$$\sum_{k=1}^{N} p(k)=\left\lfloor\frac{N}{S}\right\rfloor\sum_{k=1}^{S}p(k)+\sum_{k=1}^{N\bmod S}p(k).$$
Esa es la reducción decisiva: un rango exterior gigantesco se reemplaza por un único período finito en \(k\).
La cadena infinita empieza con las expansiones decimales de \(14025256,7410149,5847003,\dots\), así que sus primeros dígitos son
$$1,4,0,2,5,2,5,6,7,4,1,0,1,4,9,\dots$$
y las sumas prefijo correspondientes empiezan como
$$0,1,5,5,7,12,14,19,25,32,36,37,37,38,42,51,\dots$$
Tomemos \(k=6\). Si \(z=1\), necesitaríamos una suma prefijo igual a \(6\), pero la suma acumulada salta de \(5\) a \(7\). Por tanto, ningún bloque que empiece en el primer dígito suma \(6\).
Si \(z=2\), la suma prefijo inicial es \(1\), y \(1+6=7\) sí aparece más adelante. Entonces el bloque \(4,0,2\) tiene suma \(6\), y por lo tanto
$$p(6)=2.$$
Ese ejemplo pequeño refleja exactamente el método general: restar la suma prefijo inicial, buscar el objetivo desplazado entre los residuos visitados y quedarse con el primer inicio que funciona.
Las implementaciones en C++, Python y Java iteran la recurrencia cuadrática desde la semilla dada, recuerdan la primera aparición de cada estado y se detienen cuando un estado se repite. Como el estado repetido es la propia semilla, los dígitos decimales acumulados forman ya un período completo de la cadena infinita. A continuación se calculan las sumas prefijo de ese período y la suma total \(S\).
Después, la implementación marca cada residuo \(P_i\bmod S\) en una tabla densa de pertenencia y también guarda la secuencia periódica de residuos de arranque \(P_0,P_1,\dots,P_{L-1}\bmod S\). Esas dos estructuras codifican todo el criterio matemático: para una posición candidata y un objetivo \(k\), basta una suma modular y una consulta a tabla.
Para cada \(k=1,2,\dots,S\), la implementación prueba posiciones iniciales \(z=1,2,3,\dots\) hasta que la condición de residuos se cumple, y registra ese primer éxito como \(p(k)\). Las versiones de C++ y Java reparten los distintos intervalos de \(k\) entre varios hilos; la versión en Python hace la misma búsqueda en serie. Una vez conocida la tabla \(p(1),\dots,p(S)\), la respuesta final sale directamente de la descomposición en bloques completos y resto.
Sean \(L\) la cantidad de dígitos de un período y \(S\) la suma de esos dígitos. Construir el ciclo de estados, el bloque de dígitos y las sumas prefijo cuesta \(O(L)\) tiempo. Marcar el conjunto de residuos también cuesta \(O(L)\) tiempo y necesita \(O(S)\) memoria para la tabla de pertenencia.
El coste dominante en estas implementaciones es la búsqueda directa de cada \(p(k)\). En el peor caso, un valor de \(k\) puede recorrer casi un período completo antes de encontrar la primera posición válida, de modo que el tiempo total en peor caso es \(O(SL)\). La memoria total es \(O(S+L)\). La paralelización en las versiones compiladas reduce el tiempo real de ejecución, pero la mejora matemática principal viene de la periodicidad: en vez de tratar \(2\cdot10^{15}\) objetivos por separado, se calcula y reutiliza una sola tabla periódica finita.
从 \(s_0=14025256\) 出发，按下式递推：
$$s_{n+1}=s_n^2 \pmod{20300713}.$$
把 \(s_0,s_1,s_2,\dots\) 的十进制表示依次拼接起来，得到无限数字串 \(w=w_1w_2w_3\cdots\)。对每个正整数 \(k\)，定义 \(p(k)\) 为最小的起始位置 \(z\ge 1\)，使得存在某个结束位置 \(y\ge z\)，满足连续区间 \(w_z w_{z+1}\dots w_y\) 的数字和恰好等于 \(k\)。题目要求计算
$$\sum_{k=1}^{2\cdot 10^{15}} p(k).$$
难点不在于递推本身，而在于规模：数字串是无限的，而外层求和又大到无法逐项处理。实现采用的思路，是先把无限对象压缩成一个有限周期，再把所有 \(p(k)\) 的行为归结到这个周期上。
整道题的核心对象有三个：模平方递推的状态循环、由它诱导出的周期性数字块，以及该数字块在一个周期内的前缀和对整周期数字和取模后的剩余类。
递推只会落在有限多个模 \(20300713\) 的剩余类中，所以根据有限状态重复原理，某个状态必然再次出现。一旦某个状态重复，之后的演化就会完全重复。在本题中，情况更强：第一次重复出现的状态恰好就是初始种子本身，因此不存在“前导非周期段”。
这意味着从 \(s_0\) 开始，生成的整数序列就是一个纯循环。把这些整数的十进制表示连接起来，得到一个长度为 \(L\) 的数字块
$$d_1,d_2,\dots,d_L$$
并且这个数字块会无限次重复。实现会显式检测这个周期，得到
$$L=18{,}886{,}117,\qquad S=\sum_{i=1}^{L} d_i = 80{,}846{,}691.$$
这里 \(L\) 是一个完整周期中的数字个数，\(S\) 是这个周期内全部数字之和。
定义一个周期内的前缀和：
$$P_0=0,\qquad P_i=\sum_{t=1}^{i} d_t\quad (1\le i\le L).$$
于是 \(P_L=S\)。由于数字块按周期重复，无限串的任意前缀和都可写成
$$T_{mL+i}=mS+P_i,\qquad m\ge 0,\ 0\le i\le L,$$
其中 \(T_n=w_1+\cdots+w_n\) 表示前 \(n\) 个数字的总和。
如果一个区间从位置 \(z\) 开始，到位置 \(y\) 结束，并且数字和恰好为 \(k\)，那么必须满足
$$T_y-T_{z-1}=k.$$
因此，\(p(k)\) 就是使这个方程存在至少一个 \(y\ge z\) 解的最小起点 \(z\)。
把起点写成 \(z-1=mL+b\)，其中 \(0\le b<L\)。于是
$$T_{z-1}=mS+P_b.$$
若希望从位置 \(z\) 开始获得数字和 \(k\)，则需要
$$T_y=mS+P_b+k.$$
另一方面，每个 \(T_y\) 都是某个 \(qS+P_i\) 的形式，所以存在这样的 \(y\) 当且仅当存在 \(i\in\{0,1,\dots,L\}\) 使得
$$P_i\equiv P_b+k \pmod S.$$
这就引出了剩余类集合
$$R=\{P_i\bmod S:0\le i\le L\}.$$
现在，“起点 \(z\) 是否能实现目标和 \(k\)”这个问题，被压缩为一个有限判定：
$$\big(P_b+k\big)\bmod S\in R.$$
实现中真正执行的就是这个检查。原本看上去需要在无限长字符串里寻找终点的位置问题，变成了对有限剩余类表的一次查询。
上面的判定只依赖于 \(k\bmod S\)。因此，对 \(k\) 有效的起点集合，与对 \(k+S\) 有效的起点集合完全相同，于是
$$p(k+S)=p(k).$$
同时，起点对应的前缀剩余类每隔 \(L\) 个数字就会重复一次，所以某个位置是否有效，只取决于 \((z-1)\bmod L\)。这说明如果某个目标和可以实现，那么它的最早有效起点一定出现在第一个数字周期之内。
因此，只要计算一次 \(p(1),p(2),\dots,p(S)\) 就够了。令 \(N=2\cdot10^{15}\)，则
$$\sum_{k=1}^{N} p(k)=\left\lfloor\frac{N}{S}\right\rfloor\sum_{k=1}^{S}p(k)+\sum_{k=1}^{N\bmod S}p(k).$$
这就是本题最关键的化简：极大的求和范围，被压缩成一个关于 \(k\) 的有限周期表。
无限串一开始来自 \(14025256,7410149,5847003,\dots\) 的十进制拼接，所以前几个数字是
$$1,4,0,2,5,2,5,6,7,4,1,0,1,4,9,\dots$$
对应的前缀和开头为
$$0,1,5,5,7,12,14,19,25,32,36,37,37,38,42,51,\dots$$
考虑 \(k=6\)。如果从 \(z=1\) 开始，那么需要后面某个前缀和正好等于 \(6\)，但累积和从 \(5\) 直接跳到 \(7\)，所以从第一个数字开始不可能得到和为 \(6\) 的连续段。
如果从 \(z=2\) 开始，起始前缀和是 \(1\)，而 \(1+6=7\) 的确在后面出现过。因此区间 \(4,0,2\) 的数字和就是 \(6\)，于是
$$p(6)=2.$$
这个小例子和完整算法完全同构：先减去起点处的前缀和，再看平移后的目标值是否落在访问过的前缀剩余类中，最后取最早成功的起点。
C++、Python 和 Java 实现都会从给定种子开始迭代二次递推，记录每个状态第一次出现的位置，并在某个状态重复时停止。由于重复的状态就是初始种子，所以收集到的十进制数字恰好构成无限字符串的一个完整周期。随后实现会建立这个数字周期的前缀和，并计算整周期数字和 \(S\)。
接下来，实现把所有 \(P_i\bmod S\) 标记到一个稠密的成员表中，同时保存起点剩余类的周期序列 \(P_0,P_1,\dots,P_{L-1}\bmod S\)。这两个结构就编码了前面的数学判定：给定候选起点和目标 \(k\)，只需要一次模加法和一次数组查询，就能判断该起点是否可行。
对于每个 \(k=1,2,\dots,S\)，实现按 \(z=1,2,3,\dots\) 的顺序扫描起点，直到剩余类条件第一次成立，并把这个最早成功的位置记为 \(p(k)\)。C++ 和 Java 版本会把不同的 \(k\) 区间分配给多个线程并行处理；Python 版本执行完全相同的搜索，只是串行完成。得到 \(p(1),\dots,p(S)\) 之后，再利用整块和余块分解公式计算最终答案。
设 \(L\) 为一个数字周期的长度，\(S\) 为该周期内数字之和。构造状态循环、数字块与前缀和需要 \(O(L)\) 时间。建立剩余类成员表同样是 \(O(L)\) 时间，并需要 \(O(S)\) 空间来保存稠密查询数组。
这些实现中的主要耗时来自逐个寻找 \(p(k)\)。在最坏情况下，某个 \(k\) 可能要扫描接近一个完整数字周期才能首次成功，因此总的最坏时间复杂度是 \(O(SL)\)，总空间复杂度是 \(O(S+L)\)。编译型实现通过并行化缩短了实际运行时间，但真正重要的数学收益是周期化：原本要面对 \(2\cdot10^{15}\) 个目标值，现在只需求出一个有限周期表并反复利用。
Берём \(s_0=14025256\) и строим последовательность по правилу
$$s_{n+1}=s_n^2 \pmod{20300713}.$$
Десятичные записи чисел \(s_0,s_1,s_2,\dots\) приписываются друг к другу, образуя бесконечную строку цифр \(w=w_1w_2w_3\cdots\). Для каждого положительного целого \(k\) величина \(p(k)\) определяется как минимальная стартовая позиция \(z\ge 1\), для которой существует правая граница \(y\ge z\) и сумма цифр блока \(w_z w_{z+1}\dots w_y\) равна ровно \(k\). Требуется найти
$$\sum_{k=1}^{2\cdot 10^{15}} p(k).$$
Лобовое решение недостижимо: строка бесконечна, а диапазон внешней суммы слишком велик. Используемый в реализациях подход сводит задачу к конечному периоду генератора и конечной таблице значений.
Ключевые объекты здесь таковы: цикл состояний модульной рекурсии, периодический блок цифр, который он порождает, и префиксные суммы этого блока по модулю полной суммы цифр за один период.
Последовательность живёт в конечном множестве остатков по модулю \(20300713\), значит, рано или поздно некоторое состояние повторится. После первого повтора всё дальнейшее развитие становится периодическим. В данной задаче происходит ещё более сильный факт: первым повторяющимся состоянием оказывается исходное значение, так что допериодической части вообще нет.
Следовательно, начиная с \(s_0\), последовательность чисел уже образует чистый цикл. Если склеить их десятичные записи, получится блок цифр
$$d_1,d_2,\dots,d_L$$
который затем повторяется бесконечно. Реализации находят этот период напрямую и получают
$$L=18{,}886{,}117,\qquad S=\sum_{i=1}^{L} d_i = 80{,}846{,}691.$$
Здесь \(L\) — число цифр в одном полном периоде, а \(S\) — сумма цифр этого периода.
Введём префиксные суммы одного периода:
$$P_0=0,\qquad P_i=\sum_{t=1}^{i} d_t\quad (1\le i\le L).$$
Тогда \(P_L=S\). Поскольку цифровой блок повторяется, любая префиксная сумма бесконечной строки имеет вид
$$T_{mL+i}=mS+P_i,\qquad m\ge 0,\ 0\le i\le L,$$
где \(T_n=w_1+\cdots+w_n\) — сумма первых \(n\) цифр строки.
Блок, начинающийся в позиции \(z\) и заканчивающийся в позиции \(y\), имеет сумму цифр \(k\) тогда и только тогда, когда
$$T_y-T_{z-1}=k.$$
Значит, \(p(k)\) — это минимальное \(z\), для которого у этого уравнения есть хотя бы одно решение \(y\ge z\).
Запишем \(z-1=mL+b\), где \(0\le b<L\). Тогда
$$T_{z-1}=mS+P_b.$$
Чтобы блок, начинающийся в \(z\), имел сумму \(k\), нужно
$$T_y=mS+P_b+k.$$
Но каждое \(T_y\) имеет вид \(qS+P_i\), поэтому существование такого \(y\) эквивалентно тому, что найдётся \(i\in\{0,1,\dots,L\}\), удовлетворяющий сравнению
$$P_i\equiv P_b+k \pmod S.$$
Отсюда появляется множество остатков
$$R=\{P_i\bmod S:0\le i\le L\}.$$
Теперь вопрос “подходит ли стартовая позиция \(z\) для целевой суммы \(k\)?” сводится к конечной проверке
$$\big(P_b+k\big)\bmod S\in R.$$
Именно этот критерий реализован в коде. Поиск правой границы в бесконечной строке заменяется проверкой принадлежности конечному набору остатков.
Полученный критерий зависит от \(k\) только через \(k\bmod S\). Поэтому множество стартовых позиций, работающих для \(k\), совпадает с множеством стартовых позиций для \(k+S\), и потому
$$p(k+S)=p(k).$$
Есть и вторая периодичность: стартовый остаток повторяется каждые \(L\) цифр. Значит, пригодность позиции \(z\) зависит только от \((z-1)\bmod L\). Если некоторая целевая сумма достижима, то её самый ранний допустимый старт обязательно лежит в пределах первого периода.
Следовательно, достаточно один раз вычислить \(p(1),p(2),\dots,p(S)\). Для \(N=2\cdot10^{15}\) получаем
$$\sum_{k=1}^{N} p(k)=\left\lfloor\frac{N}{S}\right\rfloor\sum_{k=1}^{S}p(k)+\sum_{k=1}^{N\bmod S}p(k).$$
Это и есть основное упрощение задачи: колоссальный диапазон по \(k\) заменяется одной конечной периодической таблицей.
Бесконечная строка начинается с десятичных записей \(14025256,7410149,5847003,\dots\), поэтому её первые цифры таковы:
$$1,4,0,2,5,2,5,6,7,4,1,0,1,4,9,\dots$$
Соответствующие префиксные суммы начинаются так:
$$0,1,5,5,7,12,14,19,25,32,36,37,37,38,42,51,\dots$$
Возьмём \(k=6\). Если стартовать с \(z=1\), нужно было бы встретить префиксную сумму \(6\), но накопленная сумма перескакивает с \(5\) сразу на \(7\). Значит, ни один блок, начинающийся с первой цифры, не имеет сумму \(6\).
Если же стартовать с \(z=2\), начальная префиксная сумма равна \(1\), а значение \(1+6=7\) действительно встречается позже. Поэтому блок \(4,0,2\) имеет сумму цифр \(6\), и
$$p(6)=2.$$
Это и есть миниатюрная версия полного метода: вычесть стартовую префиксную сумму, проверить наличие сдвинутой цели среди посещённых остатков и взять самый ранний успешный старт.
Реализации на C++, Python и Java итерируют квадратичную рекурсию от заданного начального значения, запоминают первое появление каждого состояния и останавливаются при первом повторе. Поскольку повторившееся состояние совпадает с начальной семенем, собранные десятичные цифры уже образуют один полный период бесконечной строки. Затем строятся префиксные суммы этого периода и его полная сумма цифр \(S\).
Далее реализация помечает каждый остаток \(P_i\bmod S\) в плотной таблице принадлежности и отдельно сохраняет периодическую последовательность стартовых остатков \(P_0,P_1,\dots,P_{L-1}\bmod S\). Именно эти две структуры кодируют математический критерий: для кандидатного старта и заданного \(k\) достаточно одной модульной суммы и одного обращения к таблице.
Для каждого \(k=1,2,\dots,S\) реализация перебирает стартовые позиции \(z=1,2,3,\dots\), пока условие на остатки впервые не выполнится, и записывает эту позицию как \(p(k)\). Версии на C++ и Java распределяют независимые диапазоны \(k\) по нескольким потокам; версия на Python делает тот же поиск последовательно. После вычисления таблицы \(p(1),\dots,p(S)\) окончательный ответ получается по формуле разбиения на полные блоки и хвост.
Пусть \(L\) — число цифр в одном периоде, а \(S\) — сумма цифр этого периода. Построение цикла состояний, цифрового блока и префиксных сумм занимает \(O(L)\) времени. Пометка множества остатков тоже стоит \(O(L)\) времени и требует \(O(S)\) памяти для плотного массива принадлежности.
Основная стоимость в этих реализациях связана с прямым поиском каждого \(p(k)\). В худшем случае одно значение \(k\) может просмотреть почти весь цифровой период до первого успеха, так что общая асимптотика по времени равна \(O(SL)\). Память составляет \(O(S+L)\). Параллелизация в компилируемых реализациях сокращает реальное время работы, но главный математический выигрыш даёт периодичность: вместо \(2\cdot10^{15}\) отдельных целей вычисляется и многократно используется одна конечная таблица.
نبدأ بالقيمة \(s_0=14025256\) ثم نكرر العلاقة
$$s_{n+1}=s_n^2 \pmod{20300713}.$$
نكتب التمثيل العشري للأعداد \(s_0,s_1,s_2,\dots\) على التوالي لنحصل على سلسلة لا نهائية من الأرقام \(w=w_1w_2w_3\cdots\). لكل عدد صحيح موجب \(k\)، تُعرَّف \(p(k)\) بأنها أصغر موضع بداية \(z\ge 1\) يوجد معه موضع نهاية \(y\ge z\) بحيث يكون مجموع أرقام المقطع \(w_z w_{z+1}\dots w_y\) مساوياً تماماً لـ \(k\). المطلوب هو حساب
$$\sum_{k=1}^{2\cdot 10^{15}} p(k).$$
المشكلة لا يمكن التعامل معها مباشرة، لأن السلسلة نفسها لا نهائية وحدّ الجمع الخارجي هائل جداً. الفكرة المستعملة في التنفيذ هي اختزال كل ذلك إلى دورة منتهية واحدة للمولد، ثم إعادة استخدام هذه الدورة مراراً.
العناصر الحاسمة هنا هي: دورة الحالات التي تنتجها العلاقة التربيعية المعيارية، وكتلة الأرقام الدورية الناتجة عنها، ثم المجاميع البادئة لتلك الكتلة بعد أخذها بترديد مجموع أرقام دورة كاملة.
بما أن العلاقة تعمل داخل عدد منتهٍ من البواقي modulo \(20300713\)، فلا بد أن تتكرر حالة ما في النهاية. وعندما تتكرر حالة، فإن السلوك اللاحق كله يتكرر أيضاً. في هذه المسألة يظهر أمر أقوى: أول حالة مكررة هي البذرة الابتدائية نفسها، أي لا توجد مرحلة تمهيدية قبل بدء الدورة.
إذن متتالية الأعداد الناتجة من \(s_0\) فصاعداً هي دورة خالصة. وعند وصل تمثيلاتها العشرية نحصل على كتلة أرقام
$$d_1,d_2,\dots,d_L$$
تتكرر إلى ما لا نهاية. التنفيذ يستخرج هذه الدورة صراحة ويصل إلى
$$L=18{,}886{,}117,\qquad S=\sum_{i=1}^{L} d_i = 80{,}846{,}691.$$
هنا تمثل \(L\) عدد الأرقام في دورة كاملة، وتمثل \(S\) مجموع أرقام تلك الدورة.
نعرّف المجاميع البادئة داخل دورة واحدة بالصيغة
$$P_0=0,\qquad P_i=\sum_{t=1}^{i} d_t\quad (1\le i\le L).$$
وعندئذٍ يكون \(P_L=S\). وبما أن كتلة الأرقام دورية، فإن أي مجموع بادئ في السلسلة اللانهائية يكتب على الصورة
$$T_{mL+i}=mS+P_i,\qquad m\ge 0,\ 0\le i\le L,$$
حيث \(T_n=w_1+\cdots+w_n\) هو مجموع أول \(n\) رقماً من السلسلة.
المقطع الذي يبدأ عند الموضع \(z\) وينتهي عند الموضع \(y\) يملك مجموع أرقام يساوي \(k\) إذا وفقط إذا تحقق
$$T_y-T_{z-1}=k.$$
وبالتالي تصبح \(p(k)\) هي أصغر قيمة \(z\) يملك معها هذا الشرط حلاً واحداً على الأقل بحيث \(y\ge z\).
لنكتب \(z-1=mL+b\) حيث \(0\le b<L\). عندئذٍ
$$T_{z-1}=mS+P_b.$$
وإذا أردنا مقطعاً يبدأ من \(z\) ويكون مجموع أرقامه \(k\)، فعلينا أن نجد
$$T_y=mS+P_b+k.$$
لكن كل قيمة من الشكل \(T_y\) تكتب كـ \(qS+P_i\)، ولذلك فإن وجود مثل هذا \(y\) يكافئ وجود \(i\in\{0,1,\dots,L\}\) يحقق
$$P_i\equiv P_b+k \pmod S.$$
ومن هنا نبني مجموعة البواقي
$$R=\{P_i\bmod S:0\le i\le L\}.$$
بعد هذه الخطوة يصبح السؤال “هل يصلح الموضع \(z\) لبناء مجموع هدفه \(k\)؟” مجرد اختبار منتهٍ:
$$\big(P_b+k\big)\bmod S\in R.$$
وهذا هو الشرط الذي تفحصه التطبيقات فعلياً. البحث اللانهائي عن موضع النهاية يتحول إلى استعلام في جدول بواقي منتهٍ.
الشرط السابق يعتمد على \(k\) فقط عبر \(k\bmod S\). لذلك فإن مجموعة مواضع البداية الصالحة لـ \(k\) هي نفسها تماماً لمجموعات \(k+S\)، ومن ثم
$$p(k+S)=p(k).$$
وهناك دورية ثانية أيضاً: باقي موضع البداية يتكرر كل \(L\) رقماً. معنى ذلك أن صلاحية الموضع \(z\) تعتمد فقط على \((z-1)\bmod L\). فإذا كان المجموع الهدف قابلاً للتحقق، فإن أول موضع بداية صالح له لا بد أن يقع داخل الدورة الأولى للأرقام.
لذلك يكفي حساب \(p(1),p(2),\dots,p(S)\) مرة واحدة فقط. وإذا كتبنا \(N=2\cdot10^{15}\)، نحصل على
$$\sum_{k=1}^{N} p(k)=\left\lfloor\frac{N}{S}\right\rfloor\sum_{k=1}^{S}p(k)+\sum_{k=1}^{N\bmod S}p(k).$$
هذا هو الاختزال الحاسم في المسألة: مجال جمع فلكي يتحول إلى جدول دوري محدود في \(k\).
بداية السلسلة اللانهائية تأتي من كتابة \(14025256,7410149,5847003,\dots\) على التوالي، ولذلك تكون الأرقام الأولى
$$1,4,0,2,5,2,5,6,7,4,1,0,1,4,9,\dots$$
وتبدأ المجاميع البادئة المقابلة على الصورة
$$0,1,5,5,7,12,14,19,25,32,36,37,37,38,42,51,\dots$$
خذ \(k=6\). إذا بدأنا من \(z=1\)، فنحن بحاجة إلى مجموع بادئ لاحق يساوي \(6\)، لكن المجاميع تقفز من \(5\) مباشرة إلى \(7\). إذن لا يوجد مقطع يبدأ من الرقم الأول ويعطي مجموعاً مقداره \(6\).
أما إذا بدأنا من \(z=2\)، فالمجموع البادئ الابتدائي يساوي \(1\)، والقيمة \(1+6=7\) تظهر لاحقاً فعلاً. لذلك فإن المقطع \(4,0,2\) يملك مجموع أرقام يساوي \(6\)، وبالتالي
$$p(6)=2.$$
وهذا المثال الصغير هو نفس الآلية العامة: اطرح المجموع البادئ عند نقطة البداية، وابحث عن الهدف المزاح بين البواقي المزارة، ثم خذ أول بداية تنجح.
تنفذ البرامج في C++ وPython وJava العلاقة التربيعية انطلاقاً من البذرة المعطاة، وتحفظ أول موضع لكل حالة تظهر، وتتوقف عندما تتكرر حالة ما. وبما أن الحالة المتكررة هي البذرة نفسها، فإن الأرقام العشرية التي جُمعت تمثل بالفعل دورة كاملة واحدة من السلسلة اللانهائية. بعد ذلك تُبنى المجاميع البادئة لهذه الدورة ويُحسب مجموع أرقامها الكلي \(S\).
في المرحلة التالية تضع التطبيقات كل باقي من الشكل \(P_i\bmod S\) داخل جدول عضوية كثيف، وتحفظ كذلك السلسلة الدورية لبواقي البدايات \(P_0,P_1,\dots,P_{L-1}\bmod S\). هاتان البنيتان تختزلان المعيار الرياضي كله: لأي بداية مرشحة وأي هدف \(k\)، تكفي عملية جمع معيارية واحدة واستعلام واحد في الجدول.
لكل \(k=1,2,\dots,S\)، يقوم التنفيذ بفحص مواضع البداية \(z=1,2,3,\dots\) حتى ينجح شرط البواقي لأول مرة، ثم يسجل هذا الموضع بوصفه \(p(k)\). إصدارا C++ وJava يوزعان مجالات \(k\) المستقلة على عدة خيوط تنفيذ؛ أما إصدار Python فيجري البحث نفسه بصورة تسلسلية. وبعد تكوين الجدول \(p(1),\dots,p(S)\)، تُستخرج الإجابة النهائية مباشرة من صيغة تفكيك الجمع إلى كتل كاملة وباقٍ أخير.
ليكن \(L\) عدد الأرقام في دورة واحدة، و\(S\) مجموع أرقام هذه الدورة. بناء دورة الحالات وكتلة الأرقام والمجاميع البادئة يكلف \(O(L)\) زمناً. كما أن تعليم مجموعة البواقي يكلف \(O(L)\) زمناً ويحتاج إلى \(O(S)\) من الذاكرة من أجل جدول العضوية الكثيف.
أما الكلفة المسيطرة في هذه التطبيقات فتأتي من البحث المباشر عن كل \(p(k)\). ففي أسوأ الحالات قد يمر هدف واحد \(k\) على ما يقارب دورة رقمية كاملة قبل العثور على أول نجاح، ولذلك يكون تعقيد الزمن الكلي في أسوأ حالة هو \(O(SL)\)، بينما يكون استهلاك الذاكرة \(O(S+L)\). التنفيذ المتوازي في النسخ المترجمة يخفض الزمن الفعلي، لكن المكسب الرياضي الأهم يأتي من الدورية نفسها: بدلاً من معالجة \(2\cdot10^{15}\) هدفاً على حدة، يكفي حساب جدول دوري محدود وإعادة استخدامه.