For each prime \(p \equiv 1 \pmod{5}\), the problem studies the polynomial map
$$f_p(x)=x+x^{(p+4)/5}\pmod p,$$
counts how many residues \(x \in \mathbb F_p\) are periodic under iteration of that map, and denotes this count by \(C(p)\). The global quantity computed by the implementations is
$$S(L)=\sum_{\substack{p \le L\\ p \equiv 1 \pmod{5}}} C(p).$$
A naive method would inspect every residue modulo every relevant prime and explicitly follow the orbit of each starting value. That is already expensive for one large prime, and completely impractical when the limit is \(10^8\). The key simplification is that, for nonzero residues, the map depends only on which fifth-root class the value belongs to, so each prime collapses to a functional graph on exactly five states.
The entire derivation starts from rewriting the exponent and then using the multiplicative structure of \(\mathbb F_p^\times\).
Write
$$t=\frac{p-1}{5}, \qquad \frac{p+4}{5}=t+1.$$
For every nonzero \(x\),
$$f_p(x)=x+x^{t+1}=x(1+x^t).$$
Because \(x^{p-1}=1\) in \(\mathbb F_p^\times\), we have
$$\left(x^t\right)^5=x^{p-1}=1,$$
so \(x^t\) is always a fifth root of unity. Choose an element \(\omega\) of order 5. Then every nonzero residue belongs to exactly one class
$$A_r=\{x \in \mathbb F_p^\times : x^t=\omega^r\}, \qquad r=0,1,2,3,4.$$
These are the fibers of the homomorphism \(x \mapsto x^t\) from the cyclic group \(\mathbb F_p^\times\) of size \(5t\) onto its subgroup of fifth roots of unity of size 5, so each class has exactly \(t\) elements.
If \(x \in A_r\), then \(x^t=\omega^r\), hence
$$f_p(x)=x(1+\omega^r).$$
The multiplier \(1+\omega^r\) is nonzero: a fifth root of unity cannot equal \(-1\) when \(p\) is odd. Therefore
$$f_p(x)^t=x^t(1+\omega^r)^t=\omega^r(1+\omega^r)^t.$$
Now \((1+\omega^r)^t\) is also a fifth root of unity, so there is a unique \(s_r \in \{0,1,2,3,4\}\) such that
$$ (1+\omega^r)^t=\omega^{s_r}. $$
It follows that every element of \(A_r\) is sent into the single class
$$A_{r+s_r \bmod 5}.$$
Thus one prime \(p\) gives a functional graph on five nodes:
$$r \longmapsto r+s_r \pmod 5.$$
This graph contains all the information needed for periodicity. The actual residue \(x\) still matters for the exact orbit inside a class, but the question “can this orbit ever come back?” is decided entirely by the class graph.
Suppose a class \(A_r\) lies on a directed cycle of length \(\ell\) in the five-node graph. After \(\ell\) iterations, every \(x \in A_r\) has returned to the same class, so the map on that class is simply multiplication by a fixed nonzero field element \(\lambda\):
$$f_p^{(\ell)}(x)=\lambda x.$$
Since \(\lambda \in \mathbb F_p^\times\), Fermat's little theorem gives \(\lambda^{p-1}=1\), and therefore
$$f_p^{(\ell(p-1))}(x)=x.$$
So every element of a cycle class is periodic. Conversely, if a class is not on a cycle of the class graph, its label eventually falls into some other class cycle and never returns to the starting label, so no element of that class can be periodic.
The special residue \(x=0\) is even simpler:
$$f_p(0)=0,$$
so it is always a fixed point. If \(c_p\) denotes the number of nodes that lie on cycles in the five-node graph, then
$$\boxed{C(p)=1+t\,c_p.}$$
That formula is exactly what the implementations evaluate.
For \(p=11\) we have \(t=(11-1)/5=2\). One choice of fifth root of unity is \(\omega=4\), because \(4^5 \equiv 1 \pmod{11}\) and \(4 \not\equiv 1\). Its powers are
$$1,\ 4,\ 5,\ 9,\ 3.$$
The five classes are
$$A_0=\{1,10\},\quad A_1=\{2,9\},\quad A_2=\{4,7\},\quad A_3=\{3,8\},\quad A_4=\{5,6\}.$$
Now compute \((1+\omega^r)^2\):
$$2^2=4=\omega^1,\quad 5^2=3=\omega^4,\quad 6^2=3=\omega^4,\quad 10^2=1=\omega^0,\quad 4^2=5=\omega^2.$$
So the class transitions are
$$0 \to 1,\quad 1 \to 0,\quad 2 \to 1,\quad 3 \to 3,\quad 4 \to 1.$$
The cycle nodes are \(0\), \(1\), and \(3\): there is a 2-cycle \(0 \leftrightarrow 1\) and a fixed node \(3\). Hence \(c_{11}=3\), and
$$C(11)=1+2\cdot 3=7.$$
This agrees with a direct brute-force orbit count, but the class-graph method obtains it without enumerating all trajectories.
The C++, Python, and Java implementations first generate all primes up to the required limit with a straightforward sieve, then keep only primes congruent to \(1 \pmod 5\). Everything after that is done prime by prime.
For a fixed prime \(p\), the implementation sets \(t=(p-1)/5\) and searches for a nontrivial fifth root of unity by scanning small bases \(a\) until \(a^t \not\equiv 1 \pmod p\). Any such value has order 5, because its fifth power is 1 and it is not equal to 1. The five powers \(1,\omega,\omega^2,\omega^3,\omega^4\) are then listed explicitly.
For each class index \(r\), the code evaluates \((1+\omega^r)^t \bmod p\), identifies which power of \(\omega\) it matches, and therefore determines the successor of node \(r\) in the functional graph.
Once the successor table is known, the remaining job is just cycle detection on a graph of five nodes. The implementations use a standard three-state traversal: unseen, currently on the exploration stack, and finished. That counts exactly how many nodes belong to directed cycles.
After obtaining \(c_p\), the contribution of the prime is \(1+t\,c_p\). The compiled implementations also perform small sanity checks by comparing this fast method against direct orbit simulation for a few small primes, and they verify the small aggregate value \(S(100)=127\) before printing the full answer.
The sieve up to \(L\) costs \(O(L \log \log L)\) time and \(O(L)\) memory in the direct form used here. After the sieve, each relevant prime requires only a constant number of modular exponentiations and a constant-size graph traversal. Each modular exponentiation takes \(O(\log p)\) modular multiplications, so the post-sieve work is
$$O\!\left(\sum_{\substack{p \le L\\ p \equiv 1 \pmod 5}} \log p\right)=O(\pi(L)\log L)$$
up to standard prime-counting bounds.
In practice, the important point is qualitative rather than asymptotic: instead of examining all \(p\) residues and their orbits for every prime, the algorithm reduces each prime to five class transitions and one cycle count on five nodes. That is the reason the method scales to the full limit.
Für jede Primzahl \(p \equiv 1 \pmod{5}\) betrachtet die Aufgabe die Polynomabbildung
$$f_p(x)=x+x^{(p+4)/5}\pmod p,$$
zählt die unter Iteration periodischen Restklassen \(x \in \mathbb F_p\) und nennt diese Anzahl \(C(p)\). Die von den Implementierungen berechnete Gesamtsumme ist
$$S(L)=\sum_{\substack{p \le L\\ p \equiv 1 \pmod{5}}} C(p).$$
Brute Force wäre viel zu teuer: Für jede relevante Primzahl müsste man alle Restklassen verfolgen und ihre Bahnen explizit analysieren. Der entscheidende Schritt besteht darin, dass das Verhalten aller von Null verschiedenen Elemente nur davon abhängt, in welcher fünften-Wurzel-Klasse sie liegen. Für jede Primzahl schrumpft das Problem daher auf einen Funktionsgraphen mit genau fünf Knoten.
Die Herleitung beginnt mit einer einfachen Umformung des Exponenten und nutzt dann die multiplikative Struktur von \(\mathbb F_p^\times\).
Setze
$$t=\frac{p-1}{5}, \qquad \frac{p+4}{5}=t+1.$$
Für jedes \(x \ne 0\) gilt dann
$$f_p(x)=x+x^{t+1}=x(1+x^t).$$
Wegen \(x^{p-1}=1\) in \(\mathbb F_p^\times\) folgt
$$\left(x^t\right)^5=x^{p-1}=1,$$
also ist \(x^t\) immer eine fünfte Einheitswurzel. Wähle ein Element \(\omega\) der Ordnung 5. Dann gehört jedes von Null verschiedene \(x\) genau zu einer Klasse
$$A_r=\{x \in \mathbb F_p^\times : x^t=\omega^r\}, \qquad r=0,1,2,3,4.$$
Das sind die Fasern des Homomorphismus \(x \mapsto x^t\) von der zyklischen Gruppe \(\mathbb F_p^\times\) der Größe \(5t\) auf ihre Untergruppe der fünften Einheitswurzeln der Größe 5. Daher enthält jede Klasse genau \(t\) Elemente.
Liegt \(x\) in \(A_r\), so ist \(x^t=\omega^r\), also
$$f_p(x)=x(1+\omega^r).$$
Der Faktor \(1+\omega^r\) ist ungleich null: Eine fünfte Einheitswurzel kann bei ungeradem \(p\) nicht \(-1\) sein. Deshalb gilt
$$f_p(x)^t=x^t(1+\omega^r)^t=\omega^r(1+\omega^r)^t.$$
Nun ist auch \((1+\omega^r)^t\) wieder eine fünfte Einheitswurzel. Also gibt es ein eindeutig bestimmtes \(s_r \in \{0,1,2,3,4\}\) mit
$$ (1+\omega^r)^t=\omega^{s_r}. $$
Damit wird jedes Element aus \(A_r\) in die einzelne Klasse
$$A_{r+s_r \bmod 5}$$
abgebildet. Für jede Primzahl entsteht also ein Funktionsgraph auf fünf Knoten:
$$r \longmapsto r+s_r \pmod 5.$$
Dieser Graph entscheidet bereits über die Periodizität. Die genaue Bahn innerhalb einer Klasse hängt noch von \(x\) ab, aber ob eine Rückkehr überhaupt möglich ist, wird vollständig auf Klassenebene festgelegt.
Angenommen, die Klasse \(A_r\) liegt auf einem gerichteten Zyklus der Länge \(\ell\) im Fünf-Knoten-Graphen. Nach \(\ell\) Iterationen ist jedes \(x \in A_r\) wieder in derselben Klasse, also wirkt die \(\ell\)-te Iteration dort nur noch als Multiplikation mit einem festen \(\lambda \in \mathbb F_p^\times\):
$$f_p^{(\ell)}(x)=\lambda x.$$
Aus dem kleinen Satz von Fermat folgt \(\lambda^{p-1}=1\) und damit
$$f_p^{(\ell(p-1))}(x)=x.$$
Somit ist jedes Element einer Zyklusklasse periodisch. Umgekehrt kann kein Element einer Klasse außerhalb der Klassenzyklen periodisch sein, denn seine Klassenmarke wandert irgendwann in einen anderen Zyklus und kehrt nie zur Startklasse zurück.
Der Rest \(x=0\) ist noch einfacher:
$$f_p(0)=0,$$
also ist 0 immer ein Fixpunkt. Bezeichnet \(c_p\) die Anzahl der Knoten, die im Fünf-Knoten-Graphen auf Zyklen liegen, dann gilt
$$\boxed{C(p)=1+t\,c_p.}$$
Genau diese Formel berechnen die Implementierungen.
Für \(p=11\) ist \(t=(11-1)/5=2\). Eine mögliche fünfte Einheitswurzel ist \(\omega=4\), denn \(4^5 \equiv 1 \pmod{11}\) und \(4 \not\equiv 1\). Ihre Potenzen sind
$$1,\ 4,\ 5,\ 9,\ 3.$$
Die fünf Klassen lauten
$$A_0=\{1,10\},\quad A_1=\{2,9\},\quad A_2=\{4,7\},\quad A_3=\{3,8\},\quad A_4=\{5,6\}.$$
Nun berechnet man \((1+\omega^r)^2\):
$$2^2=4=\omega^1,\quad 5^2=3=\omega^4,\quad 6^2=3=\omega^4,\quad 10^2=1=\omega^0,\quad 4^2=5=\omega^2.$$
Daraus folgen die Klassenübergänge
$$0 \to 1,\quad 1 \to 0,\quad 2 \to 1,\quad 3 \to 3,\quad 4 \to 1.$$
Auf Zyklen liegen die Knoten \(0\), \(1\) und \(3\): Es gibt den 2-Zyklus \(0 \leftrightarrow 1\) und den Fixpunkt \(3\). Also ist \(c_{11}=3\) und damit
$$C(11)=1+2\cdot 3=7.$$
Das stimmt mit einer direkten Bahnauszählung überein, wird hier aber allein aus dem Fünf-Knoten-Modell gewonnen.
Die C++-, Python- und Java-Implementierungen erzeugen zunächst mit einem einfachen Sieb alle Primzahlen bis zur vorgegebenen Grenze und behalten dann nur die Primzahlen \(p \equiv 1 \pmod 5\). Danach wird jede Primzahl separat verarbeitet.
Für ein festes \(p\) setzt die Implementierung \(t=(p-1)/5\) und sucht durch Test kleiner Basen \(a\) nach einer nichttrivialen fünften Einheitswurzel, also nach einem \(a^t \not\equiv 1 \pmod p\). Ein solcher Wert hat automatisch Ordnung 5, denn seine fünfte Potenz ist 1 und er selbst ist nicht 1. Anschließend werden die fünf Potenzen \(1,\omega,\omega^2,\omega^3,\omega^4\) explizit aufgebaut.
Für jeden Klassenindex \(r\) berechnet der Code \((1+\omega^r)^t \bmod p\), bestimmt, welche \(\omega\)-Potenz dabei herauskommt, und legt so den Nachfolger von \(r\) im Funktionsgraphen fest.
Sobald die Nachfolgetabelle feststeht, bleibt nur noch eine Zyklensuche auf einem Graphen mit fünf Knoten. Dafür verwenden die Implementierungen eine Standard-Markierung mit drei Zuständen: noch nicht gesehen, gerade im aktuellen Suchpfad und vollständig abgearbeitet. So lässt sich exakt zählen, wie viele Knoten auf gerichteten Zyklen liegen.
Mit \(c_p\) ergibt sich der Beitrag der Primzahl als \(1+t\,c_p\). Die kompilierten Implementierungen prüfen zusätzlich einige kleine Fälle gegen direkte Orbit-Simulation und verifizieren den kleinen Summenwert \(S(100)=127\), bevor sie das Ergebnis für die volle Grenze ausgeben.
Das Sieb bis \(L\) benötigt in der hier verwendeten direkten Form \(O(L \log \log L)\) Zeit und \(O(L)\) Speicher. Danach kostet jede relevante Primzahl nur noch eine konstante Anzahl modularer Potenzierungen und eine Traversierung eines Graphen konstanter Größe. Da eine modulare Potenzierung \(O(\log p)\) Multiplikationen benötigt, ist die Nachbearbeitung insgesamt
$$O\!\left(\sum_{\substack{p \le L\\ p \equiv 1 \pmod 5}} \log p\right)=O(\pi(L)\log L).$$
Praktisch ist die zentrale Einsicht wichtiger als die exakte Formel: Statt für jede Primzahl alle \(p\) Restklassen und ihre Bahnen zu verfolgen, reduziert das Verfahren jede Primzahl auf fünf Klassenübergänge und eine winzige Zykluszählung. Genau dadurch wird die volle Grenze beherrschbar.
Her \(p \equiv 1 \pmod{5}\) asalı için problem şu polinom dönüşümünü inceler:
$$f_p(x)=x+x^{(p+4)/5}\pmod p.$$
Bu dönüşüm altında iterasyonla periyodik olan \(x \in \mathbb F_p\) kalıntılarının sayısına \(C(p)\) denir. Uygulamaların hesapladığı toplam ise
$$S(L)=\sum_{\substack{p \le L\\ p \equiv 1 \pmod{5}}} C(p).$$
Doğrudan yaklaşım, her asal için tüm kalıntıları tek tek dolaşıp her başlangıç değerinin yörüngesini izlemeyi gerektirirdi. Bu, büyük bir asal için bile pahalıdır; üst sınır \(10^8\) olduğunda ise tamamen verimsiz hale gelir. Çözümün ana fikri, sıfır dışındaki değerlerde davranışın yalnızca \(x^t\)'nin hangi beşinci kök sınıfına düştüğüne bağlı olmasıdır. Böylece her asal için problem tam olarak beş düğümlü bir fonksiyon grafına indirgenir.
Türetim, üssü yeniden yazmakla başlıyor ve ardından \(\mathbb F_p^\times\) içindeki çarpımsal yapıyı kullanıyor.
Şöyle yazalım:
$$t=\frac{p-1}{5}, \qquad \frac{p+4}{5}=t+1.$$
O zaman her \(x \ne 0\) için
$$f_p(x)=x+x^{t+1}=x(1+x^t)$$
olur. \(\mathbb F_p^\times\) içinde \(x^{p-1}=1\) olduğundan
$$\left(x^t\right)^5=x^{p-1}=1,$$
yani \(x^t\) her zaman bir beşinci birim köktür. Mertebesi 5 olan bir \(\omega\) seçelim. O zaman sıfır dışındaki her eleman tam olarak şu sınıflardan birine aittir:
$$A_r=\{x \in \mathbb F_p^\times : x^t=\omega^r\}, \qquad r=0,1,2,3,4.$$
Bunlar, büyüklüğü \(5t\) olan çevrimsel grup \(\mathbb F_p^\times\) üzerindeki \(x \mapsto x^t\) homomorfizmasının, büyüklüğü 5 olan beşinci kökler altgrubuna giden lifleridir. Bu yüzden her sınıfta tam \(t\) eleman vardır.
Eğer \(x \in A_r\) ise \(x^t=\omega^r\) olduğundan
$$f_p(x)=x(1+\omega^r).$$
\(1+\omega^r\) katsayısı sıfır değildir; tek karakteristikte bir beşinci kök \(-1\) olamaz. O halde
$$f_p(x)^t=x^t(1+\omega^r)^t=\omega^r(1+\omega^r)^t.$$
Burada \((1+\omega^r)^t\) de yine bir beşinci birim köktür. Dolayısıyla \(\{0,1,2,3,4\}\) içinde tek bir \(s_r\) vardır ve
$$ (1+\omega^r)^t=\omega^{s_r} $$
eşitliği sağlanır. Böylece \(A_r\) sınıfındaki her eleman
$$A_{r+s_r \bmod 5}$$
sınıfına gider. Yani her asal için elimizde beş düğümlü bir fonksiyon grafı vardır:
$$r \longmapsto r+s_r \pmod 5.$$
Periyodiklik sorusunun özü burada yatıyor. Sınıf içindeki tam yörünge elbette \(x\)'e bağlıdır, ama bir başlangıç değerinin geri dönme ihtimali yalnızca bu sınıf grafı tarafından belirlenir.
Diyelim ki \(A_r\) sınıfı, beş düğümlü graf içinde uzunluğu \(\ell\) olan yönlü bir çevrim üzerindedir. \(\ell\) iterasyon sonra her \(x \in A_r\) yeniden aynı sınıfa gelmiş olur; dolayısıyla bu sınıf üzerinde dönüşüm sabit bir \(\lambda \in \mathbb F_p^\times\) ile çarpmaya eşittir:
$$f_p^{(\ell)}(x)=\lambda x.$$
Küçük Fermat teoreminden \(\lambda^{p-1}=1\) gelir ve bu da
$$f_p^{(\ell(p-1))}(x)=x$$
demektir. Yani çevrim sınıfındaki her eleman periyodiktir. Tersine, bir sınıf sınıf-grafındaki çevrimlerin üzerinde değilse, etiket dizisi bir başka çevrime akar ve başlangıç etiketine geri dönmez; dolayısıyla o sınıftan hiçbir eleman periyodik olamaz.
\(x=0\) ise ayrı ve çok kolay bir durumdur:
$$f_p(0)=0,$$
yani her zaman sabit noktadır. Eğer \(c_p\), beş düğümlü graf üzerinde çevrimlerde bulunan düğüm sayısıysa
$$\boxed{C(p)=1+t\,c_p}$$
elde edilir. Uygulamaların doğrudan hesapladığı formül budur.
\(p=11\) için \(t=(11-1)/5=2\). Bir beşinci birim kök seçimi olarak \(\omega=4\) alınabilir; çünkü \(4^5 \equiv 1 \pmod{11}\) ve \(4 \not\equiv 1\). Kuvvetleri şunlardır:
$$1,\ 4,\ 5,\ 9,\ 3.$$
Beş sınıf şu hale gelir:
$$A_0=\{1,10\},\quad A_1=\{2,9\},\quad A_2=\{4,7\},\quad A_3=\{3,8\},\quad A_4=\{5,6\}.$$
Şimdi \((1+\omega^r)^2\) değerlerini hesaplayalım:
$$2^2=4=\omega^1,\quad 5^2=3=\omega^4,\quad 6^2=3=\omega^4,\quad 10^2=1=\omega^0,\quad 4^2=5=\omega^2.$$
Buna göre sınıf geçişleri
$$0 \to 1,\quad 1 \to 0,\quad 2 \to 1,\quad 3 \to 3,\quad 4 \to 1$$
olur. Çevrim üzerindeki düğümler \(0\), \(1\) ve \(3\)'tür: \(0 \leftrightarrow 1\) şeklinde bir 2-çevrim ve \(3\) üzerinde bir sabit nokta vardır. Dolayısıyla \(c_{11}=3\) ve
$$C(11)=1+2\cdot 3=7$$
çıkar. Bu sonuç doğrudan yörünge sayımıyla da doğrulanır, fakat burada yalnızca beş sınıflı modelden elde edilir.
C++, Python ve Java uygulamaları önce basit bir elek ile üst sınıra kadar olan asalları üretir, sonra sadece \(p \equiv 1 \pmod 5\) olanları işler. Bundan sonraki hesap tamamen asal-bazındadır.
Sabit bir \(p\) için uygulama \(t=(p-1)/5\) değerini hesaplar ve küçük tabanları deneyerek \(a^t \not\equiv 1 \pmod p\) sağlayan bir değer bulur. Böyle bir değer otomatik olarak mertebesi 5 olan bir beşinci köktür; çünkü beşinci kuvveti 1 olur ama kendisi 1 değildir. Sonra \(1,\omega,\omega^2,\omega^3,\omega^4\) açıkça üretilir.
Her sınıf indeksi \(r\) için \((1+\omega^r)^t \bmod p\) hesaplanır, bunun hangi \(\omega\) kuvvetine eşit olduğu bulunur ve böylece fonksiyon grafındaki sonraki düğüm belirlenir.
Sonraki-düğüm tablosu kurulduktan sonra geriye beş düğümlü bir graf üzerinde çevrim sayımı kalır. Uygulamalar bunu üç durumlu standart bir dolaşma ile yapar: hiç görülmedi, şu anda arama yığınında, tamamen işlendi. Bu yöntem yönlü çevrimler üzerindeki düğüm sayısını tam olarak verir.
\(c_p\) elde edilince ilgili asalın katkısı \(1+t\,c_p\) olur. Derlenen sürümler ayrıca birkaç küçük asalda bu hızlı yöntemi doğrudan yörünge simülasyonuyla karşılaştırır ve tam cevaba geçmeden önce küçük toplam değeri \(S(100)=127\) ile uyum kontrolü yapar.
Burada kullanılan doğrudan elek, \(L\)'ye kadar \(O(L \log \log L)\) zaman ve \(O(L)\) bellek kullanır. Elekten sonra her uygun asal için yalnızca sabit sayıda modüler üs alma ve sabit boyutlu bir graf dolaşımı gerekir. Her modüler üs alma \(O(\log p)\) çarpım gerektirdiğinden elek sonrası toplam iş
$$O\!\left(\sum_{\substack{p \le L\\ p \equiv 1 \pmod 5}} \log p\right)=O(\pi(L)\log L)$$
düzeyindedir.
Pratikte asıl önemli nokta şudur: yöntem, her asal için tüm \(p\) kalıntının yörüngesini ayrı ayrı incelemek yerine problemi beş sınıf geçişine ve beş düğümlü bir çevrim sayımına indirger. Ölçeklenebilirliği sağlayan şey tam olarak bu indirgemedir.
Para cada primo \(p \equiv 1 \pmod{5}\), el problema estudia la transformación polinómica
$$f_p(x)=x+x^{(p+4)/5}\pmod p,$$
cuenta cuántos residuos \(x \in \mathbb F_p\) son periódicos bajo iteración y llama \(C(p)\) a esa cantidad. La suma global calculada por las implementaciones es
$$S(L)=\sum_{\substack{p \le L\\ p \equiv 1 \pmod{5}}} C(p).$$
Un enfoque ingenuo tendría que recorrer todos los residuos para cada primo relevante y seguir de manera explícita la órbita de cada punto inicial. Eso ya es caro para un solo primo grande y resulta inviable cuando el límite llega a \(10^8\). La simplificación decisiva es que, para \(x \ne 0\), el comportamiento depende solo de la clase de quinta raíz a la que pertenece \(x^t\). Por eso cada primo se reduce a un grafo funcional de solo cinco estados.
La derivación empieza reescribiendo el exponente y después aprovecha la estructura multiplicativa de \(\mathbb F_p^\times\).
Escribimos
$$t=\frac{p-1}{5}, \qquad \frac{p+4}{5}=t+1.$$
Entonces, para todo \(x \ne 0\),
$$f_p(x)=x+x^{t+1}=x(1+x^t).$$
Como \(x^{p-1}=1\) en \(\mathbb F_p^\times\), se obtiene
$$\left(x^t\right)^5=x^{p-1}=1,$$
así que \(x^t\) siempre es una quinta raíz de la unidad. Elijamos un elemento \(\omega\) de orden 5. Entonces cada residuo no nulo pertenece a una única clase
$$A_r=\{x \in \mathbb F_p^\times : x^t=\omega^r\}, \qquad r=0,1,2,3,4.$$
Estas clases son las fibras del homomorfismo \(x \mapsto x^t\) desde el grupo cíclico \(\mathbb F_p^\times\) de tamaño \(5t\) hacia su subgrupo de quintas raíces de la unidad de tamaño 5, por lo que cada clase contiene exactamente \(t\) elementos.
Si \(x \in A_r\), entonces \(x^t=\omega^r\), y por tanto
$$f_p(x)=x(1+\omega^r).$$
El factor \(1+\omega^r\) no es cero: una quinta raíz de la unidad no puede ser \(-1\) cuando \(p\) es impar. Así,
$$f_p(x)^t=x^t(1+\omega^r)^t=\omega^r(1+\omega^r)^t.$$
Ahora \((1+\omega^r)^t\) vuelve a ser una quinta raíz de la unidad, de modo que existe un único \(s_r \in \{0,1,2,3,4\}\) tal que
$$ (1+\omega^r)^t=\omega^{s_r}. $$
De aquí se deduce que todo elemento de \(A_r\) va a la clase
$$A_{r+s_r \bmod 5}.$$
Para cada primo aparece entonces un grafo funcional de cinco nodos:
$$r \longmapsto r+s_r \pmod 5.$$
Ese grafo ya decide la periodicidad. La órbita exacta dentro de una clase aún depende de \(x\), pero la posibilidad de regresar al punto de partida queda determinada por la dinámica de clases.
Supongamos que la clase \(A_r\) está en un ciclo dirigido de longitud \(\ell\) del grafo de cinco nodos. Tras \(\ell\) iteraciones, cualquier \(x \in A_r\) vuelve a la misma clase, así que la \(\ell\)-ésima iteración actúa allí simplemente como multiplicación por un escalar fijo \(\lambda \in \mathbb F_p^\times\):
$$f_p^{(\ell)}(x)=\lambda x.$$
Como \(\lambda^{p-1}=1\), resulta
$$f_p^{(\ell(p-1))}(x)=x.$$
Por lo tanto, todo elemento de una clase situada en un ciclo es periódico. En cambio, si una clase no pertenece a un ciclo del grafo de clases, su etiqueta termina entrando en otro ciclo y nunca vuelve a la etiqueta inicial; por eso ningún elemento de esa clase puede ser periódico.
El residuo especial \(x=0\) es todavía más simple:
$$f_p(0)=0,$$
así que siempre es un punto fijo. Si \(c_p\) denota el número de nodos del grafo de cinco estados que pertenecen a ciclos, entonces
$$\boxed{C(p)=1+t\,c_p.}$$
Esa es exactamente la fórmula que evalúan las implementaciones.
Para \(p=11\), tenemos \(t=(11-1)/5=2\). Una elección posible de quinta raíz de la unidad es \(\omega=4\), ya que \(4^5 \equiv 1 \pmod{11}\) y \(4 \not\equiv 1\). Sus potencias son
$$1,\ 4,\ 5,\ 9,\ 3.$$
Las cinco clases quedan
$$A_0=\{1,10\},\quad A_1=\{2,9\},\quad A_2=\{4,7\},\quad A_3=\{3,8\},\quad A_4=\{5,6\}.$$
Calculamos ahora \((1+\omega^r)^2\):
$$2^2=4=\omega^1,\quad 5^2=3=\omega^4,\quad 6^2=3=\omega^4,\quad 10^2=1=\omega^0,\quad 4^2=5=\omega^2.$$
Por tanto, las transiciones de clases son
$$0 \to 1,\quad 1 \to 0,\quad 2 \to 1,\quad 3 \to 3,\quad 4 \to 1.$$
Los nodos cíclicos son \(0\), \(1\) y \(3\): hay un ciclo de longitud 2, \(0 \leftrightarrow 1\), y un punto fijo en \(3\). En consecuencia, \(c_{11}=3\) y
$$C(11)=1+2\cdot 3=7.$$
Ese valor coincide con el conteo directo de órbitas, pero aquí se obtiene sin enumerar todas las trayectorias.
Las implementaciones en C++, Python y Java generan primero todos los primos hasta el límite mediante una criba sencilla y luego conservan solo los que satisfacen \(p \equiv 1 \pmod 5\). A partir de ahí, todo se hace primo por primo.
Para un primo fijo \(p\), la implementación calcula \(t=(p-1)/5\) y busca una quinta raíz de la unidad no trivial probando bases pequeñas \(a\) hasta encontrar \(a^t \not\equiv 1 \pmod p\). Cualquier valor así tiene orden 5, porque su quinta potencia vale 1 y el propio valor no es 1. Después se forman explícitamente \(1,\omega,\omega^2,\omega^3,\omega^4\).
Para cada índice \(r\), el código evalúa \((1+\omega^r)^t \bmod p\), identifica con cuál potencia de \(\omega\) coincide y, con ello, fija el sucesor del nodo \(r\) en el grafo funcional.
Una vez construida la tabla de sucesores, solo queda detectar ciclos en un grafo de cinco nodos. Las implementaciones usan una exploración estándar con tres estados: no visitado, en la pila actual y ya procesado. Eso permite contar exactamente cuántos nodos pertenecen a ciclos dirigidos.
Con \(c_p\) ya conocido, la contribución del primo es \(1+t\,c_p\). Las implementaciones compiladas también comparan este método rápido con una simulación directa de órbitas para algunos primos pequeños y verifican el valor agregado pequeño \(S(100)=127\) antes de producir la respuesta completa.
La criba hasta \(L\) cuesta \(O(L \log \log L)\) tiempo y \(O(L)\) memoria en la forma directa usada aquí. Después de eso, cada primo relevante requiere solo un número constante de exponenciaciones modulares y un recorrido de tamaño constante. Como cada exponenciación modular cuesta \(O(\log p)\) multiplicaciones modulares, el trabajo posterior a la criba es
$$O\!\left(\sum_{\substack{p \le L\\ p \equiv 1 \pmod 5}} \log p\right)=O(\pi(L)\log L).$$
En la práctica, lo decisivo es la reducción estructural: en vez de estudiar las \(p\) órbitas posibles para cada primo, el algoritmo resume cada caso en cinco transiciones de clase y un conteo de ciclos en un grafo diminuto. Esa es la razón real de su eficiencia.
对每个满足 \(p \equiv 1 \pmod{5}\) 的素数，题目研究如下多项式映射：
$$f_p(x)=x+x^{(p+4)/5}\pmod p.$$
把在这个映射的反复迭代下最终会回到自身的元素 \(x \in \mathbb F_p\) 的个数记为 \(C(p)\)。实现中计算的总量是
$$S(L)=\sum_{\substack{p \le L\\ p \equiv 1 \pmod{5}}} C(p).$$
如果直接做，就要对每个相关素数枚举全部模 \(p\) 的剩余类，并逐个跟踪它们的轨道。这对单个大素数已经很慢，而在上界达到 \(10^8\) 时几乎不可行。真正的突破点在于：对所有非零元素来说，映射的行为只取决于 \(x^t\) 落在哪一个五次单位根类里，因此每个素数都可以压缩成一个只有五个状态的函数图。
整个推导从改写指数开始，然后利用 \(\mathbb F_p^\times\) 的乘法群结构。
记
$$t=\frac{p-1}{5}, \qquad \frac{p+4}{5}=t+1.$$
于是对任意 \(x \ne 0\)，都有
$$f_p(x)=x+x^{t+1}=x(1+x^t).$$
由于在 \(\mathbb F_p^\times\) 中 \(x^{p-1}=1\)，所以
$$\left(x^t\right)^5=x^{p-1}=1,$$
这说明 \(x^t\) 一定是某个五次单位根。取一个阶为 5 的元素 \(\omega\)。于是每个非零元素都唯一地属于某一类
$$A_r=\{x \in \mathbb F_p^\times : x^t=\omega^r\}, \qquad r=0,1,2,3,4.$$
这些集合正是群同态 \(x \mapsto x^t\) 的纤维。因为 \(\mathbb F_p^\times\) 是大小为 \(5t\) 的循环群，而五次单位根构成大小为 5 的子群，所以每个类恰好包含 \(t\) 个元素。
若 \(x \in A_r\)，则 \(x^t=\omega^r\)，从而
$$f_p(x)=x(1+\omega^r).$$
因子 \(1+\omega^r\) 不会是 0；在奇特征下，五次单位根不可能等于 \(-1\)。因此
$$f_p(x)^t=x^t(1+\omega^r)^t=\omega^r(1+\omega^r)^t.$$
而 \((1+\omega^r)^t\) 本身仍然是一个五次单位根，所以存在唯一的 \(s_r \in \{0,1,2,3,4\}\)，使得
$$ (1+\omega^r)^t=\omega^{s_r}. $$
于是 \(A_r\) 中的每个元素都会被送入同一个类
$$A_{r+s_r \bmod 5}.$$
这就把每个素数对应的动力系统压缩成一个五节点函数图：
$$r \longmapsto r+s_r \pmod 5.$$
判断一个元素是否可能成为周期点，其关键已经不在具体数值，而在于它所在的类标签在这个五节点图上是否会回到原处。
设类 \(A_r\) 位于五节点图中的一个长度为 \(\ell\) 的有向环上。经过 \(\ell\) 次迭代后，任意 \(x \in A_r\) 都会回到同一个类，因此在该类上，\(\ell\) 次迭代的效果只能是乘上某个固定的非零常数 \(\lambda \in \mathbb F_p^\times\)：
$$f_p^{(\ell)}(x)=\lambda x.$$
由于 \(\lambda^{p-1}=1\)，于是
$$f_p^{(\ell(p-1))}(x)=x.$$
这说明环上类中的每个元素都是周期点。反过来，如果一个类不在类图的环上，那么它的类标签最终会流入别的环，而且永远回不到起始类，所以这个类里的元素不可能是周期点。
特殊元素 \(x=0\) 更简单：
$$f_p(0)=0,$$
所以 0 始终是不动点。若记五节点图中位于有向环上的节点个数为 \(c_p\)，则
$$\boxed{C(p)=1+t\,c_p.}$$
这正是实现里实际使用的计数公式。
当 \(p=11\) 时，\(t=(11-1)/5=2\)。可以取 \(\omega=4\)，因为 \(4^5 \equiv 1 \pmod{11}\) 且 \(4 \not\equiv 1\)。它的幂依次为
$$1,\ 4,\ 5,\ 9,\ 3.$$
于是五个类分别是
$$A_0=\{1,10\},\quad A_1=\{2,9\},\quad A_2=\{4,7\},\quad A_3=\{3,8\},\quad A_4=\{5,6\}.$$
接着计算 \((1+\omega^r)^2\)：
$$2^2=4=\omega^1,\quad 5^2=3=\omega^4,\quad 6^2=3=\omega^4,\quad 10^2=1=\omega^0,\quad 4^2=5=\omega^2.$$
因此类之间的转移关系是
$$0 \to 1,\quad 1 \to 0,\quad 2 \to 1,\quad 3 \to 3,\quad 4 \to 1.$$
处于环上的节点是 \(0\)、\(1\) 和 \(3\)：其中 \(0 \leftrightarrow 1\) 构成一个长度为 2 的环，\(3\) 是一个不动点。所以 \(c_{11}=3\)，从而
$$C(11)=1+2\cdot 3=7.$$
这和直接枚举轨道得到的结果一致，但五状态模型完全避免了对所有轨道的逐个模拟。
C++、Python 和 Java 实现都先用一个直接筛法生成上界以内的全部素数，然后只保留满足 \(p \equiv 1 \pmod 5\) 的那些。之后的处理完全按素数逐个进行。
对于固定的 \(p\)，实现先计算 \(t=(p-1)/5\)，再从小底数开始试，寻找某个满足 \(a^t \not\equiv 1 \pmod p\) 的值。这样的值自动具有 5 阶，因为它的五次幂等于 1，但它本身不是 1。接着显式列出 \(1,\omega,\omega^2,\omega^3,\omega^4\) 这五个值。
对每个类编号 \(r\)，代码计算 \((1+\omega^r)^t \bmod p\)，判断它等于哪一个 \(\omega\) 的幂，从而得到五节点图中 \(r\) 的后继节点。
一旦后继表建立完毕，剩下的工作只是对一个五节点函数图做环检测。实现采用标准的三色或三状态遍历：未访问、当前搜索栈中、已处理完毕。这样可以准确统计有多少节点位于有向环上。
得到 \(c_p\) 之后，该素数的贡献就是 \(1+t\,c_p\)。编译型实现还会在若干个小素数上把这个快速方法和直接轨道模拟做对照，并在输出最终结果前确认小范围总和 \(S(100)=127\) 成立。
这里使用的直接筛法在上界 \(L\) 下需要 \(O(L \log \log L)\) 时间和 \(O(L)\) 空间。筛完之后，每个相关素数只需要常数次模幂运算以及一次常数规模的图遍历。由于一次模幂运算需要 \(O(\log p)\) 次模乘，因此筛后总工作量为
$$O\!\left(\sum_{\substack{p \le L\\ p \equiv 1 \pmod 5}} \log p\right)=O(\pi(L)\log L).$$
但从实际角度看，更重要的是结构性压缩：算法没有为每个素数检查全部 \(p\) 个起点的完整轨道，而是把问题概括成五个类的转移关系和一个五节点环计数。这正是它能处理完整上界的原因。
Для каждого простого числа \(p \equiv 1 \pmod{5}\) рассматривается полиномиальное отображение
$$f_p(x)=x+x^{(p+4)/5}\pmod p,$$
и требуется посчитать число элементов \(x \in \mathbb F_p\), которые являются периодическими точками при итерации этого отображения. Обозначим это число через \(C(p)\). Реализованный в программах суммарный объект имеет вид
$$S(L)=\sum_{\substack{p \le L\\ p \equiv 1 \pmod{5}}} C(p).$$
Прямой перебор означал бы, что для каждого подходящего простого нужно проследить орбиту каждого остатка по модулю \(p\). Для больших простых это уже дорого, а при верхней границе \(10^8\) такой подход становится непрактичным. Главное наблюдение состоит в том, что для ненулевых элементов поведение определяется только тем, к какому классу по пятым корням из единицы принадлежит \(x^t\). Поэтому для каждого простого вся динамика сжимается в функциональный граф из пяти вершин.
Вывод начинается с переписывания показателя степени и затем использует мультипликативную структуру группы \(\mathbb F_p^\times\).
Положим
$$t=\frac{p-1}{5}, \qquad \frac{p+4}{5}=t+1.$$
Тогда для любого \(x \ne 0\)
$$f_p(x)=x+x^{t+1}=x(1+x^t).$$
Поскольку в \(\mathbb F_p^\times\) выполнено \(x^{p-1}=1\), имеем
$$\left(x^t\right)^5=x^{p-1}=1,$$
то есть \(x^t\) всегда является пятым корнем из единицы. Выберем элемент \(\omega\) порядка 5. Тогда каждый ненулевой элемент принадлежит ровно одному классу
$$A_r=\{x \in \mathbb F_p^\times : x^t=\omega^r\}, \qquad r=0,1,2,3,4.$$
Это слои гомоморфизма \(x \mapsto x^t\) из циклической группы \(\mathbb F_p^\times\) размера \(5t\) на ее подгруппу пятых корней из единицы размера 5, поэтому в каждом классе ровно \(t\) элементов.
Если \(x \in A_r\), то \(x^t=\omega^r\), и значит
$$f_p(x)=x(1+\omega^r).$$
Множитель \(1+\omega^r\) не равен нулю: пятый корень из единицы не может совпадать с \(-1\) при нечетном \(p\). Поэтому
$$f_p(x)^t=x^t(1+\omega^r)^t=\omega^r(1+\omega^r)^t.$$
Величина \((1+\omega^r)^t\) снова является пятым корнем из единицы, так что существует единственный индекс \(s_r \in \{0,1,2,3,4\}\), для которого
$$ (1+\omega^r)^t=\omega^{s_r}. $$
Следовательно, весь класс \(A_r\) переходит в один и тот же класс
$$A_{r+s_r \bmod 5}.$$
Для каждого простого получается функциональный граф на пяти вершинах:
$$r \longmapsto r+s_r \pmod 5.$$
Именно этот граф определяет периодичность. Конкретная траектория внутри класса зависит от самого \(x\), но вопрос о возвращении к исходному состоянию решается уже на уровне классов.
Пусть класс \(A_r\) лежит на ориентированном цикле длины \(\ell\) в пятивершинном графе. После \(\ell\) итераций любой \(x \in A_r\) возвращается в тот же класс, а значит \(\ell\)-я итерация на этом классе сводится к умножению на фиксированный ненулевой элемент \(\lambda \in \mathbb F_p^\times\):
$$f_p^{(\ell)}(x)=\lambda x.$$
Так как \(\lambda^{p-1}=1\), получаем
$$f_p^{(\ell(p-1))}(x)=x.$$
Следовательно, каждый элемент класса, лежащего на цикле, является периодической точкой. Если же класс не лежит на цикле графа классов, то его метка со временем попадает в другой цикл и уже никогда не возвращается к исходной метке, поэтому периодических точек там быть не может.
Особый элемент \(x=0\) еще проще:
$$f_p(0)=0,$$
то есть это всегда неподвижная точка. Если \(c_p\) обозначает число вершин пятивершинного графа, лежащих на циклах, то
$$\boxed{C(p)=1+t\,c_p.}$$
Именно эту формулу и вычисляют реализации.
При \(p=11\) имеем \(t=(11-1)/5=2\). Можно взять \(\omega=4\), так как \(4^5 \equiv 1 \pmod{11}\) и \(4 \not\equiv 1\). Его степени равны
$$1,\ 4,\ 5,\ 9,\ 3.$$
Пять классов получаются такими:
$$A_0=\{1,10\},\quad A_1=\{2,9\},\quad A_2=\{4,7\},\quad A_3=\{3,8\},\quad A_4=\{5,6\}.$$
Далее считаем \((1+\omega^r)^2\):
$$2^2=4=\omega^1,\quad 5^2=3=\omega^4,\quad 6^2=3=\omega^4,\quad 10^2=1=\omega^0,\quad 4^2=5=\omega^2.$$
Отсюда переходы между классами таковы:
$$0 \to 1,\quad 1 \to 0,\quad 2 \to 1,\quad 3 \to 3,\quad 4 \to 1.$$
На циклах лежат вершины \(0\), \(1\) и \(3\): есть 2-цикл \(0 \leftrightarrow 1\) и неподвижная вершина \(3\). Значит, \(c_{11}=3\), и потому
$$C(11)=1+2\cdot 3=7.$$
Это совпадает с прямым подсчетом орбит, но здесь результат получается без полного перебора траекторий.
Реализации на C++, Python и Java сначала строят все простые числа до нужного предела обычным решетом, а затем оставляют только те, для которых \(p \equiv 1 \pmod 5\). После этого обработка идет по одному простому числу за раз.
Для фиксированного \(p\) программа вычисляет \(t=(p-1)/5\) и перебирает маленькие основания \(a\), пока не найдет значение с \(a^t \not\equiv 1 \pmod p\). Такое число автоматически имеет порядок 5: его пятая степень равна 1, но само число не равно 1. Затем явно строятся пять значений \(1,\omega,\omega^2,\omega^3,\omega^4\).
Для каждого индекса \(r\) код вычисляет \((1+\omega^r)^t \bmod p\), определяет, какой степени \(\omega\) оно равно, и тем самым задает следующую вершину в функциональном графе.
Когда таблица переходов готова, остается лишь найти циклы в графе из пяти вершин. Для этого используется стандартный обход с тремя состояниями: вершина не посещена, находится в текущем стеке обхода или уже полностью обработана. Такой подход точно считает число вершин, принадлежащих ориентированным циклам.
После нахождения \(c_p\) вклад простого равен \(1+t\,c_p\). Компилируемые реализации дополнительно сверяют быстрый метод с прямой симуляцией орбит для нескольких маленьких простых и проверяют малое суммарное значение \(S(100)=127\) перед выводом полного ответа.
Используемое здесь прямое решето требует \(O(L \log \log L)\) времени и \(O(L)\) памяти. После решета на каждый подходящий простой приходится лишь константное число модульных возведений в степень и обход графа постоянного размера. Поскольку одно модульное возведение в степень стоит \(O(\log p)\) умножений по модулю, суммарная работа после решета равна
$$O\!\left(\sum_{\substack{p \le L\\ p \equiv 1 \pmod 5}} \log p\right)=O(\pi(L)\log L).$$
Однако в практическом смысле важнее сама редукция: вместо того чтобы исследовать все \(p\) возможных стартов для каждого простого, алгоритм сводит задачу к пяти переходам между классами и крошечному подсчету циклов. Именно это делает полную границу достижимой.
لكل عدد أولي \(p \equiv 1 \pmod{5}\)، تدرس المسألة التحويل كثير الحدود
$$f_p(x)=x+x^{(p+4)/5}\pmod p,$$
ثم تحسب عدد العناصر \(x \in \mathbb F_p\) التي تكون دورية تحت تكرار هذا التحويل، ويرمز إلى هذا العدد بـ \(C(p)\). والكمية الكلية التي تحسبها التطبيقات هي
$$S(L)=\sum_{\substack{p \le L\\ p \equiv 1 \pmod{5}}} C(p).$$
الطريقة المباشرة ستجبرنا على تتبع مدار كل باقي modulo \(p\) لكل أولي مناسب، وهذا مكلف حتى لأوليات كبيرة منفردة، ويصبح غير عملي تمامًا عندما يصل الحد إلى \(10^8\). الفكرة الحاسمة هي أن سلوك العناصر غير الصفرية لا يعتمد على العنصر نفسه مباشرة، بل على الفئة التي ينتمي إليها \(x^t\) بين جذور الوحدة الخامسة. لذلك ينهار كل أولي إلى رسم وظيفي من خمس حالات فقط.
يبدأ الاشتقاق بإعادة كتابة الأس، ثم يستغل البنية الضربية للمجموعة \(\mathbb F_p^\times\).
لنكتب
$$t=\frac{p-1}{5}, \qquad \frac{p+4}{5}=t+1.$$
وعندئذ لكل \(x \ne 0\) نحصل على
$$f_p(x)=x+x^{t+1}=x(1+x^t).$$
وبما أن \(x^{p-1}=1\) في \(\mathbb F_p^\times\)، فإن
$$\left(x^t\right)^5=x^{p-1}=1,$$
أي إن \(x^t\) هو دائمًا جذر خامس للوحدة. نختار عنصرًا \(\omega\) رتبته 5. عندها ينتمي كل عنصر غير صفري إلى فئة واحدة بالضبط من الفئات
$$A_r=\{x \in \mathbb F_p^\times : x^t=\omega^r\}, \qquad r=0,1,2,3,4.$$
هذه الفئات هي ألياف التشاكل \(x \mapsto x^t\) من المجموعة الدورية \(\mathbb F_p^\times\) ذات الحجم \(5t\) إلى زمرة جذور الوحدة الخامسة ذات الحجم 5، ولذلك تحتوي كل فئة على \(t\) عنصرًا بالضبط.
إذا كان \(x \in A_r\)، فلدينا \(x^t=\omega^r\)، ومن ثم
$$f_p(x)=x(1+\omega^r).$$
العامل \(1+\omega^r\) غير صفري؛ فجذر خامس للوحدة لا يمكن أن يساوي \(-1\) عندما يكون \(p\) فرديًا. لذلك
$$f_p(x)^t=x^t(1+\omega^r)^t=\omega^r(1+\omega^r)^t.$$
والقيمة \((1+\omega^r)^t\) هي بدورها جذر خامس للوحدة، لذا يوجد عدد وحيد \(s_r \in \{0,1,2,3,4\}\) بحيث
$$ (1+\omega^r)^t=\omega^{s_r}. $$
إذن كل عنصر من الفئة \(A_r\) ينتقل إلى الفئة
$$A_{r+s_r \bmod 5}.$$
وهكذا نحصل لكل أولي على رسم وظيفي ذي خمس عقد:
$$r \longmapsto r+s_r \pmod 5.$$
هذا الرسم وحده يحسم مسألة الدورية. فالتفاصيل الدقيقة للحركة داخل الفئة تعتمد على \(x\)، لكن إمكانية العودة أصلًا تتحدد على مستوى فئات جذور الوحدة.
افترض أن الفئة \(A_r\) تقع على دورة موجهة طولها \(\ell\) في هذا الرسم ذي العقد الخمس. بعد \(\ell\) تكرارات يعود كل \(x \in A_r\) إلى الفئة نفسها، وبالتالي يصبح تأثير \(f_p^{(\ell)}\) على تلك الفئة مجرد ضرب في ثابت غير صفري \(\lambda \in \mathbb F_p^\times\):
$$f_p^{(\ell)}(x)=\lambda x.$$
وبما أن \(\lambda^{p-1}=1\)، فإن
$$f_p^{(\ell(p-1))}(x)=x.$$
إذًا كل عنصر في فئة تقع على دورة يكون نقطة دورية. وبالعكس، إذا لم تكن الفئة على دورة في رسم الفئات، فإن علامتها تتجه في النهاية إلى دورة أخرى ولا تعود إلى العلامة الابتدائية، ولذلك لا يمكن لأي عنصر فيها أن يكون دوريًا.
أما العنصر الخاص \(x=0\) فحالته أبسط:
$$f_p(0)=0,$$
ولهذا فهو نقطة ثابتة دائمًا. وإذا رمزنا بعدد العقد الواقعة على دورات في الرسم ذي الخمس عقد بالرمز \(c_p\)، فإن
$$\boxed{C(p)=1+t\,c_p.}$$
وهذه هي الصيغة التي تحسبها التطبيقات مباشرة.
عندما \(p=11\) يكون \(t=(11-1)/5=2\). ويمكن أخذ \(\omega=4\) لأن \(4^5 \equiv 1 \pmod{11}\) و\(4 \not\equiv 1\). قوى هذا العنصر هي
$$1,\ 4,\ 5,\ 9,\ 3.$$
ومن ثم تصبح الفئات الخمس
$$A_0=\{1,10\},\quad A_1=\{2,9\},\quad A_2=\{4,7\},\quad A_3=\{3,8\},\quad A_4=\{5,6\}.$$
نحسب الآن \((1+\omega^r)^2\):
$$2^2=4=\omega^1,\quad 5^2=3=\omega^4,\quad 6^2=3=\omega^4,\quad 10^2=1=\omega^0,\quad 4^2=5=\omega^2.$$
فتكون انتقالات الفئات
$$0 \to 1,\quad 1 \to 0,\quad 2 \to 1,\quad 3 \to 3,\quad 4 \to 1.$$
العقد الواقعة على دورات هي \(0\) و\(1\) و\(3\): توجد دورة بطول 2 هي \(0 \leftrightarrow 1\)، وعقدة ثابتة هي \(3\). لذلك \(c_{11}=3\)، ومنه
$$C(11)=1+2\cdot 3=7.$$
وهذا يطابق العد المباشر للمدارات، لكنه هنا ينتج من النموذج ذي الحالات الخمس فقط.
تنشئ تطبيقات C++ وPython وJava جميع الأعداد الأولية حتى الحد المطلوب بواسطة غربال مباشر، ثم تحتفظ فقط بالأوليات التي تحقق \(p \equiv 1 \pmod 5\). وبعد ذلك تتم المعالجة على مستوى كل أولي على حدة.
لأولي ثابت \(p\)، تحسب الشيفرة \(t=(p-1)/5\)، ثم تجرّب قواعد صغيرة \(a\) حتى تجد قيمة تحقق \(a^t \not\equiv 1 \pmod p\). وأي قيمة كهذه تكون تلقائيًا ذات رتبة 5، لأن قوتها الخامسة تساوي 1 لكنها ليست 1 نفسها. بعد ذلك تُبنى القيم الخمس \(1,\omega,\omega^2,\omega^3,\omega^4\) صراحةً.
لكل فهرس \(r\)، تحسب الشيفرة \((1+\omega^r)^t \bmod p\)، وتحدد أي قوة من قوى \(\omega\) تمثل هذه القيمة، ومن ثم تحدد العقدة التالية في الرسم الوظيفي.
بعد اكتمال جدول الانتقال، لا يبقى إلا كشف الدورات في رسم وظيفي من خمس عقد. تستخدم التطبيقات اجتيازًا قياسيًا بثلاث حالات: غير مزور، موجود حاليًا في مسار البحث، ومنتهٍ معالجته. وبهذا يمكن عد العقد الواقعة على الدورات الموجهة بدقة.
بعد الحصول على \(c_p\)، تكون مساهمة هذا الأولي هي \(1+t\,c_p\). كما أن التطبيقات المترجمة تتأكد أيضًا من صحة الطريقة السريعة عبر مقارنتها بمحاكاة مباشرة للمدارات لعدة أوليات صغيرة، وتتحقق من القيمة الصغيرة \(S(100)=127\) قبل طباعة النتيجة الكاملة.
الغربال المباشر المستخدم هنا يحتاج إلى زمن \(O(L \log \log L)\) وذاكرة \(O(L)\). وبعد مرحلة الغربال، يتطلب كل أولي مناسب عددًا ثابتًا من عمليات الأس المعياري واجتيازًا لرسم ثابت الحجم. وبما أن كل أس معياري يحتاج إلى \(O(\log p)\) عملية ضرب معيارية، فإن الكلفة بعد الغربال تساوي
$$O\!\left(\sum_{\substack{p \le L\\ p \equiv 1 \pmod 5}} \log p\right)=O(\pi(L)\log L).$$
لكن الأهم عمليًا هو طبيعة الاختزال نفسه: بدل فحص جميع المدارات الممكنة لكل أولي، تختصر الخوارزمية المسألة إلى خمس انتقالات بين الفئات وعدّ دورات في رسم صغير جدًا. وهذا هو السبب الحقيقي لقدرتها على الوصول إلى الحد الكامل.