We must sum \(a+b+c\) over all prime triples \((a,b,c)\) with \(a<b<c<n\) such that \(a+1\), \(b+1\), and \(c+1\) form a geometric progression. If we write
$$x=a+1,\qquad y=b+1,\qquad z=c+1,$$
then the defining condition is \(y^2=xz\). A naive search over all prime triples below \(n\) is infeasible for the real input, so the implementations enumerate the hidden arithmetic structure instead of scanning primes directly.
The key idea is to classify every valid triple by a common scale factor and a coprime pair that describes the geometric progression exactly.
Three positive numbers are in geometric progression exactly when the square of the middle term equals the product of the outer terms. Therefore
$$\frac{b+1}{a+1}=\frac{c+1}{b+1}\iff (b+1)^2=(a+1)(c+1).$$
With \(x=a+1\), \(y=b+1\), and \(z=c+1\), the problem becomes
$$y^2=xz,\qquad x<y<z.$$
So we no longer have to reason about geometric progressions directly; we only need a complete description of the positive integer solutions to \(y^2=xz\).
Let
$$d=\gcd(x,z),\qquad x=d r,\qquad z=d s,\qquad \gcd(r,s)=1.$$
Substituting into \(y^2=xz\) gives
$$y^2=d^2rs.$$
Hence \(rs\) must be a perfect square. Since \(r\) and \(s\) are coprime, each of them must already be a perfect square, so we may write
$$r=u^2,\qquad s=v^2,\qquad \gcd(u,v)=1.$$
Therefore every solution has the form
$$x=du^2,\qquad y=duv,\qquad z=dv^2,$$
and every positive choice of \(d,u,v\) with \(\gcd(u,v)=1\) satisfies \(y^2=xz\). Because \(x<z\), we only need \(u<v\).
Undoing the substitution yields
$$a=du^2-1,\qquad b=duv-1,\qquad c=dv^2-1.$$
Since \(u<v\), we automatically get
$$du^2<duv<dv^2,$$
so the ordering \(a<b<c\) is built into the parameterization. The coprimality condition \(\gcd(u,v)=1\) removes duplicate descriptions, which means each valid prime triple corresponds to one unique search state \((d,u,v)\).
If \(a\), \(b\), and \(c\) are all odd primes, then \(a+1\), \(b+1\), and \(c+1\) are all even, so \(x\), \(y\), and \(z\) are even. In the parameterization above that forces \(d\) to be even, because with odd \(d\) the coprime pair \(u,v\) cannot make all three numbers \(du^2\), \(duv\), and \(dv^2\) even.
Now suppose \(d\) is odd. Since \(b\) is a prime greater than \(2\), \(b+1=y\) is even, so \(uv\) must be even. Because \(\gcd(u,v)=1\), exactly one of \(u\) and \(v\) is even.
The largest prime \(c\) is also greater than \(2\), hence \(c+1=z\) must be even. Therefore \(v\) must be even and \(u\) must be odd. But then \(x=du^2\) is odd, so \(a=x-1\) is even. The only even prime is \(2\), so
$$a=2,\qquad x=a+1=3.$$
Thus
$$du^2=3,$$
which forces
$$u=1,\qquad d=3.$$
So the odd-\(d\) part of the search is not a general family at all: it is the single special branch
$$a=2,\qquad b=3v-1,\qquad c=3v^2-1,$$
with \(v\) even.
From the largest value we get
$$c=dv^2-1<n,$$
so, because everything is integral,
$$dv^2\le n,\qquad d\le \left\lfloor\frac{n}{v^2}\right\rfloor.$$
Since \(d\ge 1\), this also implies
$$v^2\le n,\qquad v\le \lfloor\sqrt{n}\rfloor.$$
Therefore the search can be organized as: loop over \(v\), loop over coprime \(u<v\), and then loop over all admissible scale factors \(d\). The main branch uses even \(d\); the only odd branch is \(d=3\), \(u=1\), \(v\) even.
The special odd branch already gives one valid triple. Taking
$$u=1,\qquad v=2,\qquad d=3$$
produces
$$a=2,\qquad b=5,\qquad c=11.$$
From the even branch, for example,
$$u=1,\qquad v=2,\qquad d=6\Rightarrow (a,b,c)=(5,11,23),$$
and
$$u=2,\qquad v=3,\qquad d=2\Rightarrow (a,b,c)=(7,11,17).$$
Continuing the enumeration below \(100\) gives exactly 11 triples:
\((2,5,11)\), \((2,11,47)\), \((5,11,23)\), \((5,17,53)\), \((7,11,17)\), \((7,23,71)\), \((11,23,47)\), \((17,23,31)\), \((17,41,97)\), \((31,47,71)\), \((71,83,97)\).
Their total is
$$18+60+39+75+35+101+81+71+155+149+251=1035,$$
which matches the checkpoint used by the implementation.
The C++, Python, and Java implementations all follow the same plan. First they build an odd-only prime table up to \(n\), so every primality test becomes a constant-time table lookup for odd numbers, plus one explicit check for \(2\).
Next they loop over \(v=2,3,\dots,\lfloor\sqrt{n}\rfloor\). For each \(v\), they compute \(v^2\) and the largest allowable scale factor \(\left\lfloor n/v^2 \right\rfloor\). Then they scan all \(u\) with \(1\le u<v\), keeping only the coprime pairs.
For each such pair, the implementation first checks the unique odd-\(d\) branch \(d=3\), \(u=1\), \(v\) even. After that it runs through all even values of \(d\) up to the bound, forms
$$a=du^2-1,\qquad b=duv-1,\qquad c=dv^2-1,$$
and adds \(a+b+c\) whenever all three numbers are prime.
The C++ implementation also performs two short internal validations before the full run: the known value \(S(100)=1035\), and a fast-versus-direct comparison at \(n=500\). The Python and Java implementations keep the same optimized search structure without the extra direct checker.
Building the odd-only sieve up to \(n\) costs \(O(n\log\log n)\) time and \(O(n)\) memory.
The search phase examines
$$\sum_{v\le \sqrt{n}}\sum_{\substack{1\le u<v\\ \gcd(u,v)=1}} O\!\left(\frac{n}{v^2}\right)$$
candidate scale factors, which is \(O(n\log n)\) overall. The gcd checks fit within the same order, so the enumeration is dominated by arithmetic generation rather than by primality testing. The full method therefore runs in \(O(n\log n)\) time and uses \(O(n)\) memory.
Gesucht ist die Summe aller Primzahl-Tripel \((a,b,c)\) mit \(a<b<c<n\), für die \(a+1\), \(b+1\) und \(c+1\) eine geometrische Folge bilden. Setzt man
$$x=a+1,\qquad y=b+1,\qquad z=c+1,$$
dann lautet die Bedingung \(y^2=xz\). Ein direkter Durchlauf über alle Primzahl-Tripel unter \(n\) ist für die echte Eingabe unbrauchbar, also zählt die Implementierung die zugrunde liegende Zahlentheorie statt die Primzahlen selbst.
Die zentrale Idee besteht darin, jedes gültige Tripel durch einen gemeinsamen Skalierungsfaktor und ein teilerfremdes Paar zu beschreiben, das die geometrische Folge eindeutig festlegt.
Drei positive Zahlen bilden genau dann eine geometrische Folge, wenn das Quadrat des mittleren Glieds gleich dem Produkt der äußeren Glieder ist. Also gilt
$$\frac{b+1}{a+1}=\frac{c+1}{b+1}\iff (b+1)^2=(a+1)(c+1).$$
Mit \(x=a+1\), \(y=b+1\) und \(z=c+1\) reduziert sich das Problem auf
$$y^2=xz,\qquad x<y<z.$$
Damit brauchen wir keine geometrischen Folgen mehr direkt zu behandeln; wir benötigen nur eine vollständige Beschreibung der positiven ganzzahligen Lösungen von \(y^2=xz\).
Setze
$$d=\gcd(x,z),\qquad x=d r,\qquad z=d s,\qquad \gcd(r,s)=1.$$
Aus \(y^2=xz\) folgt dann
$$y^2=d^2rs.$$
Also muss \(rs\) ein Quadrat sein. Da \(r\) und \(s\) teilerfremd sind, muss jeder Faktor für sich bereits ein Quadrat sein. Wir schreiben daher
$$r=u^2,\qquad s=v^2,\qquad \gcd(u,v)=1.$$
Somit hat jede Lösung die Form
$$x=du^2,\qquad y=duv,\qquad z=dv^2,$$
und umgekehrt erfüllt jede positive Wahl von \(d,u,v\) mit \(\gcd(u,v)=1\) automatisch \(y^2=xz\). Wegen \(x<z\) genügt \(u<v\).
Zurück in den ursprünglichen Variablen ergibt sich
$$a=du^2-1,\qquad b=duv-1,\qquad c=dv^2-1.$$
Aus \(u<v\) folgt sofort
$$du^2<duv<dv^2,$$
also ist die Reihenfolge \(a<b<c\) bereits in der Parametrisierung eingebaut. Die Bedingung \(\gcd(u,v)=1\) verhindert Mehrfachdarstellungen, daher entspricht jedes gültige Primzahl-Tripel genau einem Suchzustand \((d,u,v)\).
Sind \(a\), \(b\) und \(c\) alle ungerade Primzahlen, dann sind \(a+1\), \(b+1\) und \(c+1\) alle gerade, also \(x\), \(y\) und \(z\) gerade. In der Parametrisierung erzwingt das ein gerades \(d\), denn bei ungeradem \(d\) kann das teilerfremde Paar \(u,v\) die drei Werte \(du^2\), \(duv\) und \(dv^2\) nicht gleichzeitig alle gerade machen.
Nehmen wir nun an, \(d\) sei ungerade. Weil \(b\) eine Primzahl größer als \(2\) ist, ist \(b+1=y\) gerade, also muss \(uv\) gerade sein. Wegen \(\gcd(u,v)=1\) ist dann genau einer von \(u\) und \(v\) gerade.
Außerdem ist die größte Primzahl \(c\) ebenfalls größer als \(2\), also ist \(c+1=z\) gerade. Daher muss \(v\) gerade und \(u\) ungerade sein. Dann ist aber \(x=du^2\) ungerade, also \(a=x-1\) gerade. Die einzige gerade Primzahl ist \(2\), folglich
$$a=2,\qquad x=a+1=3.$$
Damit gilt
$$du^2=3,$$
und somit zwingend
$$u=1,\qquad d=3.$$
Der ungerade Teil der Suche ist also keine allgemeine Familie, sondern genau der Spezialfall
$$a=2,\qquad b=3v-1,\qquad c=3v^2-1,$$
mit geradem \(v\).
Aus dem größten Wert folgt
$$c=dv^2-1<n,$$
also wegen der Ganzzahligkeit
$$dv^2\le n,\qquad d\le \left\lfloor\frac{n}{v^2}\right\rfloor.$$
Da \(d\ge 1\), gilt außerdem
$$v^2\le n,\qquad v\le \lfloor\sqrt{n}\rfloor.$$
Die Suche lässt sich deshalb sauber organisieren: Schleife über \(v\), dann über teilerfremde \(u<v\), danach über alle zulässigen Skalierungsfaktoren \(d\). Im Hauptzweig ist \(d\) gerade; der einzige ungerade Zweig ist \(d=3\), \(u=1\), \(v\) gerade.
Der ungerade Spezialzweig liefert sofort ein gültiges Tripel. Für
$$u=1,\qquad v=2,\qquad d=3$$
erhält man
$$a=2,\qquad b=5,\qquad c=11.$$
Aus dem geraden Hauptzweig erhält man zum Beispiel
$$u=1,\qquad v=2,\qquad d=6\Rightarrow (a,b,c)=(5,11,23),$$
und
$$u=2,\qquad v=3,\qquad d=2\Rightarrow (a,b,c)=(7,11,17).$$
Setzt man die Enumeration unter \(100\) fort, entstehen genau 11 gültige Tripel:
\((2,5,11)\), \((2,11,47)\), \((5,11,23)\), \((5,17,53)\), \((7,11,17)\), \((7,23,71)\), \((11,23,47)\), \((17,23,31)\), \((17,41,97)\), \((31,47,71)\), \((71,83,97)\).
Ihre Summe ist
$$18+60+39+75+35+101+81+71+155+149+251=1035,$$
genau der Kontrollwert der Implementierung.
Die Implementierungen in C++, Python und Java verwenden alle dieselbe Struktur. Zuerst wird bis \(n\) eine Primtafel nur für ungerade Zahlen aufgebaut, sodass jede Primzahlprüfung für ungerade Kandidaten eine konstante Tabellenabfrage ist, plus einem expliziten Sonderfall für \(2\).
Danach läuft eine Schleife über \(v=2,3,\dots,\lfloor\sqrt{n}\rfloor\). Für jedes \(v\) werden \(v^2\) und der größte zulässige Skalierungsfaktor \(\left\lfloor n/v^2 \right\rfloor\) berechnet. Dann werden alle \(u\) mit \(1\le u<v\) durchlaufen, wobei nur teilerfremde Paare erhalten bleiben.
Für jedes solche Paar prüft die Implementierung zuerst den eindeutigen ungeraden Spezialzweig \(d=3\), \(u=1\), \(v\) gerade. Anschließend werden alle geraden Werte von \(d\) bis zur Schranke durchlaufen, und man bildet
$$a=du^2-1,\qquad b=duv-1,\qquad c=dv^2-1.$$
Sind alle drei Zahlen prim, wird \(a+b+c\) zum Gesamtergebnis addiert.
Die C++-Implementierung führt vor dem Vollaufbau außerdem zwei kurze interne Prüfungen aus: den bekannten Wert \(S(100)=1035\) sowie einen Vergleich zwischen schneller Methode und direkter Enumeration bei \(n=500\). Die Python- und Java-Implementierungen behalten dieselbe optimierte Suche ohne den zusätzlichen Direktvergleich.
Das Erzeugen des ungeraden Siebs bis \(n\) kostet \(O(n\log\log n)\) Zeit und \(O(n)\) Speicher.
Die Suchphase betrachtet
$$\sum_{v\le \sqrt{n}}\sum_{\substack{1\le u<v\\ \gcd(u,v)=1}} O\!\left(\frac{n}{v^2}\right)$$
zulässige Skalierungsfaktoren und liegt damit insgesamt bei \(O(n\log n)\). Die ggT-Prüfungen bleiben in derselben Größenordnung, sodass die Laufzeit von der arithmetischen Enumeration und nicht von den Primzahlabfragen dominiert wird. Insgesamt arbeitet das Verfahren also in \(O(n\log n)\) Zeit und \(O(n)\) Speicher.
Aranan şey, \(a<b<c<n\) koşulunu sağlayan asal üçlüler \((a,b,c)\) arasında \(a+1\), \(b+1\) ve \(c+1\) değerleri geometrik dizi oluşturanların toplamıdır. Şöyle yazalım:
$$x=a+1,\qquad y=b+1,\qquad z=c+1.$$
O zaman temel koşul \(y^2=xz\) olur. Gerçek giriş için tüm asal üçlüleri doğrudan taramak mümkün olmadığından, implementasyon asal sayıları değil bu eşitliğin arkasındaki aritmetik yapıyı enumerate eder.
Ana fikir, her geçerli üçlüyü ortak bir ölçek katsayısı ve geometrik diziyi belirleyen aralarında asal bir çift ile ifade etmektir.
Üç pozitif sayı geometrik dizideyse orta terimin karesi dış terimlerin çarpımına eşittir. Bu yüzden
$$\frac{b+1}{a+1}=\frac{c+1}{b+1}\iff (b+1)^2=(a+1)(c+1).$$
\(x=a+1\), \(y=b+1\), \(z=c+1\) tanımlarıyla problem
$$y^2=xz,\qquad x<y<z$$
biçimine iner. Böylece geometrik dizi fikrini doğrudan takip etmek yerine, \(y^2=xz\) eşitliğinin tüm pozitif tamsayı çözümlerini tarif etmemiz yeterlidir.
Şunu yazalım:
$$d=\gcd(x,z),\qquad x=dr,\qquad z=ds,\qquad \gcd(r,s)=1.$$
\(y^2=xz\) yerine koyunca
$$y^2=d^2rs$$
elde edilir. Buradan \(rs\)'nin tam kare olması gerekir. \(r\) ve \(s\) aralarında asal olduğundan her biri tek başına tam karedir; dolayısıyla
$$r=u^2,\qquad s=v^2,\qquad \gcd(u,v)=1$$
yazabiliriz. Böylece her çözüm
$$x=du^2,\qquad y=duv,\qquad z=dv^2$$
şeklindedir. Tersine, \(\gcd(u,v)=1\) olan her pozitif \(d,u,v\) seçimi de \(y^2=xz\) eşitliğini sağlar. \(x<z\) olduğundan \(u<v\) almak yeterlidir.
Orijinal asallara dönersek
$$a=du^2-1,\qquad b=duv-1,\qquad c=dv^2-1$$
olur. \(u<v\) olduğundan otomatik olarak
$$du^2<duv<dv^2$$
ve dolayısıyla \(a<b<c\) elde edilir. \(\gcd(u,v)=1\) şartı aynı üçlünün farklı şekillerde üretilmesini engeller; yani her geçerli asal üçlü tam olarak bir \((d,u,v)\) durumuna karşılık gelir.
Eğer \(a\), \(b\) ve \(c\) üçü de tek asal ise \(a+1\), \(b+1\), \(c+1\) üçü de çifttir; yani \(x\), \(y\), \(z\) çift olur. Bu parametreleştirmede \(d\)'nin de çift olmasını zorlar; çünkü \(d\) tekken aralarında asal \(u,v\) çifti, \(du^2\), \(duv\), \(dv^2\) değerlerinin üçünü birden çift yapamaz.
Şimdi \(d\)'nin tek olduğunu varsayalım. \(b\), \(2\)'den büyük bir asal olduğundan \(b+1=y\) çifttir; o halde \(uv\) çift olmalıdır. \(\gcd(u,v)=1\) olduğundan \(u\) ile \(v\)'den tam biri çifttir.
Ayrıca en büyük asal \(c\) de \(2\)'den büyüktür, dolayısıyla \(c+1=z\) çifttir. Bu da \(v\)'nin çift, \(u\)'nun tek olmasını zorlar. Böylece \(x=du^2\) tek olur ve \(a=x-1\) çift çıkar. Tek çift asal \(2\) olduğuna göre
$$a=2,\qquad x=a+1=3$$
olmalıdır. Demek ki
$$du^2=3$$
ve bu da zorunlu olarak
$$u=1,\qquad d=3$$
sonucunu verir. Yani tek \(d\) tarafı genel bir aile değildir; yalnızca
$$a=2,\qquad b=3v-1,\qquad c=3v^2-1$$
biçimindeki, \(v\) çift olan özel daldır.
En büyük terimden
$$c=dv^2-1<n$$
olduğuna göre, tamsayılık nedeniyle
$$dv^2\le n,\qquad d\le \left\lfloor\frac{n}{v^2}\right\rfloor$$
yazarız. \(d\ge 1\) olduğundan ayrıca
$$v^2\le n,\qquad v\le \lfloor\sqrt{n}\rfloor$$
elde edilir. Böylece arama doğal biçimde şu sırayla düzenlenir: önce \(v\), sonra \(u<v\) ve \(\gcd(u,v)=1\), sonra da uygun tüm \(d\) değerleri. Ana dalda yalnızca çift \(d\) dolaşılır; tek dal ise yalnızca \(d=3\), \(u=1\), \(v\) çift durumudur.
Özel tek dal hemen bir çözüm verir. Şu seçim için
$$u=1,\qquad v=2,\qquad d=3$$
şunu elde ederiz:
$$a=2,\qquad b=5,\qquad c=11.$$
Çift daldan örneğin
$$u=1,\qquad v=2,\qquad d=6\Rightarrow (a,b,c)=(5,11,23),$$
ve
$$u=2,\qquad v=3,\qquad d=2\Rightarrow (a,b,c)=(7,11,17)$$
gelir. \(100\) altında enumerate etmeye devam edilince tam 11 geçerli üçlü bulunur:
\((2,5,11)\), \((2,11,47)\), \((5,11,23)\), \((5,17,53)\), \((7,11,17)\), \((7,23,71)\), \((11,23,47)\), \((17,23,31)\), \((17,41,97)\), \((31,47,71)\), \((71,83,97)\).
Toplamları
$$18+60+39+75+35+101+81+71+155+149+251=1035$$
olur; bu da implementasyondaki kontrol değeriyle aynıdır.
C++, Python ve Java implementasyonları aynı akışı izler. Önce \(n\)'e kadar yalnızca tek sayıları tutan bir asal tablosu kurulur; böylece her asal testi tek adaylar için sabit zamanlı bir tablo sorgusuna, \(2\) için de tek bir özel kontrole dönüşür.
Daha sonra \(v=2,3,\dots,\lfloor\sqrt{n}\rfloor\) üzerinde dolaşılır. Her \(v\) için \(v^2\) ve izin verilen en büyük ölçek katsayısı \(\left\lfloor n/v^2 \right\rfloor\) hesaplanır. Sonra \(1\le u<v\) aralığındaki tüm değerler taranır ve sadece aralarında asal çiftler tutulur.
Her \((u,v)\) çifti için implementasyon önce tek \(d\) özel dalını, yani \(d=3\), \(u=1\), \(v\) çift durumunu kontrol eder. Ardından sınır içindeki tüm çift \(d\) değerleri için
$$a=du^2-1,\qquad b=duv-1,\qquad c=dv^2-1$$
hesaplanır; üçü de asalsa \(a+b+c\) toplamı sonuca eklenir.
C++ implementasyonu tam çalışmadan önce iki kısa iç doğrulama da yapar: bilinen \(S(100)=1035\) değeri ve \(n=500\) için hızlı yöntem ile doğrudan taramanın karşılaştırılması. Python ve Java implementasyonları aynı optimize taramayı, ek doğrudan denetleyici olmadan sürdürür.
\(n\)'e kadar tek-sayı tabanlı sieve kurmak \(O(n\log\log n)\) zaman ve \(O(n)\) bellek gerektirir.
Arama fazı
$$\sum_{v\le \sqrt{n}}\sum_{\substack{1\le u<v\\ \gcd(u,v)=1}} O\!\left(\frac{n}{v^2}\right)$$
adet aday ölçek katsayısını inceler; bunun toplamı \(O(n\log n)\)'dir. EBOB kontrolleri de aynı mertebede kalır. Dolayısıyla çalışma süresi asal sorgularından değil, aritmetik enumerasyondan baskın biçimde etkilenir. Toplam karmaşıklık \(O(n\log n)\) zaman ve \(O(n)\) bellektir.
Debemos sumar \(a+b+c\) sobre todas las ternas primas \((a,b,c)\) con \(a<b<c<n\) tales que \(a+1\), \(b+1\) y \(c+1\) formen una progresión geométrica. Si escribimos
$$x=a+1,\qquad y=b+1,\qquad z=c+1,$$
la condición central pasa a ser \(y^2=xz\). Para el valor real de \(n\), recorrer directamente todas las ternas de primos es inviable, así que la implementación enumera la estructura aritmética oculta del problema.
La idea clave es describir cada terna válida mediante un factor común de escala y un par coprimo que determina exactamente la progresión geométrica.
Tres números positivos están en progresión geométrica exactamente cuando el cuadrado del término central es igual al producto de los extremos. Por tanto,
$$\frac{b+1}{a+1}=\frac{c+1}{b+1}\iff (b+1)^2=(a+1)(c+1).$$
Con \(x=a+1\), \(y=b+1\) y \(z=c+1\), el problema se reduce a
$$y^2=xz,\qquad x<y<z.$$
Eso elimina la necesidad de trabajar directamente con razones geométricas: basta clasificar todas las soluciones enteras positivas de \(y^2=xz\).
Sea
$$d=\gcd(x,z),\qquad x=dr,\qquad z=ds,\qquad \gcd(r,s)=1.$$
Al sustituir en \(y^2=xz\) obtenemos
$$y^2=d^2rs.$$
De aquí se sigue que \(rs\) debe ser un cuadrado perfecto. Como \(r\) y \(s\) son coprimos, cada uno tiene que ser un cuadrado por separado, así que escribimos
$$r=u^2,\qquad s=v^2,\qquad \gcd(u,v)=1.$$
Entonces toda solución tiene la forma
$$x=du^2,\qquad y=duv,\qquad z=dv^2,$$
y, recíprocamente, cualquier elección positiva de \(d,u,v\) con \(\gcd(u,v)=1\) satisface \(y^2=xz\). Como \(x<z\), basta imponer \(u<v\).
Deshaciendo el cambio de variables llegamos a
$$a=du^2-1,\qquad b=duv-1,\qquad c=dv^2-1.$$
De \(u<v\) se deduce automáticamente
$$du^2<duv<dv^2,$$
de modo que el orden \(a<b<c\) ya está incorporado. La condición \(\gcd(u,v)=1\) evita descripciones repetidas, así que cada terna prima válida aparece una sola vez en la búsqueda.
Si \(a\), \(b\) y \(c\) son primos impares, entonces \(a+1\), \(b+1\) y \(c+1\) son todos pares, es decir, \(x\), \(y\) y \(z\) son pares. En la parametrización eso obliga a que \(d\) sea par, porque con \(d\) impar el par coprimo \(u,v\) no puede volver pares a \(du^2\), \(duv\) y \(dv^2\) al mismo tiempo.
Supongamos ahora que \(d\) es impar. Como \(b\) es un primo mayor que \(2\), \(b+1=y\) es par, así que \(uv\) debe ser par. Dado que \(\gcd(u,v)=1\), exactamente uno de \(u\) y \(v\) es par.
Además, el mayor primo \(c\) también es mayor que \(2\), luego \(c+1=z\) es par. Por tanto, \(v\) tiene que ser par y \(u\) impar. Entonces \(x=du^2\) es impar y \(a=x-1\) es par. El único primo par es \(2\), así que
$$a=2,\qquad x=a+1=3.$$
Eso implica
$$du^2=3,$$
y fuerza
$$u=1,\qquad d=3.$$
Por lo tanto, la parte de \(d\) impar no es una familia amplia: es solo la rama especial
$$a=2,\qquad b=3v-1,\qquad c=3v^2-1,$$
con \(v\) par.
Del valor mayor obtenemos
$$c=dv^2-1<n,$$
y, como todo es entero,
$$dv^2\le n,\qquad d\le \left\lfloor\frac{n}{v^2}\right\rfloor.$$
Puesto que \(d\ge 1\), también se cumple
$$v^2\le n,\qquad v\le \lfloor\sqrt{n}\rfloor.$$
Así, la búsqueda se organiza de manera natural: recorrer \(v\), luego los \(u<v\) coprimos con \(v\), y finalmente los factores de escala admisibles \(d\). La rama principal usa solo \(d\) pares; la rama impar se reduce al caso \(d=3\), \(u=1\), \(v\) par.
La rama especial impar ya produce una solución. Tomando
$$u=1,\qquad v=2,\qquad d=3$$
se obtiene
$$a=2,\qquad b=5,\qquad c=11.$$
De la rama par salen, por ejemplo,
$$u=1,\qquad v=2,\qquad d=6\Rightarrow (a,b,c)=(5,11,23),$$
y
$$u=2,\qquad v=3,\qquad d=2\Rightarrow (a,b,c)=(7,11,17).$$
Si continuamos la enumeración por debajo de \(100\), aparecen exactamente 11 ternas válidas:
\((2,5,11)\), \((2,11,47)\), \((5,11,23)\), \((5,17,53)\), \((7,11,17)\), \((7,23,71)\), \((11,23,47)\), \((17,23,31)\), \((17,41,97)\), \((31,47,71)\), \((71,83,97)\).
Su suma es
$$18+60+39+75+35+101+81+71+155+149+251=1035,$$
que coincide con el valor de comprobación de la implementación.
Las implementaciones en C++, Python y Java siguen el mismo esquema. Primero construyen una tabla de primalidad solo para números impares hasta \(n\), de modo que cada prueba de primalidad sea una consulta en tiempo constante para candidatos impares, más un caso especial para \(2\).
Después recorren \(v=2,3,\dots,\lfloor\sqrt{n}\rfloor\). Para cada \(v\), calculan \(v^2\) y el mayor factor de escala permitido \(\left\lfloor n/v^2 \right\rfloor\). Luego recorren todos los \(u\) con \(1\le u<v\), conservando solo los pares coprimos.
Para cada par \((u,v)\), la implementación comprueba primero la única rama impar, \(d=3\), \(u=1\), \(v\) par. Después recorre todos los valores pares de \(d\) hasta la cota, forma
$$a=du^2-1,\qquad b=duv-1,\qquad c=dv^2-1,$$
y suma \(a+b+c\) siempre que los tres números sean primos.
La implementación en C++ también realiza dos validaciones internas breves antes del cálculo completo: el valor conocido \(S(100)=1035\) y una comparación entre el método rápido y una enumeración directa en \(n=500\). Las versiones de Python y Java mantienen la misma búsqueda optimizada sin ese comprobador adicional.
Construir la criba de impares hasta \(n\) cuesta \(O(n\log\log n)\) tiempo y \(O(n)\) memoria.
La fase de búsqueda examina
$$\sum_{v\le \sqrt{n}}\sum_{\substack{1\le u<v\\ \gcd(u,v)=1}} O\!\left(\frac{n}{v^2}\right)$$
factores de escala candidatos, lo que da \(O(n\log n)\) en total. Las comprobaciones de gcd quedan dentro del mismo orden, así que el coste dominante es la enumeración aritmética y no las consultas de primalidad. El algoritmo completo usa por tanto \(O(n\log n)\) tiempo y \(O(n)\) memoria.
题目要求我们对所有满足 \(a<b<c<n\) 的素数三元组 \((a,b,c)\) 求和，其中 \(a+1\)、\(b+1\)、\(c+1\) 必须构成等比数列。设
$$x=a+1,\qquad y=b+1,\qquad z=c+1,$$
那么核心条件就是 \(y^2=xz\)。对于真实输入，直接枚举所有素数三元组完全不可行，因此实现不会直接搜索素数，而是先把这个等式背后的整数结构拆开。
关键思想是把每个合法三元组唯一写成“一个公共尺度因子”乘上“一个互素参数对”，这样等比条件就被转化成一个边界清晰的整数枚举问题。
三个正数构成等比数列，当且仅当中间项的平方等于两端项的乘积。因此有
$$\frac{b+1}{a+1}=\frac{c+1}{b+1}\iff (b+1)^2=(a+1)(c+1).$$
代入 \(x=a+1\)、\(y=b+1\)、\(z=c+1\) 后，问题变成
$$y^2=xz,\qquad x<y<z.$$
这样一来，我们不再直接讨论等比数列本身，而是转而寻找方程 \(y^2=xz\) 的所有正整数解。
先取
$$d=\gcd(x,z),\qquad x=dr,\qquad z=ds,\qquad \gcd(r,s)=1.$$
代回 \(y^2=xz\) 得到
$$y^2=d^2rs.$$
所以 \(rs\) 必须是完全平方数。由于 \(r\) 与 \(s\) 互素，一个经典结论是：若两个互素正整数的乘积是平方数，那么它们各自都必须是平方数。因此可以写成
$$r=u^2,\qquad s=v^2,\qquad \gcd(u,v)=1.$$
于是每个解都能表示为
$$x=du^2,\qquad y=duv,\qquad z=dv^2,$$
反过来，任意满足 \(\gcd(u,v)=1\) 的正整数 \(d,u,v\) 也都会自动满足 \(y^2=xz\)。再因为 \(x<z\)，所以只需要取 \(u<v\)。
把 \(x\)、\(y\)、\(z\) 还原回原题中的素数，就得到
$$a=du^2-1,\qquad b=duv-1,\qquad c=dv^2-1.$$
由于 \(u<v\)，自然有
$$du^2<duv<dv^2,$$
所以顺序 \(a<b<c\) 已经内嵌在参数化里。另一方面，\(\gcd(u,v)=1\) 保证了不会把同一个三元组用不同的参数重复表示。因此，每个合法素数三元组都恰好对应一个唯一的 \((d,u,v)\)。
如果 \(a\)、\(b\)、\(c\) 都是奇素数，那么 \(a+1\)、\(b+1\)、\(c+1\) 都是偶数，也就是 \(x\)、\(y\)、\(z\) 全部为偶数。在参数化
$$x=du^2,\qquad y=duv,\qquad z=dv^2$$
中，这会强迫 \(d\) 为偶数；因为若 \(d\) 为奇数，互素的 \(u,v\) 不可能让这三个量同时都是偶数。
现在假设 \(d\) 是奇数。由于中间素数 \(b>2\)，所以 \(b+1=y\) 必为偶数，于是 \(uv\) 必须是偶数。又因为 \(\gcd(u,v)=1\)，这说明 \(u\) 与 \(v\) 中恰好只有一个是偶数。
再看最大的素数 \(c\)。它也一定大于 \(2\)，所以 \(c+1=z\) 必须是偶数。这迫使 \(v\) 为偶数、\(u\) 为奇数。于是 \(x=du^2\) 为奇数，从而 \(a=x-1\) 是偶数。唯一的偶素数只能是 \(2\)，所以
$$a=2,\qquad x=a+1=3.$$
因此必须满足
$$du^2=3,$$
这只可能给出
$$u=1,\qquad d=3.$$
也就是说，奇数 \(d\) 不是一大类情况，而是唯一的特殊分支
$$a=2,\qquad b=3v-1,\qquad c=3v^2-1,$$
其中 \(v\) 必须为偶数。
由最大项可知
$$c=dv^2-1<n,$$
所以因为 \(d,v\) 都是整数，必有
$$dv^2\le n,\qquad d\le \left\lfloor\frac{n}{v^2}\right\rfloor.$$
又因为 \(d\ge 1\)，于是还能推出
$$v^2\le n,\qquad v\le \lfloor\sqrt{n}\rfloor.$$
这样整个搜索就有了清晰结构：先枚举 \(v\)，再枚举所有满足 \(1\le u<v\) 且 \(\gcd(u,v)=1\) 的 \(u\)，最后枚举允许的尺度因子 \(d\)。主分支只需要遍历偶数 \(d\)；奇数分支只剩下 \(d=3\)、\(u=1\)、\(v\) 为偶数这一种模式。
奇数分支立刻给出一个例子。取
$$u=1,\qquad v=2,\qquad d=3$$
就得到
$$a=2,\qquad b=5,\qquad c=11.$$
偶数分支中的两个例子是
$$u=1,\qquad v=2,\qquad d=6\Rightarrow (a,b,c)=(5,11,23),$$
以及
$$u=2,\qquad v=3,\qquad d=2\Rightarrow (a,b,c)=(7,11,17).$$
继续在 \(100\) 以内枚举，会得到恰好 11 组合法三元组：
\((2,5,11)\)、\((2,11,47)\)、\((5,11,23)\)、\((5,17,53)\)、\((7,11,17)\)、\((7,23,71)\)、\((11,23,47)\)、\((17,23,31)\)、\((17,41,97)\)、\((31,47,71)\)、\((71,83,97)\)。
它们的总和是
$$18+60+39+75+35+101+81+71+155+149+251=1035,$$
这与实现中的校验值完全一致。
C++、Python 和 Java 实现都遵循同一套结构。第一步是建立一个只存奇数的素性表，范围直到 \(n\)。这样对奇数候选的素性判断就是常数时间查表，再额外单独处理数字 \(2\)。
接着外层循环遍历 \(v=2,3,\dots,\lfloor\sqrt{n}\rfloor\)。对每个 \(v\)，先算出 \(v^2\) 以及允许的最大尺度因子 \(\left\lfloor n/v^2 \right\rfloor\)。然后遍历所有 \(1\le u<v\) 的整数，只保留与 \(v\) 互素的那些。
对于每个互素参数对 \((u,v)\)，实现会先检查唯一的奇数分支：\(d=3\)、\(u=1\)、\(v\) 为偶数。之后再遍历所有不超过上界的偶数 \(d\)，并构造
$$a=du^2-1,\qquad b=duv-1,\qquad c=dv^2-1.$$
只要三者都为素数，就把 \(a+b+c\) 累加到答案中。
C++ 实现还会在正式计算前做两个很短的内部验证：已知值 \(S(100)=1035\)，以及在 \(n=500\) 处把快速方法与直接枚举做一次对照。Python 和 Java 实现保留了同样的优化搜索框架，但没有附带这个直接校验器。
构造到 \(n\) 为止的奇数筛需要 \(O(n\log\log n)\) 时间和 \(O(n)\) 空间。
枚举阶段检查的尺度因子个数满足
$$\sum_{v\le \sqrt{n}}\sum_{\substack{1\le u<v\\ \gcd(u,v)=1}} O\!\left(\frac{n}{v^2}\right),$$
其总量为 \(O(n\log n)\)。gcd 检查不会改变这个主数量级，因此程序的主要开销来自参数枚举，而不是素性测试。整体算法的时间复杂度是 \(O(n\log n)\)，空间复杂度是 \(O(n)\)。
Нужно просуммировать \(a+b+c\) по всем простым тройкам \((a,b,c)\), для которых \(a<b<c<n\) и числа \(a+1\), \(b+1\), \(c+1\) образуют геометрическую прогрессию. Если обозначить
$$x=a+1,\qquad y=b+1,\qquad z=c+1,$$
то основное условие превращается в \(y^2=xz\). Полный перебор всех простых троек до реального предела невозможен, поэтому реализация перечисляет не сами простые числа, а скрытую арифметическую структуру задачи.
Ключевая идея состоит в том, чтобы однозначно кодировать каждую допустимую тройку общим множителем и взаимно простым параметрическим парным набором.
Три положительных числа образуют геометрическую прогрессию тогда и только тогда, когда квадрат среднего равен произведению крайних. Поэтому
$$\frac{b+1}{a+1}=\frac{c+1}{b+1}\iff (b+1)^2=(a+1)(c+1).$$
После замены \(x=a+1\), \(y=b+1\), \(z=c+1\) задача становится такой:
$$y^2=xz,\qquad x<y<z.$$
Значит, вместо прямой работы с прогрессией достаточно описать все положительные целочисленные решения уравнения \(y^2=xz\).
Положим
$$d=\gcd(x,z),\qquad x=dr,\qquad z=ds,\qquad \gcd(r,s)=1.$$
Подстановка в \(y^2=xz\) дает
$$y^2=d^2rs.$$
Следовательно, \(rs\) должно быть полным квадратом. Поскольку \(r\) и \(s\) взаимно просты, каждый из них сам обязан быть квадратом, то есть
$$r=u^2,\qquad s=v^2,\qquad \gcd(u,v)=1.$$
Отсюда любое решение имеет вид
$$x=du^2,\qquad y=duv,\qquad z=dv^2,$$
и, наоборот, любая положительная тройка \(d,u,v\) с \(\gcd(u,v)=1\) автоматически удовлетворяет \(y^2=xz\). Из-за \(x<z\) достаточно брать \(u<v\).
Возвращаясь к \(a\), \(b\), \(c\), получаем
$$a=du^2-1,\qquad b=duv-1,\qquad c=dv^2-1.$$
Из \(u<v\) сразу следует
$$du^2<duv<dv^2,$$
поэтому порядок \(a<b<c\) встроен в параметризацию. Условие \(\gcd(u,v)=1\) устраняет повторные представления, так что каждая допустимая простая тройка появляется в поиске ровно один раз.
Если \(a\), \(b\), \(c\) — все нечетные простые, то \(a+1\), \(b+1\), \(c+1\) — четные, то есть \(x\), \(y\), \(z\) все четны. В параметризации это означает, что \(d\) обязан быть четным: при нечетном \(d\) взаимно простые \(u,v\) не смогут сделать одновременно четными \(du^2\), \(duv\) и \(dv^2\).
Предположим теперь, что \(d\) нечетно. Так как \(b>2\) и является простым, число \(b+1=y\) четно, значит \(uv\) должно быть четным. Из \(\gcd(u,v)=1\) следует, что четным является ровно одно из чисел \(u\) и \(v\).
Максимальный простой \(c\) тоже больше \(2\), поэтому \(c+1=z\) обязано быть четным. Следовательно, \(v\) должно быть четным, а \(u\) — нечетным. Тогда \(x=du^2\) нечетно, а значит \(a=x-1\) четно. Единственный четный простой — это \(2\), поэтому
$$a=2,\qquad x=a+1=3.$$
Получаем
$$du^2=3,$$
что возможно только при
$$u=1,\qquad d=3.$$
Итак, нечетный \(d\) не образует широкую семью: это единственная специальная ветвь
$$a=2,\qquad b=3v-1,\qquad c=3v^2-1,$$
где \(v\) четно.
Из максимального элемента следует
$$c=dv^2-1<n,$$
а значит, так как все величины целые,
$$dv^2\le n,\qquad d\le \left\lfloor\frac{n}{v^2}\right\rfloor.$$
Поскольку \(d\ge 1\), дополнительно получаем
$$v^2\le n,\qquad v\le \lfloor\sqrt{n}\rfloor.$$
Тем самым поиск удобно организуется так: сначала перебор \(v\), затем всех \(u<v\), взаимно простых с \(v\), и потом всех допустимых масштабов \(d\). В основной ветви рассматриваются только четные \(d\); вся нечетная часть сжимается до случая \(d=3\), \(u=1\), \(v\) четно.
Специальная нечетная ветвь сразу дает один пример. При
$$u=1,\qquad v=2,\qquad d=3$$
получаем
$$a=2,\qquad b=5,\qquad c=11.$$
Из четной ветви, например, выходят
$$u=1,\qquad v=2,\qquad d=6\Rightarrow (a,b,c)=(5,11,23),$$
и
$$u=2,\qquad v=3,\qquad d=2\Rightarrow (a,b,c)=(7,11,17).$$
Если продолжить перечисление ниже \(100\), получится ровно 11 допустимых троек:
\((2,5,11)\), \((2,11,47)\), \((5,11,23)\), \((5,17,53)\), \((7,11,17)\), \((7,23,71)\), \((11,23,47)\), \((17,23,31)\), \((17,41,97)\), \((31,47,71)\), \((71,83,97)\).
Их сумма равна
$$18+60+39+75+35+101+81+71+155+149+251=1035,$$
что совпадает с контрольным значением реализации.
Реализации на C++, Python и Java используют одну и ту же схему. Сначала строится таблица простоты только для нечетных чисел до \(n\), так что проверка простоты для любого нечетного кандидата становится константным обращением к таблице, плюс отдельный случай для числа \(2\).
Далее внешний цикл идет по \(v=2,3,\dots,\lfloor\sqrt{n}\rfloor\). Для каждого \(v\) вычисляются \(v^2\) и максимальный допустимый масштаб \(\left\lfloor n/v^2 \right\rfloor\). Затем перебираются все \(u\) с \(1\le u<v\), и сохраняются только взаимно простые пары.
Для каждой пары \((u,v)\) код сначала проверяет единственную нечетную ветвь \(d=3\), \(u=1\), \(v\) четно. После этого он проходит по всем четным значениям \(d\) до границы и формирует
$$a=du^2-1,\qquad b=duv-1,\qquad c=dv^2-1.$$
Если все три числа простые, к ответу прибавляется \(a+b+c\).
В реализации на C++ перед полным запуском есть еще две короткие внутренние проверки: известное значение \(S(100)=1035\) и сравнение быстрой схемы с прямым перебором при \(n=500\). Варианты на Python и Java используют ту же оптимизированную структуру без дополнительного прямого проверяющего блока.
Построение решета по нечетным числам до \(n\) требует \(O(n\log\log n)\) времени и \(O(n)\) памяти.
Фаза поиска проверяет
$$\sum_{v\le \sqrt{n}}\sum_{\substack{1\le u<v\\ \gcd(u,v)=1}} O\!\left(\frac{n}{v^2}\right)$$
масштабных множителей-кандидатов, что в сумме дает \(O(n\log n)\). Проверки gcd остаются в том же порядке, поэтому доминирует именно арифметическое перечисление, а не тесты на простоту. В итоге весь метод работает за \(O(n\log n)\) времени и использует \(O(n)\) памяти.
نريد حساب مجموع \(a+b+c\) على جميع الثلاثيات الأولية \((a,b,c)\) التي تحقق \(a<b<c<n\)، مع الشرط أن تكون القيم \(a+1\) و\(b+1\) و\(c+1\) في متتالية هندسية. إذا كتبنا
$$x=a+1,\qquad y=b+1,\qquad z=c+1,$$
فإن الشرط الأساسي يصبح \(y^2=xz\). ومن الواضح أن تعداد جميع الثلاثيات الأولية مباشرةً حتى الحد الحقيقي للمسألة غير عملي، لذلك تعتمد التطبيقات على إعادة صياغة البنية العددية الكامنة بدلًا من فحص جميع الأعداد الأولية الممكنة.
الفكرة الأساسية هي تمثيل كل ثلاثية صالحة بطريقة وحيدة باستخدام عامل قياس مشترك وزوج من المعلمات المتباينتين نسبيًا، بحيث تصير المتتالية الهندسية موصوفة بشكل صريح.
ثلاثة أعداد موجبة تكون في متتالية هندسية إذا وفقط إذا كان مربع الحد الأوسط مساويًا لحاصل ضرب الحدين الطرفيين. ولذلك
$$\frac{b+1}{a+1}=\frac{c+1}{b+1}\iff (b+1)^2=(a+1)(c+1).$$
وباستعمال \(x=a+1\) و\(y=b+1\) و\(z=c+1\)، تصبح المسألة
$$y^2=xz,\qquad x<y<z.$$
وهكذا لا نحتاج إلى التعامل مع النسبة الهندسية مباشرة، بل يكفي أن نصف جميع الحلول الصحيحة الموجبة للمعادلة \(y^2=xz\).
لنأخذ
$$d=\gcd(x,z),\qquad x=dr,\qquad z=ds,\qquad \gcd(r,s)=1.$$
بالتعويض في \(y^2=xz\) نحصل على
$$y^2=d^2rs.$$
إذن لا بد أن يكون \(rs\) مربعًا كاملًا. وبما أن \(r\) و\(s\) متباينان نسبيًا، فإن كلًا منهما يجب أن يكون مربعًا كاملًا بحد ذاته، فنكتب
$$r=u^2,\qquad s=v^2,\qquad \gcd(u,v)=1.$$
ومن ثم يكون كل حل على الصورة
$$x=du^2,\qquad y=duv,\qquad z=dv^2,$$
وبالعكس فإن أي اختيار موجب لـ \(d,u,v\) مع \(\gcd(u,v)=1\) يحقق تلقائيًا العلاقة \(y^2=xz\). ولأن \(x<z\)، يكفي أن نفرض \(u<v\).
بالعودة إلى \(a,b,c\) نحصل على
$$a=du^2-1,\qquad b=duv-1,\qquad c=dv^2-1.$$
ومن الشرط \(u<v\) ينتج مباشرة
$$du^2<duv<dv^2,$$
ولذلك فإن الترتيب \(a<b<c\) مضمَّن داخل البارامتريّة نفسها. كما أن الشرط \(\gcd(u,v)=1\) يمنع تكرار الوصف، فتظهر كل ثلاثية أولية صالحة مرة واحدة فقط في عملية البحث.
إذا كانت \(a\) و\(b\) و\(c\) جميعها أعدادًا أولية فردية، فإن \(a+1\) و\(b+1\) و\(c+1\) كلها أعداد زوجية، أي إن \(x\) و\(y\) و\(z\) زوجية. وفي البارامتريّة السابقة يفرض ذلك أن يكون \(d\) زوجيًا، لأنه عند \(d\) الفردي لا يمكن للزوج المتباين نسبيًا \(u,v\) أن يجعل \(du^2\) و\(duv\) و\(dv^2\) كلها زوجية في الوقت نفسه.
افترض الآن أن \(d\) فردي. بما أن \(b\) عدد أولي أكبر من \(2\)، فإن \(b+1=y\) عدد زوجي، وهذا يفرض أن يكون \(uv\) زوجيًا. ومع \(\gcd(u,v)=1\) فهذا يعني أن واحدًا فقط من \(u\) و\(v\) هو الزوجي.
ومن جهة أخرى فإن \(c\) أيضًا أولي أكبر من \(2\)، ولذلك يجب أن يكون \(c+1=z\) زوجيًا. ومن ثم لا بد أن يكون \(v\) زوجيًا و\(u\) فرديًا. عندها يصبح \(x=du^2\) فرديًا، وبالتالي يكون \(a=x-1\) زوجيًا. والعدد الأولي الزوجي الوحيد هو \(2\)، لذا
$$a=2,\qquad x=a+1=3.$$
وعليه لا بد من تحقق
$$du^2=3,$$
وهذا لا يترك إلا الاحتمال
$$u=1,\qquad d=3.$$
إذن الجزء الفردي من \(d\) ليس عائلة عامة، بل هو الفرع الخاص الوحيد
$$a=2,\qquad b=3v-1,\qquad c=3v^2-1,$$
مع \(v\) زوجي.
من أكبر حد نحصل على
$$c=dv^2-1<n,$$
ولأن جميع الكميات صحيحة، فإن ذلك يكافئ
$$dv^2\le n,\qquad d\le \left\lfloor\frac{n}{v^2}\right\rfloor.$$
وبما أن \(d\ge 1\)، ينتج أيضًا
$$v^2\le n,\qquad v\le \lfloor\sqrt{n}\rfloor.$$
وهكذا يمكن ترتيب البحث على نحو طبيعي: أولًا المرور على \(v\)، ثم على كل \(u<v\) مع \(\gcd(u,v)=1\)، ثم على جميع قيم \(d\) المسموح بها. الفرع الرئيسي يستعمل القيم الزوجية لـ \(d\)، أما الفرع الفردي فينحصر تمامًا في الحالة \(d=3\)، \(u=1\)، و\(v\) زوجي.
الفرع الخاص الفردي يعطي حلًا مباشرًا. عند
$$u=1,\qquad v=2,\qquad d=3$$
نحصل على
$$a=2,\qquad b=5,\qquad c=11.$$
ومن الفرع الزوجي نحصل مثلًا على
$$u=1,\qquad v=2,\qquad d=6\Rightarrow (a,b,c)=(5,11,23),$$
وكذلك
$$u=2,\qquad v=3,\qquad d=2\Rightarrow (a,b,c)=(7,11,17).$$
وبمتابعة التعداد تحت \(100\) نحصل على 11 ثلاثية صالحة بالضبط:
\((2,5,11)\)، \((2,11,47)\)، \((5,11,23)\)، \((5,17,53)\)، \((7,11,17)\)، \((7,23,71)\)، \((11,23,47)\)، \((17,23,31)\)، \((17,41,97)\)، \((31,47,71)\)، \((71,83,97)\).
ومجموعها هو
$$18+60+39+75+35+101+81+71+155+149+251=1035,$$
وهو نفس مقدار التحقق المستخدم في التنفيذ.
تتبع تطبيقات C++ وPython وJava البنية نفسها. أولًا تُبنى بنية أولية للأعداد الفردية فقط حتى \(n\)، بحيث تصبح كل عملية فحص للأولية بالنسبة للمرشحات الفردية مجرد استعلام ثابت الزمن، مع معالجة خاصة وحيدة للعدد \(2\).
بعد ذلك يدور البرنامج على \(v=2,3,\dots,\lfloor\sqrt{n}\rfloor\). ولكل قيمة من \(v\) يحسب \(v^2\) وأكبر عامل قياس مسموح به وهو \(\left\lfloor n/v^2 \right\rfloor\). ثم يمر على جميع \(u\) التي تحقق \(1\le u<v\)، ويحتفظ فقط بالأزواج المتباينة نسبيًا.
لكل زوج \((u,v)\)، يفحص التنفيذ أولًا الفرع الفردي الوحيد: \(d=3\)، \(u=1\)، و\(v\) زوجي. بعد ذلك يمر على جميع القيم الزوجية لـ \(d\) حتى الحد الأعلى، ويشكّل
$$a=du^2-1,\qquad b=duv-1,\qquad c=dv^2-1.$$
فإذا كانت القيم الثلاث أولية، أضيف \(a+b+c\) إلى المجموع.
كما أن تنفيذ C++ يجري قبل التشغيل الكامل تحققين داخليين قصيرين: القيمة المعروفة \(S(100)=1035\)، ومقارنة بين الطريقة السريعة وتعداد مباشر عند \(n=500\). أما تنفيذا Python وJava فيحتفظان بالبنية المحسنة نفسها من دون ذلك الفاحص المباشر الإضافي.
بناء الغربال الفردي حتى \(n\) يكلف \(O(n\log\log n)\) زمنًا و\(O(n)\) ذاكرة.
أما مرحلة البحث فتفحص عددًا من عوامل القياس المرشحة يساوي رتبيًا
$$\sum_{v\le \sqrt{n}}\sum_{\substack{1\le u<v\\ \gcd(u,v)=1}} O\!\left(\frac{n}{v^2}\right),$$
وهو ما يعطي \(O(n\log n)\) إجمالًا. كما أن فحوص \(\gcd\) تبقى ضمن الرتبة نفسها، لذلك تهيمن عملية التعداد الحسابي على زمن التنفيذ، لا اختبارات الأولية. وبالتالي فإن الخوارزمية الكاملة تعمل في \(O(n\log n)\) زمنًا وتستخدم \(O(n)\) ذاكرة.