Define the coresilience of a positive integer by
$$C(n)=\frac{n-\varphi(n)}{n-1}.$$
Problem 245 asks for the sum of all composite numbers \(n\le 2\cdot 10^{11}\) whose coresilience is a unit fraction. Equivalently, we must find every composite \(n\) for which
$$\frac{n-1}{n-\varphi(n)}\in\mathbb Z.$$
If we write
$$n-1=k(n-\varphi(n)),\qquad k\in\mathbb Z_{\ge 2},$$
then \(C(n)=1/k\). A direct sweep up to \(2\cdot 10^{11}\) with explicit totients would be far too slow, so the solution turns this divisibility condition into a structural classification of the admissible composite numbers.
The integer \(k\) is the natural organizing parameter of the search. Rearranging the defining equation gives the invariant
$$k\varphi(n)=(k-1)n+1.$$
Everything in the final algorithm comes from forcing this identity to coexist with the prime factorization of \(n\).
Suppose \(p^2\mid n\) for some prime \(p\). Then \(p\mid n\), and also \(p\mid \varphi(n)\), because the totient of any integer divisible by \(p^2\) still carries a factor of \(p\). Hence \(p\mid n-\varphi(n)\).
But \(n\equiv 0\pmod p\) implies \(n-1\equiv -1\pmod p\), so \(p\nmid n-1\). Therefore \(n-\varphi(n)\) cannot divide \(n-1\). Every valid composite must be squarefree:
$$n=p_1p_2\cdots p_r,\qquad \varphi(n)=\prod_{i=1}^{r}(p_i-1).$$
This is why the multi-prime branch of the implementation only builds products of distinct primes.
From \(k\varphi(n)=(k-1)n+1\) we obtain
$$\frac{n}{\varphi(n)}=\frac{k}{k-1}-\frac{1}{(k-1)\varphi(n)}\lt\frac{k}{k-1}.$$
Because \(n\) is squarefree,
$$\frac{n}{\varphi(n)}=\prod_{p\mid n}\frac{p}{p-1}.$$
The function \(x\mapsto \frac{x}{x-1}\) decreases for \(x\gt 1\). If some prime divisor satisfied \(p\le k\), then
$$\frac{p}{p-1}\ge \frac{k}{k-1},$$
and multiplying by the remaining factors, all of which are \(\gt 1\), would force \(\frac{n}{\varphi(n)}\) to be at least \(\frac{k}{k-1}\), contradicting the previous inequality. Hence
$$p_i\gt k.$$
This immediately explains the two main search bounds. If \(n=pq\), then \(n\gt (k+1)^2\), so only \(k\le \sqrt{L}\) can contribute. If \(n\) has at least three prime factors, then \(n\gt (k+1)^3\), so only \(k\lt \sqrt[3]{L}\) need be explored in that branch.
Let \(n=pq\) with distinct primes \(p\) and \(q\). Then
$$\varphi(n)=(p-1)(q-1)=pq-p-q+1,$$
so
$$n-\varphi(n)=pq-(pq-p-q+1)=p+q-1.$$
Substituting into \(n-1=k(n-\varphi(n))\) gives
$$pq-1=k(p+q-1).$$
Rearranging yields
$$pq-kp-kq+k^2=k^2-k+1,$$
hence
$$\boxed{(p-k)(q-k)=k^2-k+1.}$$
Now define
$$K(k)=k^2-k+1.$$
Every semiprime solution for that \(k\) comes from a divisor pair \(ab=K(k)\):
$$p=k+a,\qquad q=k+b.$$
So the semiprime stage reduces to factoring \(K(k)\), enumerating its divisor pairs, shifting them by \(k\), and testing primality.
Factoring each \(K(k)\) independently would still be too expensive. The implementations instead sieve the polynomial values arithmetically. If an odd prime \(r\) divides \(K(k)\), then
$$k^2-k+1\equiv 0\pmod r\iff (2k-1)^2\equiv -3\pmod r.$$
Therefore \(k\) must lie in one of the residue classes
$$k\equiv \frac{1\pm \sqrt{-3}}{2}\pmod r.$$
For \(r=3\), this collapses to the single class \(k\equiv 2\pmod 3\). For other odd primes, a square root of \(-3\) exists only when the prime is in the right quadratic-residue class, which here means \(r\equiv 1\pmod 3\). That is why the sieve skips \(2\) and all primes \(r\equiv 2\pmod 3\), and uses Tonelli-Shanks only for the relevant primes to recover the admissible residue classes. Once those classes are known, the prime powers are stripped from every matching \(K(k)\), producing the factor tables used later to generate all divisor pairs.
Now consider a squarefree candidate with at least three prime factors. Suppose we have already chosen distinct primes \(q_1,\dots,q_t\) and set
$$m=\prod_{i=1}^{t}q_i,\qquad A=\prod_{i=1}^{t}(q_i-1).$$
If the final number is \(n=mp\), then \(\varphi(n)=A(p-1)\). Substituting this into
$$k\varphi(n)=(k-1)n+1$$
gives
$$kA(p-1)=(k-1)mp+1.$$
Collecting the terms containing \(p\),
$$p\bigl(kA-(k-1)m\bigr)=kA+1,$$
so the final prime is forced to be
$$\boxed{p=\frac{kA+1}{kA-(k-1)m}.}$$
This formula is the backbone of the recursive search. A branch succeeds only if the denominator is positive, it divides the numerator exactly, the resulting \(p\) is prime, it is larger than the primes already chosen, and \(mp\le L\).
The semiprime \(n=15=3\cdot 5\) comes from \(k=2\). Here
$$K(2)=2^2-2+1=3,$$
and the divisor pair \((1,3)\) yields
$$p=2+1=3,\qquad q=2+3=5.$$
Indeed \(\varphi(15)=8\), so
$$\frac{15-1}{15-\varphi(15)}=\frac{14}{7}=2.$$
A three-prime example is \(n=255=3\cdot 5\cdot 17\), again with \(k=2\). After choosing \(m=3\cdot 5=15\) and \(A=(3-1)(5-1)=8\), the forced last prime is
$$p=\frac{2\cdot 8+1}{2\cdot 8-(2-1)\cdot 15}=\frac{17}{1}=17.$$
Since \(\varphi(255)=128\), we get
$$\frac{255-1}{255-\varphi(255)}=\frac{254}{127}=2.$$
These two examples are exactly the two mechanisms used by the code: divisor pairs for semiprimes, and the forced-final-prime formula for the squarefree recursive branch.
The full implementations first generate all primes up to \(\sqrt{L}\). Those primes drive the congruence sieve for \(K(k)\), provide the candidates used in the recursive squarefree search, and answer small primality queries directly. Larger candidates are checked with a deterministic Miller-Rabin test in the relevant 64-bit range.
For each \(k\le \sqrt{L}\), the implementation stores the current remainder of \(K(k)\) together with the prime exponents found so far. Each admissible sieve prime contributes one or two residue classes of \(k\), and the algorithm walks exactly those progressions while stripping powers of that prime from the corresponding \(K(k)\). After the sieve phase, every divisor of \(K(k)\) is generated from the recorded factorization, translated into \(p=k+a\) and \(q=k+b\), tested for primality, and kept only when \(pq\le L\).
The multi-prime branch runs only for \(k\lt \sqrt[3]{L}\). It performs a depth-first search over strictly increasing primes \(\gt k\), maintaining the pair \((m,A)\). At every node, the formula
$$p=\frac{kA+1}{kA-(k-1)m}$$
is evaluated as a potential closing step. Whenever it produces a valid prime and at least two primes have already been chosen, a composite with at least three factors is recorded. The pruning is strong: if \(kA-(k-1)m\le 0\), no completion is possible, and if the next prime \(q\) would already force \(mq^2\gt L\), then there is no room for both \(q\) and a larger final prime.
The C++ implementation contains the full optimized search and parallelizes both collection stages with worker threads. It also includes small-limit brute-force checks to validate the fast method. The Java implementation mirrors the same number-theoretic search directly in one process. The Python implementation is deliberately thin: it ensures a compiled solver is available and then invokes that same fast search, so all three language entries correspond to the same mathematics and the same final answer.
The semiprime stage is the dominant part of the runtime. It covers all \(k\le \sqrt{L}\), but its cost is much lower than naive independent factorization because each sieve prime only visits the residue classes where \(k^2-k+1\) can actually be divisible by that prime. Divisor enumeration is then done from compact factorizations rather than from trial division.
The multi-prime branch is smaller. It only runs up to \(k\lt \sqrt[3]{L}\), only explores increasing primes \(\gt k\), and is pruned by the positivity test for \(kA-(k-1)m\), by exact divisibility of the forced-final-prime formula, by primality of the recovered last prime, and by the product bound \(n\le L\). Memory usage is moderate: a prime list, factor tables for the polynomial values, and a set of accepted solutions before sorting and deduplication. In practice the method is fast because it replaces an impossible totient sweep up to \(2\cdot 10^{11}\) with two highly structured searches.
Die Coresilience einer positiven ganzen Zahl sei definiert durch
$$C(n)=\frac{n-\varphi(n)}{n-1}.$$
In Problem 245 soll die Summe aller zusammengesetzten Zahlen \(n\le 2\cdot 10^{11}\) bestimmt werden, deren Coresilience ein Stammbruch ist. Äquivalent dazu suchen wir alle zusammengesetzten \(n\), für die
$$\frac{n-1}{n-\varphi(n)}\in\mathbb Z$$
gilt. Schreibt man
$$n-1=k(n-\varphi(n)),\qquad k\in\mathbb Z_{\ge 2},$$
dann ist \(C(n)=1/k\). Ein direkter Totientensweep bis \(2\cdot 10^{11}\) wäre unpraktikabel, daher formt die Lösung die Teilbarkeitsbedingung in eine Beschreibung der möglichen Primfaktorzerlegungen um.
Der natürliche Ordnungsparameter ist die ganze Zahl \(k\). Durch Umstellen der Grundgleichung erhält man die Invariante
$$k\varphi(n)=(k-1)n+1.$$
Die gesamte Herleitung untersucht nun, welche Folgen diese Gleichung für die Primfaktoren von \(n\) hat.
Angenommen, es gäbe eine Primzahl \(p\) mit \(p^2\mid n\). Dann teilt \(p\) nicht nur \(n\), sondern auch \(\varphi(n)\), weil die Phi-Funktion bei jeder Zahl mit einem quadratischen Primfaktor ebenfalls noch einen Faktor \(p\) enthält. Also gilt \(p\mid n-\varphi(n)\).
Andererseits folgt aus \(n\equiv 0\pmod p\), dass \(n-1\equiv -1\pmod p\), also \(p\nmid n-1\). Damit kann \(n-\varphi(n)\) den Wert \(n-1\) nicht teilen. Jede gültige zusammengesetzte Lösung ist also quadratfrei:
$$n=p_1p_2\cdots p_r,\qquad \varphi(n)=\prod_{i=1}^{r}(p_i-1).$$
Genau deshalb baut die rekursive Mehrprimzahl-Suche im Code nur Produkte verschiedener Primzahlen auf.
Aus \(k\varphi(n)=(k-1)n+1\) folgt
$$\frac{n}{\varphi(n)}=\frac{k}{k-1}-\frac{1}{(k-1)\varphi(n)}\lt\frac{k}{k-1}.$$
Für quadratfreies \(n\) gilt zugleich
$$\frac{n}{\varphi(n)}=\prod_{p\mid n}\frac{p}{p-1}.$$
Die Funktion \(x\mapsto \frac{x}{x-1}\) ist für \(x\gt 1\) streng fallend. Hätte also ein Primfaktor \(p\le k\), dann wäre
$$\frac{p}{p-1}\ge \frac{k}{k-1},$$
und zusammen mit den übrigen Faktoren, die alle \(\gt 1\) sind, würde das Produkt mindestens \(\frac{k}{k-1}\) werden. Das widerspricht der vorherigen Schranke. Also gilt
$$p_i\gt k.$$
Damit erhält man sofort die Suchgrenzen. Für \(n=pq\) gilt \(n\gt (k+1)^2\), also genügt \(k\le \sqrt{L}\). Hat \(n\) mindestens drei Primfaktoren, dann gilt \(n\gt (k+1)^3\), also reicht \(k\lt \sqrt[3]{L}\) in diesem Zweig.
Sei \(n=pq\) mit verschiedenen Primzahlen \(p\) und \(q\). Dann ist
$$\varphi(n)=(p-1)(q-1)=pq-p-q+1,$$
also
$$n-\varphi(n)=pq-(pq-p-q+1)=p+q-1.$$
Setzt man dies in \(n-1=k(n-\varphi(n))\) ein, so erhält man
$$pq-1=k(p+q-1).$$
Umgeformt ergibt das
$$pq-kp-kq+k^2=k^2-k+1,$$
also
$$\boxed{(p-k)(q-k)=k^2-k+1.}$$
Definiere nun
$$K(k)=k^2-k+1.$$
Jede semiprime Lösung zu diesem \(k\) entsteht aus einem Teilerpaar \(ab=K(k)\) durch
$$p=k+a,\qquad q=k+b.$$
Damit reduziert sich dieser Teil des Problems auf das Faktorisieren von \(K(k)\), das Auflisten aller Teilerpaare und anschließende Primzahltests der verschobenen Werte.
Würde man jedes \(K(k)\) separat faktorisieren, wäre der Aufwand immer noch hoch. Deshalb sieben die Implementierungen die Polynomwerte gesammelt. Falls eine ungerade Primzahl \(r\) den Wert \(K(k)\) teilt, dann gilt
$$k^2-k+1\equiv 0\pmod r\iff (2k-1)^2\equiv -3\pmod r.$$
Also muss \(k\) in einer der Restklassen
$$k\equiv \frac{1\pm \sqrt{-3}}{2}\pmod r$$
liegen. Für \(r=3\) bleibt nur die Klasse \(k\equiv 2\pmod 3\). Bei anderen ungeraden Primzahlen existiert eine Wurzel von \(-3\) nur in den passenden quadratischen Restklassen; hier bedeutet das \(r\equiv 1\pmod 3\). Darum überspringt das Sieb die \(2\) und alle Primzahlen \(r\equiv 2\pmod 3\), während für die übrigen mit Tonelli-Shanks die zulässigen Restklassen berechnet werden. Danach werden auf genau diesen arithmetischen Progressionen die entsprechenden Primzahlpotenzen aus den Werten \(K(k)\) herausdividiert.
Betrachte nun den quadratfreien Zweig mit mindestens drei Primfaktoren. Seien bereits verschiedene Primzahlen \(q_1,\dots,q_t\) gewählt, und setze
$$m=\prod_{i=1}^{t}q_i,\qquad A=\prod_{i=1}^{t}(q_i-1).$$
Ist die endgültige Zahl \(n=mp\), dann gilt \(\varphi(n)=A(p-1)\). Eingesetzt in
$$k\varphi(n)=(k-1)n+1$$
ergibt dies
$$kA(p-1)=(k-1)mp+1.$$
Nach Zusammenfassen der \(p\)-Terme folgt
$$p\bigl(kA-(k-1)m\bigr)=kA+1,$$
also
$$\boxed{p=\frac{kA+1}{kA-(k-1)m}.}$$
Diese Formel ist der Kern der rekursiven Suche. Ein Zweig wird genau dann akzeptiert, wenn der Nenner positiv ist, den Zähler ganzzahlig teilt, die entstehende Zahl \(p\) prim ist, größer als die bereits gewählten Primzahlen ist und außerdem \(mp\le L\) erfüllt.
Das Semiprime \(n=15=3\cdot 5\) stammt von \(k=2\). Hier ist
$$K(2)=2^2-2+1=3,$$
und das Teilerpaar \((1,3)\) liefert
$$p=2+1=3,\qquad q=2+3=5.$$
Tatsächlich ist \(\varphi(15)=8\), also
$$\frac{15-1}{15-\varphi(15)}=\frac{14}{7}=2.$$
Ein Beispiel mit drei Primfaktoren ist \(n=255=3\cdot 5\cdot 17\), ebenfalls mit \(k=2\). Nach der Wahl von \(m=3\cdot 5=15\) und \(A=(3-1)(5-1)=8\) ergibt die Formel für den letzten Primfaktor
$$p=\frac{2\cdot 8+1}{2\cdot 8-(2-1)\cdot 15}=\frac{17}{1}=17.$$
Da \(\varphi(255)=128\) gilt, erhält man
$$\frac{255-1}{255-\varphi(255)}=\frac{254}{127}=2.$$
Diese beiden Beispiele zeigen exakt die beiden Mechanismen der Lösung: Teilerpaare für Semiprime und die explizite Bestimmung des letzten Primfaktors im rekursiven, quadratfreien Zweig.
Die vollständigen Implementierungen erzeugen zunächst alle Primzahlen bis \(\sqrt{L}\). Diese Liste wird im Kongruenzsieb für \(K(k)\), als Kandidatenquelle für die rekursive Mehrprimzahl-Suche und für kleine Primzahlabfragen verwendet. Größere Kandidaten werden im relevanten 64-Bit-Bereich mit einem deterministischen Miller-Rabin-Test geprüft.
Für jedes \(k\le \sqrt{L}\) speichert die Implementierung den aktuellen Rest von \(K(k)\) zusammen mit den bisher gefundenen Primzahlpotenzen. Jede zulässige Siebprimzahl liefert eine oder zwei Restklassen für \(k\), und genau diese Progressionen werden durchlaufen, um entsprechende Faktoren aus den Werten \(K(k)\) zu entfernen. Danach werden aus der gespeicherten Faktorisierung alle Teiler erzeugt, in \(p=k+a\) und \(q=k+b\) übersetzt, auf Primzahleigenschaft geprüft und bei \(pq\le L\) als semiprime Treffer übernommen.
Der Mehrprimzahl-Zweig läuft nur für \(k\lt \sqrt[3]{L}\). Er führt eine Tiefensuche über streng wachsende Primzahlen \(\gt k\) aus und hält dabei das Paar \((m,A)\) aktuell. An jedem Knoten wird die Formel
$$p=\frac{kA+1}{kA-(k-1)m}$$
als möglicher Abschlussschritt ausgewertet. Liefert sie eine gültige Primzahl und wurden bereits mindestens zwei Primzahlen gewählt, dann ist ein zusammengesetzter Treffer mit mindestens drei Faktoren gefunden. Der Suchbaum wird stark beschnitten: Ist \(kA-(k-1)m\le 0\), kann kein Abschluss mehr funktionieren, und falls die nächste Primzahl \(q\) bereits \(mq^2\gt L\) erzwingen würde, gibt es keinen Platz mehr für \(q\) und einen noch größeren letzten Primfaktor.
Die C++-Version enthält die vollständige optimierte Suche und parallelisiert beide Sammelphasen mit Worker-Threads. Zusätzlich besitzt sie kleine Brute-Force-Prüfungen für Testgrenzen, um die schnelle Methode zu verifizieren. Die Java-Version bildet dieselbe zahlentheoretische Suche direkt in einem einzelnen Prozess nach. Die Python-Version ist bewusst schlank: Sie sorgt dafür, dass ein kompiliertes Programm vorhanden ist, und ruft dann genau diese schnelle Suche auf. Inhaltlich beruhen also alle drei Sprachblöcke auf demselben Algorithmus.
Die semiprime Stufe dominiert die Laufzeit. Sie betrachtet alle \(k\le \sqrt{L}\), aber durch das Kongruenzsieb ist sie deutlich günstiger als eine naive Einzel-Faktorisierung aller Werte \(K(k)\): Jede Siebprimzahl besucht nur jene Restklassen, in denen \(k^2-k+1\) überhaupt durch diese Primzahl teilbar sein kann. Die Auflistung der Teiler erfolgt dann aus kompakten Faktorisierungen statt aus Probeteilung.
Der Mehrprimzahl-Zweig ist kleiner. Er läuft nur für \(k\lt \sqrt[3]{L}\), untersucht nur wachsende Primzahlen \(\gt k\) und wird durch Positivität des Nenners, exakte Teilbarkeit der Endformel, Primzahleigenschaft des letzten Faktors und die Schranke \(n\le L\) stark reduziert. Der Speicherbedarf bleibt moderat: eine Primzahlliste, Faktortabellen für die Polynomwerte und die Menge der gefundenen Lösungen vor Sortierung und Deduplikation. Effizient wird das Verfahren, weil es einen unmöglichen Totientensweep durch zwei scharf strukturierte Suchen ersetzt.
Bir pozitif tam sayının coresilience değeri
$$C(n)=\frac{n-\varphi(n)}{n-1}$$
olarak tanımlansın. Problem 245, coresilience değeri bir birim kesir olan tüm bileşik \(n\le 2\cdot 10^{11}\) sayılarının toplamını istiyor. Bu koşul
$$\frac{n-1}{n-\varphi(n)}\in\mathbb Z$$
ile tamamen eşdeğerdir. Şöyle yazalım:
$$n-1=k(n-\varphi(n)),\qquad k\in\mathbb Z_{\ge 2}.$$
O zaman \(C(n)=1/k\) olur. \(2\cdot 10^{11}\) sınırına kadar tüm \(\varphi(n)\) değerlerini doğrudan taramak mümkün olmadığı için çözüm, bu bölünebilme koşulunu asal çarpan yapısı üzerinden çözülebilen iki arama dalına dönüştürür.
Aramanın doğal parametresi \(k\)'dır. Temel denklemi yeniden düzenleyince
$$k\varphi(n)=(k-1)n+1$$
invariantı elde edilir. Geri kalan her adım, bu eşitliğin \(n\)'in asal çarpanlarına ne zorladığını anlamaktan ibarettir.
Diyelim ki bir asal \(p\) için \(p^2\mid n\) olsun. Bu durumda \(p\mid n\) olduğu gibi \(p\mid \varphi(n)\) de olur; çünkü kareli bir asal çarpan içeren sayının totienti de aynı asaldan bir çarpan taşır. O halde \(p\mid n-\varphi(n)\).
Fakat \(n\equiv 0\pmod p\) olduğundan \(n-1\equiv -1\pmod p\) ve dolayısıyla \(p\nmid n-1\). Bu nedenle \(n-\varphi(n)\), \(n-1\)'i bölemez. Demek ki her geçerli bileşik çözüm kare-katsızdır:
$$n=p_1p_2\cdots p_r,\qquad \varphi(n)=\prod_{i=1}^{r}(p_i-1).$$
Koddaki çok-asallı dalın yalnızca farklı asalları biriktirmesinin nedeni tam olarak budur.
\(k\varphi(n)=(k-1)n+1\) eşitliğinden
$$\frac{n}{\varphi(n)}=\frac{k}{k-1}-\frac{1}{(k-1)\varphi(n)}\lt\frac{k}{k-1}$$
çıkar. \(n\) kare-katsız olduğundan aynı zamanda
$$\frac{n}{\varphi(n)}=\prod_{p\mid n}\frac{p}{p-1}$$
yazılır. \(x\mapsto \frac{x}{x-1}\) fonksiyonu \(x\gt 1\) için azalandır. Eğer bir asal bölen \(p\le k\) olsaydı,
$$\frac{p}{p-1}\ge \frac{k}{k-1}$$
olurdu; geri kalan çarpanların her biri de \(\gt 1\) olduğundan tüm çarpım en az \(\frac{k}{k-1}\) olurdu. Bu ise yukarıdaki sıkı üst sınıra aykırıdır. Sonuç:
$$p_i\gt k.$$
Bu tek eşitsizlik iki ana sınırı hemen açıklar. \(n=pq\) ise \(n\gt (k+1)^2\), dolayısıyla yalnızca \(k\le \sqrt{L}\) önemlidir. \(n\)'in en az üç asal çarpanı varsa \(n\gt (k+1)^3\) olur; bu yüzden o dalda sadece \(k\lt \sqrt[3]{L}\) incelenir.
\(n=pq\) ve \(p,q\) farklı asallar olsun. O zaman
$$\varphi(n)=(p-1)(q-1)=pq-p-q+1,$$
dolayısıyla
$$n-\varphi(n)=pq-(pq-p-q+1)=p+q-1.$$
Bunu \(n-1=k(n-\varphi(n))\) denklemine koyunca
$$pq-1=k(p+q-1)$$
elde edilir. Düzenlersek
$$pq-kp-kq+k^2=k^2-k+1,$$
yani
$$\boxed{(p-k)(q-k)=k^2-k+1.}$$
Şimdi
$$K(k)=k^2-k+1$$
tanımını yapalım. Verilen bir \(k\) için her semiprime çözüm, \(ab=K(k)\) bölen çiftinden
$$p=k+a,\qquad q=k+b$$
şeklinde gelir. Böylece semiprime dalı, \(K(k)\)'yi çarpanlara ayırma, tüm bölen çiftlerini üretme, bunları \(k\) kadar kaydırma ve asal testine sokma işine dönüşür.
Her \(K(k)\) değerini tek tek çarpanlara ayırmak yine de pahalı olurdu. Bunun yerine uygulamalar bu polinom değerlerini birlikte eler. Tek bir tek asal \(r\), \(K(k)\)'yi bölüyorsa
$$k^2-k+1\equiv 0\pmod r\iff (2k-1)^2\equiv -3\pmod r$$
olmalıdır. Bu da \(k\)'nın ancak
$$k\equiv \frac{1\pm \sqrt{-3}}{2}\pmod r$$
artık sınıflarından birinde bulunabileceğini söyler. \(r=3\) için bu tek sınıfa, yani \(k\equiv 2\pmod 3\)'e düşer. Diğer tek asallarda \(-3\)'ün karekökü ancak uygun kuadratik artık sınıflarında vardır; burada bu, \(r\equiv 1\pmod 3\) demektir. Bu yüzden eleme \(2\)'yi ve \(r\equiv 2\pmod 3\) olan asalları atlar, ilgili asallar için ise Tonelli-Shanks ile uygun sınıfları bulur. Ardından yalnızca bu aritmetik diziler üzerinde ilerleyip uygun asal kuvvetlerini \(K(k)\)'lerden söker.
Şimdi en az üç asal çarpanlı kare-katsız duruma geçelim. Farklı asallar \(q_1,\dots,q_t\) seçilmiş olsun ve
$$m=\prod_{i=1}^{t}q_i,\qquad A=\prod_{i=1}^{t}(q_i-1)$$
olsun. Son sayı \(n=mp\) ise \(\varphi(n)=A(p-1)\) olur. Bunu
$$k\varphi(n)=(k-1)n+1$$
eşitliğine koyarsak
$$kA(p-1)=(k-1)mp+1$$
elde edilir. \(p\)'li terimleri toplarsak
$$p\bigl(kA-(k-1)m\bigr)=kA+1,$$
yani son asal zorunlu olarak
$$\boxed{p=\frac{kA+1}{kA-(k-1)m}.}$$
şeklindedir. Rekürsiyonun omurgası budur. Bir dal ancak şu şartların hepsi sağlanırsa çözüm üretir: payda pozitiftir, paydaya tam bölünür, ortaya çıkan \(p\) asaldır, daha önce seçilen asallardan büyüktür ve \(mp\le L\) olur.
Semiprime örneği olarak \(n=15=3\cdot 5\) sayısı \(k=2\)'den gelir. Burada
$$K(2)=2^2-2+1=3,$$
ve \((1,3)\) bölen çifti
$$p=2+1=3,\qquad q=2+3=5$$
değerlerini verir. Gerçekten \(\varphi(15)=8\) olduğu için
$$\frac{15-1}{15-\varphi(15)}=\frac{14}{7}=2$$
sağlanır. Üç asal çarpanlı örnek olarak \(n=255=3\cdot 5\cdot 17\) de yine \(k=2\)'ye karşılık gelir. \(m=3\cdot 5=15\) ve \(A=(3-1)(5-1)=8\) seçildiğinde son asal formülü
$$p=\frac{2\cdot 8+1}{2\cdot 8-(2-1)\cdot 15}=\frac{17}{1}=17$$
sonucunu verir. \(\varphi(255)=128\) olduğundan
$$\frac{255-1}{255-\varphi(255)}=\frac{254}{127}=2$$
elde edilir. Bu iki örnek, kodun neden biri bölen çiftlerine dayanan, diğeri de zorlanmış son asal formülüne dayanan iki ayrı dal kullandığını açıkça gösterir.
Tam uygulamalar önce \(\sqrt{L}\)'ye kadar bütün asalları üretir. Bu liste hem \(K(k)\) için kurulan kongruans eleğinde, hem rekürsif kare-katsız aramada, hem de küçük sayıların asal olup olmadığını doğrudan yanıtlamada kullanılır. Daha büyük adaylar için ilgili 64-bit aralıkta deterministik Miller-Rabin testi uygulanır.
Her \(k\le \sqrt{L}\) için uygulama, \(K(k)\)'nin güncel kalan kısmını ve o ana kadar sökülmüş asal üslerini saklar. Elemede kullanılabilen her asal, \(k\) için bir ya da iki artık sınıf üretir; algoritma yalnızca bu diziler üzerinde ilerleyerek karşılık gelen \(K(k)\) değerlerinden o asalı çıkarır. Eleme tamamlanınca saklanan çarpanlardan tüm bölenler üretilir, bunlar \(p=k+a\) ve \(q=k+b\)'ye çevrilir, asal testine girer ve \(pq\le L\) şartıyla semiprime sonuç listesine eklenir.
Çok-asallı dal yalnızca \(k\lt \sqrt[3]{L}\) için çalışır. Arama, \(k\)'dan büyük ve giderek artan asallar üzerinde derinlik öncelikli ilerler; her düğümde \((m,A)\) çifti tutulur. Her adımda
$$p=\frac{kA+1}{kA-(k-1)m}$$
ifadesi kapanış adayı olarak hesaplanır. Bu ifade geçerli bir asal verirse ve daha önce en az iki asal seçilmişse, en az üç asal çarpanlı bir bileşik çözüm bulunmuş olur. Budama çok güçlüdür: \(kA-(k-1)m\le 0\) ise dalın devamından çözüm çıkmaz; sıradaki asal \(q\) için \(mq^2\gt L\) oluyorsa, hem \(q\) hem de ondan büyük son asal için artık yer kalmamıştır.
C++ sürümü tam optimize aramayı içerir ve iki toplama aşamasını iş parçacıklarıyla paralelleştirir. Ayrıca hızlı yöntemi doğrulamak için küçük limitlerde brute-force kontrolleri vardır. Java sürümü aynı sayı teorisi aramasını tek süreç içinde doğrudan uygular. Python sürümü ise bilinçli olarak ince tutulmuştur: derlenmiş çözücünün hazır olduğundan emin olur ve sonra aynı hızlı aramayı çağırır. Yani üç dilde de anlatılan matematik aynıdır.
Çalışma süresinin baskın kısmı semiprime aşamasıdır. Bu aşama tüm \(k\le \sqrt{L}\) değerlerini kapsar; ancak kongruans eleği sayesinde maliyet, her \(K(k)\)'yi bağımsız deneme bölmesiyle çarpanlara ayırmaktan çok daha düşüktür. Her asal yalnızca gerçekten bölebileceği artık sınıflarına uğrar ve bölen üretimi de doğrudan hazır çarpan tablosundan yapılır.
Çok-asallı dal daha küçüktür. Yalnızca \(k\lt \sqrt[3]{L}\) aralığında çalışır, yalnızca \(k\)'dan büyük artan asalları dener ve paydanın işareti, kapanış formülünün tam bölünebilmesi, bulunan son asalin asal olması ve \(n\le L\) sınırı ile agresif biçimde budanır. Bellek kullanımı makuldür: bir asal listesi, polinom değerleri için çarpan tabloları ve sonradan sıralanıp tekrarsızlaştırılan çözüm kümesi. Verimli olmasının nedeni, imkansız bir totient taramasını iki sıkı yapılandırılmış aramaya dönüştürmesidir.
Definamos la coresiliencia de un entero positivo por
$$C(n)=\frac{n-\varphi(n)}{n-1}.$$
El Problema 245 pide sumar todos los números compuestos \(n\le 2\cdot 10^{11}\) cuya coresiliencia es una fracción unitaria. Eso equivale a buscar todos los compuestos \(n\) tales que
$$\frac{n-1}{n-\varphi(n)}\in\mathbb Z.$$
Si escribimos
$$n-1=k(n-\varphi(n)),\qquad k\in\mathbb Z_{\ge 2},$$
entonces \(C(n)=1/k\). Recorrer todos los valores hasta \(2\cdot 10^{11}\) con totientes explícitos sería inviable, así que la solución transforma la condición de divisibilidad en una descripción rígida de la factorización prima de \(n\).
El parámetro natural de la búsqueda es \(k\). Al reordenar la ecuación básica obtenemos la identidad
$$k\varphi(n)=(k-1)n+1.$$
Toda la estrategia consiste en forzar esta igualdad contra la estructura prima de \(n\).
Supongamos que existe un primo \(p\) con \(p^2\mid n\). Entonces \(p\mid n\), y también \(p\mid \varphi(n)\), porque el totiente de cualquier número divisible por \(p^2\) conserva un factor \(p\). Por tanto \(p\mid n-\varphi(n)\).
Pero de \(n\equiv 0\pmod p\) se deduce \(n-1\equiv -1\pmod p\), así que \(p\nmid n-1\). En consecuencia, \(n-\varphi(n)\) no puede dividir a \(n-1\). Toda solución compuesta válida debe ser libre de cuadrados:
$$n=p_1p_2\cdots p_r,\qquad \varphi(n)=\prod_{i=1}^{r}(p_i-1).$$
Por eso la rama recursiva del algoritmo solo construye productos de primos distintos.
De \(k\varphi(n)=(k-1)n+1\) se obtiene
$$\frac{n}{\varphi(n)}=\frac{k}{k-1}-\frac{1}{(k-1)\varphi(n)}\lt\frac{k}{k-1}.$$
Como \(n\) es libre de cuadrados, también vale
$$\frac{n}{\varphi(n)}=\prod_{p\mid n}\frac{p}{p-1}.$$
La función \(x\mapsto \frac{x}{x-1}\) es decreciente para \(x\gt 1\). Si algún primo divisor cumpliera \(p\le k\), entonces
$$\frac{p}{p-1}\ge \frac{k}{k-1},$$
y al multiplicarlo por los demás factores, todos mayores que 1, el producto completo sería al menos \(\frac{k}{k-1}\), contradicción. Por lo tanto,
$$p_i\gt k.$$
Esta desigualdad explica los dos límites de búsqueda. Si \(n=pq\), entonces \(n\gt (k+1)^2\), así que solo interesa \(k\le \sqrt{L}\). Si \(n\) tiene al menos tres primos, entonces \(n\gt (k+1)^3\), y basta con explorar \(k\lt \sqrt[3]{L}\) en esa rama.
Sea \(n=pq\) con \(p\) y \(q\) primos distintos. Entonces
$$\varphi(n)=(p-1)(q-1)=pq-p-q+1,$$
y por tanto
$$n-\varphi(n)=pq-(pq-p-q+1)=p+q-1.$$
Al sustituir esto en \(n-1=k(n-\varphi(n))\) obtenemos
$$pq-1=k(p+q-1).$$
Reordenando,
$$pq-kp-kq+k^2=k^2-k+1,$$
de donde sale
$$\boxed{(p-k)(q-k)=k^2-k+1.}$$
Definimos ahora
$$K(k)=k^2-k+1.$$
Toda solución semiprima para ese \(k\) proviene de un par de divisores \(ab=K(k)\):
$$p=k+a,\qquad q=k+b.$$
Así, esta parte del problema se convierte en factorizar \(K(k)\), enumerar sus pares de divisores, trasladarlos por \(k\) y comprobar primalidad.
Factorizar cada \(K(k)\) de manera independiente seguiría siendo costoso. Las implementaciones cribarán los valores del polinomio de forma simultánea. Si un primo impar \(r\) divide a \(K(k)\), entonces
$$k^2-k+1\equiv 0\pmod r\iff (2k-1)^2\equiv -3\pmod r.$$
Por tanto, \(k\) debe caer en una de las clases de residuos
$$k\equiv \frac{1\pm \sqrt{-3}}{2}\pmod r.$$
Para \(r=3\), esto se reduce a la única clase \(k\equiv 2\pmod 3\). Para otros primos impares, una raíz cuadrada de \(-3\) existe solo en las clases cuadráticas adecuadas; aquí eso significa \(r\equiv 1\pmod 3\). Por eso la criba ignora \(2\) y todos los primos \(r\equiv 2\pmod 3\), y utiliza Tonelli-Shanks solo cuando el primo puede contribuir. Con esas clases en la mano, va eliminando potencias primas de todos los \(K(k)\) compatibles y construye las factorizaciones que luego alimentan la enumeración de divisores.
Consideremos ahora una solución libre de cuadrados con al menos tres factores primos. Supongamos que ya se eligieron primos distintos \(q_1,\dots,q_t\) y definimos
$$m=\prod_{i=1}^{t}q_i,\qquad A=\prod_{i=1}^{t}(q_i-1).$$
Si el número final es \(n=mp\), entonces \(\varphi(n)=A(p-1)\). Al sustituir en
$$k\varphi(n)=(k-1)n+1$$
se obtiene
$$kA(p-1)=(k-1)mp+1.$$
Agrupando los términos con \(p\),
$$p\bigl(kA-(k-1)m\bigr)=kA+1,$$
y por tanto
$$\boxed{p=\frac{kA+1}{kA-(k-1)m}.}$$
Esta fórmula es el eje de la búsqueda recursiva. Una rama solo produce una solución cuando el denominador es positivo, divide exactamente al numerador, el \(p\) resultante es primo, es mayor que los primos ya escogidos y además satisface \(mp\le L\).
El semiprimo \(n=15=3\cdot 5\) aparece con \(k=2\). En este caso
$$K(2)=2^2-2+1=3,$$
y el par de divisores \((1,3)\) produce
$$p=2+1=3,\qquad q=2+3=5.$$
En efecto, \(\varphi(15)=8\), así que
$$\frac{15-1}{15-\varphi(15)}=\frac{14}{7}=2.$$
Un ejemplo con tres primos es \(n=255=3\cdot 5\cdot 17\), también con \(k=2\). Tras elegir \(m=3\cdot 5=15\) y \(A=(3-1)(5-1)=8\), el último primo viene forzado por
$$p=\frac{2\cdot 8+1}{2\cdot 8-(2-1)\cdot 15}=\frac{17}{1}=17.$$
Como \(\varphi(255)=128\), se cumple
$$\frac{255-1}{255-\varphi(255)}=\frac{254}{127}=2.$$
Estos dos ejemplos muestran exactamente por qué el algoritmo se divide en una rama de pares de divisores y otra rama recursiva con primo final forzado.
Las implementaciones completas empiezan generando todos los primos hasta \(\sqrt{L}\). Esa lista sirve para la criba de congruencias de \(K(k)\), para proponer candidatos en la búsqueda recursiva libre de cuadrados y para responder de inmediato las consultas pequeñas de primalidad. Los candidatos más grandes se verifican con Miller-Rabin determinista dentro del rango de 64 bits relevante.
Para cada \(k\le \sqrt{L}\), la implementación guarda el resto actual de \(K(k)\) y los exponentes primos ya encontrados. Cada primo admisible en la criba aporta una o dos progresiones aritméticas para \(k\), y el algoritmo recorre exactamente esas progresiones mientras extrae potencias de ese primo de los correspondientes valores de \(K(k)\). Cuando termina la criba, genera todos los divisores a partir de la factorización almacenada, los traduce a \(p=k+a\) y \(q=k+b\), comprueba si ambos son primos y conserva el producto solo cuando \(pq\le L\).
La rama multi-prima solo se ejecuta para \(k\lt \sqrt[3]{L}\). Realiza una búsqueda en profundidad sobre primos estrictamente crecientes y mayores que \(k\), manteniendo el par \((m,A)\). En cada nodo se evalúa
$$p=\frac{kA+1}{kA-(k-1)m}$$
como posible paso de cierre. Siempre que produzca un primo válido y ya se hayan elegido al menos dos primos, se registra un compuesto con al menos tres factores. La poda es intensa: si \(kA-(k-1)m\le 0\), ya no puede existir ninguna continuación válida, y si el siguiente primo \(q\) obligara a \(mq^2\gt L\), entonces no queda espacio para \(q\) y para un último primo todavía mayor.
La versión en C++ contiene toda la búsqueda optimizada y paraleliza ambas fases de recolección con varios hilos. Además incluye comprobaciones por fuerza bruta en límites pequeños para validar el método rápido. La versión en Java reproduce la misma búsqueda aritmética directamente en un único proceso. La versión en Python es intencionadamente ligera: se asegura de que exista un solucionador compilado y luego llama a esa misma búsqueda rápida. En las tres, por tanto, la matemática subyacente es la misma.
La etapa semiprima domina el tiempo de ejecución. Recorre todos los \(k\le \sqrt{L}\), pero su costo real es mucho menor que factorizar cada \(K(k)\) por separado, porque cada primo de la criba visita solo las clases de residuos en las que realmente puede dividir a \(k^2-k+1\). Después, la enumeración de divisores se hace a partir de factorizaciones compactas ya construidas.
La rama multi-prima es más pequeña. Solo se ejecuta para \(k\lt \sqrt[3]{L}\), solo explora primos crecientes mayores que \(k\), y queda muy recortada por la positividad de \(kA-(k-1)m\), por la divisibilidad exacta de la fórmula del primo final, por la primalidad de ese último primo y por la cota \(n\le L\). La memoria sigue siendo moderada: lista de primos, tablas de factores de los valores polinómicos y conjunto de soluciones antes de ordenar y deduplicar. El método funciona bien porque reemplaza un barrido imposible de totientes hasta \(2\cdot 10^{11}\) por dos búsquedas aritméticas muy estructuradas.
定义一个正整数的 coresilience 为
$$C(n)=\frac{n-\varphi(n)}{n-1}.$$
第 245 题要求把所有满足 \(n\le 2\cdot 10^{11}\) 且 coresilience 是单位分数的合数全部求和。把条件改写一下，就是要找出所有合数 \(n\)，使得
$$\frac{n-1}{n-\varphi(n)}\in\mathbb Z.$$
如果记
$$n-1=k(n-\varphi(n)),\qquad k\in\mathbb Z_{\ge 2},$$
那么 \(C(n)=1/k\)。直接从 1 扫到 \(2\cdot 10^{11}\) 并逐个计算欧拉函数显然不可行，因此实现必须把这个整除条件转化成对素因子结构的分析。
整个搜索围绕整数 \(k\) 展开。把基本等式整理后得到
$$k\varphi(n)=(k-1)n+1.$$
后面的每一步推导，都是在问：一个整数的素因子分解要满足什么条件，才能与这条恒等式同时成立。
假设某个素数 \(p\) 满足 \(p^2\mid n\)。那么 \(p\mid n\) 是显然的，而且 \(p\mid \varphi(n)\) 也成立，因为只要 \(n\) 含有平方因子 \(p^2\)，它的欧拉函数仍然会保留一个 \(p\) 因子。因此 \(p\mid n-\varphi(n)\)。
但是 \(n\equiv 0\pmod p\) 会推出 \(n-1\equiv -1\pmod p\)，所以 \(p\nmid n-1\)。这样一来，\(n-\varphi(n)\) 就不可能整除 \(n-1\)。因此所有有效的合数解都必须是平方自由的：
$$n=p_1p_2\cdots p_r,\qquad \varphi(n)=\prod_{i=1}^{r}(p_i-1).$$
这正是递归分支只构造互不相同素数乘积的原因。
由 \(k\varphi(n)=(k-1)n+1\) 可得
$$\frac{n}{\varphi(n)}=\frac{k}{k-1}-\frac{1}{(k-1)\varphi(n)}\lt\frac{k}{k-1}.$$
另一方面，因为 \(n\) 平方自由，
$$\frac{n}{\varphi(n)}=\prod_{p\mid n}\frac{p}{p-1}.$$
函数 \(x\mapsto \frac{x}{x-1}\) 在 \(x\gt 1\) 时单调递减。如果某个素因子满足 \(p\le k\)，那么
$$\frac{p}{p-1}\ge \frac{k}{k-1}.$$
再乘上其他所有大于 1 的因子，整个乘积至少会达到 \(\frac{k}{k-1}\)，这与前面的严格上界矛盾。因此
$$p_i\gt k.$$
这一条不等式直接解释了代码里的两个范围界。若 \(n=pq\)，则 \(n\gt (k+1)^2\)，所以只有 \(k\le \sqrt{L}\) 才可能产生半素数解。若 \(n\) 至少有三个素因子，则 \(n\gt (k+1)^3\)，所以那一支只需要处理 \(k\lt \sqrt[3]{L}\)。
设 \(n=pq\)，其中 \(p,q\) 是两个不同的素数。那么
$$\varphi(n)=(p-1)(q-1)=pq-p-q+1,$$
从而
$$n-\varphi(n)=pq-(pq-p-q+1)=p+q-1.$$
把它代回 \(n-1=k(n-\varphi(n))\)，得到
$$pq-1=k(p+q-1).$$
整理后变成
$$pq-kp-kq+k^2=k^2-k+1,$$
于是
$$\boxed{(p-k)(q-k)=k^2-k+1.}$$
记
$$K(k)=k^2-k+1.$$
那么固定 \(k\) 以后，每一个半素数解都来自某个因子对 \(ab=K(k)\)：
$$p=k+a,\qquad q=k+b.$$
所以半素数部分的任务就是：分解 \(K(k)\)，枚举全部因子对，把它们平移成 \(p,q\)，再检查二者是否都是素数。
如果对每个 \(K(k)\) 都单独做分解，代价仍然太大。实现真正做的是对这些多项式值统一筛选。若某个奇素数 \(r\) 整除 \(K(k)\)，则
$$k^2-k+1\equiv 0\pmod r\iff (2k-1)^2\equiv -3\pmod r.$$
这说明 \(k\) 只能落在下面两个剩余类之一：
$$k\equiv \frac{1\pm \sqrt{-3}}{2}\pmod r.$$
当 \(r=3\) 时，它退化成唯一的类 \(k\equiv 2\pmod 3\)。当 \(r\) 是其他奇素数时，\(-3\) 只有在正确的二次剩余情形下才有平方根，这里等价于 \(r\equiv 1\pmod 3\)。因此筛法会直接跳过 \(2\) 和所有 \(r\equiv 2\pmod 3\) 的素数，只对可能出现的素数调用 Tonelli-Shanks 来求出 \(\sqrt{-3}\)，再顺着对应的等差数列去剥离 \(K(k)\) 里的素因子。
现在考虑至少有三个素因子的平方自由解。假设已经选定了不同素数 \(q_1,\dots,q_t\)，并记
$$m=\prod_{i=1}^{t}q_i,\qquad A=\prod_{i=1}^{t}(q_i-1).$$
如果最终整数是 \(n=mp\)，那么 \(\varphi(n)=A(p-1)\)。代入
$$k\varphi(n)=(k-1)n+1$$
得到
$$kA(p-1)=(k-1)mp+1.$$
把含 \(p\) 的项并到一边，便有
$$p\bigl(kA-(k-1)m\bigr)=kA+1,$$
于是最后一个素数必须满足
$$\boxed{p=\frac{kA+1}{kA-(k-1)m}.}$$
这就是递归搜索的核心公式。一个分支只有在分母为正、分母整除分子、求出的 \(p\) 是素数、它大于此前已经选中的素数并且 \(mp\le L\) 时，才会产出一个有效解。
半素数例子可以看 \(n=15=3\cdot 5\)，它对应 \(k=2\)。此时
$$K(2)=2^2-2+1=3,$$
因子对 \((1,3)\) 给出
$$p=2+1=3,\qquad q=2+3=5.$$
而 \(\varphi(15)=8\)，所以
$$\frac{15-1}{15-\varphi(15)}=\frac{14}{7}=2.$$
一个三素数例子是 \(n=255=3\cdot 5\cdot 17\)，同样对应 \(k=2\)。先取 \(m=3\cdot 5=15\)，\(A=(3-1)(5-1)=8\)，那么闭合公式给出
$$p=\frac{2\cdot 8+1}{2\cdot 8-(2-1)\cdot 15}=\frac{17}{1}=17.$$
再算 \(\varphi(255)=128\)，便得到
$$\frac{255-1}{255-\varphi(255)}=\frac{254}{127}=2.$$
这两个例子正好对应代码中的两条主线：半素数用因子对生成，多素数用“最后一个素数被公式强制确定”的递归搜索。
完整实现会先生成所有不超过 \(\sqrt{L}\) 的素数。这些素数同时用于 \(K(k)\) 的同余筛、平方自由递归搜索中的候选枚举，以及较小候选值的直接素性判断。更大的候选数则使用适用于当前 64 位范围的确定性 Miller-Rabin 测试。
对于每个 \(k\le \sqrt{L}\)，实现会保存 \(K(k)\) 当前剩余值及其已知素因子指数。每个允许进入筛法的素数都会给出一条或两条 \(k\) 的同余类，算法只沿着这些进程前进，并从对应的 \(K(k)\) 中不断除去该素数的幂。筛完以后，再根据记录下来的分解生成所有因子，把它们转换成 \(p=k+a\)、\(q=k+b\)，测试二者是否为素数，并在 \(pq\le L\) 时记录这个半素数。
多素数分支只在 \(k\lt \sqrt[3]{L}\) 时运行。它对所有大于 \(k\) 的递增素数做深度优先搜索，并在每个节点维护 \((m,A)\)。每一步都把
$$p=\frac{kA+1}{kA-(k-1)m}$$
当作潜在的闭合步骤来尝试。如果它确实给出一个合法素数，而且此前至少已经选过两个素数，那么就找到了一个至少含三个素因子的合数解。剪枝也很直接：若 \(kA-(k-1)m\le 0\)，这个分支以后不可能再闭合；若下一枚素数 \(q\) 已经使 \(mq^2\gt L\)，那么就连加入 \(q\) 和更大的最后一个素数都没有空间了。
C++ 实现包含完整的优化搜索，并把两条收集流程都分配给多个工作线程。它还带有小规模上界的暴力校验，用来确认快速算法无误。Java 实现则在单个进程里直接复现同一套数论搜索。Python 实现故意做得很薄，只负责确保编译后的求解器存在，然后调用相同的快速搜索。因此三种语言对应的是同一个数学方案，而不是三套不同的思路。
运行时间的主导部分是半素数阶段。它覆盖全部 \(k\le \sqrt{L}\)，但由于同余筛只访问那些真正可能让 \(k^2-k+1\) 被某个素数整除的剩余类，因此远快于对每个 \(K(k)\) 独立试除。完成筛法后，因子枚举也建立在已经得到的紧凑分解之上。
多素数分支规模更小。它只处理 \(k\lt \sqrt[3]{L}\)，只尝试大于 \(k\) 的递增素数，并且会被分母符号、闭合公式的整除性、最后一个素数的素性以及 \(n\le L\) 的上界强力剪枝。内存占用较为温和，主要是素数表、多项式值的因子表以及去重前的答案集合。这个方法之所以高效，是因为它把“不可能的 totient 全范围扫描”压缩成了两次高度结构化的数论搜索。
Определим coresilience положительного целого числа как
$$C(n)=\frac{n-\varphi(n)}{n-1}.$$
В задаче 245 требуется просуммировать все составные числа \(n\le 2\cdot 10^{11}\), у которых coresilience является единичной дробью. Это равносильно условию
$$\frac{n-1}{n-\varphi(n)}\in\mathbb Z.$$
Если записать
$$n-1=k(n-\varphi(n)),\qquad k\in\mathbb Z_{\ge 2},$$
то получится \(C(n)=1/k\). Прямой перебор с вычислением \(\varphi(n)\) для всех значений до \(2\cdot 10^{11}\) невозможен, поэтому решение переводит условие делимости в жесткие ограничения на разложение числа \(n\) на простые множители.
Главный параметр поиска — целое число \(k\). После перестановки членов базовое условие принимает вид
$$k\varphi(n)=(k-1)n+1.$$
Дальше нужно понять, какие именно разложения \(n\) на простые множители совместимы с этим тождеством.
Пусть для некоторого простого \(p\) выполняется \(p^2\mid n\). Тогда \(p\mid n\), и одновременно \(p\mid \varphi(n)\), потому что у числа, содержащего квадрат \(p^2\), функция Эйлера тоже сохраняет множитель \(p\). Значит, \(p\mid n-\varphi(n)\).
Но из \(n\equiv 0\pmod p\) следует \(n-1\equiv -1\pmod p\), так что \(p\nmid n-1\). Следовательно, \(n-\varphi(n)\) не может делить \(n-1\). Поэтому всякое подходящее составное число обязательно квадратсвободно:
$$n=p_1p_2\cdots p_r,\qquad \varphi(n)=\prod_{i=1}^{r}(p_i-1).$$
Именно поэтому рекурсивная ветвь алгоритма перебирает только произведения различных простых.
Из равенства \(k\varphi(n)=(k-1)n+1\) получаем
$$\frac{n}{\varphi(n)}=\frac{k}{k-1}-\frac{1}{(k-1)\varphi(n)}\lt\frac{k}{k-1}.$$
Так как \(n\) квадратсвободно,
$$\frac{n}{\varphi(n)}=\prod_{p\mid n}\frac{p}{p-1}.$$
Функция \(x\mapsto \frac{x}{x-1}\) убывает при \(x\gt 1\). Если бы какой-то простой делитель удовлетворял \(p\le k\), то
$$\frac{p}{p-1}\ge \frac{k}{k-1},$$
а умножение на остальные множители, каждый из которых больше 1, дало бы произведение не меньше \(\frac{k}{k-1}\). Это противоречит строгой верхней оценке. Значит,
$$p_i\gt k.$$
Отсюда сразу следуют границы поиска. Если \(n=pq\), то \(n\gt (k+1)^2\), поэтому достаточно рассматривать \(k\le \sqrt{L}\). Если же у \(n\) хотя бы три простых множителя, то \(n\gt (k+1)^3\), и в этой ветви нужно изучать только \(k\lt \sqrt[3]{L}\).
Пусть \(n=pq\), где \(p\) и \(q\) — различные простые. Тогда
$$\varphi(n)=(p-1)(q-1)=pq-p-q+1,$$
следовательно,
$$n-\varphi(n)=pq-(pq-p-q+1)=p+q-1.$$
Подставляя это в \(n-1=k(n-\varphi(n))\), получаем
$$pq-1=k(p+q-1).$$
После преобразования выходит
$$pq-kp-kq+k^2=k^2-k+1,$$
то есть
$$\boxed{(p-k)(q-k)=k^2-k+1.}$$
Обозначим
$$K(k)=k^2-k+1.$$
Тогда любая полупростая подходящая величина для данного \(k\) возникает из пары делителей \(ab=K(k)\):
$$p=k+a,\qquad q=k+b.$$
Таким образом, эта ветвь сводится к факторизации \(K(k)\), перебору пар делителей и проверке того, что сдвинутые значения действительно простые.
Факторизовать каждое \(K(k)\) по отдельности было бы слишком дорого. Поэтому реализации просеивают значения полинома сразу для всех \(k\). Если нечётный простой \(r\) делит \(K(k)\), то
$$k^2-k+1\equiv 0\pmod r\iff (2k-1)^2\equiv -3\pmod r.$$
Значит, \(k\) должен лежать в одном из классов вычетов
$$k\equiv \frac{1\pm \sqrt{-3}}{2}\pmod r.$$
Для \(r=3\) это вырождается в единственный класс \(k\equiv 2\pmod 3\). Для остальных нечётных простых корень из \(-3\) существует только в допустимых квадратичных классах; в данной задаче это означает \(r\equiv 1\pmod 3\). Поэтому сито сразу пропускает \(2\) и все простые \(r\equiv 2\pmod 3\), а для остальных находит \(\sqrt{-3}\) с помощью Tonelli-Shanks и проходит только по нужным арифметическим прогрессиям \(k\).
Теперь рассмотрим квадратсвободную ветвь с как минимум тремя простыми множителями. Пусть уже выбраны различные простые \(q_1,\dots,q_t\), и введены обозначения
$$m=\prod_{i=1}^{t}q_i,\qquad A=\prod_{i=1}^{t}(q_i-1).$$
Если итоговое число равно \(n=mp\), тогда \(\varphi(n)=A(p-1)\). Подстановка в
$$k\varphi(n)=(k-1)n+1$$
дает
$$kA(p-1)=(k-1)mp+1.$$
Собирая члены с \(p\), получаем
$$p\bigl(kA-(k-1)m\bigr)=kA+1,$$
откуда следует принудительная формула
$$\boxed{p=\frac{kA+1}{kA-(k-1)m}.}$$
Именно она лежит в основе рекурсивного поиска. Ветвь принимается только тогда, когда знаменатель положителен, он делит числитель без остатка, полученное \(p\) простое, больше ранее выбранных простых и удовлетворяет ограничению \(mp\le L\).
Полупростой пример — \(n=15=3\cdot 5\), который соответствует \(k=2\). Здесь
$$K(2)=2^2-2+1=3,$$
и пара делителей \((1,3)\) дает
$$p=2+1=3,\qquad q=2+3=5.$$
Действительно, \(\varphi(15)=8\), поэтому
$$\frac{15-1}{15-\varphi(15)}=\frac{14}{7}=2.$$
Пример с тремя простыми множителями — \(n=255=3\cdot 5\cdot 17\), опять же при \(k=2\). После выбора \(m=3\cdot 5=15\) и \(A=(3-1)(5-1)=8\) формула для последнего простого дает
$$p=\frac{2\cdot 8+1}{2\cdot 8-(2-1)\cdot 15}=\frac{17}{1}=17.$$
Так как \(\varphi(255)=128\), получаем
$$\frac{255-1}{255-\varphi(255)}=\frac{254}{127}=2.$$
Эти два примера точно отражают две идеи алгоритма: перебор пар делителей в полупростой ветви и рекурсивное восстановление последнего простого множителя в квадратсвободной многопростой ветви.
Полные реализации сначала строят все простые числа до \(\sqrt{L}\). Эта таблица используется в сите для \(K(k)\), в рекурсивном переборе квадратсвободных произведений и для мгновенных ответов на маленькие проверки простоты. Более крупные кандидаты тестируются детерминированным вариантом Миллера-Рабина в нужном 64-битном диапазоне.
Для каждого \(k\le \sqrt{L}\) алгоритм хранит текущий остаток от \(K(k)\) и уже найденные показатели простых множителей. Каждый допустимый простой ситового этапа задает одну или две прогрессии значений \(k\), и именно по ним снимаются соответствующие степени этого простого из подходящих \(K(k)\). После завершения ситового этапа из сохраненной факторизации генерируются все делители, затем они переводятся в \(p=k+a\) и \(q=k+b\), проверяются на простоту, и при условии \(pq\le L\) произведение добавляется в набор полупростых ответов.
Многопростая ветвь запускается только для \(k\lt \sqrt[3]{L}\). Она выполняет поиск в глубину по строго возрастающим простым \(\gt k\), поддерживая текущее состояние \((m,A)\). В каждой вершине вычисляется
$$p=\frac{kA+1}{kA-(k-1)m}$$
как возможный завершающий шаг. Если формула дает корректный простой и до этого уже выбраны как минимум два простых множителя, найдено составное число хотя бы с тремя простыми делителями. Отсечение очень сильное: если \(kA-(k-1)m\le 0\), завершение уже невозможно, а если следующий простой \(q\) сразу дает \(mq^2\gt L\), то места для \(q\) и ещё большего финального простого уже не остается.
Версия на C++ содержит полный оптимизированный поиск и распараллеливает обе фазы сбора результатов. Кроме того, в ней есть проверочные brute-force прогоны на малых границах, подтверждающие правильность быстрого метода. Версия на Java воспроизводит тот же арифметический поиск внутри одного процесса. Версия на Python намеренно минималистична: она лишь обеспечивает наличие скомпилированного решателя и вызывает тот же быстрый алгоритм. Иначе говоря, все три реализации описывают одну и ту же математику.
Основную часть времени занимает полупростая ветвь. Она проходит по всем \(k\le \sqrt{L}\), но стоит значительно дешевле, чем независимая факторизация каждого \(K(k)\), потому что сито посещает только те классы вычетов, в которых соответствующий простой вообще может делить \(k^2-k+1\). После этого перечисление делителей выполняется уже по компактным готовым факторизациям.
Многопростая ветвь заметно меньше. Она работает только для \(k\lt \sqrt[3]{L}\), рассматривает только возрастающие простые \(\gt k\) и сильно обрезается условиями положительности знаменателя, точной делимости в формуле последнего простого, простоты найденного завершающего множителя и ограничения \(n\le L\). Память расходуется умеренно: таблица простых, данные по факторизациям полиномиальных значений и множество найденных ответов до сортировки и удаления дублей. Эффективность достигается тем, что вместо невозможного тотального прохода по \(\varphi(n)\) до \(2\cdot 10^{11}\) алгоритм выполняет две очень узко направленные поисковые процедуры.
لنعرّف قيمة coresilience للعدد الصحيح الموجب بالصيغة
$$C(n)=\frac{n-\varphi(n)}{n-1}.$$
تطلب المسألة 245 جمع جميع الأعداد المركبة \(n\le 2\cdot 10^{11}\) التي تكون فيها coresilience كسرًا وحديًا. وهذا مكافئ تمامًا للبحث عن كل عدد مركب \(n\) يحقق
$$\frac{n-1}{n-\varphi(n)}\in\mathbb Z.$$
إذا كتبنا
$$n-1=k(n-\varphi(n)),\qquad k\in\mathbb Z_{\ge 2},$$
فإن \(C(n)=1/k\). ومن الواضح أن فحص جميع القيم حتى \(2\cdot 10^{11}\) مع حساب \(\varphi(n)\) مباشرة غير عملي، لذلك يحوّل الحل شرط القسمة هذا إلى شروط صارمة على البنية الأولية للعدد \(n\).
المعامل الطبيعي الذي ينظم البحث هو العدد الصحيح \(k\). وبعد إعادة ترتيب المعادلة الأساسية نحصل على العلاقة
$$k\varphi(n)=(k-1)n+1.$$
كل خطوات الحل اللاحقة هي استخراج ما تفرضه هذه المساواة على تحليل \(n\) إلى عوامل أولية.
افترض أن هناك عددًا أوليًا \(p\) بحيث \(p^2\mid n\). عندئذٍ يكون \(p\mid n\)، كما أن \(p\mid \varphi(n)\) أيضًا، لأن دالة أويلر لعدد يحوي العامل \(p^2\) تحتفظ بعامل \(p\). إذن \(p\mid n-\varphi(n)\).
لكن من \(n\equiv 0\pmod p\) نحصل على \(n-1\equiv -1\pmod p\)، وبالتالي \(p\nmid n-1\). وهذا يعني أن \(n-\varphi(n)\) لا يمكن أن يقسم \(n-1\). لذلك فكل حل مركب صالح لا بد أن يكون خاليًا من المربعات:
$$n=p_1p_2\cdots p_r,\qquad \varphi(n)=\prod_{i=1}^{r}(p_i-1).$$
ولهذا السبب تحديدًا فإن الفرع العودي في التنفيذ لا يبني إلا جداءات من أعداد أولية مختلفة.
من المعادلة \(k\varphi(n)=(k-1)n+1\) نستنتج
$$\frac{n}{\varphi(n)}=\frac{k}{k-1}-\frac{1}{(k-1)\varphi(n)}\lt\frac{k}{k-1}.$$
وبما أن \(n\) خالٍ من المربعات، فلدينا أيضًا
$$\frac{n}{\varphi(n)}=\prod_{p\mid n}\frac{p}{p-1}.$$
والدالة \(x\mapsto \frac{x}{x-1}\) متناقصة عندما \(x\gt 1\). فإذا وُجد عامل أولي يحقق \(p\le k\)، فإن
$$\frac{p}{p-1}\ge \frac{k}{k-1},$$
ومع ضربه في بقية العوامل، وكلها أكبر من 1، يصبح الناتج الكلي على الأقل \(\frac{k}{k-1}\)، وهذا يناقض الحد الأعلى الصارم أعلاه. إذن
$$p_i\gt k.$$
ومن هنا تظهر حدود البحث مباشرة. إذا كان \(n=pq\)، فلدينا \(n\gt (k+1)^2\)، لذلك لا نحتاج إلا إلى \(k\le \sqrt{L}\). وإذا كان \(n\) يحوي ثلاثة عوامل أولية أو أكثر، فإن \(n\gt (k+1)^3\)، ولهذا يكفي في ذلك الفرع فحص \(k\lt \sqrt[3]{L}\).
لنفرض أن \(n=pq\) حيث \(p\) و\(q\) أوليان مختلفان. عندئذٍ
$$\varphi(n)=(p-1)(q-1)=pq-p-q+1,$$
ومن ثم
$$n-\varphi(n)=pq-(pq-p-q+1)=p+q-1.$$
وبالتعويض في \(n-1=k(n-\varphi(n))\) نحصل على
$$pq-1=k(p+q-1).$$
وبإعادة الترتيب يظهر أن
$$pq-kp-kq+k^2=k^2-k+1,$$
أي
$$\boxed{(p-k)(q-k)=k^2-k+1.}$$
لنعرّف
$$K(k)=k^2-k+1.$$
كل حل شبه أولي لهذا \(k\) ينتج من زوج قواسم \(ab=K(k)\) عبر
$$p=k+a,\qquad q=k+b.$$
وهكذا تصبح هذه المرحلة قائمة على تحليل \(K(k)\) إلى عوامله، وتوليد أزواج القواسم، ثم إزاحتها بمقدار \(k\) واختبار أوليتها.
تحليل كل قيمة \(K(k)\) على حدة ما زال مكلفًا. لذلك تقوم التطبيقات بغربلة قيم كثير الحدود مجتمعة. إذا كان عدد أولي فردي \(r\) يقسم \(K(k)\)، فلدينا
$$k^2-k+1\equiv 0\pmod r\iff (2k-1)^2\equiv -3\pmod r.$$
وهذا يعني أن \(k\) لا بد أن ينتمي إلى أحد الصنفين الباقيين
$$k\equiv \frac{1\pm \sqrt{-3}}{2}\pmod r.$$
عندما \(r=3\) ينهار هذا إلى الصنف الوحيد \(k\equiv 2\pmod 3\). أما للأعداد الأولية الفردية الأخرى، فلا يوجد جذر تربيعي لـ \(-3\) إلا في أصناف البواقي المناسبة، وهنا يعادل ذلك الشرط \(r\equiv 1\pmod 3\). ولهذا تتجاوز الغربلة العدد \(2\) وكل الأعداد الأولية التي تحقق \(r\equiv 2\pmod 3\)، وتستخدم Tonelli-Shanks فقط عندما يكون من الممكن أن يساهم العدد الأولي فعلًا، ثم تمر على المتتاليات الحسابية الموافقة لتجريد قيم \(K(k)\) من قوى ذلك العامل الأولي.
لننظر الآن إلى الفرع الخالي من المربعات عندما يكون هناك ثلاثة عوامل أولية على الأقل. لنفترض أننا اخترنا بالفعل أعدادًا أولية مختلفة \(q_1,\dots,q_t\)، وعرّفنا
$$m=\prod_{i=1}^{t}q_i,\qquad A=\prod_{i=1}^{t}(q_i-1).$$
إذا كان العدد النهائي هو \(n=mp\)، فإن \(\varphi(n)=A(p-1)\). وبالتعويض في
$$k\varphi(n)=(k-1)n+1$$
نحصل على
$$kA(p-1)=(k-1)mp+1.$$
وبجمع حدود \(p\) في طرف واحد يظهر أن
$$p\bigl(kA-(k-1)m\bigr)=kA+1,$$
ومن ثم يكون العامل الأولي الأخير محددًا بالضرورة بواسطة
$$\boxed{p=\frac{kA+1}{kA-(k-1)m}.}$$
هذه هي الصيغة الأساسية في البحث العودي. لا تُقبل أي شجرة بحث إلا إذا كان المقام موجبًا، وكان يقسم البسط تمامًا، وكانت القيمة الناتجة \(p\) أولية، وأكبر من العوامل المختارة سابقًا، وتحقق كذلك \(mp\le L\).
مثال شبه أولي بسيط هو \(n=15=3\cdot 5\)، ويقابله \(k=2\). هنا
$$K(2)=2^2-2+1=3,$$
وزوج القواسم \((1,3)\) يعطي
$$p=2+1=3,\qquad q=2+3=5.$$
وبالفعل \(\varphi(15)=8\)، ولذلك
$$\frac{15-1}{15-\varphi(15)}=\frac{14}{7}=2.$$
ومثال بثلاثة عوامل أولية هو \(n=255=3\cdot 5\cdot 17\)، وهو أيضًا يأتي من \(k=2\). بعد اختيار \(m=3\cdot 5=15\) و\(A=(3-1)(5-1)=8\)، تعطي صيغة العامل الأخير
$$p=\frac{2\cdot 8+1}{2\cdot 8-(2-1)\cdot 15}=\frac{17}{1}=17.$$
ومع \(\varphi(255)=128\) نحصل على
$$\frac{255-1}{255-\varphi(255)}=\frac{254}{127}=2.$$
وهذان المثالان يوضحان بالضبط لماذا ينقسم الحل إلى فرع لأزواج القواسم في الحالة شبه الأولية، وفرع عودي يعتمد على صيغة العامل الأولي الأخير في الحالة متعددة العوامل.
تبدأ التطبيقات الكاملة بتوليد جميع الأعداد الأولية حتى \(\sqrt{L}\). وتُستخدم هذه القائمة في غربلة قيم \(K(k)\)، وفي اقتراح العوامل في البحث العودي الخالي من المربعات، وفي الإجابة السريعة عن اختبارات الأولية الصغيرة. أما المرشحون الأكبر حجمًا فيُفحصون باختبار Miller-Rabin الحتمي ضمن مجال 64-بت المناسب.
لكل \(k\le \sqrt{L}\) تحتفظ الشيفرة بباقي \(K(k)\) الحالي وبالأسس الأولية التي كُشفت حتى تلك اللحظة. كل عدد أولي صالح في مرحلة الغربلة يحدد صنفًا واحدًا أو صنفين من أصناف \(k\) الباقية، وتتحرك الخوارزمية فقط على هذه التقدّمات الحسابية بينما تزيل قوى هذا العدد الأولي من القيم المطابقة لـ \(K(k)\). بعد انتهاء الغربلة، تُولَّد جميع القواسم من التحليل المخزن، ثم تُحوَّل إلى \(p=k+a\) و\(q=k+b\)، وتُفحص أوليتهما، ويُسجَّل الجداء فقط إذا تحقق الشرط \(pq\le L\).
فرع العوامل الأولية المتعددة يعمل فقط عندما \(k\lt \sqrt[3]{L}\). وهو ينفذ بحثًا بعمق أولًا على أعداد أولية متزايدة وأكبر من \(k\)، مع تتبع الزوج \((m,A)\) في كل عقدة. في كل خطوة تُختبر الصيغة
$$p=\frac{kA+1}{kA-(k-1)m}$$
بوصفها خطوة إغلاق محتملة. فإذا أعطت عددًا أوليًا صالحًا وكان قد تم اختيار عاملين أوليين على الأقل قبلها، سُجل عدد مركب يملك ثلاثة عوامل أولية أو أكثر. وتكون عملية القص قوية جدًا: إذا صار \(kA-(k-1)m\le 0\) فلن توجد أي متابعة ناجحة، وإذا كان العدد الأولي التالي \(q\) يفرض بالفعل \(mq^2\gt L\)، فلن يبقى مجال لـ \(q\) ولعامل أخير أكبر منه.
نسخة C++ تحتوي على البحث المحسن كاملًا وتوازي مرحلتي الجمع باستخدام خيوط عمل متعددة. كما تتضمن اختبارات brute-force عند حدود صغيرة للتحقق من صحة الطريقة السريعة. نسخة Java تعيد تنفيذ البحث العددي نفسه داخل عملية واحدة. أما نسخة Python فهي نحيفة عمدًا: تتأكد فقط من وجود محلل مترجم ثم تستدعي نفس البحث السريع. لذلك فاللغات الثلاث تعرض المنهج الرياضي نفسه لا ثلاث خوارزميات مختلفة.
الجزء المهيمن زمنيًا هو مرحلة الأعداد شبه الأولية. فهي تغطي كل \(k\le \sqrt{L}\)، لكن تكلفتها أقل بكثير من تحليل كل قيمة \(K(k)\) على نحو مستقل، لأن الغربلة لا تزور إلا أصناف البواقي التي يمكن فيها فعلًا أن يقسم عدد أولي ما التعبير \(k^2-k+1\). وبعد ذلك يتم توليد القواسم من تحليلات أولية مدمجة جاهزة.
أما الفرع متعدد العوامل الأولية فهو أصغر بكثير. فهو يعمل فقط حتى \(k\lt \sqrt[3]{L}\)، ويجرّب أعدادًا أولية متزايدة أكبر من \(k\)، ويُقص بقوة بواسطة شرط إيجابية المقام، وبشرط القسمة التامة في صيغة العامل الأخير، وبأولية هذا العامل، وبالقيد \(n\le L\). واستهلاك الذاكرة معتدل: قائمة للأعداد الأولية، وجداول لتحليل قيم كثير الحدود، ومجموعة للحلول المقبولة قبل الفرز وإزالة التكرار. تكمن كفاءة الطريقة في أنها تستبدل مسحًا مستحيلًا حتى \(2\cdot 10^{11}\) ببحثين عدديين عاليي البنية.