For the Project Euler parameters \(N=40{,}000{,}000\) and \(T=25\), define the totient chain of a positive integer by repeatedly applying Euler's totient function until the value reaches \(1\):
$$n \to \varphi(n) \to \varphi(\varphi(n)) \to \cdots \to 1.$$
The problem asks for the sum of all primes \(p < N\) whose chain has length exactly \(T\). If we denote the chain length by \(\ell(n)\), then the target quantity is
$$S(N,T)=\sum_{\substack{p < N\\ \ell(p)=T}} p,$$
where the sum runs over primes. A naive prime-by-prime search would recompute the same totient values again and again. The implementations avoid that duplication by building one global table of \(\varphi(n)\) and one global table of chain lengths.
The key object is the directed map \(n \mapsto \varphi(n)\). For Problem 214, every useful fact comes from understanding how this map behaves on all integers up to the bound, not just on the primes that appear in the final sum.
For every integer \(n > 1\), Euler's totient satisfies \(\varphi(n) < n\). Therefore repeated iteration cannot cycle above \(1\); it must eventually terminate at \(1\). This makes the chain length well defined for every positive integer.
The natural base case is
$$\ell(1)=1,$$
because the chain starting at \(1\) already consists of a single term. For \(n \ge 2\), one step of the chain removes the first term and leaves the chain starting at \(\varphi(n)\), so
$$\ell(n)=1+\ell(\varphi(n)).$$
This is the central recurrence in all three implementations. Because \(\varphi(n)\) is strictly smaller than \(n\), the values form a dependency graph that is automatically topologically ordered by the ordinary numeric order \(1,2,3,\dots,N\).
If \(p\) is prime, then every number \(1 \le a \lt p\) is coprime to \(p\), so
$$\varphi(p)=p-1.$$
Hence every candidate prime immediately reduces to a composite even number:
$$\ell(p)=1+\ell(p-1).$$
This does not mean we can skip the composite numbers; on the contrary, the prime case depends on them directly. Problem 214 is solved only after the chain length has been computed for every integer up to the bound.
The implementations compute all totients with a linear sieve. Maintain a growing list of discovered primes. When an integer \(i\) has not been marked composite, it is prime, so its totient is known immediately:
$$\varphi(i)=i-1.$$
Then combine \(i\) with each known prime \(q\) to form \(v=i q\). Two cases determine \(\varphi(v)\):
$$\varphi(iq)= \begin{cases} \varphi(i)\,q, & q \mid i,\\ \varphi(i)\,(q-1), & q \nmid i. \end{cases}$$
The second line is just multiplicativity for coprime factors: if \(\gcd(i,q)=1\), then \(\varphi(iq)=\varphi(i)\varphi(q)=\varphi(i)(q-1)\). The first line follows from writing \(i=q^a m\) with \(q \nmid m\): then
$$\varphi(i)=q^{a-1}(q-1)\varphi(m),\qquad \varphi(iq)=q^a(q-1)\varphi(m)=q\,\varphi(i).$$
The linear sieve stops the inner generation as soon as it uses the smallest prime divisor of \(i\). That invariant ensures each composite is produced exactly once, so the totient table is filled in overall \(O(N)\) time.
A few small chains show the recurrence in action:
$$5 \to 4 \to 2 \to 1,\qquad \ell(5)=4,$$
$$7 \to 6 \to 2 \to 1,\qquad \ell(7)=4,$$
$$11 \to 10 \to 4 \to 2 \to 1,\qquad \ell(11)=5.$$
So for the small test case \(N=100\) and \(T=4\), the qualifying primes are \(5\) and \(7\), whose sum is \(12\). For \(N=1000\) and \(T=5\), the qualifying primes are \(11,13,19\), whose sum is \(43\). Those two values are exactly the checkpoint cases used by the C++ implementation.
After the sieve has produced the prime list and all values \(\varphi(n)\), and after the recurrence has produced all values \(\ell(n)\), nothing difficult remains. One final pass over the prime list is enough: keep the primes with \(\ell(p)=T\) and add them. There is no need to follow any chain on demand during this last stage, because each chain length is already available as a table lookup.
The C++, Python, and Java implementations all start with a linear sieve over \(2,3,\dots,N\). In the same loop they identify primes, mark composites, and assign \(\varphi(n)\) using the two-case recurrence above. This is the mathematically decisive preprocessing step, because every later calculation depends on \(\varphi(n)\).
With \(\varphi(1),\varphi(2),\dots,\varphi(N)\) already known, the implementations allocate a second array for chain lengths, set \(\ell(1)=1\), and process \(n=2,3,\dots,N\) in order. Each entry is obtained from the recurrence
$$\ell(n)=1+\ell(\varphi(n)).$$
Because \(\varphi(n) < n\), the right-hand side always refers to an earlier entry. No recursion is needed; the table is filled iteratively in one linear sweep.
Once chain lengths are known, the final pass is over primes only. Whenever a prime has the target length, it is added to the running total. The Python and Java implementations hardcode the Project Euler parameters \(N=40{,}000{,}000\) and \(T=25\). The C++ implementation uses the same algorithm but also supports alternate bounds and target lengths, and it verifies itself on the two small checkpoint sums before the full computation.
The linear sieve is \(O(N)\) time because each composite number is generated once. The chain-length pass is another \(O(N)\) sweep, and the final prime filter is \(O(\pi(N))\), which is contained in \(O(N)\). Therefore the overall running time is linear in the bound:
$$O(N).$$
The memory usage is also \(O(N)\): one array for composite markers, one for totients, one for chain lengths, and a list of primes. For Problem 214 this linear behavior is essential, because \(N=40{,}000{,}000\) is far beyond the range where repeated per-prime chain simulation would be comfortable.
Für die Parameter des Problems \(N=40{,}000{,}000\) und \(T=25\) wird für jede positive Zahl eine Totient-Kette gebildet, indem man die eulersche Phi-Funktion so lange iteriert, bis \(1\) erreicht ist:
$$n \to \varphi(n) \to \varphi(\varphi(n)) \to \cdots \to 1.$$
Gesucht ist die Summe aller Primzahlen \(p < N\), deren Kettenlänge genau \(T\) beträgt. Bezeichnet \(\ell(n)\) die Länge der Kette von \(n\), dann ist die Zielgröße
$$S(N,T)=\sum_{\substack{p < N\\ \ell(p)=T}} p,$$
wobei nur über Primzahlen summiert wird. Ein naiver Ansatz würde für viele verschiedene Primzahlen immer wieder dieselben Totientwerte neu berechnen. Die Implementierungen vermeiden das, indem sie \(\varphi(n)\) und \(\ell(n)\) für alle Zahlen bis zur Schranke einmal global vorrechnen.
Das zentrale Objekt ist die Abbildung \(n \mapsto \varphi(n)\). Für Problem 214 reicht es nicht, einzelne Primzahlen isoliert zu betrachten; man muss verstehen, wie diese Abbildung auf allen Zahlen bis \(N\) wirkt.
Für jede ganze Zahl \(n > 1\) gilt \(\varphi(n) < n\). Daher kann die Iteration oberhalb von \(1\) keinen Zyklus bilden; sie muss irgendwann bei \(1\) ankommen. Damit ist die Kettenlänge für jede positive Zahl wohldefiniert.
Der natürliche Anfangswert ist
$$\ell(1)=1,$$
denn die Kette von \(1\) besteht bereits aus genau einem Glied. Für \(n \ge 2\) entfernt ein Totient-Schritt nur das erste Glied und lässt die Restkette bei \(\varphi(n)\) beginnen. Also gilt
$$\ell(n)=1+\ell(\varphi(n)).$$
Das ist die entscheidende Rekursion aller drei Implementierungen. Weil \(\varphi(n)\) echt kleiner als \(n\) ist, entsteht automatisch eine Abhängigkeitsstruktur, die in der natürlichen Reihenfolge \(1,2,3,\dots,N\) topologisch sortiert ist.
Ist \(p\) prim, dann sind alle Zahlen \(1 \le a < p\) zu \(p\) teilerfremd, also
$$\varphi(p)=p-1.$$
Jede Kandidaten-Primzahl springt deshalb sofort zu einer geraden zusammengesetzten Zahl:
$$\ell(p)=1+\ell(p-1).$$
Gerade das zeigt, warum man die zusammengesetzten Zahlen nicht umgehen kann. Die Frage nach einer Primzahlkette wird sofort zu einer Frage über bereits berechnete Werte unterhalb von \(p\).
Die Implementierungen berechnen alle Totientwerte mit einem linearen Sieb. Man verwaltet eine wachsende Liste bereits gefundener Primzahlen. Wenn eine Zahl \(i\) noch nicht als zusammengesetzt markiert ist, dann ist sie prim und man kennt sofort
$$\varphi(i)=i-1.$$
Danach bildet man für jede bekannte Primzahl \(q\) das Produkt \(v=i q\). Der Wert \(\varphi(v)\) folgt aus genau zwei Fällen:
$$\varphi(iq)= \begin{cases} \varphi(i)\,q, & q \mid i,\\ \varphi(i)\,(q-1), & q \nmid i. \end{cases}$$
Die zweite Zeile ist die Multiplikativität für teilerfremde Faktoren. Die erste Zeile erhält man durch \(i=q^a m\) mit \(q \nmid m\): dann ist
$$\varphi(i)=q^{a-1}(q-1)\varphi(m),\qquad \varphi(iq)=q^a(q-1)\varphi(m)=q\,\varphi(i).$$
Im linearen Sieb wird die innere Erzeugung genau dann abgebrochen, wenn der kleinste Primteiler von \(i\) benutzt wurde. Dadurch erscheint jede zusammengesetzte Zahl genau einmal, und die gesamte Totienttabelle entsteht in \(O(N)\)-Zeit.
Einige kleine Ketten zeigen die Rekursion sehr klar:
$$5 \to 4 \to 2 \to 1,\qquad \ell(5)=4,$$
$$7 \to 6 \to 2 \to 1,\qquad \ell(7)=4,$$
$$11 \to 10 \to 4 \to 2 \to 1,\qquad \ell(11)=5.$$
Für den kleinen Testfall \(N=100\) und \(T=4\) qualifizieren sich also genau die Primzahlen \(5\) und \(7\), ihre Summe ist \(12\). Für \(N=1000\) und \(T=5\) sind es \(11,13,19\), also insgesamt \(43\). Genau diese beiden Werte verwendet die C++-Implementierung als Kontrollfälle.
Sobald das Sieb die Primzahlliste und alle Werte \(\varphi(n)\) geliefert hat und die Rekursion alle Werte \(\ell(n)\) aufgebaut hat, bleibt nur noch ein letzter Durchlauf über die Primzahlen. Jede Primzahl mit \(\ell(p)=T\) wird zur Summe addiert. In dieser Phase muss keine Kette mehr explizit verfolgt werden, denn jede benötigte Länge liegt bereits als Tabellenwert vor.
Die Implementierungen in C++, Python und Java beginnen alle mit einem linearen Sieb über \(2,3,\dots,N\). In derselben Schleife werden Primzahlen erkannt, zusammengesetzte Zahlen markiert und die Werte \(\varphi(n)\) über die Zweifall-Rekursion eingetragen. Das ist der entscheidende Vorverarbeitungsschritt.
Nachdem \(\varphi(1),\varphi(2),\dots,\varphi(N)\) bekannt sind, wird ein zweites Feld für die Kettenlängen angelegt, mit \(\ell(1)=1\) initialisiert und dann in aufsteigender Reihenfolge gefüllt. Jeder Eintrag kommt direkt aus
$$\ell(n)=1+\ell(\varphi(n)).$$
Da \(\varphi(n) < n\) ist, verweist die rechte Seite immer auf einen bereits berechneten Eintrag. Deshalb genügt ein iterativer linearer Durchlauf ohne Rekursion.
Im letzten Schritt wird nur noch über Primzahlen iteriert. Wenn die gespeicherte Kettenlänge gleich dem Zielwert ist, wird die Primzahl zur laufenden Summe addiert. Python und Java verwenden die Projekt-Euler-Parameter \(N=40{,}000{,}000\) und \(T=25\) direkt im Programm. Die C++-Version benutzt denselben Kernalgorithmus, erlaubt aber auch andere Schranken und Zielwerte und prüft sich vorher an den beiden kleinen Kontrollsummen.
Das lineare Sieb benötigt \(O(N)\)-Zeit, weil jede zusammengesetzte Zahl genau einmal erzeugt wird. Der Durchlauf für die Kettenlängen ist eine weitere \(O(N)\)-Phase. Der abschließende Primzahlfilter kostet \(O(\pi(N))\) und liegt damit ebenfalls innerhalb von \(O(N)\). Insgesamt ergibt sich also
$$O(N).$$
Auch der Speicherverbrauch ist \(O(N)\): ein Feld für Kompositmarkierungen, eines für Totienten, eines für Kettenlängen und eine Primzahlliste. Für Problem 214 ist dieses lineare Verhalten wesentlich, weil \(N=40{,}000{,}000\) für eine naive Kettenverfolgung pro Primzahl zu groß wäre.
Problemdeki parametreler \(N=40{,}000{,}000\) ve \(T=25\) olarak verilir. Her pozitif tam sayı için Euler phi fonksiyonu tekrar tekrar uygulanarak bir totient zinciri oluşturulur:
$$n \to \varphi(n) \to \varphi(\varphi(n)) \to \cdots \to 1.$$
İstenen, zincir uzunluğu tam olarak \(T\) olan ve \(N\)'den küçük bulunan tüm asalların toplamıdır. Zincir uzunluğunu \(\ell(n)\) ile gösterirsek hedef büyüklük
$$S(N,T)=\sum_{\substack{p < N\\ \ell(p)=T}} p,$$
şeklindedir; burada toplam yalnızca asallar üzerinde alınır. Her asal için zinciri ayrı ayrı izleyen saf bir yaklaşım, aynı \(\varphi\) değerlerini tekrar tekrar hesaplar. Uygulamalar bunun yerine \(\varphi(n)\) tablosunu ve zincir uzunluğu tablosunu bir kez küresel olarak üretir.
Çözümün merkezindeki nesne \(n \mapsto \varphi(n)\) dönüşümüdür. Problem 214'te kritik fikir, sadece son toplamda görünen asallara bakmak değil, sınıra kadar olan bütün sayılar üzerindeki bu dönüşümü tek seferde anlamaktır.
Her \(n > 1\) için \(\varphi(n) < n\) olur. Bu nedenle totient iterasyonu \(1\)'in üstünde bir çevrime giremez; mutlaka sonunda \(1\)'e ulaşır. Böylece her pozitif tam sayı için zincir uzunluğu iyi tanımlanır.
Doğal başlangıç değeri
$$\ell(1)=1$$
olur; çünkü \(1\)'den başlayan zincir zaten tek terimlidir. \(n \ge 2\) için bir adım ilerlemek sadece ilk terimi atıp zinciri \(\varphi(n)\) noktasından başlatır. Dolayısıyla
$$\ell(n)=1+\ell(\varphi(n)).$$
Üç uygulamanın da dayandığı temel yineleme budur. \(\varphi(n)\) her zaman \(n\)'den küçük olduğu için, bağımlılık grafiği doğal olarak \(1,2,3,\dots,N\) sırasıyla topolojik biçimde dizilmiş olur.
\(p\) asal ise \(1 \le a < p\) aralığındaki bütün sayılar \(p\) ile aralarında asaldır. Bu yüzden
$$\varphi(p)=p-1.$$
Dolayısıyla her aday asal ilk adımda doğrudan çift bir bileşik sayıya düşer:
$$\ell(p)=1+\ell(p-1).$$
Bu gözlem, bileşik sayıları atlayamayacağımızı da gösterir. Bir asalın zinciri hakkındaki soru, daha ilk adımda daha küçük sayılar için önceden hesaplanmış değerlere bağlanır.
Uygulamalar bütün totient değerlerini lineer sieve ile hesaplar. Keşfedilmiş asalların büyüyen bir listesi tutulur. Bir \(i\) sayısı henüz bileşik olarak işaretlenmemişse asaldır ve hemen
$$\varphi(i)=i-1$$
yazılır. Sonra listedeki her asal \(q\) için \(v=i q\) çarpımı kurulur. \(\varphi(v)\) değeri tam iki duruma ayrılır:
$$\varphi(iq)= \begin{cases} \varphi(i)\,q, & q \mid i,\\ \varphi(i)\,(q-1), & q \nmid i. \end{cases}$$
İkinci satır, aralarında asal çarpanlar için çarpımsallıktır: \(\gcd(i,q)=1\) ise \(\varphi(iq)=\varphi(i)\varphi(q)=\varphi(i)(q-1)\). Birinci satır ise \(i=q^a m\) ve \(q \nmid m\) yazımından gelir:
$$\varphi(i)=q^{a-1}(q-1)\varphi(m),\qquad \varphi(iq)=q^a(q-1)\varphi(m)=q\,\varphi(i).$$
Lineer sieve, \(i\)'nin en küçük asal böleni kullanıldığı anda iç üretimi durdurur. Bu değişmez sayesinde her bileşik sayı tam bir kez üretilir; dolayısıyla tüm totient tablosu toplamda \(O(N)\) zamanda doldurulur.
Küçük birkaç zincir yinelemeyi somutlaştırır:
$$5 \to 4 \to 2 \to 1,\qquad \ell(5)=4,$$
$$7 \to 6 \to 2 \to 1,\qquad \ell(7)=4,$$
$$11 \to 10 \to 4 \to 2 \to 1,\qquad \ell(11)=5.$$
Buna göre küçük test \(N=100\), \(T=4\) için uygun asallar \(5\) ve \(7\) olur; toplam \(12\)'dir. \(N=1000\), \(T=5\) için uygun asallar \(11,13,19\) olup toplam \(43\) eder. C++ uygulamasındaki kontrol örnekleri tam olarak bu iki değeri doğrular.
Sieve asal listesini ve tüm \(\varphi(n)\) değerlerini ürettikten, yineleme de tüm \(\ell(n)\) değerlerini doldurduktan sonra geriye zor bir iş kalmaz. Son adımda yalnızca asal listesi üzerinden geçilir; \(\ell(p)=T\) olanlar seçilir ve toplanır. Bu aşamada zinciri yeniden izlemeye gerek yoktur, çünkü her gerekli uzunluk zaten tablo bakışıyla elde edilir.
C++, Python ve Java uygulamalarının hepsi \(2,3,\dots,N\) aralığında lineer sieve ile başlar. Aynı döngü içinde asallar belirlenir, bileşikler işaretlenir ve yukarıdaki iki durumlu formülle \(\varphi(n)\) atanır. Matematiksel olarak belirleyici ön işlem budur.
\(\varphi(1),\varphi(2),\dots,\varphi(N)\) hazır olduğunda ikinci bir dizi zincir uzunlukları için ayrılır, \(\ell(1)=1\) atanır ve \(n=2,3,\dots,N\) sırasıyla işlenir. Her giriş doğrudan şu bağıntıdan gelir:
$$\ell(n)=1+\ell(\varphi(n)).$$
\(\varphi(n) < n\) olduğu için sağ taraf her zaman daha önce hesaplanmış bir hücreye bakar. Bu yüzden özyineleme yerine tek bir iteratif doğrusal geçiş yeterlidir.
Zincir uzunlukları hazır olunca son geçiş yalnızca asallar üzerindedir. Hedef uzunluğa sahip her asal çalışan toplama eklenir. Python ve Java uygulamaları Project Euler parametrelerini doğrudan \(N=40{,}000{,}000\) ve \(T=25\) olarak sabitler. C++ sürümü aynı algoritmayı kullanır; ayrıca farklı sınırlar ve hedefler için çalışabilir ve tam hesaptan önce iki küçük kontrol toplamını doğrular.
Lineer sieve, her bileşik sayıyı yalnızca bir kez ürettiği için \(O(N)\) zamanda çalışır. Zincir uzunluğu geçişi ek bir \(O(N)\) taramadır. Son asal filtresi \(O(\pi(N))\) maliyetindedir ve bu da zaten \(O(N)\) içinde kalır. Toplam çalışma süresi dolayısıyla
$$O(N)$$
olur. Bellek kullanımı da \(O(N)\)'dir: bileşik işaretleri, totient değerleri, zincir uzunlukları ve asal listesi tutulur. Problem 214'te bu doğrusal davranış kritiktir; çünkü \(N=40{,}000{,}000\) için her asal adına zinciri ayrı ayrı simüle etmek pratik değildir.
Para los parámetros del problema \(N=40{,}000{,}000\) y \(T=25\), se define la cadena totiente de un entero positivo aplicando repetidamente la función phi de Euler hasta llegar a \(1\):
$$n \to \varphi(n) \to \varphi(\varphi(n)) \to \cdots \to 1.$$
Hay que sumar todos los primos \(p < N\) cuya cadena tenga longitud exactamente \(T\). Si \(\ell(n)\) denota la longitud de la cadena que empieza en \(n\), la cantidad buscada es
$$S(N,T)=\sum_{\substack{p < N\\ \ell(p)=T}} p,$$
donde la suma se toma solo sobre primos. Un enfoque ingenuo, siguiendo la cadena de cada primo por separado, repetiría muchas veces los mismos valores de \(\varphi\). Las implementaciones evitan esa repetición construyendo una tabla global de \(\varphi(n)\) y otra tabla global de longitudes.
El objeto central es la aplicación dirigida \(n \mapsto \varphi(n)\). En el problema 214, la clave no es estudiar cada primo de forma aislada, sino comprender esa aplicación simultáneamente para todos los enteros hasta la cota.
Para todo entero \(n > 1\), se cumple \(\varphi(n) < n\). Por lo tanto, la iteración no puede entrar en un ciclo por encima de \(1\); necesariamente termina en \(1\). Eso hace que la longitud de la cadena esté bien definida para cualquier entero positivo.
El caso base natural es
$$\ell(1)=1,$$
porque la cadena que parte de \(1\) ya contiene un solo término. Para \(n \ge 2\), un paso de la cadena elimina el primer término y deja la subcadena que empieza en \(\varphi(n)\). En consecuencia,
$$\ell(n)=1+\ell(\varphi(n)).$$
Ésa es la recurrencia fundamental de las tres implementaciones. Como \(\varphi(n)\) siempre es menor que \(n\), el orden natural \(1,2,3,\dots,N\) ya es un orden topológico válido para calcular todas las longitudes.
Si \(p\) es primo, entonces todos los enteros \(1 \le a < p\) son coprimos con \(p\), así que
$$\varphi(p)=p-1.$$
Eso significa que cada primo candidato cae inmediatamente en un número compuesto par:
$$\ell(p)=1+\ell(p-1).$$
Lejos de permitirnos ignorar los compuestos, esta identidad muestra que son imprescindibles: la longitud de la cadena de un primo depende directamente de valores ya calculados para números menores.
Las implementaciones calculan todos los totientes mediante una criba lineal. Se mantiene una lista creciente de los primos descubiertos. Cuando un entero \(i\) todavía no está marcado como compuesto, es primo y se conoce de inmediato que
$$\varphi(i)=i-1.$$
Después, para cada primo conocido \(q\), se forma \(v=i q\). El valor \(\varphi(v)\) se obtiene con exactamente dos casos:
$$\varphi(iq)= \begin{cases} \varphi(i)\,q, & q \mid i,\\ \varphi(i)\,(q-1), & q \nmid i. \end{cases}$$
La segunda línea es la multiplicatividad para factores coprimos: si \(\gcd(i,q)=1\), entonces \(\varphi(iq)=\varphi(i)\varphi(q)=\varphi(i)(q-1)\). La primera aparece escribiendo \(i=q^a m\) con \(q \nmid m\):
$$\varphi(i)=q^{a-1}(q-1)\varphi(m),\qquad \varphi(iq)=q^a(q-1)\varphi(m)=q\,\varphi(i).$$
La criba lineal detiene la generación interna en el momento en que utiliza el menor factor primo de \(i\). Ese invariante garantiza que cada compuesto se genera una sola vez, de modo que toda la tabla de totientes se llena en tiempo total \(O(N)\).
Unos pocos ejemplos pequeños hacen visible la recurrencia:
$$5 \to 4 \to 2 \to 1,\qquad \ell(5)=4,$$
$$7 \to 6 \to 2 \to 1,\qquad \ell(7)=4,$$
$$11 \to 10 \to 4 \to 2 \to 1,\qquad \ell(11)=5.$$
Así, para el caso pequeño \(N=100\) y \(T=4\), los primos que cuentan son \(5\) y \(7\), cuya suma es \(12\). Para \(N=1000\) y \(T=5\), los primos son \(11,13,19\), con suma \(43\). Esos dos valores coinciden exactamente con las comprobaciones internas usadas por la implementación en C++.
Cuando la criba ya ha producido la lista de primos y todos los valores \(\varphi(n)\), y la recurrencia ya ha producido todas las longitudes \(\ell(n)\), ya no queda ningún cálculo difícil. Basta un recorrido final por la lista de primos: se conservan los que cumplen \(\ell(p)=T\) y se suman. En esa fase no se sigue ninguna cadena en tiempo real, porque cada longitud necesaria ya está disponible por consulta directa.
Las implementaciones en C++, Python y Java empiezan todas con una criba lineal sobre \(2,3,\dots,N\). En ese mismo bucle identifican primos, marcan compuestos y asignan \(\varphi(n)\) con la recurrencia de dos casos. Éste es el preprocesamiento matemáticamente decisivo.
Con \(\varphi(1),\varphi(2),\dots,\varphi(N)\) ya disponibles, las implementaciones reservan una segunda tabla para las longitudes, fijan \(\ell(1)=1\) y procesan \(n=2,3,\dots,N\) en orden ascendente. Cada entrada se obtiene directamente de
$$\ell(n)=1+\ell(\varphi(n)).$$
Como \(\varphi(n) < n\), el lado derecho siempre apunta a una celda anterior. No hace falta recursión; basta una pasada iterativa lineal.
Una vez conocidas las longitudes, el último recorrido examina solo primos. Cada primo cuya longitud coincide con el objetivo se añade al total. Las versiones en Python y Java fijan directamente los valores de Project Euler \(N=40{,}000{,}000\) y \(T=25\). La versión en C++ usa el mismo algoritmo, pero además permite otras cotas y otras longitudes objetivo, y se valida antes con las dos sumas de control pequeñas.
La criba lineal cuesta \(O(N)\) tiempo porque cada número compuesto se genera una sola vez. El recorrido para las longitudes es otra fase \(O(N)\). El filtrado final de primos cuesta \(O(\pi(N))\), que sigue estando contenido en \(O(N)\). Por tanto, el tiempo total es
$$O(N).$$
El uso de memoria también es \(O(N)\): una estructura para marcas de compuestos, una para los totientes, una para las longitudes y una lista de primos. En el problema 214 esta linealidad es indispensable, porque \(N=40{,}000{,}000\) hace poco realista seguir cadenas completas por separado para cada primo.
本题的参数是 \(N=40{,}000{,}000\) 与 \(T=25\)。对每个正整数，反复施加欧拉函数，直到数值降到 \(1\)，便得到一条 totient 链：
$$n \to \varphi(n) \to \varphi(\varphi(n)) \to \cdots \to 1.$$
题目要求把所有满足 \(p < N\) 且链长恰好等于 \(T\) 的素数 \(p\) 相加。若记链长为 \(\ell(n)\)，那么目标可以写成
$$S(N,T)=\sum_{\substack{p < N\\ \ell(p)=T}} p,$$
其中求和范围只包含素数。若对每个素数单独追踪整条链，会反复计算大量相同的 \(\varphi\) 值。三份实现采取的是全局预处理思路：先一次性求出所有 \(\varphi(n)\)，再一次性求出所有链长。
这道题的核心对象是映射 \(n \mapsto \varphi(n)\)。真正有效的做法不是把每个素数当成独立问题，而是把 \(1\) 到 \(N\) 之间所有整数放在同一个结构里统一处理。
对任意 \(n > 1\)，都有 \(\varphi(n) < n\)。因此不断迭代欧拉函数时，不可能在大于 \(1\) 的范围里形成循环，最终一定会到达 \(1\)。这保证了每个正整数的链长都是良定义的。
最自然的基例是
$$\ell(1)=1,$$
因为从 \(1\) 开始的链只包含一个项。对 \(n \ge 2\)，链的第一步把 \(n\) 变成 \(\varphi(n)\)，其余部分就是从 \(\varphi(n)\) 开始的同类问题，所以
$$\ell(n)=1+\ell(\varphi(n)).$$
这就是三种语言实现共同使用的主递推。由于右侧引用的 \(\varphi(n)\) 总是比 \(n\) 小，按自然顺序 \(1,2,3,\dots,N\) 递增处理时，所有依赖都会自动提前准备好。
如果 \(p\) 是素数，那么 \(1 \le a < p\) 的每个整数都与 \(p\) 互素，因此
$$\varphi(p)=p-1.$$
于是每个候选素数的第一步都立刻落到一个更小的偶合数上：
$$\ell(p)=1+\ell(p-1).$$
这条恒等式并不是说可以绕开合数，恰恰相反，它说明素数情形直接依赖于合数情形。要判断一个素数是否满足目标链长，必须先把较小整数的链长全部算好。
三份实现都用线性筛构造 totient 表。方法是维护一个已经发现的素数表。若某个整数 \(i\) 尚未被标记为合数，那么它本身就是素数，于是立刻得到
$$\varphi(i)=i-1.$$
然后对每个已知素数 \(q\) 形成乘积 \(v=i q\)。\(\varphi(v)\) 只有两种情况：
$$\varphi(iq)= \begin{cases} \varphi(i)\,q, & q \mid i,\\ \varphi(i)\,(q-1), & q \nmid i. \end{cases}$$
第二种情况来自互素时的乘法性：若 \(\gcd(i,q)=1\)，则 \(\varphi(iq)=\varphi(i)\varphi(q)=\varphi(i)(q-1)\)。第一种情况可由 \(i=q^a m\)、且 \(q \nmid m\) 推出：
$$\varphi(i)=q^{a-1}(q-1)\varphi(m),\qquad \varphi(iq)=q^a(q-1)\varphi(m)=q\,\varphi(i).$$
线性筛在使用到 \(i\) 的最小素因子之后立即停止当前内部生成，这个不变式保证每个合数只会被构造一次，因此整张 totient 表的总时间是 \(O(N)\)。
看几个小例子，就能把递推关系看得很清楚：
$$5 \to 4 \to 2 \to 1,\qquad \ell(5)=4,$$
$$7 \to 6 \to 2 \to 1,\qquad \ell(7)=4,$$
$$11 \to 10 \to 4 \to 2 \to 1,\qquad \ell(11)=5.$$
因此在小测试 \(N=100\)、\(T=4\) 下，满足条件的素数只有 \(5\) 和 \(7\)，总和是 \(12\)。在 \(N=1000\)、\(T=5\) 下，满足条件的素数是 \(11,13,19\)，总和是 \(43\)。这两个数正是 C++ 实现中内置的校验结果。
当筛法已经给出素数表和所有 \(\varphi(n)\)，递推也已经给出所有 \(\ell(n)\) 之后，剩下的工作非常直接：只遍历素数，把满足 \(\ell(p)=T\) 的项加入答案即可。最后这一步不再需要临时追踪任何链，因为所需链长都已经保存在表里了。
C++、Python 和 Java 实现都先对 \(2,3,\dots,N\) 做一次线性筛。在同一个循环里，它们判断素数、标记合数，并根据上面的两分公式填入 \(\varphi(n)\)。这是整个算法最关键的预处理阶段。
在 \(\varphi(1),\varphi(2),\dots,\varphi(N)\) 已经全部可用之后，程序再分配一张链长表，先设 \(\ell(1)=1\)，然后按 \(n=2,3,\dots,N\) 递增填表。每个位置都直接由
$$\ell(n)=1+\ell(\varphi(n))$$
得到。因为 \(\varphi(n) < n\)，右侧一定引用更早的位置，所以完全不需要递归，只要做一趟线性扫描即可。
链长表完成后，最后一阶段只需要扫描素数。凡是链长等于目标值的素数，就把它加到运行总和中。Python 和 Java 实现直接写死了 Project Euler 的参数 \(N=40{,}000{,}000\)、\(T=25\)。C++ 实现使用完全相同的核心算法，但还支持其他上界和目标长度，并且会先验证前面提到的两个小型校验和。
线性筛之所以是 \(O(N)\)，是因为每个合数只被生成一次。链长递推又是一趟 \(O(N)\) 的顺序扫描。最后筛选素数的开销是 \(O(\pi(N))\)，仍然包含在 \(O(N)\) 之内。因此总时间复杂度为
$$O(N).$$
空间复杂度同样是 \(O(N)\)：需要保存合数标记、totient 表、链长表以及素数表。对本题的 \(N=40{,}000{,}000\) 而言，这种线性做法是必要的；如果对每个素数都单独模拟整条链，重复工作会非常明显。
В задаче используются параметры \(N=40{,}000{,}000\) и \(T=25\). Для каждого положительного числа строится цепочка функции Эйлера: мы многократно применяем \(\varphi\), пока значение не станет равным \(1\):
$$n \to \varphi(n) \to \varphi(\varphi(n)) \to \cdots \to 1.$$
Нужно найти сумму всех простых чисел \(p < N\), для которых длина такой цепочки равна ровно \(T\). Если обозначить длину цепочки через \(\ell(n)\), то искомая величина имеет вид
$$S(N,T)=\sum_{\substack{p < N\\ \ell(p)=T}} p,$$
где суммирование ведется только по простым. Наивный подход, который отдельно прослеживает цепочку для каждого простого, снова и снова вычислял бы одни и те же значения \(\varphi\). Реальные реализации этого не делают: они сначала строят общую таблицу \(\varphi(n)\), а затем общую таблицу длин цепочек.
Главный объект здесь - отображение \(n \mapsto \varphi(n)\). Для задачи 214 важно не локальное поведение одной конкретной простой, а глобальная структура этого отображения на всех числах до заданной границы.
Для любого \(n > 1\) выполняется неравенство \(\varphi(n) < n\). Поэтому при повторном применении функции Эйлера нельзя зациклиться выше \(1\); процесс обязательно дойдет до \(1\). Значит, длина цепочки корректно определена для каждого положительного целого.
Естественное базовое значение таково:
$$\ell(1)=1,$$
потому что цепочка, начинающаяся с \(1\), уже состоит из одного члена. Для \(n \ge 2\) первый шаг просто отбрасывает стартовое значение и переводит нас к цепочке, начинающейся с \(\varphi(n)\). Следовательно,
$$\ell(n)=1+\ell(\varphi(n)).$$
Это основная рекуррентная формула всех трех реализаций. Поскольку \(\varphi(n)\) строго меньше \(n\), естественный порядок \(1,2,3,\dots,N\) автоматически является топологическим порядком вычисления.
Если \(p\) - простое число, то все числа \(1 \le a < p\) взаимно просты с \(p\), и потому
$$\varphi(p)=p-1.$$
Отсюда следует, что каждая рассматриваемая простая сразу переходит в четное составное число:
$$\ell(p)=1+\ell(p-1).$$
Это не позволяет обойтись без составных чисел; наоборот, длина цепочки простой напрямую зависит от уже посчитанных значений для меньших чисел.
Во всех реализациях таблица totient строится линейным решетом. Поддерживается растущий список найденных простых. Если число \(i\) еще не отмечено как составное, значит оно простое, и сразу известно, что
$$\varphi(i)=i-1.$$
Затем для каждого уже известного простого \(q\) строится \(v=i q\). Значение \(\varphi(v)\) определяется двумя случаями:
$$\varphi(iq)= \begin{cases} \varphi(i)\,q, & q \mid i,\\ \varphi(i)\,(q-1), & q \nmid i. \end{cases}$$
Вторая строка - это мультипликативность для взаимно простых множителей: если \(\gcd(i,q)=1\), то \(\varphi(iq)=\varphi(i)\varphi(q)=\varphi(i)(q-1)\). Первая строка получается из разложения \(i=q^a m\), где \(q \nmid m\):
$$\varphi(i)=q^{a-1}(q-1)\varphi(m),\qquad \varphi(iq)=q^a(q-1)\varphi(m)=q\,\varphi(i).$$
Линейное решето прекращает внутреннюю генерацию, как только использован наименьший простой делитель числа \(i\). Этот инвариант гарантирует, что каждое составное число возникает ровно один раз, поэтому вся таблица \(\varphi\) заполняется за суммарное время \(O(N)\).
Небольшие примеры хорошо показывают, как работает рекурсия:
$$5 \to 4 \to 2 \to 1,\qquad \ell(5)=4,$$
$$7 \to 6 \to 2 \to 1,\qquad \ell(7)=4,$$
$$11 \to 10 \to 4 \to 2 \to 1,\qquad \ell(11)=5.$$
Значит, в маленьком тесте \(N=100\), \(T=4\) подходят только простые \(5\) и \(7\), а их сумма равна \(12\). Для \(N=1000\), \(T=5\) подходят \(11,13,19\), и сумма равна \(43\). Именно эти два значения используются как контрольные проверки в реализации на C++.
Когда решето уже дало список простых и все значения \(\varphi(n)\), а рекуррентный проход уже дал все значения \(\ell(n)\), сложной работы больше нет. Остается один проход по простым: те из них, для которых \(\ell(p)=T\), добавляются к ответу. На этой стадии не нужно заново разворачивать цепочки, потому что каждая длина уже лежит в таблице.
Реализации на C++, Python и Java начинают с линейного решета по диапазону \(2,3,\dots,N\). В одном и том же цикле они распознают простые числа, помечают составные и заполняют \(\varphi(n)\) по двухслучайной формуле. Это ключевой этап предварительной обработки.
Когда \(\varphi(1),\varphi(2),\dots,\varphi(N)\) уже известны, выделяется вторая таблица для длин цепочек, задается \(\ell(1)=1\), и далее числа \(n=2,3,\dots,N\) обрабатываются по возрастанию. Каждая ячейка получается напрямую из
$$\ell(n)=1+\ell(\varphi(n)).$$
Так как \(\varphi(n) < n\), правая часть всегда ссылается на уже заполненную позицию. Поэтому достаточно одной итеративной линейной проходки без рекурсии.
После этого остается пройти только по простым. Если сохраненная длина цепочки совпадает с целью, простое добавляется к сумме. Реализации на Python и Java фиксируют параметры Project Euler \(N=40{,}000{,}000\) и \(T=25\) прямо в программе. Реализация на C++ использует тот же алгоритм, но умеет работать и с другими пределами и длинами, а перед полным запуском проверяет два маленьких контрольных случая.
Линейное решето работает за \(O(N)\), потому что каждое составное число порождается ровно один раз. Проход для длин цепочек - еще одна фаза \(O(N)\). Финальная фильтрация простых требует \(O(\pi(N))\), что также входит в \(O(N)\). Итак, полное время работы равно
$$O(N).$$
Память тоже имеет порядок \(O(N)\): нужны массив отметок составности, массив totient, массив длин цепочек и список простых. Для задачи 214 такая линейная схема принципиальна, потому что при \(N=40{,}000{,}000\) отдельное моделирование цепочки для каждой простой давало бы слишком много повторной работы.
في هذه المسألة تكون المعلمات \(N=40{,}000{,}000\) و\(T=25\). نعرّف سلسلة دالة أويلر لعدد صحيح موجب عبر تطبيق الدالة \(\varphi\) مرارًا حتى نصل إلى \(1\):
$$n \to \varphi(n) \to \varphi(\varphi(n)) \to \cdots \to 1.$$
المطلوب هو مجموع جميع الأعداد الأولية \(p < N\) التي يكون طول سلسلتها مساويًا تمامًا لـ \(T\). وإذا رمزنا إلى طول السلسلة بـ \(\ell(n)\)، فإن الكمية المطلوبة هي
$$S(N,T)=\sum_{\substack{p < N\\ \ell(p)=T}} p,$$
حيث يُؤخذ المجموع على الأعداد الأولية فقط. الطريقة الساذجة التي تتتبع سلسلة كل عدد أولي على حدة ستعيد حساب نفس قيم \(\varphi\) مرات كثيرة. أما الحلول البرمجية هنا فتتجنب هذا التكرار ببناء جدول شامل لقيم \(\varphi(n)\) وجدول شامل لأطوال السلاسل.
الفكرة الأساسية تدور حول التطبيق \(n \mapsto \varphi(n)\). في المسألة 214 لا يكفي أن ننظر إلى كل عدد أولي كحالة منفصلة؛ بل يجب فهم هذا التطبيق على جميع الأعداد حتى الحد \(N\) دفعة واحدة.
لكل \(n > 1\) يتحقق \(\varphi(n) < n\). لذلك فإن تكرار تطبيق دالة أويلر لا يمكن أن يصنع دورة فوق \(1\)، بل لا بد أن ينتهي عند \(1\). وهذا ما يجعل طول السلسلة معرفًا جيدًا لكل عدد صحيح موجب.
حالة الأساس الطبيعية هي
$$\ell(1)=1,$$
لأن السلسلة التي تبدأ من \(1\) تحتوي أصلًا على حد واحد فقط. ولأي \(n \ge 2\)، فإن خطوة واحدة من السلسلة تحذف الحد الأول وتترك لنا السلسلة التي تبدأ من \(\varphi(n)\)، وبالتالي
$$\ell(n)=1+\ell(\varphi(n)).$$
هذه هي العلاقة التراجعية المركزية في تطبيقات C++ وPython وJava جميعًا. وبما أن \(\varphi(n)\) أصغر دائمًا من \(n\)، فإن الترتيب الطبيعي \(1,2,3,\dots,N\) يشكل تلقائيًا ترتيبًا صالحًا لحساب جميع القيم تصاعديًا.
إذا كان \(p\) أوليًا، فإن كل عدد \(1 \le a < p\) يكون أوليًا نسبيًا مع \(p\)، ومن ثم
$$\varphi(p)=p-1.$$
وهذا يعني أن كل عدد أولي مرشح يقفز مباشرة في أول خطوة إلى عدد زوجي مركب أصغر:
$$\ell(p)=1+\ell(p-1).$$
وهنا تظهر أهمية الأعداد المركبة: لا يمكن تجاوزها، لأن طول سلسلة العدد الأولي يعتمد فورًا على قيمة محسوبة سابقًا لعدد أصغر منه.
تحسب التطبيقات جميع قيم التوتيانت باستخدام غربال خطي. تُحفظ قائمة متزايدة بالأعداد الأولية المكتشفة. فإذا كان العدد \(i\) غير موسوم بوصفه مركبًا، فهو عدد أولي، وعندئذٍ نعرف مباشرة أن
$$\varphi(i)=i-1.$$
بعد ذلك نكوّن \(v=i q\) لكل عدد أولي معروف \(q\). وتُحسب \(\varphi(v)\) بحالتين فقط:
$$\varphi(iq)= \begin{cases} \varphi(i)\,q, & q \mid i,\\ \varphi(i)\,(q-1), & q \nmid i. \end{cases}$$
السطر الثاني يأتي من خاصية الضرب للأعداد المتباينة نسبيًا: إذا كانت \(\gcd(i,q)=1\) فإن \(\varphi(iq)=\varphi(i)\varphi(q)=\varphi(i)(q-1)\). أما السطر الأول فينتج من كتابة \(i=q^a m\) بحيث \(q \nmid m\)، فنحصل على
$$\varphi(i)=q^{a-1}(q-1)\varphi(m),\qquad \varphi(iq)=q^a(q-1)\varphi(m)=q\,\varphi(i).$$
ويوقف الغربال الخطي التوليد الداخلي بمجرد استعمال أصغر قاسم أولي للعدد \(i\). هذا الثابت البنيوي يضمن أن كل عدد مركب يُنشأ مرة واحدة فقط، ولذلك تمتلئ كل قيم \(\varphi\) في زمن كلي \(O(N)\).
تكفي بعض الأمثلة الصغيرة لرؤية الفكرة بوضوح:
$$5 \to 4 \to 2 \to 1,\qquad \ell(5)=4,$$
$$7 \to 6 \to 2 \to 1,\qquad \ell(7)=4,$$
$$11 \to 10 \to 4 \to 2 \to 1,\qquad \ell(11)=5.$$
لذلك، في الحالة الصغيرة \(N=100\) و\(T=4\)، يكون العددان الأوليان الموافقان هما \(5\) و\(7\)، ومجموعهما \(12\). وفي الحالة \(N=1000\) و\(T=5\)، تكون الأعداد \(11,13,19\) ومجموعها \(43\). وهاتان القيمتان هما بالضبط حالتا التحقق اللتان تستعملهما نسخة C++.
بعد أن يُنتج الغربال قائمة الأعداد الأولية وجميع قيم \(\varphi(n)\)، وبعد أن تُنتج العلاقة التراجعية جميع قيم \(\ell(n)\)، لا يبقى أي حساب معقد. يكفي مرور أخير على قائمة الأعداد الأولية: كل عدد أولي يحقق \(\ell(p)=T\) يضاف إلى الجواب. ولا حاجة في هذه المرحلة إلى تتبع السلسلة من جديد، لأن كل طول مطلوب صار متاحًا مباشرة من الجدول.
تبدأ تطبيقات C++ وPython وJava جميعًا بغربال خطي على المجال \(2,3,\dots,N\). داخل الحلقة نفسها تُكتشف الأعداد الأولية، وتوسم الأعداد المركبة، وتُملأ قيم \(\varphi(n)\) بواسطة العلاقة ذات الحالتين. وهذه هي خطوة المعالجة المسبقة الحاسمة رياضيًا.
بعد أن تصبح \(\varphi(1),\varphi(2),\dots,\varphi(N)\) معروفة، يُنشأ جدول ثانٍ لأطوال السلاسل، وتُضبط \(\ell(1)=1\)، ثم تُعالج القيم \(n=2,3,\dots,N\) تصاعديًا. كل خانة تأتي مباشرة من
$$\ell(n)=1+\ell(\varphi(n)).$$
ولأن \(\varphi(n) < n\)، فإن الطرف الأيمن يشير دائمًا إلى خانة أقدم سبق حسابها. لذلك لا توجد حاجة إلى الاستدعاء الذاتي؛ تمريرة خطية واحدة تكفي.
بعد اكتمال جدول الأطوال، تمر المرحلة الأخيرة على الأعداد الأولية فقط. كل عدد أولي يملك طول السلسلة المطلوب يُضاف إلى المجموع. تطبيقا Python وJava يثبتان مباشرة قيم Project Euler وهي \(N=40{,}000{,}000\) و\(T=25\). أما تطبيق C++ فيستخدم الخوارزمية نفسها، لكنه يدعم كذلك حدودًا وأطوالًا أخرى، ويتحقق أولًا من حالتي التحقق الصغيرتين المذكورتين أعلاه.
الغربال الخطي يعمل في \(O(N)\) زمنًا لأن كل عدد مركب يُولد مرة واحدة فقط. وتمريرة أطوال السلاسل هي أيضًا \(O(N)\). أما الترشيح النهائي على الأعداد الأولية فتكلفته \(O(\pi(N))\)، وهي ما تزال ضمن \(O(N)\). إذًا زمن التنفيذ الكلي هو
$$O(N).$$
واستهلاك الذاكرة كذلك من الرتبة \(O(N)\): نحتاج إلى بنية لوسم المركبات، وجدول للتوتيانت، وجدول لأطوال السلاسل، وقائمة للأعداد الأولية. وفي المسألة 214 يُعد هذا السلوك الخطي ضروريًا، لأن \(N=40{,}000{,}000\) كبير بما يكفي لجعل تتبع سلسلة كاملة لكل عدد أولي على حدة خيارًا ضعيفًا.