For a given bound \(n\), we sum \(p+q\) over all triples of positive integers \((p,q,r)\) satisfying
$$q > p > r,\qquad pr \equiv 1 \pmod q,\qquad qr \equiv 1 \pmod p,\qquad p \le n.$$
A naive search over all triples is far too expensive. The key observation is that, once \(r\) is fixed, every valid pair \((p,q)\) comes from a divisor of \(r^2-1\), so the problem becomes a structured divisor-enumeration task instead of a three-dimensional brute-force scan.
Let \(S(n)\) denote the required total:
$$S(n)=\sum (p+q),$$
where the sum ranges over all triples \((p,q,r)\) satisfying the conditions above. The derivation below explains why the implementations only need to loop over \(r\) and divisors of \(r^2-1\).
Because \(pr \equiv 1 \pmod q\), there is an integer \(a\) such that
$$pr-1=aq.$$
Likewise, from \(qr \equiv 1 \pmod p\), there is an integer \(b\) with
$$qr-1=bp.$$
Since \(q>r\), we have
$$0 \le a=\frac{pr-1}{q} < p.$$
Reduce the first equation modulo \(p\). Because \(qr \equiv 1 \pmod p\), the number \(q\) is the inverse of \(r\) modulo \(p\). Multiplying \(pr-1=aq\) by \(r\) modulo \(p\) gives
$$-r \equiv aqr \equiv a \pmod p.$$
The unique integer in \([0,p-1]\) congruent to \(-r\) modulo \(p\) is \(p-r\), so
$$a=p-r.$$
Therefore
$$pr-1=(p-r)q,\qquad q=\frac{pr-1}{p-r}.$$
By symmetry, the second congruence yields
$$qr-1=(q-r)p,\qquad p=\frac{qr-1}{q-r}.$$
Set
$$d=p-r,\qquad e=q-r,$$
so that
$$p=r+d,\qquad q=r+e,\qquad d>0,\ e>0.$$
Insert \(p=r+d\) into the formula for \(q\):
$$q=\frac{(r+d)r-1}{d}=r+\frac{r^2-1}{d}.$$
Hence
$$e=\frac{r^2-1}{d},\qquad de=r^2-1.$$
This is the core reduction. For a fixed \(r\), every valid triple corresponds to a factor pair of \(r^2-1\).
The condition \(p \le n\) becomes
$$r+d \le n,\qquad d \le n-r.$$
The ordering \(q>p\) is equivalent to \(e>d\). Since \(de=r^2-1\), this means
$$d^2 < r^2-1.$$
For integers \(r \ge 2\), that is equivalent to
$$d \le r-1.$$
So the admissible divisors are exactly those satisfying
$$1 \le d \le m_r,\qquad m_r=\min(r-1,n-r),\qquad d \mid (r^2-1).$$
Once such a divisor is chosen, the corresponding pair is forced:
$$p=r+d,\qquad q=r+\frac{r^2-1}{d}.$$
The reduction is not just necessary; it is exact. Suppose \(r \ge 2\) and \(d\) is a divisor of \(r^2-1\) with \(1 \le d \le m_r\). Define
$$e=\frac{r^2-1}{d},\qquad p=r+d,\qquad q=r+e.$$
Then
$$pr-1=r(r+d)-1=r^2+rd-1=d(r+e)=dq=(p-r)q,$$
so \(pr \equiv 1 \pmod q\). Similarly,
$$qr-1=r(r+e)-1=r^2+re-1=e(r+d)=ep=(q-r)p,$$
so \(qr \equiv 1 \pmod p\). The bound \(d \le n-r\) guarantees \(p \le n\), and \(d \le r-1\) guarantees \(q>p\). Therefore every admissible divisor produces one valid triple, and every valid triple produces one admissible divisor. This is a bijection.
For a fixed \(r\), each valid divisor contributes
$$p+q=(r+d)+\left(r+\frac{r^2-1}{d}\right)=2r+d+\frac{r^2-1}{d}.$$
Thus
$$S(n)=\sum_{r=2}^{n-1}\ \sum_{d \mid (r^2-1),\ 1 \le d \le m_r}\left(2r+d+\frac{r^2-1}{d}\right),$$
where \(m_r=\min(r-1,n-r)\). This is exactly the quantity computed by the implementations.
Only \(r=2,3,4\) can contribute.
For \(r=2\), we have \(r^2-1=3\) and \(m_r=\min(1,3)=1\). The only admissible divisor is \(d=1\), giving
$$p=2+1=3,\qquad q=2+\frac{3}{1}=5,$$
so the contribution is \(3+5=8\).
For \(r=3\), we have \(r^2-1=8\) and \(m_r=\min(2,2)=2\). The admissible divisors are \(d=1,2\):
$$d=1 \Rightarrow (p,q)=(4,11),\quad p+q=15,$$
$$d=2 \Rightarrow (p,q)=(5,7),\quad p+q=12.$$
For \(r=4\), we have \(r^2-1=15\) and \(m_r=\min(3,1)=1\). Only \(d=1\) is allowed, producing
$$ (p,q)=(5,19),\quad p+q=24. $$
Adding everything gives
$$S(5)=8+15+12+24=59.$$
The C++, Python, and Java implementations all follow the same structure. They begin by building a smallest-prime-factor table up to slightly above \(n\). That allows fast factorizations of \(r-1\) and \(r+1\) for every \(r\).
For each \(r\) from \(2\) to \(n-1\), the implementation computes \(m_r=\min(r-1,n-r)\). If \(m_r \le 0\), that \(r\) cannot contribute. Otherwise, it factors \(r-1\) and \(r+1\), merges the prime exponents, and thereby obtains the prime factorization of
$$r^2-1=(r-1)(r+1).$$
Next, it recursively enumerates divisors from that factorization. During this search, branches are pruned as soon as the partial divisor already exceeds \(m_r\), because such a divisor cannot yield a valid \(p\).
Whenever a complete admissible divisor \(d\) is produced, the implementation computes
$$p=r+d,\qquad q=r+\frac{r^2-1}{d},$$
and adds \(p+q\) to the running total. The whole algorithm is therefore a careful divisor-generation procedure driven by the exact bijection proved above.
Building the smallest-prime-factor table costs \(O(n\log\log n)\) time and \(O(n)\) memory. For each \(r\), factoring \(r-1\) and \(r+1\) is fast because the factorization follows the precomputed table. The dominant work is enumerating admissible divisors of \(r^2-1\), so the total running time is well described by
$$O\!\left(n\log\log n+\sum_{r=2}^{n-1}\tau(r^2-1)\right),$$
up to the usual small-factor savings from pruning divisors larger than \(m_r\). In practice, this is dramatically smaller than brute-force enumeration over all candidate triples.
Für eine gegebene Schranke \(n\) soll die Summe \(p+q\) über alle positiven Tripel \((p,q,r)\) berechnet werden, die
$$q > p > r,\qquad pr \equiv 1 \pmod q,\qquad qr \equiv 1 \pmod p,\qquad p \le n$$
erfüllen. Ein direkter Dreifach-Scan wäre viel zu langsam. Die entscheidende Beobachtung ist, dass bei festem \(r\) jedes gültige Paar \((p,q)\) aus einem Teiler von \(r^2-1\) entsteht.
Bezeichne die gesuchte Summe mit
$$S(n)=\sum (p+q),$$
wobei über alle zulässigen Tripel summiert wird. Die Herleitung zeigt, warum man nur über \(r\) und über Teiler von \(r^2-1\) iterieren muss.
Aus \(pr \equiv 1 \pmod q\) folgt, dass es ein ganzzahliges \(a\) mit
$$pr-1=aq$$
gibt. Analog liefert \(qr \equiv 1 \pmod p\) ein ganzzahliges \(b\) mit
$$qr-1=bp.$$
Wegen \(q>r\) gilt
$$0 \le a=\frac{pr-1}{q} < p.$$
Reduziert man \(pr-1=aq\) modulo \(p\), dann ist \(q\) wegen \(qr \equiv 1 \pmod p\) das Inverse von \(r\) modulo \(p\). Multiplikation mit \(r\) ergibt
$$-r \equiv aqr \equiv a \pmod p.$$
Die einzige Zahl in \([0,p-1]\), die zu \(-r\) modulo \(p\) kongruent ist, lautet \(p-r\). Also
$$a=p-r.$$
Damit folgt
$$pr-1=(p-r)q,\qquad q=\frac{pr-1}{p-r}.$$
Symmetrisch erhält man
$$qr-1=(q-r)p,\qquad p=\frac{qr-1}{q-r}.$$
Setze
$$d=p-r,\qquad e=q-r,$$
also
$$p=r+d,\qquad q=r+e,\qquad d>0,\ e>0.$$
Setzt man \(p=r+d\) in die Formel für \(q\) ein, erhält man
$$q=\frac{(r+d)r-1}{d}=r+\frac{r^2-1}{d}.$$
Daraus folgt unmittelbar
$$e=\frac{r^2-1}{d},\qquad de=r^2-1.$$
Das ist die zentrale Reduktion: Für festes \(r\) entsprechen gültige Tripel genau den Faktorzerlegungen von \(r^2-1\).
Die Bedingung \(p \le n\) wird zu
$$r+d \le n,\qquad d \le n-r.$$
Außerdem ist \(q>p\) genau dann erfüllt, wenn \(e>d\). Wegen \(de=r^2-1\) ist das äquivalent zu
$$d^2 < r^2-1.$$
Für ganze \(r \ge 2\) bedeutet das genau
$$d \le r-1.$$
Die zulässigen Teiler sind also exakt diejenigen mit
$$1 \le d \le m_r,\qquad m_r=\min(r-1,n-r),\qquad d \mid (r^2-1).$$
Ist ein solcher Teiler gewählt, dann sind \(p\) und \(q\) fest bestimmt durch
$$p=r+d,\qquad q=r+\frac{r^2-1}{d}.$$
Die Reduktion ist nicht nur notwendig, sondern exakt. Sei \(r \ge 2\) und \(d\) ein Teiler von \(r^2-1\) mit \(1 \le d \le m_r\). Definiere
$$e=\frac{r^2-1}{d},\qquad p=r+d,\qquad q=r+e.$$
Dann gilt
$$pr-1=r(r+d)-1=r^2+rd-1=d(r+e)=dq=(p-r)q,$$
also \(pr \equiv 1 \pmod q\). Ebenso
$$qr-1=r(r+e)-1=r^2+re-1=e(r+d)=ep=(q-r)p,$$
also \(qr \equiv 1 \pmod p\). Die Schranke \(d \le n-r\) sichert \(p \le n\), und \(d \le r-1\) sichert \(q>p\). Damit entsteht aus jedem zulässigen Teiler genau ein gültiges Tripel, und umgekehrt. Es handelt sich also um eine Bijektion.
Für festes \(r\) trägt jeder zulässige Teiler den Wert
$$p+q=(r+d)+\left(r+\frac{r^2-1}{d}\right)=2r+d+\frac{r^2-1}{d}$$
bei. Somit gilt
$$S(n)=\sum_{r=2}^{n-1}\ \sum_{d \mid (r^2-1),\ 1 \le d \le m_r}\left(2r+d+\frac{r^2-1}{d}\right),$$
wobei \(m_r=\min(r-1,n-r)\). Genau diese Summe wird vom Programm ausgewertet.
Nur \(r=2,3,4\) können beitragen.
Für \(r=2\) gilt \(r^2-1=3\) und \(m_r=\min(1,3)=1\). Der einzige zulässige Teiler ist \(d=1\), also
$$p=2+1=3,\qquad q=2+\frac{3}{1}=5,$$
mit Beitrag \(3+5=8\).
Für \(r=3\) gilt \(r^2-1=8\) und \(m_r=\min(2,2)=2\). Zulässig sind \(d=1,2\):
$$d=1 \Rightarrow (p,q)=(4,11),\quad p+q=15,$$
$$d=2 \Rightarrow (p,q)=(5,7),\quad p+q=12.$$
Für \(r=4\) gilt \(r^2-1=15\) und \(m_r=\min(3,1)=1\). Nur \(d=1\) ist erlaubt, also
$$ (p,q)=(5,19),\quad p+q=24. $$
Insgesamt erhält man
$$S(5)=8+15+12+24=59.$$
Die Implementierungen in C++, Python und Java folgen demselben Schema. Zuerst wird eine Tabelle der kleinsten Primfaktoren bis etwas über \(n\) aufgebaut. Dadurch lassen sich \(r-1\) und \(r+1\) für jedes \(r\) schnell faktorisieren.
Für jedes \(r\) von \(2\) bis \(n-1\) wird \(m_r=\min(r-1,n-r)\) bestimmt. Ist \(m_r \le 0\), kann dieses \(r\) nichts beitragen. Andernfalls werden \(r-1\) und \(r+1\) faktorisiert und ihre Primexponenten zusammengeführt, sodass die Zerlegung von
$$r^2-1=(r-1)(r+1)$$
vorliegt.
Danach erzeugt die Implementierung rekursiv alle Teiler aus dieser Primfaktorzerlegung. Sobald ein partielles Produkt bereits größer als \(m_r\) ist, wird der entsprechende Suchzweig abgeschnitten, weil daraus kein gültiges \(p\) mehr entstehen kann.
Jeder vollständige zulässige Teiler \(d\) liefert dann direkt
$$p=r+d,\qquad q=r+\frac{r^2-1}{d},$$
und der Wert \(p+q\) wird zur Gesamtsumme addiert. Der Programmablauf ist also eine gezielte Teilererzeugung auf Basis der hergeleiteten Bijektion.
Das Sieb für die kleinsten Primfaktoren benötigt \(O(n\log\log n)\) Zeit und \(O(n)\) Speicher. Die Faktorisierung von \(r-1\) und \(r+1\) ist dank dieser Tabelle schnell. Der dominierende Anteil ist die Erzeugung der zulässigen Teiler von \(r^2-1\), weshalb die Gesamtlaufzeit sinnvoll durch
$$O\!\left(n\log\log n+\sum_{r=2}^{n-1}\tau(r^2-1)\right)$$
beschrieben wird, abzüglich der praktischen Einsparungen durch das frühe Abschneiden von Zweigen mit zu großen Teilern. Das ist um Größenordnungen kleiner als ein naiver Dreifach-Scan.
Verilen \(n\) sınırı için
$$q > p > r,\qquad pr \equiv 1 \pmod q,\qquad qr \equiv 1 \pmod p,\qquad p \le n$$
koşullarını sağlayan tüm pozitif tamsayı üçlüleri \((p,q,r)\) üzerinde \(p+q\) toplamı istenir. Doğrudan üçlü taraması çok pahalıdır. Asıl fikir, sabit bir \(r\) için her geçerli \((p,q)\) çiftinin \(r^2-1\)'in bir böleninden üretilebilmesidir.
Aranan toplamı
$$S(n)=\sum (p+q)$$
olarak yazalım; burada toplam tüm uygun üçlüler üzerindedir. Aşağıdaki dönüşüm, neden yalnızca \(r\) ve \(r^2-1\)'in bölenleri üzerinden gitmenin yeterli olduğunu gösterir.
\(pr \equiv 1 \pmod q\) olduğundan bir \(a\) tamsayısı için
$$pr-1=aq$$
yazabiliriz. Benzer şekilde \(qr \equiv 1 \pmod p\) olduğundan bir \(b\) tamsayısı için
$$qr-1=bp$$
vardır. \(q>r\) olduğu için
$$0 \le a=\frac{pr-1}{q} < p$$
elde edilir. İlk eşitliği modulo \(p\) inceleyelim. \(qr \equiv 1 \pmod p\) olduğundan \(q\), modulo \(p\) altında \(r\)'nin tersidir. Bu yüzden \(pr-1=aq\) eşitliğini modulo \(p\) tarafında \(r\) ile çarparsak
$$-r \equiv aqr \equiv a \pmod p$$
buluruz. \([0,p-1]\) aralığında \(-r\)'ye eşdeğer tek sayı \(p-r\) olduğundan
$$a=p-r$$
olur. Dolayısıyla
$$pr-1=(p-r)q,\qquad q=\frac{pr-1}{p-r}.$$
Simetrik olarak
$$qr-1=(q-r)p,\qquad p=\frac{qr-1}{q-r}$$
sonucunu da elde ederiz.
Şimdi
$$d=p-r,\qquad e=q-r$$
tanımlarını yapalım. Böylece
$$p=r+d,\qquad q=r+e,\qquad d>0,\ e>0$$
olur. \(p=r+d\) ifadesini \(q\) formülüne koyarsak
$$q=\frac{(r+d)r-1}{d}=r+\frac{r^2-1}{d}$$
çıkar. Buradan
$$e=\frac{r^2-1}{d},\qquad de=r^2-1$$
elde edilir. Yani sabit bir \(r\) için tüm geçerli durumlar, \(r^2-1\)'in çarpan çiftlerine indirgenmiş olur.
\(p \le n\) koşulu
$$r+d \le n,\qquad d \le n-r$$
şeklindedir. Ayrıca \(q>p\) olması için \(e>d\) gerekir. \(de=r^2-1\) olduğundan bu koşul
$$d^2 < r^2-1$$
ile aynıdır. \(r \ge 2\) için bu tam olarak
$$d \le r-1$$
anlamına gelir. Demek ki geçerli bölenler
$$1 \le d \le m_r,\qquad m_r=\min(r-1,n-r),\qquad d \mid (r^2-1)$$
şartını sağlayanlardır. Böyle bir \(d\) seçildiğinde çift doğrudan
$$p=r+d,\qquad q=r+\frac{r^2-1}{d}$$
olarak belirlenir.
Bu indirgeme yalnızca gerekli değil, aynı zamanda yeterlidir. \(r \ge 2\) ve \(1 \le d \le m_r\) koşullarını sağlayan bir \(d \mid (r^2-1)\) alalım. Şunu tanımlayalım:
$$e=\frac{r^2-1}{d},\qquad p=r+d,\qquad q=r+e.$$
O zaman
$$pr-1=r(r+d)-1=r^2+rd-1=d(r+e)=dq=(p-r)q,$$
dolayısıyla \(pr \equiv 1 \pmod q\). Benzer şekilde
$$qr-1=r(r+e)-1=r^2+re-1=e(r+d)=ep=(q-r)p,$$
olduğundan \(qr \equiv 1 \pmod p\). \(d \le n-r\) olduğu için \(p \le n\), \(d \le r-1\) olduğu için de \(q>p\) sağlanır. Böylece her uygun bölen tam bir geçerli üçlü üretir ve her geçerli üçlü tam bir uygun bölen verir. Yani arada bire bir eşleme vardır.
Sabit \(r\) için her uygun bölenin katkısı
$$p+q=(r+d)+\left(r+\frac{r^2-1}{d}\right)=2r+d+\frac{r^2-1}{d}$$
olur. Bu nedenle
$$S(n)=\sum_{r=2}^{n-1}\ \sum_{d \mid (r^2-1),\ 1 \le d \le m_r}\left(2r+d+\frac{r^2-1}{d}\right),$$
burada \(m_r=\min(r-1,n-r)\). Uygulanan algoritma tam olarak bu toplamı hesaplar.
Katkı verebilecek \(r\) değerleri yalnızca \(2,3,4\)'tür.
\(r=2\) için \(r^2-1=3\) ve \(m_r=\min(1,3)=1\). Tek uygun bölen \(d=1\) olur:
$$p=2+1=3,\qquad q=2+\frac{3}{1}=5,$$
katkı \(3+5=8\).
\(r=3\) için \(r^2-1=8\) ve \(m_r=\min(2,2)=2\). Uygun bölenler \(d=1,2\):
$$d=1 \Rightarrow (p,q)=(4,11),\quad p+q=15,$$
$$d=2 \Rightarrow (p,q)=(5,7),\quad p+q=12.$$
\(r=4\) için \(r^2-1=15\) ve \(m_r=\min(3,1)=1\). Sadece \(d=1\) geçerlidir:
$$ (p,q)=(5,19),\quad p+q=24. $$
Toplam sonuç
$$S(5)=8+15+12+24=59$$
olur.
C++, Python ve Java uygulamaları aynı planı izler. Önce \(n\)'in biraz üzerine kadar en küçük asal çarpan tablosu kurulur. Böylece her \(r\) için \(r-1\) ve \(r+1\) hızlı biçimde asal çarpanlarına ayrılabilir.
Daha sonra \(r=2\)'den \(n-1\)'e kadar dönülür ve
$$m_r=\min(r-1,n-r)$$
hesaplanır. \(m_r \le 0\) ise o \(r\) hiçbir şey katkı vermez. Aksi halde \(r-1\) ve \(r+1\)'in faktorizasyonları birleştirilerek
$$r^2-1=(r-1)(r+1)$$
sayısının asal üsleri elde edilir.
Ardından bu üslerden özyinelemeli olarak bölenler üretilir. Kısmi çarpım \(m_r\)'yi aşar aşmaz ilgili dal kesilir; çünkü o bölen artık geçerli bir \(p\) oluşturamaz.
Tam ve geçerli bir bölen \(d\) bulunduğunda uygulama doğrudan
$$p=r+d,\qquad q=r+\frac{r^2-1}{d}$$
hesabını yapıp \(p+q\)'yu toplama ekler. Böylece kod, yukarıdaki bire bir eşlemeyi doğrudan kullanan bir bölen üretim algoritmasına dönüşür.
En küçük asal çarpan eleği \(O(n\log\log n)\) zamanda ve \(O(n)\) bellekte kurulur. \(r-1\) ile \(r+1\)'in çarpanlara ayrılması bu tablo sayesinde hızlıdır. Baskın maliyet, \(r^2-1\)'in geçerli bölenlerini üretmektir; bu yüzden toplam çalışma süresi iyi bir yaklaşım olarak
$$O\!\left(n\log\log n+\sum_{r=2}^{n-1}\tau(r^2-1)\right)$$
şeklinde ifade edilir. Pratikte büyük bölenler erken elendiği için gerçek süre bundan genellikle daha iyidir ve yine de üçlü brute-force taramadan çok daha küçüktür.
Para un límite dado \(n\), hay que sumar \(p+q\) sobre todos los triples de enteros positivos \((p,q,r)\) que cumplen
$$q > p > r,\qquad pr \equiv 1 \pmod q,\qquad qr \equiv 1 \pmod p,\qquad p \le n.$$
Buscar directamente todos los triples sería demasiado costoso. La idea clave es que, fijado \(r\), cada par válido \((p,q)\) procede de un divisor de \(r^2-1\), de modo que el problema pasa a ser una enumeración organizada de divisores.
Denotemos por
$$S(n)=\sum (p+q)$$
la suma pedida sobre todos los triples válidos. La derivación siguiente muestra por qué basta recorrer \(r\) y los divisores de \(r^2-1\).
De \(pr \equiv 1 \pmod q\) se sigue que existe un entero \(a\) tal que
$$pr-1=aq.$$
Del mismo modo, \(qr \equiv 1 \pmod p\) implica la existencia de un entero \(b\) con
$$qr-1=bp.$$
Como \(q>r\), se cumple
$$0 \le a=\frac{pr-1}{q} < p.$$
Reduciendo la primera ecuación módulo \(p\), y usando que \(qr \equiv 1 \pmod p\), vemos que \(q\) es el inverso de \(r\) módulo \(p\). Al multiplicar por \(r\), obtenemos
$$-r \equiv aqr \equiv a \pmod p.$$
El único entero en \([0,p-1]\) congruente con \(-r\) módulo \(p\) es \(p-r\). Por tanto,
$$a=p-r.$$
Así,
$$pr-1=(p-r)q,\qquad q=\frac{pr-1}{p-r}.$$
Por simetría también se obtiene
$$qr-1=(q-r)p,\qquad p=\frac{qr-1}{q-r}.$$
Definamos
$$d=p-r,\qquad e=q-r,$$
de modo que
$$p=r+d,\qquad q=r+e,\qquad d>0,\ e>0.$$
Sustituyendo \(p=r+d\) en la fórmula de \(q\), resulta
$$q=\frac{(r+d)r-1}{d}=r+\frac{r^2-1}{d}.$$
Luego
$$e=\frac{r^2-1}{d},\qquad de=r^2-1.$$
Esta es la reducción central: para un \(r\) fijo, cada triple válido corresponde a un par de factores de \(r^2-1\).
La condición \(p \le n\) equivale a
$$r+d \le n,\qquad d \le n-r.$$
Además, \(q>p\) equivale a \(e>d\). Como \(de=r^2-1\), esto es lo mismo que exigir
$$d^2 < r^2-1.$$
Para enteros \(r \ge 2\), eso equivale exactamente a
$$d \le r-1.$$
Por tanto, los divisores admisibles son exactamente los que verifican
$$1 \le d \le m_r,\qquad m_r=\min(r-1,n-r),\qquad d \mid (r^2-1).$$
Una vez elegido ese divisor, el par queda fijado por
$$p=r+d,\qquad q=r+\frac{r^2-1}{d}.$$
La reducción no solo es necesaria; también es suficiente. Supongamos \(r \ge 2\) y un divisor \(d\) de \(r^2-1\) con \(1 \le d \le m_r\). Definimos
$$e=\frac{r^2-1}{d},\qquad p=r+d,\qquad q=r+e.$$
Entonces
$$pr-1=r(r+d)-1=r^2+rd-1=d(r+e)=dq=(p-r)q,$$
y por tanto \(pr \equiv 1 \pmod q\). De forma análoga,
$$qr-1=r(r+e)-1=r^2+re-1=e(r+d)=ep=(q-r)p,$$
y así \(qr \equiv 1 \pmod p\). La desigualdad \(d \le n-r\) garantiza \(p \le n\), y \(d \le r-1\) garantiza \(q>p\). Cada divisor admisible produce exactamente un triple válido, y cada triple válido produce exactamente un divisor admisible. Hay una biyección.
Para un \(r\) fijo, cada divisor válido aporta
$$p+q=(r+d)+\left(r+\frac{r^2-1}{d}\right)=2r+d+\frac{r^2-1}{d}.$$
Así,
$$S(n)=\sum_{r=2}^{n-1}\ \sum_{d \mid (r^2-1),\ 1 \le d \le m_r}\left(2r+d+\frac{r^2-1}{d}\right),$$
donde \(m_r=\min(r-1,n-r)\). Esa es exactamente la cantidad que calculan las implementaciones.
Solo pueden contribuir \(r=2,3,4\).
Para \(r=2\), se tiene \(r^2-1=3\) y \(m_r=\min(1,3)=1\). El único divisor admisible es \(d=1\), por lo que
$$p=2+1=3,\qquad q=2+\frac{3}{1}=5,$$
y la contribución es \(3+5=8\).
Para \(r=3\), \(r^2-1=8\) y \(m_r=\min(2,2)=2\). Los divisores admisibles son \(d=1,2\):
$$d=1 \Rightarrow (p,q)=(4,11),\quad p+q=15,$$
$$d=2 \Rightarrow (p,q)=(5,7),\quad p+q=12.$$
Para \(r=4\), \(r^2-1=15\) y \(m_r=\min(3,1)=1\). Solo vale \(d=1\), y entonces
$$ (p,q)=(5,19),\quad p+q=24. $$
Sumando todo,
$$S(5)=8+15+12+24=59.$$
Las implementaciones en C++, Python y Java siguen el mismo esquema. Primero construyen una tabla del menor factor primo hasta un poco por encima de \(n\). Con esa tabla, factorizar \(r-1\) y \(r+1\) para cada \(r\) es rápido.
Para cada \(r\) entre \(2\) y \(n-1\), la implementación calcula
$$m_r=\min(r-1,n-r).$$
Si \(m_r \le 0\), ese valor de \(r\) no aporta nada. En caso contrario, factoriza \(r-1\) y \(r+1\), suma los exponentes de los primos comunes y obtiene así la factorización prima de
$$r^2-1=(r-1)(r+1).$$
Después enumera recursivamente los divisores construidos a partir de esos exponentes. Si un divisor parcial ya supera \(m_r\), se poda ese ramo porque no puede generar un valor válido de \(p\).
Cada vez que aparece un divisor completo admisible \(d\), la implementación calcula
$$p=r+d,\qquad q=r+\frac{r^2-1}{d},$$
y añade \(p+q\) al total acumulado. En esencia, el programa es una enumeración de divisores guiada por la biyección demostrada antes.
Construir la tabla del menor factor primo cuesta \(O(n\log\log n)\) tiempo y \(O(n)\) memoria. Factorizar \(r-1\) y \(r+1\) es rápido gracias a esa precomputación. El trabajo dominante es enumerar los divisores admisibles de \(r^2-1\), así que una descripción razonable del coste total es
$$O\!\left(n\log\log n+\sum_{r=2}^{n-1}\tau(r^2-1)\right).$$
En la práctica suele ser algo menor por la poda temprana de divisores demasiado grandes, y en cualquier caso es muchísimo más eficiente que un barrido ingenuo de todos los triples posibles.
给定上界 \(n\)，题目要求对所有满足下列条件的正整数三元组 \((p,q,r)\) 求和 \(p+q\)：
$$q > p > r,\qquad pr \equiv 1 \pmod q,\qquad qr \equiv 1 \pmod p,\qquad p \le n.$$
如果直接枚举所有可能的 \((p,q,r)\)，规模会非常大，几乎不可行。真正有效的做法是固定 \(r\) 之后，把所有合法的 \((p,q)\) 转化为 \(r^2-1\) 的约数问题。这样一来，原本的三重搜索就被压缩成了“遍历 \(r\) + 枚举约数”的结构化计算。
记所求总和为
$$S(n)=\sum (p+q),$$
其中求和范围是所有满足条件的三元组。下面按步骤说明，为什么实现只需要围绕 \(r\) 和 \(r^2-1\) 的约数展开。
由
$$pr \equiv 1 \pmod q$$
可知存在整数 \(a\)，使得
$$pr-1=aq.$$
同理，由
$$qr \equiv 1 \pmod p$$
可知存在整数 \(b\)，使得
$$qr-1=bp.$$
因为 \(q>r\)，所以
$$0 \le a=\frac{pr-1}{q} < p.$$
现在把等式 \(pr-1=aq\) 放到模 \(p\) 的意义下观察。由于 \(qr \equiv 1 \pmod p\)，说明 \(q\) 在模 \(p\) 下正好是 \(r\) 的逆元。于是两边同乘 \(r\)，得到
$$-r \equiv aqr \equiv a \pmod p.$$
而 \(a\) 已经被限制在区间 \([0,p-1]\) 内，在这个区间里与 \(-r\) 同余的唯一整数就是 \(p-r\)。因此
$$a=p-r.$$
于是第一条同余条件可以精确地写成
$$pr-1=(p-r)q,\qquad q=\frac{pr-1}{p-r}.$$
完全对称地，第二条同余条件给出
$$qr-1=(q-r)p,\qquad p=\frac{qr-1}{q-r}.$$
令
$$d=p-r,\qquad e=q-r,$$
于是
$$p=r+d,\qquad q=r+e,\qquad d>0,\ e>0.$$
把 \(p=r+d\) 代入刚才得到的公式
$$q=\frac{pr-1}{p-r}$$
中，可以化简为
$$q=\frac{(r+d)r-1}{d}=r+\frac{r^2-1}{d}.$$
因此
$$e=\frac{r^2-1}{d},\qquad de=r^2-1.$$
这一步是整个问题的核心。它说明：一旦 \(r\) 固定，所有合法的 \((p,q)\) 都等价于 \(r^2-1\) 的一个因子对。
首先，题目要求 \(p \le n\)。由于 \(p=r+d\)，这等价于
$$r+d \le n,\qquad d \le n-r.$$
其次，还需要 \(q>p\)。因为 \(q=r+e\)、\(p=r+d\)，这等价于
$$e>d.$$
再利用 \(de=r^2-1\)，就得到
$$d^2 < r^2-1.$$
当 \(r \ge 2\) 时，这与
$$d \le r-1$$
是完全等价的。于是，真正需要枚举的约数正好是
$$1 \le d \le m_r,\qquad m_r=\min(r-1,n-r),\qquad d \mid (r^2-1).$$
只要找到这样的 \(d\)，对应的 \((p,q)\) 就唯一确定为
$$p=r+d,\qquad q=r+\frac{r^2-1}{d}.$$
上面的推导不仅给出了必要条件，而且给出了充分条件。也就是说，只要我们选定 \(r \ge 2\)，再选一个满足
$$1 \le d \le m_r,\qquad d \mid (r^2-1)$$
的约数，就一定能构造出一个合法三元组。令
$$e=\frac{r^2-1}{d},\qquad p=r+d,\qquad q=r+e.$$
此时
$$pr-1=r(r+d)-1=r^2+rd-1=d(r+e)=dq=(p-r)q,$$
所以
$$pr \equiv 1 \pmod q.$$
同理，
$$qr-1=r(r+e)-1=r^2+re-1=e(r+d)=ep=(q-r)p,$$
从而
$$qr \equiv 1 \pmod p.$$
由于 \(d \le n-r\)，所以 \(p \le n\) 自动满足；由于 \(d \le r-1\)，所以 \(q>p\) 也自动满足。因此，合法三元组与这些约数之间是一一对应的，没有重复，也没有遗漏。
对于固定的 \(r\)，每个合法约数 \(d\) 的贡献是
$$p+q=(r+d)+\left(r+\frac{r^2-1}{d}\right)=2r+d+\frac{r^2-1}{d}.$$
因此总和可以写成
$$S(n)=\sum_{r=2}^{n-1}\ \sum_{d \mid (r^2-1),\ 1 \le d \le m_r}\left(2r+d+\frac{r^2-1}{d}\right),$$
其中 \(m_r=\min(r-1,n-r)\)。这正是实现所计算的量。
当 \(n=5\) 时，只有 \(r=2,3,4\) 可能产生贡献。
当 \(r=2\) 时，
$$r^2-1=3,\qquad m_r=\min(1,3)=1.$$
唯一可用的约数是 \(d=1\)，于是
$$p=2+1=3,\qquad q=2+\frac{3}{1}=5,$$
贡献为 \(3+5=8\)。
当 \(r=3\) 时，
$$r^2-1=8,\qquad m_r=\min(2,2)=2.$$
可用约数是 \(d=1,2\)：
$$d=1 \Rightarrow (p,q)=(4,11),\quad p+q=15,$$
$$d=2 \Rightarrow (p,q)=(5,7),\quad p+q=12.$$
当 \(r=4\) 时，
$$r^2-1=15,\qquad m_r=\min(3,1)=1.$$
只有 \(d=1\) 合法，于是
$$ (p,q)=(5,19),\quad p+q=24. $$
把三部分相加，得到
$$S(5)=8+15+12+24=59.$$
C++、Python 和 Java 实现都遵循同一个思路。首先，它们会预处理一张最小质因子表，范围略大于 \(n\)。这样一来，每个 \(r\) 对应的 \(r-1\) 和 \(r+1\) 都能很快完成质因数分解。
接着，对每个 \(r=2,3,\dots,n-1\)，实现先计算
$$m_r=\min(r-1,n-r).$$
如果 \(m_r \le 0\)，那么这个 \(r\) 不可能贡献任何结果。否则，就分别分解 \(r-1\) 和 \(r+1\)，并把相同质数的指数合并，从而得到
$$r^2-1=(r-1)(r+1)$$
的完整质因数分解。
然后，程序按照这些质因数指数递归生成约数。一旦某个部分积已经超过 \(m_r\)，这条分支就立即停止，因为它不可能再形成有效的 \(p\)。这种剪枝能显著减少无效搜索。
每当生成一个完整且合法的约数 \(d\) 时，实现就直接计算
$$p=r+d,\qquad q=r+\frac{r^2-1}{d},$$
并把 \(p+q\) 加入总和。整个程序本质上就是把上面的数学双射，原样翻译成了一个高效的约数枚举过程。
最小质因子表的构建复杂度为 \(O(n\log\log n)\)，空间复杂度为 \(O(n)\)。在这张表的帮助下，分解 \(r-1\) 与 \(r+1\) 的代价较低。真正占主导的是对 \(r^2-1\) 合法约数的枚举，因此总时间可以近似写成
$$O\!\left(n\log\log n+\sum_{r=2}^{n-1}\tau(r^2-1)\right).$$
其中 \(\tau\) 表示约数个数函数。由于程序会提前剪去所有已经超过 \(m_r\) 的分支，实际运行通常还会比这个上界更快。无论如何，它都远远优于直接枚举所有三元组的做法。
Для заданной границы \(n\) нужно вычислить сумму \(p+q\) по всем тройкам положительных целых чисел \((p,q,r)\), удовлетворяющим условиям
$$q > p > r,\qquad pr \equiv 1 \pmod q,\qquad qr \equiv 1 \pmod p,\qquad p \le n.$$
Прямой перебор всех троек слишком дорог. Ключевое наблюдение состоит в том, что при фиксированном \(r\) каждая допустимая пара \((p,q)\) однозначно задается делителем числа \(r^2-1\). Поэтому задача сводится к перебору \(r\) и делителей, а не к полному тройному перебору.
Обозначим искомую сумму через
$$S(n)=\sum (p+q),$$
где суммирование ведется по всем допустимым тройкам. Ниже показано, почему реализация может работать только с \(r\) и делителями \(r^2-1\).
Из условия
$$pr \equiv 1 \pmod q$$
следует существование целого числа \(a\), такого что
$$pr-1=aq.$$
Аналогично из
$$qr \equiv 1 \pmod p$$
получаем целое число \(b\), для которого
$$qr-1=bp.$$
Так как \(q>r\), имеем
$$0 \le a=\frac{pr-1}{q} < p.$$
Рассмотрим равенство \(pr-1=aq\) по модулю \(p\). Поскольку \(qr \equiv 1 \pmod p\), число \(q\) является обратным к \(r\) по модулю \(p\). Умножая на \(r\), получаем
$$-r \equiv aqr \equiv a \pmod p.$$
Единственное число из интервала \([0,p-1]\), сравнимое с \(-r\) по модулю \(p\), равно \(p-r\). Следовательно,
$$a=p-r.$$
Значит,
$$pr-1=(p-r)q,\qquad q=\frac{pr-1}{p-r}.$$
По симметрии получаем и вторую формулу:
$$qr-1=(q-r)p,\qquad p=\frac{qr-1}{q-r}.$$
Положим
$$d=p-r,\qquad e=q-r,$$
тогда
$$p=r+d,\qquad q=r+e,\qquad d>0,\ e>0.$$
Подставляя \(p=r+d\) в формулу для \(q\), получаем
$$q=\frac{(r+d)r-1}{d}=r+\frac{r^2-1}{d}.$$
Отсюда следует
$$e=\frac{r^2-1}{d},\qquad de=r^2-1.$$
Это и есть центральное упрощение: для фиксированного \(r\) все допустимые пары \((p,q)\) соответствуют парам множителей числа \(r^2-1\).
Условие \(p \le n\) эквивалентно неравенству
$$r+d \le n,\qquad d \le n-r.$$
Условие \(q>p\) эквивалентно \(e>d\). С учетом \(de=r^2-1\) это то же самое, что
$$d^2 < r^2-1.$$
Для целых \(r \ge 2\) это в точности означает
$$d \le r-1.$$
Следовательно, нужно перебирать ровно те делители, которые удовлетворяют условиям
$$1 \le d \le m_r,\qquad m_r=\min(r-1,n-r),\qquad d \mid (r^2-1).$$
После выбора такого \(d\) числа \(p\) и \(q\) задаются однозначно:
$$p=r+d,\qquad q=r+\frac{r^2-1}{d}.$$
Полученное условие не только необходимо, но и достаточно. Пусть \(r \ge 2\), а \(d\) — делитель числа \(r^2-1\), для которого выполнено \(1 \le d \le m_r\). Определим
$$e=\frac{r^2-1}{d},\qquad p=r+d,\qquad q=r+e.$$
Тогда
$$pr-1=r(r+d)-1=r^2+rd-1=d(r+e)=dq=(p-r)q,$$
поэтому \(pr \equiv 1 \pmod q\). Аналогично,
$$qr-1=r(r+e)-1=r^2+re-1=e(r+d)=ep=(q-r)p,$$
следовательно, \(qr \equiv 1 \pmod p\). Неравенство \(d \le n-r\) гарантирует \(p \le n\), а \(d \le r-1\) гарантирует \(q>p\). Значит, каждому допустимому делителю соответствует ровно одна допустимая тройка, и наоборот. Это биекция.
Для фиксированного \(r\) вклад одного допустимого делителя равен
$$p+q=(r+d)+\left(r+\frac{r^2-1}{d}\right)=2r+d+\frac{r^2-1}{d}.$$
Следовательно,
$$S(n)=\sum_{r=2}^{n-1}\ \sum_{d \mid (r^2-1),\ 1 \le d \le m_r}\left(2r+d+\frac{r^2-1}{d}\right),$$
где \(m_r=\min(r-1,n-r)\). Именно эту сумму вычисляют реализации.
Вклад могут дать только значения \(r=2,3,4\).
При \(r=2\) имеем
$$r^2-1=3,\qquad m_r=\min(1,3)=1.$$
Единственный допустимый делитель — \(d=1\), поэтому
$$p=2+1=3,\qquad q=2+\frac{3}{1}=5,$$
и вклад равен \(3+5=8\).
При \(r=3\) получаем
$$r^2-1=8,\qquad m_r=\min(2,2)=2.$$
Допустимы \(d=1\) и \(d=2\):
$$d=1 \Rightarrow (p,q)=(4,11),\quad p+q=15,$$
$$d=2 \Rightarrow (p,q)=(5,7),\quad p+q=12.$$
При \(r=4\) имеем
$$r^2-1=15,\qquad m_r=\min(3,1)=1.$$
Подходит только \(d=1\), откуда
$$ (p,q)=(5,19),\quad p+q=24. $$
Итоговая сумма равна
$$S(5)=8+15+12+24=59.$$
Реализации на C++, Python и Java устроены одинаково. Сначала они строят таблицу наименьших простых делителей для чисел примерно до \(n\). Благодаря этому числа \(r-1\) и \(r+1\) факторизуются очень быстро для каждого \(r\).
Затем для каждого \(r\) от \(2\) до \(n-1\) вычисляется
$$m_r=\min(r-1,n-r).$$
Если \(m_r \le 0\), такой \(r\) ничего не добавляет. Иначе программа факторизует \(r-1\) и \(r+1\), объединяет показатели степеней одинаковых простых чисел и тем самым получает разложение
$$r^2-1=(r-1)(r+1).$$
После этого из полученных простых степеней рекурсивно перечисляются делители. Если частичное произведение уже превысило \(m_r\), ветвь сразу отбрасывается, поскольку она не может привести к допустимому \(p\).
Когда найден полный допустимый делитель \(d\), реализация сразу вычисляет
$$p=r+d,\qquad q=r+\frac{r^2-1}{d},$$
и прибавляет \(p+q\) к общей сумме. То есть программа буквально реализует доказанную выше биекцию между решениями и подходящими делителями.
Построение таблицы наименьших простых делителей требует \(O(n\log\log n)\) времени и \(O(n)\) памяти. Разложение чисел \(r-1\) и \(r+1\) благодаря этой таблице выполняется быстро. Основная стоимость приходится на перечисление допустимых делителей числа \(r^2-1\), поэтому общую сложность разумно оценивать как
$$O\!\left(n\log\log n+\sum_{r=2}^{n-1}\tau(r^2-1)\right).$$
На практике она часто ниже из-за раннего отсечения слишком больших делителей, но в любом случае это несравнимо лучше полного перебора всех возможных троек.
لعدد حدّي معطى \(n\)، نريد حساب مجموع \(p+q\) على جميع الثلاثيات الصحيحة الموجبة \((p,q,r)\) التي تحقق
$$q > p > r,\qquad pr \equiv 1 \pmod q,\qquad qr \equiv 1 \pmod p,\qquad p \le n.$$
الفحص المباشر لكل الثلاثيات مكلف جدًا. الفكرة الأساسية هي أنه عند تثبيت \(r\)، فإن كل زوج صالح \((p,q)\) ينتج من قاسم للعدد \(r^2-1\). وهكذا تتحول المسألة من بحث ثلاثي ضخم إلى تعداد منظّم للقواسم.
لنرمز إلى المجموع المطلوب بالرمز
$$S(n)=\sum (p+q),$$
حيث يمتد الجمع على جميع الثلاثيات الصالحة. الخطوات التالية تشرح لماذا يكفي أن ندور على \(r\) وعلى قواسم \(r^2-1\).
من الشرط
$$pr \equiv 1 \pmod q$$
نعلم بوجود عدد صحيح \(a\) بحيث
$$pr-1=aq.$$
وبالمثل، من
$$qr \equiv 1 \pmod p$$
يوجد عدد صحيح \(b\) يحقق
$$qr-1=bp.$$
ولأن \(q>r\)، فإن
$$0 \le a=\frac{pr-1}{q} < p.$$
الآن ننظر إلى المعادلة \(pr-1=aq\) بترديد \(p\). بما أن \(qr \equiv 1 \pmod p\)، فإن \(q\) هو المعكوس الضربي لـ \(r\) بترديد \(p\). لذلك إذا ضربنا في \(r\) نحصل على
$$-r \equiv aqr \equiv a \pmod p.$$
والعدد الوحيد في المجال \([0,p-1]\) الموافق لـ \(-r\) بترديد \(p\) هو \(p-r\)، ومن ثم
$$a=p-r.$$
إذن يصبح لدينا
$$pr-1=(p-r)q,\qquad q=\frac{pr-1}{p-r}.$$
وبنفس الطريقة نحصل على
$$qr-1=(q-r)p,\qquad p=\frac{qr-1}{q-r}.$$
لنضع
$$d=p-r,\qquad e=q-r,$$
وعندئذ
$$p=r+d,\qquad q=r+e,\qquad d>0,\ e>0.$$
بالتعويض عن \(p=r+d\) في صيغة \(q\)، نحصل على
$$q=\frac{(r+d)r-1}{d}=r+\frac{r^2-1}{d}.$$
ومن هنا
$$e=\frac{r^2-1}{d},\qquad de=r^2-1.$$
هذه هي النقطة الجوهرية في الحل. فعند تثبيت \(r\)، تصبح كل الحلول الصالحة مقابلة مباشرة لأزواج عوامل العدد \(r^2-1\).
الشرط \(p \le n\) يتحول إلى
$$r+d \le n,\qquad d \le n-r.$$
كذلك فإن \(q>p\) يكافئ \(e>d\). وباستخدام العلاقة \(de=r^2-1\) يصبح هذا الشرط
$$d^2 < r^2-1.$$
وبالنسبة للأعداد الصحيحة \(r \ge 2\)، فهذا يكافئ تمامًا
$$d \le r-1.$$
إذن القواسم الصالحة هي بالضبط القواسم التي تحقق
$$1 \le d \le m_r,\qquad m_r=\min(r-1,n-r),\qquad d \mid (r^2-1).$$
ومتى اخترنا مثل هذا القاسم، فإن الزوج الموافق له يكون
$$p=r+d,\qquad q=r+\frac{r^2-1}{d}.$$
الاختزال السابق ليس ضروريًا فقط بل كافٍ أيضًا. إذا أخذنا \(r \ge 2\) وقاسمًا \(d\) للعدد \(r^2-1\) بحيث \(1 \le d \le m_r\)، ثم عرّفنا
$$e=\frac{r^2-1}{d},\qquad p=r+d,\qquad q=r+e,$$
فإننا نحصل على
$$pr-1=r(r+d)-1=r^2+rd-1=d(r+e)=dq=(p-r)q,$$
ومن ثم
$$pr \equiv 1 \pmod q.$$
وبالمثل،
$$qr-1=r(r+e)-1=r^2+re-1=e(r+d)=ep=(q-r)p,$$
وبالتالي
$$qr \equiv 1 \pmod p.$$
والقيد \(d \le n-r\) يضمن \(p \le n\)، بينما القيد \(d \le r-1\) يضمن \(q>p\). إذن كل قاسم صالح يولد ثلاثية صالحة واحدة بالضبط، وكل ثلاثية صالحة تعطي قاسمًا صالحًا واحدًا بالضبط. أي أن بين الجانبين تقابلًا واحدًا لواحد.
عند تثبيت \(r\)، تكون مساهمة كل قاسم صالح هي
$$p+q=(r+d)+\left(r+\frac{r^2-1}{d}\right)=2r+d+\frac{r^2-1}{d}.$$
لذلك يمكن كتابة المجموع على الصورة
$$S(n)=\sum_{r=2}^{n-1}\ \sum_{d \mid (r^2-1),\ 1 \le d \le m_r}\left(2r+d+\frac{r^2-1}{d}\right),$$
حيث \(m_r=\min(r-1,n-r)\). وهذه هي الصيغة التي تنفذها التطبيقات مباشرة.
القيم الممكنة لـ \(r\) هنا هي \(2,3,4\) فقط.
عندما \(r=2\)، لدينا
$$r^2-1=3,\qquad m_r=\min(1,3)=1.$$
القاسم الوحيد المسموح هو \(d=1\)، ومنه
$$p=2+1=3,\qquad q=2+\frac{3}{1}=5,$$
فتكون المساهمة \(3+5=8\).
عندما \(r=3\)، نحصل على
$$r^2-1=8,\qquad m_r=\min(2,2)=2.$$
والقواسم المسموحة هي \(d=1,2\):
$$d=1 \Rightarrow (p,q)=(4,11),\quad p+q=15,$$
$$d=2 \Rightarrow (p,q)=(5,7),\quad p+q=12.$$
وعندما \(r=4\)، يكون
$$r^2-1=15,\qquad m_r=\min(3,1)=1.$$
ولا يبقى إلا \(d=1\)، فنحصل على
$$ (p,q)=(5,19),\quad p+q=24. $$
إذًا
$$S(5)=8+15+12+24=59.$$
تتبع تطبيقات C++ وPython وJava البنية نفسها. في البداية تُبنى جدول لأصغر عامل أولي حتى مدى أكبر قليلًا من \(n\). وبهذه الطريقة يصبح تحليل \(r-1\) و\(r+1\) إلى عوامل أولية سريعًا لكل قيمة من \(r\).
بعد ذلك، يمر التنفيذ على جميع القيم \(r=2,3,\dots,n-1\)، ويحسب
$$m_r=\min(r-1,n-r).$$
إذا كان \(m_r \le 0\)، فلا يمكن أن تعطي هذه القيمة أي مساهمة. وإلا، تُحلَّل القيمتان \(r-1\) و\(r+1\) إلى عوامل أولية، ثم تُجمع أسس العوامل المشتركة للحصول على تحليل
$$r^2-1=(r-1)(r+1)$$
كاملًا.
بعد ذلك تُولَّد القواسم الممكنة توليدًا تكراريًا انطلاقًا من هذه الأسس. وكلما تجاوز حاصل الضرب الجزئي القيمة \(m_r\)، تُقطع تلك الشعبة مباشرة لأنها لن تنتج قيمة صالحة لـ \(p\).
وعندما يُولد قاسم كامل صالح \(d\)، يحسب التنفيذ مباشرة
$$p=r+d,\qquad q=r+\frac{r^2-1}{d},$$
ثم يضيف \(p+q\) إلى المجموع الكلي. وبذلك يكون الكود ترجمة مباشرة للتقابل الرياضي بين الحلول والقواسم المناسبة.
بناء جدول أصغر عامل أولي يحتاج إلى \(O(n\log\log n)\) زمنًا و\(O(n)\) ذاكرة. وبعد هذه التهيئة يصبح تحليل \(r-1\) و\(r+1\) سريعًا. أما الجزء الغالب في الكلفة فهو تعداد القواسم الصالحة للعدد \(r^2-1\)، ولذلك يمكن وصف الزمن الكلي تقريبًا بالصيغة
$$O\!\left(n\log\log n+\sum_{r=2}^{n-1}\tau(r^2-1)\right).$$
وغالبًا ما يكون الأداء العملي أفضل من هذا الوصف لأن الفروع التي تتجاوز \(m_r\) تُستبعد مبكرًا. ومع ذلك يبقى الفرق هائلًا مقارنة بالبحث الساذج على جميع الثلاثيات.