This problem comes from a lattice-point configuration involving a parabola and a line. After the geometric reduction used by the implementation, the remaining task is to evaluate an exact arithmetic counting function \(S(N)\). The Project Euler target is the residue of \(S(10^{12})\) modulo \(10^8\).
The important point is that the implementation never enumerates lattice points one by one. Instead, it uses a closed formula made of a fixed polynomial part and a quotient-dependent summation whose values are grouped into floor-division blocks.
The reduced counting formula is built from three polynomial prefix functions:
$$P_1(t)=\frac{(t^2-t+6)(t+1)}{6},$$
$$P_2(t)=\frac{(t^2-t+12)(t+1)(t+2)}{24},$$
$$P_3(t)=\frac{(t^2-t+20)(t+1)(t+2)(t+3)}{120}.$$
Expanding them shows that they are cubic, quartic, and quintic polynomials:
$$P_1(t)=\frac{t^3+5t+6}{6},\qquad P_2(t)=\frac{t^4+2t^3+11t^2+34t+24}{24},$$
$$P_3(t)=\frac{t^5+5t^4+25t^3+115t^2+214t+120}{120}.$$
What matters computationally is their telescoping behavior:
$$P_1(t)-P_1(t-1)=\frac{t(t-1)}{2}+1,$$
$$P_2(t)-P_2(t-1)=P_1(t),\qquad P_3(t)-P_3(t-1)=P_2(t).$$
So \(P_2\) is a prefix sum of \(P_1\), and \(P_3\) is a prefix sum of \(P_2\). This is exactly why long ranges can later be collapsed to differences of polynomial values.
The formulas also satisfy convenient zero values:
$$P_2(-1)=P_2(-2)=0,\qquad P_3(-1)=P_3(-2)=P_3(-3)=0.$$
These vanishings are not accidental: they come from the explicit factors \((t+1)(t+2)\) in \(P_2\) and \((t+1)(t+2)(t+3)\) in \(P_3\). As a result, the same telescoping identities remain valid even when a boundary term lands just below zero. That allows the implementation to use one uniform arithmetic formula at block boundaries without adding special cases.
After the geometric part has been reduced away, the exact count has the form
$$S(N)=B(N)+\sum_{m=2}^{N-1} H_N(m),$$
where the fixed base contribution is
$$B(N)=P_2(N)+P_2(N+1)+P_2(N-2)+P_1(N)+P_1(N+1).$$
For each integer \(m\) in the remaining sum, define the quotient
$$q=\left\lfloor\frac{N}{m}\right\rfloor.$$
The summand is then piecewise:
$$H_N(m)= \begin{cases} P_2(m+q)+P_2(q-m), & m\le q,\\ P_2(m+q)-P_2(m-q-1), & m\gt q. \end{cases}$$
This is the exact arithmetic content used by the C++, Python, and Java implementations. The two branches correspond to the two regimes on opposite sides of the diagonal \(m=q\), equivalently on opposite sides of \(\sqrt N\).
The expensive-looking term is the quotient \(q=\lfloor N/m\rfloor\). But \(q\) is constant on intervals of consecutive \(m\)-values. If a block begins at \(L\), then the common quotient is
$$q=\left\lfloor\frac{N}{L}\right\rfloor,$$
and the block ends at
$$R=\left\lfloor\frac{N}{q}\right\rfloor.$$
Therefore every \(m\in[L,R]\) shares the same quotient \(q\). The classic fact behind this technique is that \(\lfloor N/m\rfloor\) takes only \(O(\sqrt N)\) distinct values, which turns the summation into a block computation rather than a linear scan.
Because \(P_3\) is a prefix sum of \(P_2\), each block can be collapsed in constant time.
If the block lies entirely in the region \(m\le q\), then
$$\sum_{m=L}^{R} H_N(m)=\sum_{m=L}^{R}\bigl(P_2(m+q)+P_2(q-m)\bigr).$$
Applying the prefix identity twice gives
$$\sum_{m=L}^{R} H_N(m)=P_3(R+q)-P_3(L+q-1)+P_3(q-L)-P_3(q-R-1).$$
If the block lies entirely in the region \(m\gt q\), then
$$\sum_{m=L}^{R} H_N(m)=\sum_{m=L}^{R}\bigl(P_2(m+q)-P_2(m-q-1)\bigr),$$
so
$$\sum_{m=L}^{R} H_N(m)=P_3(R+q)-P_3(L+q-1)-P_3(R-q-1)+P_3(L-q-2).$$
Each quotient block lies wholly on one side of the diagonal. Indeed, blocks with \(m\le q\) are exactly the ones in the small-\(m\) region \(m\le \sqrt N\), while blocks with \(m\gt q\) lie in the large-\(m\) region \(m\gt \sqrt N\). That is why one branch choice per block is enough.
First evaluate the base term:
$$P_2(5)=56,\qquad P_2(6)=98,\qquad P_2(3)=15,\qquad P_1(5)=26,\qquad P_1(6)=42,$$
hence
$$B(5)=56+98+15+26+42=237.$$
Now process the quotient blocks.
For \(m=2\), we have \(q=\lfloor 5/2\rfloor=2\), so this is the \(m\le q\) case:
$$H_5(2)=P_2(4)+P_2(0)=30+1=31.$$
For \(m=3,4\), the quotient is \(q=1\). This is a single \(m\gt q\) block with \(L=3\) and \(R=4\):
$$\sum_{m=3}^{4} H_5(m)=P_3(5)-P_3(3)-P_3(2)+P_3(0).$$
Using \(P_3(5)=112\), \(P_3(3)=26\), \(P_3(2)=11\), and \(P_3(0)=1\), we get
$$\sum_{m=3}^{4} H_5(m)=112-26-11+1=76.$$
Therefore
$$S(5)=237+31+76=344,$$
which matches the checkpoint used by the implementation. A second checkpoint is
$$S(100)=26709528.$$
The C++, Python, and Java implementations all follow the same strategy. They evaluate the fixed base term once, then sweep the remaining range by quotient blocks rather than by individual indices. For each block, they compute one shared floor quotient, determine the block endpoint from that quotient, and add the corresponding telescoped \(P_3\)-difference formula.
The sum is kept exact throughout. Only after the full integer value of \(S(N)\) has been assembled do the implementations reduce it modulo \(10^8\). That is essential because the exact count for \(N=10^{12}\) is far larger than ordinary machine integers can hold safely.
The number of distinct values of \(\lfloor N/m\rfloor\) is \(O(\sqrt N)\). Each block requires only a constant number of polynomial evaluations and integer additions/subtractions, so the total running time is
$$O(\sqrt N).$$
The algorithm stores only a fixed amount of state apart from arbitrary-precision integer temporaries, so the memory usage is \(O(1)\).
Diese Aufgabe entsteht aus einer Gitterpunkt-Konfiguration mit einer Parabel und einer Geraden. Nach der geometrischen Reduktion, die in der Implementierung bereits vorausgesetzt wird, bleibt eine exakte arithmetische Zählfunktion \(S(N)\). Für Project Euler wird der Rest von \(S(10^{12})\) modulo \(10^8\) gesucht.
Entscheidend ist, dass die Implementierung keine Gitterpunkte einzeln aufzählt. Stattdessen verwendet sie eine geschlossene Formel aus einem festen polynomialen Grundterm und einer quotientabhängigen Summe, deren Werte zu Blöcken gleicher Ganzzahldivision zusammengefasst werden.
Die reduzierte Zählformel basiert auf drei polynomialen Präfixfunktionen:
$$P_1(t)=\frac{(t^2-t+6)(t+1)}{6},$$
$$P_2(t)=\frac{(t^2-t+12)(t+1)(t+2)}{24},$$
$$P_3(t)=\frac{(t^2-t+20)(t+1)(t+2)(t+3)}{120}.$$
Ausmultipliziert sind das ein kubisches, ein quartisches und ein quintisches Polynom:
$$P_1(t)=\frac{t^3+5t+6}{6},\qquad P_2(t)=\frac{t^4+2t^3+11t^2+34t+24}{24},$$
$$P_3(t)=\frac{t^5+5t^4+25t^3+115t^2+214t+120}{120}.$$
Für die Berechnung ist ihre Teleskopstruktur entscheidend:
$$P_1(t)-P_1(t-1)=\frac{t(t-1)}{2}+1,$$
$$P_2(t)-P_2(t-1)=P_1(t),\qquad P_3(t)-P_3(t-1)=P_2(t).$$
Damit ist \(P_2\) eine Präfixsumme von \(P_1\) und \(P_3\) eine Präfixsumme von \(P_2\). Genau dadurch lassen sich lange Summenintervalle später auf Differenzen weniger Polynomwerte reduzieren.
Die Formeln besitzen außerdem bequeme Nullstellen an kleinen negativen Stellen:
$$P_2(-1)=P_2(-2)=0,\qquad P_3(-1)=P_3(-2)=P_3(-3)=0.$$
Das folgt direkt aus den Faktoren \((t+1)(t+2)\) in \(P_2\) und \((t+1)(t+2)(t+3)\) in \(P_3\). Deshalb bleiben die Teleskopformeln auch dann korrekt, wenn ein Randterm knapp unter null fällt. Zusätzliche Sonderbehandlungen an Blockgrenzen sind also nicht nötig.
Nach der geometrischen Reduktion hat die exakte Anzahl die Form
$$S(N)=B(N)+\sum_{m=2}^{N-1} H_N(m),$$
wobei der feste Grundbeitrag
$$B(N)=P_2(N)+P_2(N+1)+P_2(N-2)+P_1(N)+P_1(N+1)$$
ist. Für jedes \(m\) der restlichen Summe definieren wir den Quotienten
$$q=\left\lfloor\frac{N}{m}\right\rfloor.$$
Dann gilt für den Summanden
$$H_N(m)= \begin{cases} P_2(m+q)+P_2(q-m), & m\le q,\\ P_2(m+q)-P_2(m-q-1), & m\gt q. \end{cases}$$
Genau dieser arithmetische Ausdruck wird von den C++-, Python- und Java-Implementierungen ausgewertet. Die zwei Zweige entsprechen den beiden Bereichen auf unterschiedlichen Seiten der Diagonale \(m=q\), also äquivalent auf unterschiedlichen Seiten von \(\sqrt N\).
Der scheinbar schwierige Teil ist der Quotient \(q=\lfloor N/m\rfloor\). Aber dieser Wert bleibt auf ganzen Intervallen konstant. Beginnt ein Block bei \(L\), dann ist der gemeinsame Quotient
$$q=\left\lfloor\frac{N}{L}\right\rfloor,$$
und das Blockende ist
$$R=\left\lfloor\frac{N}{q}\right\rfloor.$$
Somit besitzen alle \(m\in[L,R]\) denselben Quotienten \(q\). Hinter dieser Technik steckt die Standardbeobachtung, dass \(\lfloor N/m\rfloor\) nur \(O(\sqrt N)\) verschiedene Werte annimmt. Daher wird aus einer linearen Summation eine Blockrechnung.
Da \(P_3\) eine Präfixsumme von \(P_2\) ist, lässt sich jeder Block mit konstant vielen Auswertungen zusammenfassen.
Liegt der gesamte Block im Bereich \(m\le q\), dann
$$\sum_{m=L}^{R} H_N(m)=\sum_{m=L}^{R}\bigl(P_2(m+q)+P_2(q-m)\bigr).$$
Durch zweimaliges Teleskopieren folgt
$$\sum_{m=L}^{R} H_N(m)=P_3(R+q)-P_3(L+q-1)+P_3(q-L)-P_3(q-R-1).$$
Liegt der gesamte Block im Bereich \(m\gt q\), dann
$$\sum_{m=L}^{R} H_N(m)=\sum_{m=L}^{R}\bigl(P_2(m+q)-P_2(m-q-1)\bigr),$$
also
$$\sum_{m=L}^{R} H_N(m)=P_3(R+q)-P_3(L+q-1)-P_3(R-q-1)+P_3(L-q-2).$$
Jeder Quotientenblock liegt vollständig auf einer Seite der Diagonale. Blöcke mit \(m\le q\) befinden sich genau im kleinen Bereich \(m\le \sqrt N\), und Blöcke mit \(m\gt q\) im großen Bereich \(m\gt \sqrt N\). Darum genügt pro Block genau eine Fallunterscheidung.
Zuerst der Grundterm:
$$P_2(5)=56,\qquad P_2(6)=98,\qquad P_2(3)=15,\qquad P_1(5)=26,\qquad P_1(6)=42,$$
also
$$B(5)=56+98+15+26+42=237.$$
Nun die Quotientenblöcke.
Für \(m=2\) gilt \(q=\lfloor 5/2\rfloor=2\), also der Fall \(m\le q\):
$$H_5(2)=P_2(4)+P_2(0)=30+1=31.$$
Für \(m=3,4\) ist der Quotient \(q=1\). Das ist ein einzelner Block mit \(m\gt q\), also \(L=3\) und \(R=4\):
$$\sum_{m=3}^{4} H_5(m)=P_3(5)-P_3(3)-P_3(2)+P_3(0).$$
Mit \(P_3(5)=112\), \(P_3(3)=26\), \(P_3(2)=11\) und \(P_3(0)=1\) erhält man
$$\sum_{m=3}^{4} H_5(m)=112-26-11+1=76.$$
Damit folgt
$$S(5)=237+31+76=344,$$
genau der Kontrollwert der Implementierung. Ein zweiter Kontrollwert ist
$$S(100)=26709528.$$
Die C++-, Python- und Java-Implementierungen verwenden dieselbe Strategie. Zuerst berechnen sie einmal den festen Grundterm. Danach durchlaufen sie den restlichen Bereich nicht indexweise, sondern blockweise nach konstantem Ganzzahlquotienten. Für jeden Block bestimmen sie den gemeinsamen Quotienten, daraus das Blockende und addieren anschließend die passende teleskopierte \(P_3\)-Differenzformel.
Die Summe bleibt dabei stets exakt. Erst nachdem der vollständige ganzzahlige Wert von \(S(N)\) zusammengesetzt wurde, erfolgt die Reduktion modulo \(10^8\). Das ist nötig, weil die exakte Anzahl für \(N=10^{12}\) weit über den Bereich gewöhnlicher Maschinenzahlen hinausgeht.
Die Anzahl verschiedener Werte von \(\lfloor N/m\rfloor\) ist \(O(\sqrt N)\). Jeder Block benötigt nur konstant viele Polynomauswertungen sowie ganzzahlige Additionen und Subtraktionen, daher beträgt die Laufzeit insgesamt
$$O(\sqrt N).$$
Abgesehen von temporären Ganzzahlen beliebiger Präzision ist nur konstanter Zusatzspeicher nötig, also \(O(1)\).
Bu problem, bir parabol ile bir doğru arasında kalan kafes noktalarıyla ilgili bir yapıdan gelir. Uygulamanın kullandığı geometrik indirgeme yapıldıktan sonra geriye tam sayılı bir aritmetik sayım fonksiyonu \(S(N)\) kalır. Project Euler hedefi, \(S(10^{12})\) değerinin \(10^8\) modundaki kalıntısını bulmaktır.
Önemli nokta şudur: uygulama kafes noktalarını tek tek dolaşmaz. Bunun yerine, sabit bir polinom katkısı ile bölüm değerine bağlı bir toplamdan oluşan kapalı bir formül kullanır; bu toplam da aynı taban bölme sonucunu veren bloklar halinde işlenir.
İndirgenmiş sayım formülü üç polinom ön toplam fonksiyonuna dayanır:
$$P_1(t)=\frac{(t^2-t+6)(t+1)}{6},$$
$$P_2(t)=\frac{(t^2-t+12)(t+1)(t+2)}{24},$$
$$P_3(t)=\frac{(t^2-t+20)(t+1)(t+2)(t+3)}{120}.$$
Açarsak bunların sırasıyla kübik, dördüncü dereceden ve beşinci dereceden polinomlar olduğunu görürüz:
$$P_1(t)=\frac{t^3+5t+6}{6},\qquad P_2(t)=\frac{t^4+2t^3+11t^2+34t+24}{24},$$
$$P_3(t)=\frac{t^5+5t^4+25t^3+115t^2+214t+120}{120}.$$
Asıl önemli olan teleskopik fark ilişkileridir:
$$P_1(t)-P_1(t-1)=\frac{t(t-1)}{2}+1,$$
$$P_2(t)-P_2(t-1)=P_1(t),\qquad P_3(t)-P_3(t-1)=P_2(t).$$
Buna göre \(P_2\), \(P_1\)'in; \(P_3\) ise \(P_2\)'nin ön toplamıdır. Uzun aralıkların birkaç polinom farkına indirgenebilmesinin nedeni tam olarak budur.
Formüller küçük negatif değerlerde şu sıfırlara da sahiptir:
$$P_2(-1)=P_2(-2)=0,\qquad P_3(-1)=P_3(-2)=P_3(-3)=0.$$
Bu özellik, \(P_2\)'deki \((t+1)(t+2)\) ve \(P_3\)'teki \((t+1)(t+2)(t+3)\) çarpanlarından doğrudan gelir. Böylece bir blok sınır terimi sıfırın biraz altına düşse bile teleskopik ifadeler bozulmaz; ayrıca ayrı bir özel durum kodu yazmak gerekmez.
Geometrik kısım elendikten sonra tam sayı
$$S(N)=B(N)+\sum_{m=2}^{N-1} H_N(m)$$
şeklinde yazılır. Buradaki sabit temel katkı
$$B(N)=P_2(N)+P_2(N+1)+P_2(N-2)+P_1(N)+P_1(N+1)$$
olarak verilir. Kalan toplamda her \(m\) için
$$q=\left\lfloor\frac{N}{m}\right\rfloor$$
tanımını yapalım. O zaman terim
$$H_N(m)= \begin{cases} P_2(m+q)+P_2(q-m), & m\le q,\\ P_2(m+q)-P_2(m-q-1), & m\gt q \end{cases}$$
olur. C++, Python ve Java uygulamalarının doğrudan hesapladığı aritmetik ifade budur. İki dal, \(m=q\) köşegeninin iki tarafındaki iki rejimi, eşdeğer olarak da \(\sqrt N\)'nin iki tarafını temsil eder.
Zor gibi görünen kısım \(q=\lfloor N/m\rfloor\) bölümüdür. Fakat bu değer ardışık \(m\) aralıklarında sabittir. Bir blok \(L\) noktasında başlıyorsa ortak bölüm
$$q=\left\lfloor\frac{N}{L}\right\rfloor$$
olur ve blok sonu
$$R=\left\lfloor\frac{N}{q}\right\rfloor$$
şeklindedir. Dolayısıyla \(L\le m\le R\) aralığındaki her değer aynı \(q\) bölümünü paylaşır. Temel gözlem, \(\lfloor N/m\rfloor\) ifadesinin yalnızca \(O(\sqrt N)\) farklı değer almasıdır; böylece lineer toplama yerine blok bazlı hesap yapılabilir.
\(P_3\), \(P_2\)'nin ön toplamı olduğu için her blok sabit zamanda hesaplanabilir.
Eğer blok tamamen \(m\le q\) bölgesindeyse
$$\sum_{m=L}^{R} H_N(m)=\sum_{m=L}^{R}\bigl(P_2(m+q)+P_2(q-m)\bigr).$$
İki kez ön toplam kullanınca
$$\sum_{m=L}^{R} H_N(m)=P_3(R+q)-P_3(L+q-1)+P_3(q-L)-P_3(q-R-1)$$
elde edilir. Eğer blok tamamen \(m\gt q\) bölgesindeyse
$$\sum_{m=L}^{R} H_N(m)=\sum_{m=L}^{R}\bigl(P_2(m+q)-P_2(m-q-1)\bigr),$$
dolayısıyla
$$\sum_{m=L}^{R} H_N(m)=P_3(R+q)-P_3(L+q-1)-P_3(R-q-1)+P_3(L-q-2).$$
Her bölüm bloğu köşegenin tamamen bir tarafında kalır. \(m\le q\) olan bloklar tam olarak \(m\le \sqrt N\) küçük bölgesinde, \(m\gt q\) olanlar ise \(m\gt \sqrt N\) büyük bölgesindedir. Bu yüzden blok başına tek bir durum seçimi yeterlidir.
Önce taban terimi hesaplayalım:
$$P_2(5)=56,\qquad P_2(6)=98,\qquad P_2(3)=15,\qquad P_1(5)=26,\qquad P_1(6)=42,$$
buradan
$$B(5)=56+98+15+26+42=237$$
çıkar. Şimdi bölüm bloklarına geçelim.
\(m=2\) için \(q=\lfloor 5/2\rfloor=2\), yani \(m\le q\) durumu:
$$H_5(2)=P_2(4)+P_2(0)=30+1=31.$$
\(m=3,4\) için bölüm \(q=1\)'dir. Bu, \(L=3\) ve \(R=4\) olan tek bir \(m\gt q\) bloğudur:
$$\sum_{m=3}^{4} H_5(m)=P_3(5)-P_3(3)-P_3(2)+P_3(0).$$
\(P_3(5)=112\), \(P_3(3)=26\), \(P_3(2)=11\), \(P_3(0)=1\) olduğundan
$$\sum_{m=3}^{4} H_5(m)=112-26-11+1=76$$
bulunur. Böylece
$$S(5)=237+31+76=344,$$
yani uygulamadaki kontrol değeri elde edilir. İkinci kontrol değeri de
$$S(100)=26709528$$
şeklindedir.
C++, Python ve Java uygulamaları aynı yöntemi izler. Önce sabit taban katkısı bir kez hesaplanır. Daha sonra kalan aralık tek tek değil, sabit taban bölümüne göre bloklar halinde dolaşılır. Her blok için ortak bölüm bulunur, bu bölümden blok sonu çıkarılır ve uygun teleskopik \(P_3\) fark formülü eklenir.
Toplam her aşamada tam sayı olarak korunur. \(S(N)\)'in tam değeri elde edildikten sonra ancak en son \(10^8\) ile mod alınır. Bu gereklidir; çünkü \(N=10^{12}\) için tam sonuç sıradan makine tamsayılarının rahatça taşıyabileceği aralığın çok üzerindedir.
\(\lfloor N/m\rfloor\) ifadesinin farklı değer sayısı \(O(\sqrt N)\) mertebesindedir. Her blok sabit sayıda polinom değerlendirmesi ile birkaç toplama ve çıkarma gerektirdiğinden toplam çalışma süresi
$$O(\sqrt N)$$
olur. Keyfi büyüklükte tam sayı geçicileri dışında ek bellek kullanımı \(O(1)\)'dir.
Este problema procede de una configuración de puntos de retícula relacionada con una parábola y una recta. Tras la reducción geométrica que ya incorpora la implementación, la tarea restante es evaluar una función aritmética exacta \(S(N)\). El objetivo de Project Euler es el residuo de \(S(10^{12})\) módulo \(10^8\).
Lo importante es que la implementación no enumera los puntos uno por uno. En su lugar usa una fórmula cerrada formada por una parte polinómica fija y una suma dependiente de cocientes enteros, agrupada en bloques donde el valor de la división entera permanece constante.
La fórmula reducida se construye a partir de tres funciones prefijo polinómicas:
$$P_1(t)=\frac{(t^2-t+6)(t+1)}{6},$$
$$P_2(t)=\frac{(t^2-t+12)(t+1)(t+2)}{24},$$
$$P_3(t)=\frac{(t^2-t+20)(t+1)(t+2)(t+3)}{120}.$$
Al expandirlas obtenemos un polinomio cúbico, uno cuártico y uno de grado cinco:
$$P_1(t)=\frac{t^3+5t+6}{6},\qquad P_2(t)=\frac{t^4+2t^3+11t^2+34t+24}{24},$$
$$P_3(t)=\frac{t^5+5t^4+25t^3+115t^2+214t+120}{120}.$$
La propiedad decisiva es su comportamiento telescópico:
$$P_1(t)-P_1(t-1)=\frac{t(t-1)}{2}+1,$$
$$P_2(t)-P_2(t-1)=P_1(t),\qquad P_3(t)-P_3(t-1)=P_2(t).$$
Así, \(P_2\) es una suma prefijo de \(P_1\), y \(P_3\) es una suma prefijo de \(P_2\). Por eso intervalos largos pueden comprimirse en diferencias de unos pocos valores polinómicos.
Las fórmulas también tienen ceros convenientes en enteros negativos pequeños:
$$P_2(-1)=P_2(-2)=0,\qquad P_3(-1)=P_3(-2)=P_3(-3)=0.$$
Esto se debe a los factores \((t+1)(t+2)\) en \(P_2\) y \((t+1)(t+2)(t+3)\) en \(P_3\). En consecuencia, las identidades telescópicas siguen siendo correctas incluso cuando un extremo del bloque cae ligeramente por debajo de cero. No hace falta introducir casos especiales en esas fronteras.
Una vez eliminada la parte geométrica, el recuento exacto toma la forma
$$S(N)=B(N)+\sum_{m=2}^{N-1} H_N(m),$$
donde la contribución base es
$$B(N)=P_2(N)+P_2(N+1)+P_2(N-2)+P_1(N)+P_1(N+1).$$
Para cada entero \(m\) de la suma restante definimos
$$q=\left\lfloor\frac{N}{m}\right\rfloor.$$
Entonces el sumando es
$$H_N(m)= \begin{cases} P_2(m+q)+P_2(q-m), & m\le q,\\ P_2(m+q)-P_2(m-q-1), & m\gt q. \end{cases}$$
Ese es exactamente el contenido aritmético que evalúan las implementaciones en C++, Python y Java. Las dos ramas corresponden a los dos regímenes separados por la diagonal \(m=q\), o de forma equivalente, por \(\sqrt N\).
La parte aparentemente costosa es \(q=\lfloor N/m\rfloor\). Sin embargo, ese cociente permanece constante en intervalos consecutivos de \(m\). Si un bloque empieza en \(L\), el cociente común es
$$q=\left\lfloor\frac{N}{L}\right\rfloor,$$
y el bloque termina en
$$R=\left\lfloor\frac{N}{q}\right\rfloor.$$
Por tanto todos los \(m\in[L,R]\) comparten el mismo valor de \(q\). La observación clásica es que \(\lfloor N/m\rfloor\) sólo toma \(O(\sqrt N)\) valores distintos; eso convierte una suma lineal imposible en un recorrido por bloques.
Como \(P_3\) es suma prefijo de \(P_2\), cada bloque puede evaluarse en tiempo constante.
Si el bloque cae por completo en la región \(m\le q\), entonces
$$\sum_{m=L}^{R} H_N(m)=\sum_{m=L}^{R}\bigl(P_2(m+q)+P_2(q-m)\bigr).$$
Aplicando la identidad de prefijos dos veces, obtenemos
$$\sum_{m=L}^{R} H_N(m)=P_3(R+q)-P_3(L+q-1)+P_3(q-L)-P_3(q-R-1).$$
Si el bloque cae por completo en la región \(m\gt q\), entonces
$$\sum_{m=L}^{R} H_N(m)=\sum_{m=L}^{R}\bigl(P_2(m+q)-P_2(m-q-1)\bigr),$$
y por tanto
$$\sum_{m=L}^{R} H_N(m)=P_3(R+q)-P_3(L+q-1)-P_3(R-q-1)+P_3(L-q-2).$$
Cada bloque de cociente queda completamente a un lado de la diagonal. Los bloques con \(m\le q\) son precisamente los del rango pequeño \(m\le \sqrt N\), y los bloques con \(m\gt q\) pertenecen al rango grande \(m\gt \sqrt N\). Por eso basta una sola elección de rama por bloque.
Primero calculamos el término base:
$$P_2(5)=56,\qquad P_2(6)=98,\qquad P_2(3)=15,\qquad P_1(5)=26,\qquad P_1(6)=42,$$
de donde
$$B(5)=56+98+15+26+42=237.$$
Ahora tratamos los bloques de cociente.
Para \(m=2\), \(q=\lfloor 5/2\rfloor=2\), así que estamos en el caso \(m\le q\):
$$H_5(2)=P_2(4)+P_2(0)=30+1=31.$$
Para \(m=3,4\), el cociente es \(q=1\). Es un único bloque con \(m\gt q\), \(L=3\) y \(R=4\):
$$\sum_{m=3}^{4} H_5(m)=P_3(5)-P_3(3)-P_3(2)+P_3(0).$$
Usando \(P_3(5)=112\), \(P_3(3)=26\), \(P_3(2)=11\) y \(P_3(0)=1\), resulta
$$\sum_{m=3}^{4} H_5(m)=112-26-11+1=76.$$
Por lo tanto
$$S(5)=237+31+76=344,$$
que coincide con la comprobación de la implementación. Una segunda comprobación es
$$S(100)=26709528.$$
Las implementaciones en C++, Python y Java siguen exactamente la misma estrategia. Evalúan una vez la parte base fija, y después recorren el resto del rango por bloques de cociente constante en lugar de hacerlo índice por índice. Para cada bloque calculan el cociente común, deducen el extremo del bloque y añaden la fórmula telescópica adecuada basada en diferencias de \(P_3\).
La suma se mantiene exacta durante todo el proceso. Sólo después de ensamblar el valor entero completo de \(S(N)\) se reduce módulo \(10^8\). Eso es necesario porque el recuento exacto para \(N=10^{12}\) es muchísimo mayor que el rango cómodo de los enteros máquina ordinarios.
El número de valores distintos de \(\lfloor N/m\rfloor\) es \(O(\sqrt N)\). Cada bloque requiere sólo un número constante de evaluaciones polinómicas y sumas o restas enteras, de modo que el tiempo total es
$$O(\sqrt N).$$
Salvo temporales de enteros de precisión arbitraria, la memoria adicional es \(O(1)\).
这道题来自一个由抛物线与直线围出的格点计数问题。按照实现中已经采用的几何化简，最后需要计算的是一个精确的算术计数函数 \(S(N)\)。Project Euler 真正要求的是 \(S(10^{12}) \bmod 10^8\)。
关键点在于，程序并不会逐个枚举格点。它使用的是一个闭式公式：先加上一部分固定的多项式贡献，再处理一个依赖于整除商的求和，并把相同整除商对应的连续区间合并成块。
化简后的计数公式建立在三个多项式前缀函数之上：
$$P_1(t)=\frac{(t^2-t+6)(t+1)}{6},$$
$$P_2(t)=\frac{(t^2-t+12)(t+1)(t+2)}{24},$$
$$P_3(t)=\frac{(t^2-t+20)(t+1)(t+2)(t+3)}{120}.$$
把它们展开，可以看出它们分别是三次、四次和五次多项式：
$$P_1(t)=\frac{t^3+5t+6}{6},\qquad P_2(t)=\frac{t^4+2t^3+11t^2+34t+24}{24},$$
$$P_3(t)=\frac{t^5+5t^4+25t^3+115t^2+214t+120}{120}.$$
真正有用的是它们的差分关系：
$$P_1(t)-P_1(t-1)=\frac{t(t-1)}{2}+1,$$
$$P_2(t)-P_2(t-1)=P_1(t),\qquad P_3(t)-P_3(t-1)=P_2(t).$$
也就是说，\(P_2\) 是 \(P_1\) 的前缀和，\(P_3\) 是 \(P_2\) 的前缀和。因此很长的区间和可以压缩成少数几个多项式值的差。
这些公式在若干负整数处还有方便的零点：
$$P_2(-1)=P_2(-2)=0,\qquad P_3(-1)=P_3(-2)=P_3(-3)=0.$$
这是因为 \(P_2\) 含有因子 \((t+1)(t+2)\)，而 \(P_3\) 含有因子 \((t+1)(t+2)(t+3)\)。于是即使某个区间端点在变形后略微落到零以下，望远镜求和公式仍然成立，不需要为这些边界再写额外分支。
去掉几何部分之后，精确计数写成
$$S(N)=B(N)+\sum_{m=2}^{N-1} H_N(m),$$
其中固定的基础项为
$$B(N)=P_2(N)+P_2(N+1)+P_2(N-2)+P_1(N)+P_1(N+1).$$
对剩余求和中的每个 \(m\)，定义
$$q=\left\lfloor\frac{N}{m}\right\rfloor.$$
对应的被加项是分段函数
$$H_N(m)= \begin{cases} P_2(m+q)+P_2(q-m), & m\le q,\\ P_2(m+q)-P_2(m-q-1), & m\gt q. \end{cases}$$
这正是 C++、Python 与 Java 实现所计算的精确算术内容。两段分别对应于对角线 \(m=q\) 两侧的两种情形，也等价于 \(\sqrt N\) 两侧的两种区域。
看上去最难处理的是 \(q=\lfloor N/m\rfloor\)，但它在连续的一段 \(m\) 上保持不变。若某个块从 \(L\) 开始，则公共商为
$$q=\left\lfloor\frac{N}{L}\right\rfloor,$$
块的右端点为
$$R=\left\lfloor\frac{N}{q}\right\rfloor.$$
于是所有 \(m\in[L,R]\) 都有相同的 \(q\)。经典结论是 \(\lfloor N/m\rfloor\) 只会取到 \(O(\sqrt N)\) 个不同值，因此原本线性的求和可以改写成按块处理。
由于 \(P_3\) 是 \(P_2\) 的前缀和，每个块都能用常数次计算完成。
如果整个块位于 \(m\le q\) 区域，那么
$$\sum_{m=L}^{R} H_N(m)=\sum_{m=L}^{R}\bigl(P_2(m+q)+P_2(q-m)\bigr).$$
两次使用前缀和关系可得
$$\sum_{m=L}^{R} H_N(m)=P_3(R+q)-P_3(L+q-1)+P_3(q-L)-P_3(q-R-1).$$
如果整个块位于 \(m\gt q\) 区域，那么
$$\sum_{m=L}^{R} H_N(m)=\sum_{m=L}^{R}\bigl(P_2(m+q)-P_2(m-q-1)\bigr),$$
从而
$$\sum_{m=L}^{R} H_N(m)=P_3(R+q)-P_3(L+q-1)-P_3(R-q-1)+P_3(L-q-2).$$
每个整除商块都会完整地落在对角线的一侧。满足 \(m\le q\) 的块恰好位于小参数区间 \(m\le \sqrt N\)，而满足 \(m\gt q\) 的块则位于大参数区间 \(m\gt \sqrt N\)。所以每个块只需选择一次分支公式即可。
先算基础项：
$$P_2(5)=56,\qquad P_2(6)=98,\qquad P_2(3)=15,\qquad P_1(5)=26,\qquad P_1(6)=42,$$
因此
$$B(5)=56+98+15+26+42=237.$$
然后处理整除商块。
当 \(m=2\) 时，\(q=\lfloor 5/2\rfloor=2\)，属于 \(m\le q\) 情形：
$$H_5(2)=P_2(4)+P_2(0)=30+1=31.$$
当 \(m=3,4\) 时，商都是 \(q=1\)。这是一个 \(m\gt q\) 的单独块，\(L=3\)、\(R=4\)：
$$\sum_{m=3}^{4} H_5(m)=P_3(5)-P_3(3)-P_3(2)+P_3(0).$$
代入 \(P_3(5)=112\)、\(P_3(3)=26\)、\(P_3(2)=11\)、\(P_3(0)=1\)，得到
$$\sum_{m=3}^{4} H_5(m)=112-26-11+1=76.$$
所以
$$S(5)=237+31+76=344,$$
这与实现中的校验值一致。第二个校验值是
$$S(100)=26709528.$$
C++、Python 和 Java 实现采用完全相同的策略。它们先一次性算出固定基础项，然后不再逐项扫描，而是按公共整除商相同的块来推进。对每个块，只需计算公共商、由此求出块终点，再套用相应的 \(P_3\) 差分公式即可。
整个过程中始终保持精确整数求和。只有在得到完整的 \(S(N)\) 后，才最后对 \(10^8\) 取模。这一点很重要，因为 \(N=10^{12}\) 时的精确值远远超出普通机器整数可以安全容纳的范围。
\(\lfloor N/m\rfloor\) 的不同取值个数为 \(O(\sqrt N)\)。每个块只需要常数次多项式求值以及整数加减，因此总时间复杂度为
$$O(\sqrt N).$$
除去任意精度整数临时量之外，额外空间复杂度为 \(O(1)\)。
Эта задача возникает из конфигурации решётчатых точек, связанной с параболой и прямой. После геометрического сведения, уже заложенного в реализации, остаётся вычислить точную арифметическую функцию подсчёта \(S(N)\). Для Project Euler требуется остаток \(S(10^{12})\) по модулю \(10^8\).
Главная идея в том, что реализация не перебирает точки по одной. Вместо этого используется замкнутая формула, состоящая из фиксированного полиномиального вклада и суммы, зависящей от целой части \(\lfloor N/m\rfloor\), причём одинаковые значения этого частного обрабатываются блоками.
Сведённая формула опирается на три полиномиальные префиксные функции:
$$P_1(t)=\frac{(t^2-t+6)(t+1)}{6},$$
$$P_2(t)=\frac{(t^2-t+12)(t+1)(t+2)}{24},$$
$$P_3(t)=\frac{(t^2-t+20)(t+1)(t+2)(t+3)}{120}.$$
После раскрытия скобок видно, что это полиномы степеней \(3\), \(4\) и \(5\):
$$P_1(t)=\frac{t^3+5t+6}{6},\qquad P_2(t)=\frac{t^4+2t^3+11t^2+34t+24}{24},$$
$$P_3(t)=\frac{t^5+5t^4+25t^3+115t^2+214t+120}{120}.$$
Для вычислений решающими являются разностные тождества:
$$P_1(t)-P_1(t-1)=\frac{t(t-1)}{2}+1,$$
$$P_2(t)-P_2(t-1)=P_1(t),\qquad P_3(t)-P_3(t-1)=P_2(t).$$
Значит, \(P_2\) является префиксной суммой для \(P_1\), а \(P_3\) является префиксной суммой для \(P_2\). Благодаря этому длинные диапазоны затем сворачиваются в разности нескольких полиномиальных значений.
У этих формул есть удобные нули при малых отрицательных значениях:
$$P_2(-1)=P_2(-2)=0,\qquad P_3(-1)=P_3(-2)=P_3(-3)=0.$$
Это напрямую следует из множителей \((t+1)(t+2)\) в \(P_2\) и \((t+1)(t+2)(t+3)\) в \(P_3\). Поэтому телескопические формулы остаются корректными даже тогда, когда после преобразования один из граничных индексов оказывается немного меньше нуля. Отдельных специальных случаев не требуется.
После устранения геометрической части точный счёт имеет вид
$$S(N)=B(N)+\sum_{m=2}^{N-1} H_N(m),$$
где фиксированный базовый вклад равен
$$B(N)=P_2(N)+P_2(N+1)+P_2(N-2)+P_1(N)+P_1(N+1).$$
Для каждого \(m\) в оставшейся сумме определим
$$q=\left\lfloor\frac{N}{m}\right\rfloor.$$
Тогда слагаемое задаётся по частям:
$$H_N(m)= \begin{cases} P_2(m+q)+P_2(q-m), & m\le q,\\ P_2(m+q)-P_2(m-q-1), & m\gt q. \end{cases}$$
Именно это арифметическое выражение вычисляют реализации на C++, Python и Java. Две ветви соответствуют двум режимам по разные стороны диагонали \(m=q\), то есть, что то же самое, по разные стороны точки порядка \(\sqrt N\).
Наиболее неприятным на вид является частное \(q=\lfloor N/m\rfloor\). Но оно постоянно на целых отрезках последовательных значений \(m\). Если блок начинается в точке \(L\), то общий для него частный равен
$$q=\left\lfloor\frac{N}{L}\right\rfloor,$$
а правая граница блока равна
$$R=\left\lfloor\frac{N}{q}\right\rfloor.$$
Следовательно, все \(m\in[L,R]\) имеют одно и то же значение \(q\). Классический факт состоит в том, что \(\lfloor N/m\rfloor\) принимает лишь \(O(\sqrt N)\) различных значений. Именно это превращает невозможную линейную сумму в обработку по блокам.
Поскольку \(P_3\) является префиксной суммой для \(P_2\), вклад каждого блока вычисляется за константное время.
Если весь блок лежит в области \(m\le q\), то
$$\sum_{m=L}^{R} H_N(m)=\sum_{m=L}^{R}\bigl(P_2(m+q)+P_2(q-m)\bigr).$$
Дважды применяя префиксное тождество, получаем
$$\sum_{m=L}^{R} H_N(m)=P_3(R+q)-P_3(L+q-1)+P_3(q-L)-P_3(q-R-1).$$
Если весь блок лежит в области \(m\gt q\), то
$$\sum_{m=L}^{R} H_N(m)=\sum_{m=L}^{R}\bigl(P_2(m+q)-P_2(m-q-1)\bigr),$$
и поэтому
$$\sum_{m=L}^{R} H_N(m)=P_3(R+q)-P_3(L+q-1)-P_3(R-q-1)+P_3(L-q-2).$$
Каждый блок частного целиком лежит по одну сторону диагонали. Блоки с \(m\le q\) находятся именно в малой области \(m\le \sqrt N\), а блоки с \(m\gt q\) лежат в большой области \(m\gt \sqrt N\). Поэтому для каждого блока достаточно одного выбора ветви.
Сначала вычислим базовый вклад:
$$P_2(5)=56,\qquad P_2(6)=98,\qquad P_2(3)=15,\qquad P_1(5)=26,\qquad P_1(6)=42,$$
откуда
$$B(5)=56+98+15+26+42=237.$$
Теперь переходим к блокам по частному.
Для \(m=2\) имеем \(q=\lfloor 5/2\rfloor=2\), значит это случай \(m\le q\):
$$H_5(2)=P_2(4)+P_2(0)=30+1=31.$$
Для \(m=3,4\) частное равно \(q=1\). Это один блок с \(m\gt q\), где \(L=3\), \(R=4\):
$$\sum_{m=3}^{4} H_5(m)=P_3(5)-P_3(3)-P_3(2)+P_3(0).$$
Подставляя \(P_3(5)=112\), \(P_3(3)=26\), \(P_3(2)=11\) и \(P_3(0)=1\), получаем
$$\sum_{m=3}^{4} H_5(m)=112-26-11+1=76.$$
Следовательно,
$$S(5)=237+31+76=344,$$
что совпадает с контрольным значением реализации. Второй контрольный результат:
$$S(100)=26709528.$$
Реализации на C++, Python и Java используют одну и ту же схему. Сначала один раз вычисляется фиксированный базовый вклад. Затем оставшийся диапазон обходится не по отдельным индексам, а по блокам постоянного целочисленного частного. Для каждого блока вычисляется общий частный, по нему определяется правая граница, после чего добавляется нужная телескопическая формула через разности \(P_3\).
Сумма всё время хранится точно. Только после сборки полного целого значения \(S(N)\) выполняется взятие по модулю \(10^8\). Это необходимо, потому что точный результат при \(N=10^{12}\) намного больше диапазона обычных машинных целых.
Число различных значений \(\lfloor N/m\rfloor\) равно \(O(\sqrt N)\). На каждый блок приходится лишь константное число вычислений полиномов и целочисленных сложений или вычитаний, поэтому общее время работы равно
$$O(\sqrt N).$$
Если не считать временных объектов произвольной точности, дополнительная память составляет \(O(1)\).
تنشأ هذه المسألة من عدّ نقاط شبكية مرتبطة بقطع مكافئ ومستقيم. بعد الاختزال الهندسي الذي تعتمد عليه الخوارزمية، يبقى لدينا حساب دالة عدّ حسابية دقيقة \(S(N)\). والمطلوب في Project Euler هو إيجاد \(S(10^{12}) \bmod 10^8\).
النقطة الأساسية أن التنفيذ لا يعدّ النقاط واحدةً واحدة. بدلاً من ذلك يستعمل صيغة مغلقة تتكوّن من جزء كثير حدود ثابت، ثم مجموع يعتمد على قيمة القسمة الأرضية ويُعالَج على شكل كتل تتشارك القيمة نفسها.
تعتمد الصيغة المختزلة على ثلاث دوال بادئة كثيرة الحدود:
$$P_1(t)=\frac{(t^2-t+6)(t+1)}{6},$$
$$P_2(t)=\frac{(t^2-t+12)(t+1)(t+2)}{24},$$
$$P_3(t)=\frac{(t^2-t+20)(t+1)(t+2)(t+3)}{120}.$$
وبعد التوسيع نرى أنها كثيرات حدود من الدرجات الثالثة والرابعة والخامسة:
$$P_1(t)=\frac{t^3+5t+6}{6},\qquad P_2(t)=\frac{t^4+2t^3+11t^2+34t+24}{24},$$
$$P_3(t)=\frac{t^5+5t^4+25t^3+115t^2+214t+120}{120}.$$
الأهم من ذلك هو علاقات الفروق المتتالية:
$$P_1(t)-P_1(t-1)=\frac{t(t-1)}{2}+1,$$
$$P_2(t)-P_2(t-1)=P_1(t),\qquad P_3(t)-P_3(t-1)=P_2(t).$$
إذن \(P_2\) هو مجموع بادئ لـ \(P_1\)، و\(P_3\) هو مجموع بادئ لـ \(P_2\). ولهذا يمكن ضغط المجاميع الطويلة إلى فروق بين عدد قليل من قيم كثيرات الحدود.
لهذه الصيغ أيضاً أصفار مفيدة عند بعض القيم السالبة الصغيرة:
$$P_2(-1)=P_2(-2)=0,\qquad P_3(-1)=P_3(-2)=P_3(-3)=0.$$
ويرجع ذلك مباشرة إلى العوامل \((t+1)(t+2)\) في \(P_2\) والعوامل \((t+1)(t+2)(t+3)\) في \(P_3\). لذلك تبقى صيغ التلسكوب صحيحة حتى لو هبط أحد طرفي المجال قليلاً تحت الصفر، ولا حاجة إلى معالجة خاصة عند تلك الحدود.
بعد التخلص من الجزء الهندسي يصبح العدّ الدقيق على الصورة
$$S(N)=B(N)+\sum_{m=2}^{N-1} H_N(m),$$
حيث إن الجزء الأساسي الثابت هو
$$B(N)=P_2(N)+P_2(N+1)+P_2(N-2)+P_1(N)+P_1(N+1).$$
ولكل \(m\) في المجموع المتبقي نعرّف
$$q=\left\lfloor\frac{N}{m}\right\rfloor.$$
وعندئذ يكون الحد
$$H_N(m)= \begin{cases} P_2(m+q)+P_2(q-m), & m\le q,\\ P_2(m+q)-P_2(m-q-1), & m\gt q. \end{cases}$$
وهذا هو تماماً المحتوى الحسابي الذي تنفذه حلول C++ وPython وJava. الفرعان يمثلان حالتين على جانبي القطر \(m=q\)، أو بصورة مكافئة على جانبي \(\sqrt N\).
الجزء الذي يبدو مكلفاً هو \(q=\lfloor N/m\rfloor\)، لكن هذه القيمة تبقى ثابتة على فترات متتالية من \(m\). إذا بدأت كتلة عند \(L\)، فإن القاسم المشترك لها هو
$$q=\left\lfloor\frac{N}{L}\right\rfloor,$$
وتنتهي الكتلة عند
$$R=\left\lfloor\frac{N}{q}\right\rfloor.$$
إذن كل \(m\in[L,R]\) يشارك القيمة نفسها لـ \(q\). والملاحظة القياسية هنا أن \(\lfloor N/m\rfloor\) لا يأخذ إلا \(O(\sqrt N)\) قيماً مختلفة، ولذلك يتحول الجمع من مسح خطي مستحيل إلى معالجة على مستوى الكتل.
بما أن \(P_3\) هو مجموع بادئ لـ \(P_2\)، فيمكن حساب كل كتلة بزمن ثابت.
إذا كانت الكتلة كلها تقع في المجال \(m\le q\)، فلدينا
$$\sum_{m=L}^{R} H_N(m)=\sum_{m=L}^{R}\bigl(P_2(m+q)+P_2(q-m)\bigr).$$
وباستخدام علاقة المجموع البادئ مرتين نحصل على
$$\sum_{m=L}^{R} H_N(m)=P_3(R+q)-P_3(L+q-1)+P_3(q-L)-P_3(q-R-1).$$
أما إذا كانت الكتلة كلها تقع في المجال \(m\gt q\)، فإن
$$\sum_{m=L}^{R} H_N(m)=\sum_{m=L}^{R}\bigl(P_2(m+q)-P_2(m-q-1)\bigr),$$
ومن ثم
$$\sum_{m=L}^{R} H_N(m)=P_3(R+q)-P_3(L+q-1)-P_3(R-q-1)+P_3(L-q-2).$$
كل كتلة من كتل القسمة تقع بالكامل على أحد جانبي القطر. الكتل التي تحقق \(m\le q\) هي بالضبط كتل المنطقة الصغيرة \(m\le \sqrt N\)، أما الكتل التي تحقق \(m\gt q\) فتقع في المنطقة الكبيرة \(m\gt \sqrt N\). لذلك يكفي اختيار فرع واحد لكل كتلة.
نحسب أولاً الجزء الأساسي:
$$P_2(5)=56,\qquad P_2(6)=98,\qquad P_2(3)=15,\qquad P_1(5)=26,\qquad P_1(6)=42,$$
ومن ثم
$$B(5)=56+98+15+26+42=237.$$
بعد ذلك نعالج كتل القسمة.
عند \(m=2\) يكون \(q=\lfloor 5/2\rfloor=2\)، أي إننا في حالة \(m\le q\):
$$H_5(2)=P_2(4)+P_2(0)=30+1=31.$$
وعند \(m=3,4\) تكون قيمة القسمة \(q=1\). وهذه كتلة واحدة من نوع \(m\gt q\) حيث \(L=3\) و\(R=4\):
$$\sum_{m=3}^{4} H_5(m)=P_3(5)-P_3(3)-P_3(2)+P_3(0).$$
وباستخدام \(P_3(5)=112\) و\(P_3(3)=26\) و\(P_3(2)=11\) و\(P_3(0)=1\) نجد
$$\sum_{m=3}^{4} H_5(m)=112-26-11+1=76.$$
إذن
$$S(5)=237+31+76=344,$$
وهو يطابق قيمة التحقق المستخدمة في التنفيذ. كما أن قيمة تحقق ثانية هي
$$S(100)=26709528.$$
تتبع تطبيقات C++ وPython وJava الإستراتيجية نفسها. فهي تحسب الجزء الأساسي الثابت مرة واحدة، ثم تمسح بقية المجال على شكل كتل ذات قسمة صحيحة مشتركة بدلاً من المرور على كل مؤشر على حدة. في كل كتلة تُحسب قيمة القسمة المشتركة، ومنها يُستنتج طرف الكتلة، ثم تُضاف صيغة الفروق المناسبة المبنية على \(P_3\).
يبقى المجموع دقيقاً طوال العملية. وبعد تركيب القيمة الصحيحة الكاملة لـ \(S(N)\) فقط، يُؤخذ الباقي بترديد \(10^8\). وهذا ضروري لأن القيمة الدقيقة عند \(N=10^{12}\) أكبر بكثير من المجال الذي تستوعبه الأعداد الصحيحة الآلية العادية.
عدد القيم المختلفة لـ \(\lfloor N/m\rfloor\) هو \(O(\sqrt N)\). وكل كتلة تحتاج فقط إلى عدد ثابت من تقييمات كثيرات الحدود مع بعض عمليات الجمع والطرح الصحيحة، لذلك يكون الزمن الكلي
$$O(\sqrt N).$$
أما الذاكرة الإضافية فهي \(O(1)\)، إذا استثنينا القيم المؤقتة ذات الدقة غير المحدودة.