A gozinta chain for \(n\) is a sequence
$$1=a_0\lt a_1\lt\cdots\lt a_t=n,$$
where each term divides the next one. Let \(g(n)\) be the number of such chains, and let
$$S(N)=\sum_{\substack{k\le N\\ g(k)=252}} k.$$
The task is to find the last nine digits of \(S(10^{36})\). A direct scan up to \(10^{36}\) is hopeless, so the solution first characterizes exactly which prime-exponent patterns produce 252 chains, then sums those integers in a much more structured way.
Write
$$n=\prod_{j=1}^{r} p_j^{e_j},\qquad \Omega=e_1+\cdots+e_r.$$
The crucial observation is that the number of gozinta chains depends only on the exponent pattern \((e_1,\dots,e_r)\), not on the actual primes \(p_j\).
Every divisor of \(n\) can be written uniquely as
$$d=\prod_{j=1}^{r} p_j^{b_j},\qquad 0\le b_j\le e_j.$$
So divisors correspond to lattice points \(b=(b_1,\dots,b_r)\) inside the box \([0,e_1]\times\cdots\times[0,e_r]\). A gozinta chain is therefore a strictly increasing coordinatewise chain
$$ (0,\dots,0)=v^{(0)}\lt v^{(1)}\lt\cdots\lt v^{(k)}=(e_1,\dots,e_r), $$
where at least one coordinate increases at every step. Since this description uses only the exponents, the chain count is completely determined by the exponent pattern.
Fix a chain length \(k\), meaning \(k\) strict divisibility moves from \(1\) to \(n\). Let the increment in coordinate \(j\) during step \(t\) be \(\delta_{j,t}\). Then
$$\delta_{j,t}\ge 0,\qquad \sum_{t=1}^{k}\delta_{j,t}=e_j.$$
For one fixed prime \(p_j\), the number of weak compositions of \(e_j\) into \(k\) parts is
$$\binom{e_j+k-1}{k-1}.$$
Multiplying over all prime coordinates gives the number of increment tables if zero steps are temporarily allowed:
$$T_k(e_1,\dots,e_r)=\prod_{j=1}^{r}\binom{e_j+k-1}{k-1}.$$
However, \(T_k\) still counts forbidden cases where some step has \(\delta_{1,t}=\cdots=\delta_{r,t}=0\), which would repeat a divisor instead of moving to a strictly larger one.
To obtain genuine gozinta chains, every step must increase at least one coordinate. If exactly \(i\) of the \(k\) step positions are declared active, the same stars-and-bars argument gives
$$\prod_{j=1}^{r}\binom{e_j+i-1}{i-1}$$
possibilities. Choosing the active positions and applying inclusion-exclusion yields
$$ F_k(e_1,\dots,e_r)=\sum_{i=1}^{k}(-1)^{k-i}\binom{k}{i}\prod_{j=1}^{r}\binom{e_j+i-1}{i-1}. $$
This is the number of chains with exactly \(k\) strict moves. Because each move raises the total exponent sum by at least \(1\), we must have \(1\le k\le \Omega\). Therefore
$$ G(e_1,\dots,e_r)=\sum_{k=1}^{\Omega} F_k(e_1,\dots,e_r) $$
is the total number of gozinta chains for any integer having exponent pattern \((e_1,\dots,e_r)\).
The implementations enumerate exponent partitions and evaluate the exact formula above. The outcome is strikingly simple: the only pattern with
$$G(e_1,\dots,e_r)=252$$
is
$$ (e_1,\dots,e_r)=(3,3). $$
Hence every qualifying integer has the form
$$ n=p^3q^3=(pq)^3,\qquad p\lt q \text{ prime}. $$
The primes must be distinct: \(p^6\) has pattern \((6)\), not \((3,3)\), so it does not belong to the target set.
Take \(n=2^3\cdot 3^3=216\). Here \(\Omega=6\), and for a fixed step count \(k\) we get
$$ T_k=\binom{3+k-1}{k-1}^2=\binom{k+2}{2}^2. $$
Applying inclusion-exclusion gives
$$ F_k=\sum_{i=1}^{k}(-1)^{k-i}\binom{k}{i}\binom{i+2}{2}^2. $$
The values are
$$ \begin{aligned} F_1&=1,\\ F_2&=14,\\ F_3&=55,\\ F_4&=92,\\ F_5&=70,\\ F_6&=20. \end{aligned} $$
Summing them shows
$$ 1+14+55+92+70+20=252. $$
So \(216\) really has exactly 252 gozinta chains, and by the previous step every other qualifying number is obtained by replacing \(2\) and \(3\) with any distinct prime pair.
Let
$$ X=\left\lfloor N^{1/3}\right\rfloor. $$
Then \((pq)^3\le N\) is equivalent to \(pq\le X\), so
$$ S(N)=\sum_{\substack{p\lt q\\ pq\le X}} (pq)^3. $$
For the actual problem, \(N=10^{36}\), hence \(X=10^{12}\).
Now define the prime-cube prefix sum
$$ P_3(y)=\sum_{\substack{q\le y\\ q\text{ prime}}} q^3. $$
Grouping terms by the smaller prime \(p\) gives
$$ S(N)=\sum_{p\le \sqrt{X}} p^3\left(P_3\!\left(\left\lfloor\frac{X}{p}\right\rfloor\right)-P_3(p)\right). $$
The subtraction by \(P_3(p)\) enforces \(q>p\), so every unordered prime pair is counted exactly once.
A full sieve up to \(10^{12}\) would be too large, so the implementation works only with the distinct quotient values
$$ v=\left\lfloor\frac{X}{i}\right\rfloor, $$
of which there are only \(O(\sqrt{X})\). For each such \(v\), it starts from the ordinary cube sum
$$ \sum_{m=2}^{v} m^3=\left(\frac{v(v+1)}{2}\right)^2-1. $$
Then it performs Min_25-style prime corrections. When sieving by a prime \(p\), every state with \(v\ge p^2\) is updated by subtracting the contribution of numbers whose smallest remaining prime factor is \(p\):
$$ H(v)\leftarrow H(v)-p^3\left(H\!\left(\left\lfloor\frac{v}{p}\right\rfloor\right)-\sum_{q<p} q^3\right). $$
After all primes up to \(\sqrt{X}\) have been processed, \(H(v)\) equals \(P_3(v)\). Because only the last nine digits are needed, every arithmetic operation is reduced modulo \(10^9\).
The C++, Python, and Java implementations follow the same mathematical reduction. They first verify the structural claim by evaluating the exact chain-count formula on exponent partitions and confirming that \((3,3)\) is the only pattern with 252 chains.
Next they set \(X=10^{12}\), generate all primes up to \(\sqrt{X}\), and build the table of distinct quotient values \(\lfloor X/i\rfloor\). Each table entry is initialized with the closed form for \(\sum m^3\), then corrected prime by prime until only prime cubes remain in the summatory table.
Finally they loop over the smaller prime \(p\), query the prime-cube prefix sum at \(\lfloor X/p\rfloor\) and at \(p\), and accumulate
$$ p^3\left(P_3\!\left(\left\lfloor\frac{X}{p}\right\rfloor\right)-P_3(p)\right) $$
modulo \(10^9\). Before attacking \(10^{36}\), the implementation also checks smaller validated cases such as \(S(10^6)=8462952\) and \(S(10^{12})=623291998881978\).
The exponent-pattern verification is tiny compared with the main computation. For the main solver, sieving primes up to \(\sqrt{X}\) costs \(O(\sqrt{X}\log\log X)\) time and \(O(\sqrt{X})\) memory. The quotient table contains only \(O(\sqrt{X})\) states. During the prime-correction phase, a prime \(p\) touches only those states with \(v\ge p^2\), so the number of table updates is
$$ \sum_{p\le \sqrt{X}} O\!\left(\min\!\left(\sqrt{X},\frac{X}{p^2}\right)\right), $$
which is sublinear in \(X\) and follows the usual complexity profile of Min_25-style prime-summatory methods. The final accumulation over primes up to \(\sqrt{X}\) is linear in \(\pi(\sqrt{X})\). Overall, the implementation uses \(O(\sqrt{X})\) memory and practical sublinear time for \(X=10^{12}\).
Eine Gozinta-Kette zu \(n\) ist eine Folge
$$1=a_0\lt a_1\lt\cdots\lt a_t=n,$$
bei der jedes Glied das nächste teilt. Sei \(g(n)\) die Anzahl dieser Ketten und
$$S(N)=\sum_{\substack{k\le N\\ g(k)=252}} k.$$
Gesucht sind die letzten neun Ziffern von \(S(10^{36})\). Ein direktes Durchsuchen aller Zahlen bis \(10^{36}\) ist unmöglich, also bestimmt die Lösung zuerst das einzige Primexponenten-Muster mit 252 Ketten und summiert dann nur noch die zugehörigen Zahlen.
Schreibe
$$n=\prod_{j=1}^{r} p_j^{e_j},\qquad \Omega=e_1+\cdots+e_r.$$
Die zentrale Beobachtung lautet: Die Anzahl der Gozinta-Ketten hängt nur vom Exponentenmuster \((e_1,\dots,e_r)\) ab, nicht von den konkreten Primzahlen \(p_j\).
Jeder Teiler von \(n\) hat eindeutig die Form
$$d=\prod_{j=1}^{r} p_j^{b_j},\qquad 0\le b_j\le e_j.$$
Damit entsprechen die Teiler den Gitterpunkten \(b=(b_1,\dots,b_r)\) im Quader \([0,e_1]\times\cdots\times[0,e_r]\). Eine Gozinta-Kette ist also genau eine streng koordinatenweise wachsende Folge
$$ (0,\dots,0)=v^{(0)}\lt v^{(1)}\lt\cdots\lt v^{(k)}=(e_1,\dots,e_r), $$
bei der in jedem Schritt mindestens eine Koordinate ansteigt. Da diese Beschreibung nur die Exponenten verwendet, ist die Kettenzahl vollständig durch das Exponentenmuster bestimmt.
Fixiere eine Kettenlänge \(k\), also \(k\) echte Teilbarkeitsschritte von \(1\) nach \(n\). Sei \(\delta_{j,t}\) die Zunahme der \(j\)-ten Exponente im Schritt \(t\). Dann gilt
$$\delta_{j,t}\ge 0,\qquad \sum_{t=1}^{k}\delta_{j,t}=e_j.$$
Für eine feste Primzahl \(p_j\) ist die Anzahl schwacher Zerlegungen von \(e_j\) in \(k\) Teile gleich
$$\binom{e_j+k-1}{k-1}.$$
Über alle Primkoordinaten multipliziert erhält man die Zahl aller Inkrementtabellen, wenn vorerst leere Schritte erlaubt sind:
$$T_k(e_1,\dots,e_r)=\prod_{j=1}^{r}\binom{e_j+k-1}{k-1}.$$
Hier sind jedoch noch verbotene Fälle enthalten, in denen ein ganzer Schritt überall Null ist und somit keinen echten Sprung erzeugt.
Für echte Gozinta-Ketten muss jeder Schritt in mindestens einer Koordinate positiv sein. Wenn genau \(i\) der \(k\) Schrittpositionen aktiv sind, liefert dasselbe Stars-and-Bars-Argument
$$\prod_{j=1}^{r}\binom{e_j+i-1}{i-1}$$
Möglichkeiten. Durch Wahl der aktiven Positionen und Inklusion-Exklusion folgt
$$ F_k(e_1,\dots,e_r)=\sum_{i=1}^{k}(-1)^{k-i}\binom{k}{i}\prod_{j=1}^{r}\binom{e_j+i-1}{i-1}. $$
Das ist die Anzahl der Ketten mit genau \(k\) echten Schritten. Da jeder Schritt die Summe der Exponenten um mindestens \(1\) erhöht, gilt stets \(1\le k\le \Omega\). Also ist
$$ G(e_1,\dots,e_r)=\sum_{k=1}^{\Omega} F_k(e_1,\dots,e_r) $$
die gesamte Gozinta-Kettenzahl für jedes \(n\) mit diesem Exponentenmuster.
Die Implementierungen enumerieren ganzzahlige Partitionen der Exponenten und werten die obige Formel exakt aus. Das Ergebnis ist eindeutig: Die einzige Lösung von
$$G(e_1,\dots,e_r)=252$$
ist das Muster
$$ (e_1,\dots,e_r)=(3,3). $$
Damit hat jede gesuchte Zahl die Form
$$ n=p^3q^3=(pq)^3,\qquad p\lt q \text{ prim}. $$
Die Primzahlen müssen verschieden sein, denn \(p^6\) hätte das Muster \((6)\) und gehört daher nicht zur Zielmenge.
Betrachte \(n=2^3\cdot 3^3=216\). Dann ist \(\Omega=6\), und für eine feste Schrittzahl \(k\) gilt
$$ T_k=\binom{3+k-1}{k-1}^2=\binom{k+2}{2}^2. $$
Mit Inklusion-Exklusion erhält man
$$ F_k=\sum_{i=1}^{k}(-1)^{k-i}\binom{k}{i}\binom{i+2}{2}^2. $$
Daraus folgen die Werte
$$ \begin{aligned} F_1&=1,\\ F_2&=14,\\ F_3&=55,\\ F_4&=92,\\ F_5&=70,\\ F_6&=20. \end{aligned} $$
Also
$$ 1+14+55+92+70+20=252. $$
Damit hat \(216\) tatsächlich genau 252 Gozinta-Ketten, und wegen des vorigen Schritts erhält man alle weiteren Lösungen durch Ersetzen von \(2\) und \(3\) durch ein beliebiges verschiedenes Primzahlpaar.
Setze
$$ X=\left\lfloor N^{1/3}\right\rfloor. $$
Dann ist \((pq)^3\le N\) äquivalent zu \(pq\le X\), also
$$ S(N)=\sum_{\substack{p\lt q\\ pq\le X}} (pq)^3. $$
Für die Aufgabenparameter gilt \(N=10^{36}\), also \(X=10^{12}\).
Definiere nun die Präfixsumme der Primzahlwürfel
$$ P_3(y)=\sum_{\substack{q\le y\\ q\text{ prim}}} q^3. $$
Durch Gruppierung nach der kleineren Primzahl \(p\) wird daraus
$$ S(N)=\sum_{p\le \sqrt{X}} p^3\left(P_3\!\left(\left\lfloor\frac{X}{p}\right\rfloor\right)-P_3(p)\right). $$
Die Subtraktion von \(P_3(p)\) erzwingt \(q>p\) und verhindert jede Doppelerfassung.
Ein vollständiges Sieb bis \(10^{12}\) wäre zu groß. Deshalb arbeitet die Implementierung nur mit den verschiedenen Quotientenwerten
$$ v=\left\lfloor\frac{X}{i}\right\rfloor, $$
von denen es nur \(O(\sqrt{X})\) gibt. Für jedes solche \(v\) startet sie mit der gewöhnlichen Würfelsumme
$$ \sum_{m=2}^{v} m^3=\left(\frac{v(v+1)}{2}\right)^2-1. $$
Danach folgen Min_25-artige Primzahlkorrekturen. Beim Sieben mit einer Primzahl \(p\) wird für jeden Zustand mit \(v\ge p^2\) der Beitrag der Zahlen entfernt, deren kleinster verbleibender Primfaktor \(p\) ist:
$$ H(v)\leftarrow H(v)-p^3\left(H\!\left(\left\lfloor\frac{v}{p}\right\rfloor\right)-\sum_{q<p} q^3\right). $$
Nachdem alle Primzahlen bis \(\sqrt{X}\) verarbeitet sind, gilt \(H(v)=P_3(v)\). Da nur die letzten neun Ziffern benötigt werden, wird durchgehend modulo \(10^9\) gerechnet.
Die C++-, Python- und Java-Implementierungen folgen exakt derselben Reduktion. Zuerst bestätigen sie die Strukturbehauptung, indem sie die Kettenformel auf Exponentenpartitionen anwenden und nachweisen, dass nur \((3,3)\) die Zahl 252 liefert.
Anschließend setzen sie \(X=10^{12}\), erzeugen alle Primzahlen bis \(\sqrt{X}\) und bauen die Tabelle der verschiedenen Werte \(\lfloor X/i\rfloor\) auf. Jeder Tabelleneintrag wird mit der geschlossenen Formel für \(\sum m^3\) initialisiert und dann Primzahl für Primzahl so korrigiert, bis nur noch Primzahlwürfel übrig bleiben.
Im letzten Schritt wird über die kleinere Primzahl \(p\) iteriert und
$$ p^3\left(P_3\!\left(\left\lfloor\frac{X}{p}\right\rfloor\right)-P_3(p)\right) $$
modulo \(10^9\) aufsummiert. Vor der Endrechnung für \(10^{36}\) prüft die Implementierung auch kleinere validierte Fälle wie \(S(10^6)=8462952\) und \(S(10^{12})=623291998881978\).
Die Suche nach dem Exponentenmuster ist im Vergleich zur Hauptrechnung vernachlässigbar. Für den eigentlichen Löser kostet das Primzahlsieb bis \(\sqrt{X}\) \(O(\sqrt{X}\log\log X)\) Zeit und \(O(\sqrt{X})\) Speicher. Die Quotiententabelle besitzt nur \(O(\sqrt{X})\) Zustände. In der Primzahl-Korrekturphase berührt eine Primzahl \(p\) nur Zustände mit \(v\ge p^2\), daher ist die Zahl der Aktualisierungen
$$ \sum_{p\le \sqrt{X}} O\!\left(\min\!\left(\sqrt{X},\frac{X}{p^2}\right)\right), $$
also echt sublinear in \(X\) und typisch für Min_25-artige Primzahlsummenverfahren. Die abschließende Summe über \(p\le \sqrt{X}\) ist linear in \(\pi(\sqrt{X})\). Insgesamt benötigt die Methode \(O(\sqrt{X})\) Speicher und praktikable sublineare Laufzeit für \(X=10^{12}\).
Bir \(n\) sayisi icin gozinta zinciri,
$$1=a_0\lt a_1\lt\cdots\lt a_t=n,$$
seklinde, her terimin bir sonrakini boldugu sikı bir bolunebilirlik zinciridir. \(g(n)\) bu zincirlerin sayisi olsun ve
$$S(N)=\sum_{\substack{k\le N\\ g(k)=252}} k$$
olarak tanimlansin. Istenen sey \(S(10^{36})\)'nin son dokuz basamagidir. \(10^{36}\)'ye kadar dogrudan arama yapmak imkansiz oldugu icin cozum once hangi asal-us deseninin 252 zincir verdigini bulur, sonra sadece o bicimdeki sayilari toplar.
Simdi
$$n=\prod_{j=1}^{r} p_j^{e_j},\qquad \Omega=e_1+\cdots+e_r$$
yazalim. Temel gozlem sudur: gozinta zinciri sayisi, asalların kendisine degil yalnizca us desenine \((e_1,\dots,e_r)\) baglidir.
\(n\)'nin her boleni tek bir bicimde
$$d=\prod_{j=1}^{r} p_j^{b_j},\qquad 0\le b_j\le e_j$$
seklinde yazilir. Yani bolenler, \([0,e_1]\times\cdots\times[0,e_r]\) kutusu icindeki \(b=(b_1,\dots,b_r)\) kafes noktalarina karsilik gelir. O halde bir gozinta zinciri, koordinat bazinda artan sikı bir zincirdir:
$$ (0,\dots,0)=v^{(0)}\lt v^{(1)}\lt\cdots\lt v^{(k)}=(e_1,\dots,e_r). $$
Her adimda en az bir koordinat artmak zorundadir. Bu tanim yalnizca usleri kullandigi icin zincir sayisi butunuyse us desenince belirlenir.
Sabit bir \(k\) zincir uzunlugu secelim; yani \(1\)'den \(n\)'ye giderken tam \(k\) kez gercek artis olsun. \(t\). adimda \(j\). koordinattaki artisi \(\delta_{j,t}\) ile gosterelim. O zaman
$$\delta_{j,t}\ge 0,\qquad \sum_{t=1}^{k}\delta_{j,t}=e_j$$
olur. Tek bir asal us icin \(e_j\)'nin \(k\) parcaya zayif dagilimi
$$\binom{e_j+k-1}{k-1}$$
adet verir. Tum koordinatlar icin carpinca, sifir adimlara gecici olarak izin veren tablo sayisi
$$T_k(e_1,\dots,e_r)=\prod_{j=1}^{r}\binom{e_j+k-1}{k-1}$$
olur. Fakat bu sayi, butun koordinatlarda sifir olan ve dolayisiyla ayni boleni tekrar eden yasak adimlari da sayar.
Gecerli bir gozinta zincirinde her adim en az bir koordinatta pozitif olmalidir. \(k\) konumdan yalnizca \(i\) tanesinin etkin oldugunu varsayarsak ayni stars-and-bars sayimi
$$\prod_{j=1}^{r}\binom{e_j+i-1}{i-1}$$
sonucunu verir. Etkin konumlari secip dahil et-cikar uygularsak
$$ F_k(e_1,\dots,e_r)=\sum_{i=1}^{k}(-1)^{k-i}\binom{k}{i}\prod_{j=1}^{r}\binom{e_j+i-1}{i-1} $$
elde edilir. Bu, tam olarak \(k\) gercek adimli zincirlerin sayisidir. Her adim toplam us miktarini en az \(1\) arttirdigi icin \(1\le k\le \Omega\) olmak zorundadir. Dolayisiyla toplam zincir sayisi
$$ G(e_1,\dots,e_r)=\sum_{k=1}^{\Omega} F_k(e_1,\dots,e_r) $$
olur.
Uygulamalar, tam sayi partition'larini gezip yukaridaki formulu dogrudan degerlendirir. Sonuc tekildir:
$$G(e_1,\dots,e_r)=252$$
kosulunu saglayan tek desen
$$ (e_1,\dots,e_r)=(3,3) $$
desenidir. Bu nedenle aradigimiz her sayi
$$ n=p^3q^3=(pq)^3,\qquad p\lt q \text{ asal} $$
seklindedir. Asallar farkli olmak zorundadir; cunku \(p^6\) deseni \((6)\) olur, \((3,3)\) degil.
\(n=2^3\cdot 3^3=216\) alalim. Bu durumda \(\Omega=6\) ve sabit bir \(k\) icin
$$ T_k=\binom{3+k-1}{k-1}^2=\binom{k+2}{2}^2 $$
olur. Dahil et-cikar sonra
$$ F_k=\sum_{i=1}^{k}(-1)^{k-i}\binom{k}{i}\binom{i+2}{2}^2 $$
verir. Buradan
$$ \begin{aligned} F_1&=1,\\ F_2&=14,\\ F_3&=55,\\ F_4&=92,\\ F_5&=70,\\ F_6&=20 \end{aligned} $$
elde edilir ve toplam
$$ 1+14+55+92+70+20=252 $$
olur. Yani 216 gercekten tam 252 gozinta zincirine sahiptir.
Su tanimi yapalim:
$$ X=\left\lfloor N^{1/3}\right\rfloor. $$
O zaman \((pq)^3\le N\) kosulu \(pq\le X\) ile aynidir ve
$$ S(N)=\sum_{\substack{p\lt q\\ pq\le X}} (pq)^3 $$
elde edilir. Gercek problemde \(N=10^{36}\) oldugu icin \(X=10^{12}\) olur.
Simdi asal kup on-ek toplamini
$$ P_3(y)=\sum_{\substack{q\le y\\ q\text{ prime}}} q^3 $$
olarak tanimlayalim. Kucuk asal \(p\)'ye gore gruplarsak
$$ S(N)=\sum_{p\le \sqrt{X}} p^3\left(P_3\!\left(\left\lfloor\frac{X}{p}\right\rfloor\right)-P_3(p)\right) $$
bulunur. Buradaki \(P_3(p)\) cikarmasi \(q>p\) kosulunu saglar.
\(10^{12}\)'ye kadar tam sieve yapmak cok buyuk olur. Bunun yerine uygulama sadece
$$ v=\left\lfloor\frac{X}{i}\right\rfloor $$
ayrik degerleri uzerinde calisir; bunlarin sayisi yalnizca \(O(\sqrt{X})\) kadardir. Her \(v\) icin baslangic degeri
$$ \sum_{m=2}^{v} m^3=\left(\frac{v(v+1)}{2}\right)^2-1 $$
olarak alinir. Daha sonra Min_25 tarzinda asal duzeltmeleri uygulanir. Bir asal \(p\) icin ve \(v\ge p^2\) oldugunda guncelleme
$$ H(v)\leftarrow H(v)-p^3\left(H\!\left(\left\lfloor\frac{v}{p}\right\rfloor\right)-\sum_{q<p} q^3\right) $$
seklindedir. Tum asallar islendikten sonra \(H(v)=P_3(v)\) olur. Son dokuz basamak istendigi icin her sey \(10^9\) modunda tutulur.
C++, Python ve Java uygulamalari ayni matematiksel indirgemeyi kullanir. Once zincir sayisi formulu us partition'lari uzerinde degerlendirilir ve 252 icin tek desenin \((3,3)\) oldugu dogrulanir.
Ardindan \(X=10^{12}\) alinir, \(\sqrt{X}\)'e kadar asallar uretilir ve farkli \(\lfloor X/i\rfloor\) degerlerinden olusan tablo kurulur. Her tablo girdisi kapali kup-toplami formulu ile baslatilir, sonra asal asal duzeltilerek yalniz asal kup toplamlari kalir.
Son asamada kucuk asal \(p\) uzerinden gidilir ve
$$ p^3\left(P_3\!\left(\left\lfloor\frac{X}{p}\right\rfloor\right)-P_3(p)\right) $$
terimleri \(10^9\) modunda toplanir. Tam hedefe gecmeden once \(S(10^6)=8462952\) ve \(S(10^{12})=623291998881978\) gibi daha kucuk dogrulamalar da kontrol edilir.
Us deseni dogrulamasi ana hesaplamaya gore ihmal edilecek kadar kucuktur. Asil cozumde \(\sqrt{X}\)'e kadar asal eleği \(O(\sqrt{X}\log\log X)\) zaman ve \(O(\sqrt{X})\) bellek ister. Bolum tablosu yalnizca \(O(\sqrt{X})\) durum tutar. Asal-duzeltme asamasinda bir \(p\) asali sadece \(v\ge p^2\) olan durumlara dokunur; bu nedenle guncelleme sayisi
$$ \sum_{p\le \sqrt{X}} O\!\left(\min\!\left(\sqrt{X},\frac{X}{p^2}\right)\right) $$
olur. Bu miktar \(X\)'e gore altlineerdir ve Min_25 tarzı toplam-eleklerinin tipik davranisidir. Son toplama adimi ise \(\pi(\sqrt{X})\) ile dogrusaldir. Toplamda yontem \(O(\sqrt{X})\) bellek ve \(X=10^{12}\) icin pratik altlineer zaman kullanir.
Una cadena gozinta de \(n\) es una sucesion
$$1=a_0\lt a_1\lt\cdots\lt a_t=n,$$
donde cada termino divide al siguiente. Sea \(g(n)\) la cantidad de tales cadenas y definamos
$$S(N)=\sum_{\substack{k\le N\\ g(k)=252}} k.$$
La meta es obtener los ultimos nueve digitos de \(S(10^{36})\). Buscar todas las \(k\le 10^{36}\) no es viable, asi que la solucion identifica primero el patron exacto de exponentes primos que produce 252 cadenas y luego suma solo esos numeros.
Escribamos
$$n=\prod_{j=1}^{r} p_j^{e_j},\qquad \Omega=e_1+\cdots+e_r.$$
La observacion clave es que el numero de cadenas gozinta depende solo del patron de exponentes \((e_1,\dots,e_r)\), no de las etiquetas concretas de los primos \(p_j\).
Cada divisor de \(n\) se escribe de manera unica como
$$d=\prod_{j=1}^{r} p_j^{b_j},\qquad 0\le b_j\le e_j.$$
Por tanto, los divisores corresponden a puntos de la reticula \(b=(b_1,\dots,b_r)\) dentro de la caja \([0,e_1]\times\cdots\times[0,e_r]\). Una cadena gozinta es entonces una cadena estrictamente creciente, coordenada a coordenada,
$$ (0,\dots,0)=v^{(0)}\lt v^{(1)}\lt\cdots\lt v^{(k)}=(e_1,\dots,e_r), $$
donde en cada paso aumenta al menos una coordenada. Como esta descripcion usa solo los exponentes, el numero de cadenas queda determinado por ese patron.
Fijemos una longitud \(k\), es decir, \(k\) movimientos estrictos desde \(1\) hasta \(n\). Si \(\delta_{j,t}\) es el incremento de la coordenada \(j\) en el paso \(t\), entonces
$$\delta_{j,t}\ge 0,\qquad \sum_{t=1}^{k}\delta_{j,t}=e_j.$$
Para un primo fijo \(p_j\), el numero de composiciones debiles de \(e_j\) en \(k\) partes es
$$\binom{e_j+k-1}{k-1}.$$
Multiplicando sobre todas las coordenadas obtenemos el numero de tablas de incrementos si se permiten temporalmente pasos vacios:
$$T_k(e_1,\dots,e_r)=\prod_{j=1}^{r}\binom{e_j+k-1}{k-1}.$$
Pero \(T_k\) todavia incluye casos prohibidos en los que un paso entero tiene incremento cero en todas las coordenadas, lo cual repetiria el mismo divisor.
En una cadena valida, cada paso debe aumentar algo. Si exactamente \(i\) de las \(k\) posiciones de paso quedan activas, el mismo conteo produce
$$\prod_{j=1}^{r}\binom{e_j+i-1}{i-1}$$
posibilidades. Al elegir las posiciones activas y aplicar inclusion-exclusion se obtiene
$$ F_k(e_1,\dots,e_r)=\sum_{i=1}^{k}(-1)^{k-i}\binom{k}{i}\prod_{j=1}^{r}\binom{e_j+i-1}{i-1}. $$
Este es el numero de cadenas con exactamente \(k\) pasos estrictos. Como cada paso aumenta la suma total de exponentes en al menos \(1\), necesariamente \(1\le k\le \Omega\). Por tanto, el numero total de cadenas es
$$ G(e_1,\dots,e_r)=\sum_{k=1}^{\Omega} F_k(e_1,\dots,e_r). $$
Las implementaciones enumeran particiones de exponentes y evalúan exactamente la formula anterior. El resultado es unico: la condicion
$$G(e_1,\dots,e_r)=252$$
solo se cumple para
$$ (e_1,\dots,e_r)=(3,3). $$
En consecuencia, cada numero buscado tiene la forma
$$ n=p^3q^3=(pq)^3,\qquad p\lt q \text{ primos}. $$
Los primos deben ser distintos, porque \(p^6\) tiene patron \((6)\), no \((3,3)\).
Tomemos \(n=2^3\cdot 3^3=216\). Aqui \(\Omega=6\), y para un numero fijo de pasos \(k\) tenemos
$$ T_k=\binom{3+k-1}{k-1}^2=\binom{k+2}{2}^2. $$
Luego inclusion-exclusion da
$$ F_k=\sum_{i=1}^{k}(-1)^{k-i}\binom{k}{i}\binom{i+2}{2}^2. $$
Los valores resultan ser
$$ \begin{aligned} F_1&=1,\\ F_2&=14,\\ F_3&=55,\\ F_4&=92,\\ F_5&=70,\\ F_6&=20. \end{aligned} $$
Por lo tanto,
$$ 1+14+55+92+70+20=252. $$
Asi se comprueba de manera concreta que \(216\) tiene exactamente 252 cadenas gozinta.
Definamos
$$ X=\left\lfloor N^{1/3}\right\rfloor. $$
Entonces \((pq)^3\le N\) equivale a \(pq\le X\), y por tanto
$$ S(N)=\sum_{\substack{p\lt q\\ pq\le X}} (pq)^3. $$
Para el problema real, \(N=10^{36}\) y por eso \(X=10^{12}\).
Introducimos ahora la suma prefijo de cubos primos
$$ P_3(y)=\sum_{\substack{q\le y\\ q\text{ prime}}} q^3. $$
Agrupando por el primo pequeno \(p\), la suma se reescribe como
$$ S(N)=\sum_{p\le \sqrt{X}} p^3\left(P_3\!\left(\left\lfloor\frac{X}{p}\right\rfloor\right)-P_3(p)\right). $$
La resta de \(P_3(p)\) impone \(q>p\), asi que cada par de primos aparece una sola vez.
Una criba completa hasta \(10^{12}\) seria demasiado grande. En cambio, la implementacion trabaja solo con los distintos valores
$$ v=\left\lfloor\frac{X}{i}\right\rfloor, $$
que son solo \(O(\sqrt{X})\). Para cada \(v\), se parte de la suma ordinaria de cubos
$$ \sum_{m=2}^{v} m^3=\left(\frac{v(v+1)}{2}\right)^2-1. $$
Despues se aplican correcciones de estilo Min_25. Al procesar un primo \(p\), cada estado con \(v\ge p^2\) se actualiza restando la contribucion de los numeros cuyo menor factor primo restante es \(p\):
$$ H(v)\leftarrow H(v)-p^3\left(H\!\left(\left\lfloor\frac{v}{p}\right\rfloor\right)-\sum_{q<p} q^3\right). $$
Al final de ese proceso, \(H(v)=P_3(v)\). Como solo interesan los ultimos nueve digitos, toda la aritmetica se hace modulo \(10^9\).
Las implementaciones en C++, Python y Java siguen la misma reduccion matematica. Primero verifican la afirmacion estructural evaluando la formula exacta de cadenas sobre particiones de exponentes, y comprueban que \((3,3)\) es el unico patron que produce 252.
Despues fijan \(X=10^{12}\), generan los primos hasta \(\sqrt{X}\) y construyen la tabla de valores distintos \(\lfloor X/i\rfloor\). Cada entrada se inicializa con la formula cerrada de \(\sum m^3\), y luego se corrige primo por primo hasta que la tabla contiene solo sumas de cubos de primos.
Finalmente recorren el primo pequeno \(p\) y acumulan
$$ p^3\left(P_3\!\left(\left\lfloor\frac{X}{p}\right\rfloor\right)-P_3(p)\right) $$
modulo \(10^9\). Antes del caso \(10^{36}\), la implementacion tambien valida casos menores como \(S(10^6)=8462952\) y \(S(10^{12})=623291998881978\).
La verificacion del patron de exponentes es insignificante frente al calculo principal. En el solver principal, cribar los primos hasta \(\sqrt{X}\) cuesta \(O(\sqrt{X}\log\log X)\) tiempo y \(O(\sqrt{X})\) memoria. La tabla de cocientes tiene solo \(O(\sqrt{X})\) estados. En la fase de correccion por primos, un primo \(p\) solo toca estados con \(v\ge p^2\), de modo que el numero de actualizaciones es
$$ \sum_{p\le \sqrt{X}} O\!\left(\min\!\left(\sqrt{X},\frac{X}{p^2}\right)\right), $$
que es sublineal en \(X\) y coincide con el perfil habitual de los metodos sumatorios tipo Min_25. La acumulacion final sobre \(p\le \sqrt{X}\) es lineal en \(\pi(\sqrt{X})\). En conjunto, el metodo usa \(O(\sqrt{X})\) memoria y tiempo sublineal practico para \(X=10^{12}\).
如果一个正整数 \(n\) 存在序列
$$1=a_0\lt a_1\lt\cdots\lt a_t=n,$$
并且每一项都整除下一项，那么这样的严格整除链称为 \(n\) 的一条 gozinta 链。记 \(g(n)\) 为 gozinta 链的条数，再定义
$$S(N)=\sum_{\substack{k\le N\\ g(k)=252}} k.$$
题目要求的是 \(S(10^{36})\) 的后九位。显然不可能直接枚举到 \(10^{36}\)，因此必须先找出“恰好有 252 条 gozinta 链”的整数到底长什么样，然后再对那一类整数做高效求和。
设
$$n=\prod_{j=1}^{r} p_j^{e_j},\qquad \Omega=e_1+\cdots+e_r.$$
整个解法的核心在于：gozinta 链的数量只依赖于指数模式 \((e_1,\dots,e_r)\)，与具体是哪几个质数 \(p_j\) 无关。
\(n\) 的任意一个因子都可以唯一写成
$$d=\prod_{j=1}^{r} p_j^{b_j},\qquad 0\le b_j\le e_j.$$
也就是说，所有因子恰好对应于盒子 \([0,e_1]\times\cdots\times[0,e_r]\) 中的格点 \(b=(b_1,\dots,b_r)\)。因此，一条 gozinta 链其实就是指数向量空间中的一条严格单调链：
$$ (0,\dots,0)=v^{(0)}\lt v^{(1)}\lt\cdots\lt v^{(k)}=(e_1,\dots,e_r), $$
其中每一步都是按坐标逐项不减，并且至少有一个坐标真正增加。这个描述完全由指数决定，所以链数只和指数模式有关，不和质数标签有关。
先固定链有 \(k\) 次严格上升，也就是从 \(1\) 走到 \(n\) 一共经过 \(k\) 个非空步骤。设第 \(t\) 步在第 \(j\) 个坐标上的增量是 \(\delta_{j,t}\)，那么有
$$\delta_{j,t}\ge 0,\qquad \sum_{t=1}^{k}\delta_{j,t}=e_j.$$
对某个固定的质因子指数 \(e_j\) 来说，把 \(e_j\) 分配到 \(k\) 个步骤中的弱拆分数量是
$$\binom{e_j+k-1}{k-1}.$$
对所有坐标相乘，就得到在“暂时允许某一步完全不动”的前提下，增量表的总数：
$$T_k(e_1,\dots,e_r)=\prod_{j=1}^{r}\binom{e_j+k-1}{k-1}.$$
但这里面还包含非法情况，例如某一步在所有坐标上的增量都为 \(0\)，那就意味着这一层与上一层是同一个因子，不构成严格链。
真正的 gozinta 链要求每一步至少在某个坐标上增加。若在 \(k\) 个位置里只有 \(i\) 个位置被视为“有效步骤”，那么同样的拆分计数会给出
$$\prod_{j=1}^{r}\binom{e_j+i-1}{i-1}$$
种可能。再选择哪 \(i\) 个位置有效，并对空步骤做容斥，就得到恰好有 \(k\) 个严格步骤的链数
$$ F_k(e_1,\dots,e_r)=\sum_{i=1}^{k}(-1)^{k-i}\binom{k}{i}\prod_{j=1}^{r}\binom{e_j+i-1}{i-1}. $$
由于每一步都会把总指数和至少增加 \(1\)，所以步数不可能超过 \(\Omega\)。因此总链数就是
$$ G(e_1,\dots,e_r)=\sum_{k=1}^{\Omega} F_k(e_1,\dots,e_r). $$
这就是实现中用来判断某个指数模式是否对应 252 条链的精确公式。
实现会枚举指数的整数拆分，并对每一种模式直接计算上面的 \(G(e_1,\dots,e_r)\)。结果非常简洁：满足
$$G(e_1,\dots,e_r)=252$$
的唯一模式是
$$ (e_1,\dots,e_r)=(3,3). $$
于是所有目标整数都必须形如
$$ n=p^3q^3=(pq)^3,\qquad p\lt q \text{ 为质数}. $$
这里要求 \(p\) 与 \(q\) 不同，因为 \(p^6\) 的指数模式是 \((6)\)，而不是 \((3,3)\)。
取 \(n=2^3\cdot 3^3=216\)。这时 \(\Omega=6\)。如果链恰好有 \(k\) 步，那么“允许空步骤”的计数为
$$ T_k=\binom{3+k-1}{k-1}^2=\binom{k+2}{2}^2. $$
再做容斥可得
$$ F_k=\sum_{i=1}^{k}(-1)^{k-i}\binom{k}{i}\binom{i+2}{2}^2. $$
逐项计算得到
$$ \begin{aligned} F_1&=1,\\ F_2&=14,\\ F_3&=55,\\ F_4&=92,\\ F_5&=70,\\ F_6&=20. \end{aligned} $$
因此总数就是
$$ 1+14+55+92+70+20=252. $$
这说明 \(216\) 的确恰好有 252 条 gozinta 链。由于链数只由指数模式决定，任何 \(p^3q^3\) 都有同样的链数。
令
$$ X=\left\lfloor N^{1/3}\right\rfloor. $$
那么 \((pq)^3\le N\) 等价于 \(pq\le X\)，于是
$$ S(N)=\sum_{\substack{p\lt q\\ pq\le X}} (pq)^3. $$
对于题目中的 \(N=10^{36}\)，有 \(X=10^{12}\)。
接下来定义质数立方前缀和
$$ P_3(y)=\sum_{\substack{q\le y\\ q\text{ prime}}} q^3. $$
按较小的那个质数 \(p\) 分组后，可以改写成
$$ S(N)=\sum_{p\le \sqrt{X}} p^3\left(P_3\!\left(\left\lfloor\frac{X}{p}\right\rfloor\right)-P_3(p)\right). $$
这里减去 \(P_3(p)\) 的作用是强制 \(q>p\)，从而避免重复计算。
如果直接筛到 \(10^{12}\)，空间和时间都会过大。实现采用的是按商值分块的方法，只保留所有不同的
$$ v=\left\lfloor\frac{X}{i}\right\rfloor, $$
这样的值只有 \(O(\sqrt{X})\) 个。对每个这样的 \(v\)，先用普通整数立方和初始化：
$$ \sum_{m=2}^{v} m^3=\left(\frac{v(v+1)}{2}\right)^2-1. $$
之后再进行 Min_25 风格的质数修正。处理某个质数 \(p\) 时，对所有满足 \(v\ge p^2\) 的状态执行
$$ H(v)\leftarrow H(v)-p^3\left(H\!\left(\left\lfloor\frac{v}{p}\right\rfloor\right)-\sum_{q<p} q^3\right). $$
修正完成后，\(H(v)\) 就变成了 \(P_3(v)\)。由于题目只需要后九位，整个过程中都可以在模 \(10^9\) 下运算。
C++、Python 和 Java 实现遵循同一套数学结构。首先，它们对指数拆分直接套用链数公式，验证只有 \((3,3)\) 这一种模式会产生 252 条 gozinta 链。
然后，它们取 \(X=10^{12}\)，生成所有不超过 \(\sqrt{X}\) 的质数，并构造所有不同的 \(\lfloor X/i\rfloor\) 值组成的表。每个表项先用普通立方和公式初始化，再逐个质数做修正，直到表中只剩“质数立方前缀和”的信息。
最后，对每个较小质数 \(p\) 累加
$$ p^3\left(P_3\!\left(\left\lfloor\frac{X}{p}\right\rfloor\right)-P_3(p)\right) $$
并始终对 \(10^9\) 取模。在正式计算 \(10^{36}\) 之前，实现还会检查较小的验证值，例如 \(S(10^6)=8462952\) 和 \(S(10^{12})=623291998881978\)。
指数模式枚举相对于主计算来说几乎可以忽略。主算法中，先筛出不超过 \(\sqrt{X}\) 的质数，代价为 \(O(\sqrt{X}\log\log X)\) 时间和 \(O(\sqrt{X})\) 空间。商值表本身只有 \(O(\sqrt{X})\) 个状态。质数修正阶段里，一个质数 \(p\) 只会访问满足 \(v\ge p^2\) 的状态，因此总更新次数满足
$$ \sum_{p\le \sqrt{X}} O\!\left(\min\!\left(\sqrt{X},\frac{X}{p^2}\right)\right), $$
这对 \(X\) 来说是次线性的，并且符合 Min_25 类质数求和算法的典型复杂度轮廓。最后一层按质数 \(p\) 的累加只需要 \(O(\pi(\sqrt{X}))\)。因此，总空间复杂度为 \(O(\sqrt{X})\)，对 \(X=10^{12}\) 来说运行是可行的。
Gozinta-цепь для числа \(n\) — это последовательность
$$1=a_0\lt a_1\lt\cdots\lt a_t=n,$$
в которой каждый член делит следующий. Обозначим через \(g(n)\) число таких цепочек и введем
$$S(N)=\sum_{\substack{k\le N\\ g(k)=252}} k.$$
Нужно найти последние девять цифр числа \(S(10^{36})\). Полный перебор до \(10^{36}\) невозможен, поэтому решение сначала выясняет, какие именно шаблоны простых показателей дают 252 цепочки, а затем суммирует только соответствующие числа.
Пусть
$$n=\prod_{j=1}^{r} p_j^{e_j},\qquad \Omega=e_1+\cdots+e_r.$$
Главное наблюдение состоит в том, что число gozinta-цепей зависит только от шаблона показателей \((e_1,\dots,e_r)\), а не от самих простых \(p_j\).
Каждый делитель числа \(n\) единственным образом записывается в виде
$$d=\prod_{j=1}^{r} p_j^{b_j},\qquad 0\le b_j\le e_j.$$
Следовательно, делители соответствуют точкам решетки \(b=(b_1,\dots,b_r)\) внутри прямоугольного блока \([0,e_1]\times\cdots\times[0,e_r]\). Тогда gozinta-цепь — это строго возрастающая покоординатно последовательность
$$ (0,\dots,0)=v^{(0)}\lt v^{(1)}\lt\cdots\lt v^{(k)}=(e_1,\dots,e_r), $$
в которой на каждом шаге растет хотя бы одна координата. Поскольку описание использует только показатели, число цепей полностью определяется их шаблоном.
Зафиксируем длину \(k\), то есть \(k\) строгих переходов от \(1\) к \(n\). Пусть \(\delta_{j,t}\) — прирост \(j\)-й координаты на шаге \(t\). Тогда
$$\delta_{j,t}\ge 0,\qquad \sum_{t=1}^{k}\delta_{j,t}=e_j.$$
Для одного фиксированного простого показателя число слабых разбиений \(e_j\) на \(k\) частей равно
$$\binom{e_j+k-1}{k-1}.$$
Перемножая по всем координатам, получаем число таблиц приращений, если пока разрешить пустые шаги:
$$T_k(e_1,\dots,e_r)=\prod_{j=1}^{r}\binom{e_j+k-1}{k-1}.$$
Но в \(T_k\) входят и недопустимые случаи, когда некоторый шаг имеет нулевой прирост по всем координатам и потому не дает нового делителя.
В правильной gozinta-цепи каждый шаг должен быть непустым. Если среди \(k\) позиций активны только \(i\), то тот же подсчет дает
$$\prod_{j=1}^{r}\binom{e_j+i-1}{i-1}$$
вариантов. Выбирая активные позиции и применяя включение-исключение, получаем формулу
$$ F_k(e_1,\dots,e_r)=\sum_{i=1}^{k}(-1)^{k-i}\binom{k}{i}\prod_{j=1}^{r}\binom{e_j+i-1}{i-1}. $$
Это число цепей с ровно \(k\) строгими переходами. Поскольку каждый шаг увеличивает суммарный показатель хотя бы на \(1\), всегда \(1\le k\le \Omega\). Поэтому общее число цепей равно
$$ G(e_1,\dots,e_r)=\sum_{k=1}^{\Omega} F_k(e_1,\dots,e_r). $$
Реализации перебирают целочисленные разбиения показателей и точно вычисляют приведенную выше формулу. Результат однозначен: условие
$$G(e_1,\dots,e_r)=252$$
выполняется только для шаблона
$$ (e_1,\dots,e_r)=(3,3). $$
Следовательно, каждое подходящее число имеет вид
$$ n=p^3q^3=(pq)^3,\qquad p\lt q \text{ простые}. $$
Простые различны: число \(p^6\) имеет шаблон \((6)\), а не \((3,3)\).
Возьмем \(n=2^3\cdot 3^3=216\). Здесь \(\Omega=6\), и при фиксированном числе шагов \(k\)
$$ T_k=\binom{3+k-1}{k-1}^2=\binom{k+2}{2}^2. $$
После включения-исключения получаем
$$ F_k=\sum_{i=1}^{k}(-1)^{k-i}\binom{k}{i}\binom{i+2}{2}^2. $$
Отсюда следуют значения
$$ \begin{aligned} F_1&=1,\\ F_2&=14,\\ F_3&=55,\\ F_4&=92,\\ F_5&=70,\\ F_6&=20. \end{aligned} $$
Их сумма равна
$$ 1+14+55+92+70+20=252. $$
Значит, у числа \(216\) действительно ровно 252 gozinta-цепи, и по предыдущему шагу то же верно для любого числа вида \(p^3q^3\).
Положим
$$ X=\left\lfloor N^{1/3}\right\rfloor. $$
Тогда неравенство \((pq)^3\le N\) эквивалентно \(pq\le X\), и мы получаем
$$ S(N)=\sum_{\substack{p\lt q\\ pq\le X}} (pq)^3. $$
Для исходной задачи \(N=10^{36}\), поэтому \(X=10^{12}\).
Теперь введем префиксную сумму кубов простых
$$ P_3(y)=\sum_{\substack{q\le y\\ q\text{ prime}}} q^3. $$
Группируя по меньшему простому \(p\), переписываем сумму так:
$$ S(N)=\sum_{p\le \sqrt{X}} p^3\left(P_3\!\left(\left\lfloor\frac{X}{p}\right\rfloor\right)-P_3(p)\right). $$
Вычитание \(P_3(p)\) автоматически навязывает условие \(q>p\), поэтому каждая неупорядоченная пара простых учитывается один раз.
Полное решето до \(10^{12}\) оказалось бы слишком большим. Поэтому реализация хранит только различные значения
$$ v=\left\lfloor\frac{X}{i}\right\rfloor, $$
а их всего \(O(\sqrt{X})\). Для каждого такого \(v\) начальное значение берется из формулы обычной суммы кубов:
$$ \sum_{m=2}^{v} m^3=\left(\frac{v(v+1)}{2}\right)^2-1. $$
После этого выполняются поправки в стиле Min_25. При обработке простого \(p\) каждое состояние с \(v\ge p^2\) обновляется по формуле
$$ H(v)\leftarrow H(v)-p^3\left(H\!\left(\left\lfloor\frac{v}{p}\right\rfloor\right)-\sum_{q<p} q^3\right). $$
После обработки всех простых до \(\sqrt{X}\) получаем \(H(v)=P_3(v)\). Так как нужны только последние девять цифр, вся арифметика ведется по модулю \(10^9\).
Реализации на C++, Python и Java используют одно и то же математическое сокращение. Сначала они подтверждают структурный факт: перебирают шаблоны показателей, вычисляют точное число цепей и убеждаются, что только \((3,3)\) дает 252.
Затем они берут \(X=10^{12}\), строят список простых до \(\sqrt{X}\) и таблицу всех различных значений \(\lfloor X/i\rfloor\). Каждая ячейка таблицы инициализируется формулой суммы кубов, а затем поочередно корректируется по простым, пока в ней не останется только сумма кубов простых.
В финале перебирается меньший простой \(p\), и накапливается вклад
$$ p^3\left(P_3\!\left(\left\lfloor\frac{X}{p}\right\rfloor\right)-P_3(p)\right) $$
по модулю \(10^9\). Перед вычислением для \(10^{36}\) реализация также проверяет меньшие контрольные случаи, например \(S(10^6)=8462952\) и \(S(10^{12})=623291998881978\).
Проверка шаблонов показателей занимает ничтожное время по сравнению с основным этапом. В основном алгоритме построение простых до \(\sqrt{X}\) требует \(O(\sqrt{X}\log\log X)\) времени и \(O(\sqrt{X})\) памяти. Таблица частных содержит лишь \(O(\sqrt{X})\) состояний. На этапе поправок простой \(p\) затрагивает только состояния с \(v\ge p^2\), поэтому общее число обновлений имеет вид
$$ \sum_{p\le \sqrt{X}} O\!\left(\min\!\left(\sqrt{X},\frac{X}{p^2}\right)\right), $$
что сублинейно по \(X\) и соответствует типичному профилю методов суммирования простых типа Min_25. Заключительный проход по \(p\le \sqrt{X}\) линейен по \(\pi(\sqrt{X})\). В итоге используется \(O(\sqrt{X})\) памяти и практичное сублинейное время для \(X=10^{12}\).
سلسلة gozinta للعدد \(n\) هي متتالية من الشكل
$$1=a_0\lt a_1\lt\cdots\lt a_t=n,$$
بحيث يقسم كل حد الحد الذي يليه. نرمز بعدد هذه السلاسل بالرمز \(g(n)\)، ثم نعرّف
$$S(N)=\sum_{\substack{k\le N\\ g(k)=252}} k.$$
المطلوب هو آخر تسعة أرقام من \(S(10^{36})\). ومن الواضح أن الفحص المباشر حتى \(10^{36}\) غير ممكن، لذلك يبدأ الحل بتحديد النمط الوحيد لأسس العوامل الأولية الذي يعطي 252 سلسلة، ثم يجمع الأعداد التي تملك هذا النمط فقط.
لنكتب
$$n=\prod_{j=1}^{r} p_j^{e_j},\qquad \Omega=e_1+\cdots+e_r.$$
الفكرة الحاسمة هي أن عدد سلاسل gozinta يعتمد فقط على نمط الأسس \((e_1,\dots,e_r)\)، ولا يعتمد على أسماء الأعداد الأولية \(p_j\) نفسها.
كل قاسم للعدد \(n\) يمكن كتابته بشكل وحيد على الصورة
$$d=\prod_{j=1}^{r} p_j^{b_j},\qquad 0\le b_j\le e_j.$$
وهذا يعني أن القواسم تقابل نقاط الشبكة \(b=(b_1,\dots,b_r)\) داخل الصندوق \([0,e_1]\times\cdots\times[0,e_r]\). وعندئذ تصبح سلسلة gozinta سلسلة متزايدة إحداثيًا بصورة صارمة:
$$ (0,\dots,0)=v^{(0)}\lt v^{(1)}\lt\cdots\lt v^{(k)}=(e_1,\dots,e_r), $$
بحيث يزداد على الأقل إحداثي واحد في كل خطوة. ولأن هذا الوصف يستعمل الأسس فقط، فإن عدد السلاسل يتحدد بالكامل بواسطة نمط الأسس.
ثبّت طولًا مقداره \(k\)، أي \(k\) انتقالات صارمة من \(1\) إلى \(n\). إذا رمزنا إلى زيادة الإحداثي \(j\) في الخطوة \(t\) بالرمز \(\delta_{j,t}\)، فإن
$$\delta_{j,t}\ge 0,\qquad \sum_{t=1}^{k}\delta_{j,t}=e_j.$$
وبالنسبة إلى أس واحد \(e_j\)، فإن عدد طرق توزيعه على \(k\) خطوات توزيعًا ضعيفًا يساوي
$$\binom{e_j+k-1}{k-1}.$$
وبالضرب على جميع الإحداثيات نحصل على عدد جداول الزيادات إذا سمحنا مؤقتًا بوجود خطوات فارغة:
$$T_k(e_1,\dots,e_r)=\prod_{j=1}^{r}\binom{e_j+k-1}{k-1}.$$
لكن هذا العد ما زال يتضمن الحالات غير الصالحة التي تكون فيها إحدى الخطوات صفرية في جميع الإحداثيات، فتكرر القاسم نفسه بدل الانتقال إلى قاسم أكبر.
لكي تكون السلسلة صالحة، يجب أن تحتوي كل خطوة على زيادة حقيقية في إحداثي واحد على الأقل. إذا افترضنا أن \(i\) مواضع فقط من أصل \(k\) هي المواضع الفعالة، فإن العد نفسه يعطي
$$\prod_{j=1}^{r}\binom{e_j+i-1}{i-1}$$
احتمالًا. وبعد اختيار المواضع الفعالة ثم تطبيق الاشتمال والاستبعاد نحصل على
$$ F_k(e_1,\dots,e_r)=\sum_{i=1}^{k}(-1)^{k-i}\binom{k}{i}\prod_{j=1}^{r}\binom{e_j+i-1}{i-1}. $$
وهذا هو عدد السلاسل التي تحتوي على \(k\) خطوات صارمة بالضبط. وبما أن كل خطوة تزيد مجموع الأسس بمقدار لا يقل عن \(1\)، فلا يمكن أن يتجاوز \(k\) القيمة \(\Omega\). لذلك يكون العدد الكلي للسلاسل
$$ G(e_1,\dots,e_r)=\sum_{k=1}^{\Omega} F_k(e_1,\dots,e_r). $$
تقوم التطبيقات بتعداد تقسيمات الأسس الصحيحة وتقييم الصيغة السابقة مباشرة. والنتيجة واضحة: الشرط
$$G(e_1,\dots,e_r)=252$$
لا يتحقق إلا للنمط
$$ (e_1,\dots,e_r)=(3,3). $$
إذن كل عدد مطلوب يجب أن يكون من الصورة
$$ n=p^3q^3=(pq)^3,\qquad p\lt q \text{ أوليان}. $$
ولا بد أن يكونا أوليين مختلفين، لأن \(p^6\) يملك النمط \((6)\) لا النمط \((3,3)\).
لنأخذ \(n=2^3\cdot 3^3=216\). عندها \(\Omega=6\)، ولعدد خطوات ثابت \(k\) نحصل على
$$ T_k=\binom{3+k-1}{k-1}^2=\binom{k+2}{2}^2. $$
ثم يعطي مبدأ الاشتمال والاستبعاد
$$ F_k=\sum_{i=1}^{k}(-1)^{k-i}\binom{k}{i}\binom{i+2}{2}^2. $$
وبالحساب نجد
$$ \begin{aligned} F_1&=1,\\ F_2&=14,\\ F_3&=55,\\ F_4&=92,\\ F_5&=70,\\ F_6&=20. \end{aligned} $$
ومن ثم
$$ 1+14+55+92+70+20=252. $$
إذن العدد \(216\) يملك فعلًا 252 سلسلة gozinta، وبما أن العدد يعتمد فقط على نمط الأسس فإن كل عدد من الصورة \(p^3q^3\) يملك العدد نفسه من السلاسل.
لنضع
$$ X=\left\lfloor N^{1/3}\right\rfloor. $$
عندئذٍ يكون الشرط \((pq)^3\le N\) مكافئًا لـ \(pq\le X\)، وبالتالي
$$ S(N)=\sum_{\substack{p\lt q\\ pq\le X}} (pq)^3. $$
وبالنسبة إلى المسألة الفعلية فإن \(N=10^{36}\)، لذا \(X=10^{12}\).
الآن نعرّف مجموع البوادئ لمكعبات الأعداد الأولية:
$$ P_3(y)=\sum_{\substack{q\le y\\ q\text{ prime}}} q^3. $$
وبتجميع الحدود حسب الأصغر بين \(p\) و\(q\) نحصل على
$$ S(N)=\sum_{p\le \sqrt{X}} p^3\left(P_3\!\left(\left\lfloor\frac{X}{p}\right\rfloor\right)-P_3(p)\right). $$
إن طرح \(P_3(p)\) هو الذي يفرض الشرط \(q>p\)، وبالتالي يمنع العد المكرر.
الغربال الكامل حتى \(10^{12}\) كبير جدًا. لذلك يخزن التنفيذ فقط القيم المختلفة من الشكل
$$ v=\left\lfloor\frac{X}{i}\right\rfloor, $$
وعددها لا يتجاوز \(O(\sqrt{X})\). ولكل قيمة \(v\) يبدأ التنفيذ من مجموع المكعبات العادي
$$ \sum_{m=2}^{v} m^3=\left(\frac{v(v+1)}{2}\right)^2-1. $$
بعد ذلك تطبق تصحيحات على نمط Min_25. فعند معالجة أولي \(p\)، وكلما كان \(v\ge p^2\)، يتم التحديث وفقًا للعلاقة
$$ H(v)\leftarrow H(v)-p^3\left(H\!\left(\left\lfloor\frac{v}{p}\right\rfloor\right)-\sum_{q<p} q^3\right). $$
وبعد الانتهاء من جميع الأوليات حتى \(\sqrt{X}\) تصبح \(H(v)=P_3(v)\). ولأن المطلوب هو آخر تسعة أرقام فقط، فإن الحسابات كلها تُجرى بترديد \(10^9\).
تتبع تطبيقات C++ وPython وJava الاختزال الرياضي نفسه. في البداية تتحقق من الحقيقة البنيوية عبر تقييم صيغة عدد السلاسل على تقسيمات الأسس، ثم تتأكد أن النمط الوحيد الذي يعطي 252 هو \((3,3)\).
بعد ذلك تأخذ \(X=10^{12}\)، وتولد جميع الأعداد الأولية حتى \(\sqrt{X}\)، وتبني جدول القيم المختلفة \(\lfloor X/i\rfloor\). كل خانة تبدأ بصيغة مجموع المكعبات المعتاد، ثم تُصحح أوليًا فأوليًا حتى لا يبقى في الجدول إلا مجموع مكعبات الأوليات.
وأخيرًا تمر على الأولي الأصغر \(p\) وتجمع
$$ p^3\left(P_3\!\left(\left\lfloor\frac{X}{p}\right\rfloor\right)-P_3(p)\right) $$
مع الاختزال المستمر بترديد \(10^9\). وقبل الحالة النهائية \(10^{36}\)، يتحقق التنفيذ أيضًا من حالات أصغر معروفة مثل \(S(10^6)=8462952\) و\(S(10^{12})=623291998881978\).
تعداد أنماط الأسس صغير جدًا مقارنة بالحساب الرئيسي. أما في الخوارزمية الأساسية، فإن غربلة الأوليات حتى \(\sqrt{X}\) تكلف \(O(\sqrt{X}\log\log X)\) زمنًا و\(O(\sqrt{X})\) ذاكرة. وجدول القيم المختلفة نفسه يحوي \(O(\sqrt{X})\) حالة فقط. وفي مرحلة التصحيح، لا يلمس الأولي \(p\) إلا الحالات التي تحقق \(v\ge p^2\)، لذا يكون عدد التحديثات الكلي
$$ \sum_{p\le \sqrt{X}} O\!\left(\min\!\left(\sqrt{X},\frac{X}{p^2}\right)\right), $$
وهو مقدار دون خطي في \(X\)، ومتوافق مع السلوك المعتاد لطرائق جمع الأوليات من نوع Min_25. أما المرور الأخير على الأوليات حتى \(\sqrt{X}\) فهو خطي في \(\pi(\sqrt{X})\). وبذلك تستخدم الطريقة \(O(\sqrt{X})\) ذاكرة وزمنًا دون خطي عمليًا عندما \(X=10^{12}\).