The implementations do not explore the prime-ary tree by testing every integer up to \(N\) separately. Instead, they use a structural reduction: first identify which primes \(q\) satisfy the orbit condition that governs the problem, and then sum the squarefree products built from those primes. For the full task, the limit is \(N=10^7\).
The dynamical object attached to a prime modulus \(q\) and a prime exponent \(r\) is the orbit
$$x_0=1,\qquad x_{k+1}\equiv x_k^r+1 \pmod q.$$
A prime \(q\) is kept precisely when this orbit reaches \(0\) for every distinct prime divisor \(r\mid(q-1)\). Once those primes are known, the answer is the sum of all admissible squarefree products that do not exceed \(N\).
Write \(\mathcal P(m)\) for the set of distinct prime divisors of \(m\). The computation naturally splits into two layers: classify the primes that survive the orbit test, then enumerate the integers obtained by multiplying those primes without repetition.
For a prime \(q\) and a prime \(r\in\mathcal P(q-1)\), define
$$x_0^{(q,r)}=1,\qquad x_{k+1}^{(q,r)}\equiv \left(x_k^{(q,r)}\right)^r+1 \pmod q.$$
The implementations use the following acceptance criterion:
$$q\in\mathcal G \iff \forall r\in\mathcal P(q-1),\ \exists k\ge 0\text{ such that }x_k^{(q,r)}=0.$$
Only distinct prime divisors of \(q-1\) matter. If \(r^a\) divides \(q-1\), the condition attached to \(r\) is still checked only once, because the orbit depends on the prime exponent \(r\), not on its multiplicity in \(q-1\).
Modulo \(q\) there are only \(q\) possible residues, so every orbit is a finite-state process. Therefore exactly one of two things must happen:
$$\text{either some }x_k^{(q,r)}=0,\qquad\text{or a nonzero state repeats before }0\text{ appears.}$$
If the orbit ever repeats a nonzero value, the future evolution is periodic and \(0\) will never be reached afterward. This is why cycle detection with constant memory is enough; there is no need to store a full visited set.
There is also a useful invariant at the moment of success. If \(x_k^{(q,r)}=0\), then
$$x_{k+1}^{(q,r)}\equiv 0^r+1\equiv 1 \pmod q.$$
So hitting \(0\) means that the orbit starting from \(1\) has closed into a cycle containing both \(1\) and \(0\). The code exploits exactly this hit-or-cycle dichotomy.
Let \(\mathcal G\) be the set of primes that pass every required orbit test. The implementations then treat the admissible integers up to \(N\) as
$$\mathcal S(N)=\left\{\prod_{q\in T} q:\ T\subseteq\mathcal G,\ \prod_{q\in T} q\le N\right\}.$$
The empty subset contributes the empty product \(1\), so \(1\) is always included. The desired sum is therefore
$$A(N)=\sum_{n\in\mathcal S(N)} n=\sum_{\substack{T\subseteq\mathcal G\\ \prod_{q\in T}\le N}}\prod_{q\in T} q.$$
This description is squarefree by construction: each accepted prime can appear at most once. The compiled implementations even contain spot-checks against naively extending an accepted prime to \(q^2\), which supports the fact that repeated prime powers are not part of the final search space.
The first few primes already show how the criterion behaves.
For \(q=2\), we have \(q-1=1\), so \(\mathcal P(q-1)=\varnothing\). The condition is vacuous, hence \(2\in\mathcal G\).
For \(q=3\), the only relevant exponent is \(r=2\), and the orbit is
$$1\to 2\to 2\to 2\to\cdots \pmod 3,$$
so \(0\) is never reached. Therefore \(3\notin\mathcal G\).
For \(q=5\), again only \(r=2\) matters, but now
$$1\to 2\to 0\to 1\to\cdots \pmod 5,$$
so \(5\in\mathcal G\).
For \(q=7\), the relevant exponents are \(2\) and \(3\). The orbit for \(r=3\) is
$$1\to 2\to 2\to 2\to\cdots \pmod 7,$$
which already fails, so \(7\notin\mathcal G\).
Hence, up to \(20\), the accepted primes are exactly \(\{2,5\}\). The admissible squarefree products are
$$1,\ 2,\ 5,\ 10,$$
and therefore
$$A(20)=1+2+5+10=18.$$
This is the first built-in checkpoint in the implementations. A second checkpoint is \(A(1000)=2089\), which tests the same logic on a larger range.
All three language paths follow the same mathematical decomposition: build arithmetic infrastructure first, classify primes second, and enumerate squarefree products last.
The first stage is a linear sieve up to \(N\). It produces the prime list together with the smallest prime factor of every integer up to the limit, so factoring \(q-1\) is fast for each candidate prime \(q\).
For every \(q\), the implementation extracts the distinct primes in \(\mathcal P(q-1)\) and runs the orbit test modulo \(q\) for each of them. The transition \(x\mapsto x^r+1\pmod q\) is computed directly when \(r=2\), and by modular exponentiation for larger \(r\). Because the orbit can only hit \(0\) or enter a disjoint cycle, constant-memory cycle detection is sufficient.
The C++ implementation parallelizes this prime-screening phase across several workers. The Java implementation performs the same logic serially. The Python entry point reuses the same compiled computation instead of re-implementing the full search in pure Python.
After \(\mathcal G\) has been constructed, the remaining task is a depth-first enumeration over increasing prime indices. At each recursive state, the current product is added to the running sum, and the search continues only with later accepted primes. That ordering rule automatically prevents repeated use of the same prime.
The essential pruning inequality is
$$\text{current} \gt \frac{N}{q_{\text{next}}}.$$
Once it holds, multiplying by the next available prime would already exceed \(N\), so the entire suffix of that branch can be skipped. The compiled implementations also keep the checkpoints \(A(20)=18\) and \(A(1000)=2089\), plus small spot-checks involving \(q^2\), before running the full computation at \(N=10^7\).
The sieve stage is \(O(N)\) time and \(O(N)\) memory in the implemented model, because it stores the smallest prime factor of every integer up to \(N\). Once that table exists, extracting \(\mathcal P(q-1)\) is cheap.
For a fixed test pair \((q,r)\), the orbit phase inspects at most \(q\) residues before it either finds \(0\) or proves that the orbit cycles elsewhere. Each step costs \(O(1)\) when \(r=2\) and \(O(\log r)\) modular multiplications otherwise. A direct expression for the screening cost is
$$O\!\left(N+\sum_{\substack{q\le N\\ q\text{ prime}}}\ \sum_{r\in\mathcal P(q-1)} q\log r\right).$$
The final depth-first search is output-sensitive in practice rather than powerset-sized, because it explores only branches whose current squarefree product is still at most \(N\). Its memory usage is the recursion depth plus the stored list of accepted primes, both much smaller than the sieve table.
Die Implementierungen durchsuchen den prime-ary tree nicht, indem sie jede Zahl bis \(N\) einzeln prüfen. Stattdessen verwenden sie eine strukturelle Reduktion: Zuerst wird bestimmt, welche Primzahlen \(q\) die zugehörige Bahnbedingung erfüllen, und danach werden die quadratfreien Produkte genau dieser Primzahlen summiert. Für die eigentliche Aufgabe gilt \(N=10^7\).
Das dynamische Objekt zu einem Primmodul \(q\) und einem Primexponenten \(r\) ist die Bahn
$$x_0=1,\qquad x_{k+1}\equiv x_k^r+1 \pmod q.$$
Eine Primzahl \(q\) bleibt genau dann erhalten, wenn diese Bahn für jeden verschiedenen Primteiler \(r\mid(q-1)\) irgendwann den Wert \(0\) erreicht. Sobald diese Primzahlen bekannt sind, ist die gesuchte Summe einfach die Summe aller zulässigen quadratfreien Produkte \(\le N\).
Bezeichne mit \(\mathcal P(m)\) die Menge der verschiedenen Primteiler von \(m\). Die Rechnung zerfällt ganz natürlich in zwei Ebenen: zuerst die Klassifikation der zulässigen Primzahlen, danach die Aufzählung der Zahlen, die man aus ihnen ohne Wiederholung aufbauen darf.
Für eine Primzahl \(q\) und eine Primzahl \(r\in\mathcal P(q-1)\) definieren wir
$$x_0^{(q,r)}=1,\qquad x_{k+1}^{(q,r)}\equiv \left(x_k^{(q,r)}\right)^r+1 \pmod q.$$
Die Implementierungen verwenden dann genau das Kriterium
$$q\in\mathcal G \iff \forall r\in\mathcal P(q-1),\ \exists k\ge 0\text{ mit }x_k^{(q,r)}=0.$$
Dabei sind nur die verschiedenen Primteiler von \(q-1\) relevant. Tritt \(r\) in \(q-1\) mit einer höheren Potenz auf, entsteht dadurch kein neuer Testfall, weil die Bahn nur vom Primexponenten \(r\) abhängt, nicht von dessen Vielfachheit.
Modulo \(q\) gibt es nur \(q\) Restklassen, also ist jede Bahn ein endlicher Zustandsprozess. Deshalb muss genau eines von zwei Dingen passieren:
$$\text{entweder gilt für ein }k:\ x_k^{(q,r)}=0,\qquad\text{oder ein von Null verschiedener Zustand wiederholt sich vor }0.$$
Wird ein nichtnulliger Wert wiederholt, so ist die weitere Entwicklung periodisch, und \(0\) kann danach nie mehr auftauchen. Genau deshalb genügt eine Zyklenerkennung mit konstantem Speicher; eine vollständige Menge besuchter Zustände ist nicht erforderlich.
Außerdem gibt es beim Erfolg eine einfache Invariante. Falls \(x_k^{(q,r)}=0\), dann folgt unmittelbar
$$x_{k+1}^{(q,r)}\equiv 0^r+1\equiv 1 \pmod q.$$
Das Treffen von \(0\) bedeutet also, dass sich die von \(1\) gestartete Bahn zu einem Zyklus schließt, der sowohl \(1\) als auch \(0\) enthält. Genau diese Alternative „\(0\) treffen oder in einem fremden Zyklus landen“ nutzt der Code aus.
Sei \(\mathcal G\) die Menge aller Primzahlen, die jeden benötigten Bahntest bestehen. Die Implementierungen behandeln die zulässigen Zahlen bis \(N\) dann als
$$\mathcal S(N)=\left\{\prod_{q\in T} q:\ T\subseteq\mathcal G,\ \prod_{q\in T} q\le N\right\}.$$
Die leere Teilmenge liefert das leere Produkt \(1\), also ist \(1\) immer enthalten. Damit lautet die gesuchte Summe
$$A(N)=\sum_{n\in\mathcal S(N)} n=\sum_{\substack{T\subseteq\mathcal G\\ \prod_{q\in T}\le N}}\prod_{q\in T} q.$$
Diese Beschreibung ist von vornherein quadratfrei: Jede akzeptierte Primzahl darf höchstens einmal vorkommen. Die kompilierten Implementierungen enthalten sogar Stichproben gegen das naive Hochheben eines akzeptierten \(q\) zu \(q^2\), was die Tatsache stützt, dass wiederholte Primzahlpotenzen nicht zum endgültigen Suchraum gehören.
Schon die ersten Primzahlen zeigen gut, wie das Kriterium arbeitet.
Für \(q=2\) gilt \(q-1=1\), also \(\mathcal P(q-1)=\varnothing\). Die Bedingung ist leer und damit automatisch erfüllt, also \(2\in\mathcal G\).
Für \(q=3\) ist nur \(r=2\) relevant, und die Bahn lautet
$$1\to 2\to 2\to 2\to\cdots \pmod 3,$$
also wird \(0\) nie erreicht. Damit ist \(3\notin\mathcal G\).
Für \(q=5\) ist wieder nur \(r=2\) relevant, jetzt aber
$$1\to 2\to 0\to 1\to\cdots \pmod 5,$$
also \(5\in\mathcal G\).
Für \(q=7\) müssen \(2\) und \(3\) geprüft werden. Die Bahn für \(r=3\) ist
$$1\to 2\to 2\to 2\to\cdots \pmod 7,$$
und scheitert damit sofort. Also ist \(7\notin\mathcal G\).
Bis \(20\) sind daher genau \(\{2,5\}\) akzeptiert. Die zulässigen quadratfreien Produkte sind
$$1,\ 2,\ 5,\ 10,$$
und folglich
$$A(20)=1+2+5+10=18.$$
Das ist der erste eingebaute Prüfwert der Implementierungen. Ein zweiter Prüfwert ist \(A(1000)=2089\); damit werden dieselben Ideen in einem größeren Bereich kontrolliert.
Alle drei Sprachpfade folgen derselben mathematischen Zerlegung: zuerst die arithmetische Infrastruktur aufbauen, danach Primzahlen klassifizieren und zuletzt quadratfreie Produkte aufsummieren.
Die erste Stufe ist ein lineares Sieb bis \(N\). Es erzeugt die Primzahlliste und zugleich den kleinsten Primfaktor jeder Zahl bis zur Grenze, sodass die Faktorisierung von \(q-1\) für jedes Kandidaten-\(q\) schnell erledigt ist.
Für jedes \(q\) extrahiert die Implementierung die verschiedenen Primzahlen in \(\mathcal P(q-1)\) und führt für jede davon den Bahntest modulo \(q\) aus. Der Übergang \(x\mapsto x^r+1\pmod q\) wird für \(r=2\) direkt berechnet und für größere \(r\) über modulare Exponentiation. Weil eine Bahn nur \(0\) treffen oder in einen disjunkten Zyklus geraten kann, reicht eine Zyklenerkennung mit konstantem Speicher.
Die C++-Implementierung parallelisiert diese Primzahlfilterung über mehrere Worker. Die Java-Implementierung führt dieselbe Logik seriell aus. Der Python-Einstiegspunkt nutzt dieselbe kompilierte Berechnung weiter, anstatt die gesamte Suche rein in Python nachzubauen.
Nachdem \(\mathcal G\) feststeht, bleibt eine Tiefensuche über wachsende Primindizes. In jedem rekursiven Zustand wird das aktuelle Produkt zur Summe addiert, und die Suche geht nur mit späteren akzeptierten Primzahlen weiter. Diese feste Reihenfolge verhindert automatisch jede Wiederholung eines Primfaktors.
Die zentrale Abschneidebedingung ist
$$\text{current} \gt \frac{N}{q_{\text{next}}}.$$
Sobald sie gilt, würde schon die Multiplikation mit der nächsten verfügbaren Primzahl die Schranke \(N\) überschreiten, also kann der gesamte Restzweig übersprungen werden. Die kompilierten Implementierungen behalten außerdem die Prüfwerte \(A(20)=18\) und \(A(1000)=2089\) sowie kleine Stichproben mit \(q^2\) bei, bevor die volle Rechnung für \(N=10^7\) ausgeführt wird.
Die Siebstufe benötigt im implementierten Modell \(O(N)\) Zeit und \(O(N)\) Speicher, weil der kleinste Primfaktor jeder Zahl bis \(N\) gespeichert wird. Ist diese Tabelle einmal vorhanden, ist die Bestimmung von \(\mathcal P(q-1)\) billig.
Für ein festes Testpaar \((q,r)\) untersucht die Bahnstufe höchstens \(q\) Restklassen, bevor sie entweder \(0\) findet oder beweist, dass die Bahn anderswo zyklisch wird. Jeder Schritt kostet \(O(1)\) für \(r=2\) und sonst \(O(\log r)\) modulare Multiplikationen. Die Filterphase lässt sich daher direkt als
$$O\!\left(N+\sum_{\substack{q\le N\\ q\text{ prime}}}\ \sum_{r\in\mathcal P(q-1)} q\log r\right)$$
schreiben.
Die abschließende Tiefensuche ist in der Praxis ausgabeabhängig statt potenzmengen-groß, weil nur Zweige verfolgt werden, deren aktuelles quadratfreies Produkt noch \(\le N\) ist. Speicher benötigt sie nur für die Rekursionstiefe und die Liste akzeptierter Primzahlen, also weit weniger als das Sieb.
Uygulamalar prime-ary tree yapısını, \(N\)'ye kadar her tamsayıyı tek tek test ederek dolaşmıyor. Bunun yerine yapısal bir indirgeme kullanıyorlar: önce hangi asallar \(q\) için ilgili yörünge koşulunun sağlandığını belirliyorlar, sonra yalnızca bu asallardan kurulan karefree çarpımları topluyorlar. Tam problem için sınır \(N=10^7\).
Bir asal modül \(q\) ve bir asal üs \(r\) için dinamik nesne şu yörüngedir:
$$x_0=1,\qquad x_{k+1}\equiv x_k^r+1 \pmod q.$$
Bir asal \(q\), ancak \(q-1\)'in her farklı asal böleni \(r\) için bu yörünge sonunda \(0\)'a ulaşıyorsa kabul edilir. Bu asallar belirlendikten sonra cevap, \(N\)'yi aşmayan uygun karefree çarpımların toplamıdır.
\(\mathcal P(m)\) ile \(m\)'in farklı asal bölenleri kümesini gösterelim. Hesap doğal olarak iki katmana ayrılır: önce yörünge testini geçen asalları sınıflandırmak, sonra bu asalları tekrar etmeden çarparak oluşan sayıları toplamak.
Bir asal \(q\) ve \(r\in\mathcal P(q-1)\) olan bir asal \(r\) için
$$x_0^{(q,r)}=1,\qquad x_{k+1}^{(q,r)}\equiv \left(x_k^{(q,r)}\right)^r+1 \pmod q$$
tanımını yapalım. Uygulamaların kullandığı kabul ölçütü tam olarak şudur:
$$q\in\mathcal G \iff \forall r\in\mathcal P(q-1),\ \exists k\ge 0\text{ öyle ki }x_k^{(q,r)}=0.$$
Burada yalnızca \(q-1\)'in farklı asal bölenleri önemlidir. Eğer \(r^a\), \(q-1\)'i bölüyorsa, \(r\) için yine tek bir test yapılır; çünkü yörüngeyi belirleyen şey \(r\) asalının kendisidir, kuvveti değildir.
\(q\) modunda yalnızca \(q\) farklı kalan sınıfı vardır; dolayısıyla her yörünge sonlu durumlu bir süreçtir. Bu yüzden yalnızca iki olasılık vardır:
$$\text{ya bir }k\text{ için }x_k^{(q,r)}=0,\qquad\text{ya da }0\text{ görülmeden önce sıfırdan farklı bir durum tekrar eder.}$$
Eğer sıfır olmayan bir değer tekrar ederse, sonraki davranış periyodik olur ve artık \(0\)'a ulaşılamaz. Bu nedenle sabit bellekli döngü tespiti yeterlidir; bütün ziyaret edilmiş değerleri saklamaya gerek yoktur.
Başarı anında basit bir değişmez de vardır. Eğer \(x_k^{(q,r)}=0\) ise, hemen ardından
$$x_{k+1}^{(q,r)}\equiv 0^r+1\equiv 1 \pmod q$$
olur. Yani \(0\)'a ulaşmak, \(1\)'den başlayan yörüngenin hem \(1\)'i hem \(0\)'ı içeren bir çevrime kapandığı anlamına gelir. Kod tam olarak bu “\(0\)'a in ya da başka bir döngüye kilitlen” ayrımını kullanır.
\(\mathcal G\), bütün gerekli yörünge testlerini geçen asallar kümesi olsun. Uygulamalar \(N\)'ye kadar olan geçerli sayıları şu biçimde ele alır:
$$\mathcal S(N)=\left\{\prod_{q\in T} q:\ T\subseteq\mathcal G,\ \prod_{q\in T} q\le N\right\}.$$
Boş altküme boş çarpım olan \(1\)'i verdiği için, \(1\) her zaman dahildir. Dolayısıyla istenen toplam
$$A(N)=\sum_{n\in\mathcal S(N)} n=\sum_{\substack{T\subseteq\mathcal G\\ \prod_{q\in T}\le N}}\prod_{q\in T} q$$
şeklindedir. Bu tanım gereği karefree bir yapıdadır; her kabul edilen asal en fazla bir kez kullanılabilir. Derlenmiş uygulamalar, kabul edilen bir \(q\)'nun safça \(q^2\)'ye yükseltilmemesi gerektiğini küçük doğrulamalarla ayrıca kontrol eder; bu da tekrar eden asal kuvvetlerin son arama uzayında olmadığını destekler.
İlk birkaç asal, ölçütün nasıl çalıştığını açıkça gösterir.
\(q=2\) için \(q-1=1\) olduğundan \(\mathcal P(q-1)=\varnothing\). Koşul boş olduğu için \(2\in\mathcal G\).
\(q=3\) için yalnızca \(r=2\) önemlidir ve yörünge
$$1\to 2\to 2\to 2\to\cdots \pmod 3$$
olur; yani \(0\) hiç gelmez. Demek ki \(3\notin\mathcal G\).
\(q=5\) için yine sadece \(r=2\) vardır, ama bu kez
$$1\to 2\to 0\to 1\to\cdots \pmod 5$$
elde edilir; dolayısıyla \(5\in\mathcal G\).
\(q=7\) için \(2\) ve \(3\) sınanmalıdır. \(r=3\) için yörünge
$$1\to 2\to 2\to 2\to\cdots \pmod 7$$
olduğundan \(7\) hemen elenir.
Böylece \(20\)'ye kadar kabul edilen asallar tam olarak \(\{2,5\}\) olur. Geçerli karefree çarpımlar
$$1,\ 2,\ 5,\ 10$$
olduğundan
$$A(20)=1+2+5+10=18$$
çıkar. Bu, uygulamalardaki ilk kontrol noktasıdır. İkinci kontrol noktası \(A(1000)=2089\) değeridir; aynı mantık daha geniş bir aralıkta burada sınanır.
Üç dil yolunun da izlediği matematik aynıdır: önce aritmetik altyapıyı kur, sonra asalları sınıflandır, en sonda karefree çarpımları topla.
İlk aşama \(N\)'ye kadar lineer bir elektir. Bu elek hem asal listesini hem de sınıra kadar her sayının en küçük asal bölenini verir; böylece her aday asal \(q\) için \(q-1\)'i çarpanlara ayırmak hızlı olur.
Her \(q\) için uygulama, \(\mathcal P(q-1)\) içindeki farklı asalları çıkarır ve her biri için mod \(q\) altında yörünge testini çalıştırır. \(x\mapsto x^r+1\pmod q\) geçişi \(r=2\) olduğunda doğrudan hesaplanır, daha büyük \(r\) için modüler üs alma kullanılır. Yörünge ya \(0\)'a iner ya da ayrık bir döngüye girer; bu yüzden sabit bellekli döngü tespiti yeterlidir.
C++ uygulaması bu asal tarama aşamasını birkaç işçiye böler. Java uygulaması aynı mantığı seri yürütür. Python giriş noktası ise tam aramayı saf Python'da yeniden yazmak yerine aynı derlenmiş hesabı kullanır.
\(\mathcal G\) belirlendikten sonra geriye artan asal indisleri üzerinde derinlik öncelikli bir arama kalır. Her özyinelemeli durumda mevcut çarpım toplama eklenir ve arama yalnızca daha sonraki kabul edilmiş asallarla devam eder. Bu sabit sıra, aynı asalın ikinci kez seçilmesini otomatik olarak engeller.
Temel budama eşitsizliği
$$\text{current} \gt \frac{N}{q_{\text{next}}}$$
şeklindedir. Bu sağlandığında sıradaki asalla çarpmak bile \(N\)'yi aşacağı için, o dalın tüm devamı atlanabilir. Derlenmiş uygulamalar ayrıca tam \(N=10^7\) koşusundan önce \(A(20)=18\), \(A(1000)=2089\) ve bazı \(q^2\) kontrollerini de çalıştırır.
Uygulanan modelde elek aşaması \(O(N)\) zaman ve \(O(N)\) bellek kullanır; çünkü \(N\)'ye kadar her sayı için en küçük asal bölen saklanır. Bu tablo kurulduktan sonra \(\mathcal P(q-1)\) kümesini çıkarmak ucuzdur.
Sabit bir \((q,r)\) test çifti için yörünge aşaması, ya \(0\)'ı bulana ya da başka bir döngüye girdiğini kanıtlayana kadar en fazla \(q\) kalan sınıfı inceler. Her adımın maliyeti \(r=2\) için \(O(1)\), diğer durumlarda \(O(\log r)\) modüler çarpımdır. Bu yüzden tarama maliyeti doğrudan
$$O\!\left(N+\sum_{\substack{q\le N\\ q\text{ prime}}}\ \sum_{r\in\mathcal P(q-1)} q\log r\right)$$
olarak yazılabilir.
Son derinlik öncelikli arama pratikte tüm kuvvet kümesini gezmez; yalnızca mevcut karefree çarpımı hâlâ \(\le N\) olan dallar açılır. Bellek kullanımı özyineleme derinliği ve kabul edilen asallar listesidir; bunlar elek tablosundan çok daha küçüktür.
Las implementaciones no recorren el prime-ary tree comprobando por separado cada entero hasta \(N\). En su lugar usan una reducción estructural: primero determinan qué primos \(q\) satisfacen la condición de órbita que gobierna el problema y después suman los productos libres de cuadrados construidos con esos primos. En el problema completo el límite es \(N=10^7\).
El objeto dinámico asociado a un módulo primo \(q\) y a un exponente primo \(r\) es la órbita
$$x_0=1,\qquad x_{k+1}\equiv x_k^r+1 \pmod q.$$
Un primo \(q\) se conserva exactamente cuando esa órbita alcanza \(0\) para todo divisor primo distinto \(r\mid(q-1)\). Una vez conocida esa colección de primos, la respuesta es la suma de todos los productos libres de cuadrados admisibles que no superan \(N\).
Denotemos por \(\mathcal P(m)\) el conjunto de divisores primos distintos de \(m\). El cálculo se separa de forma natural en dos capas: clasificar los primos que sobreviven al test dinámico y luego enumerar los enteros obtenidos al multiplicarlos sin repetición.
Para un primo \(q\) y un primo \(r\in\mathcal P(q-1)\), definimos
$$x_0^{(q,r)}=1,\qquad x_{k+1}^{(q,r)}\equiv \left(x_k^{(q,r)}\right)^r+1 \pmod q.$$
El criterio de aceptación usado por las implementaciones es
$$q\in\mathcal G \iff \forall r\in\mathcal P(q-1),\ \exists k\ge 0\text{ tal que }x_k^{(q,r)}=0.$$
Solo importan los divisores primos distintos de \(q-1\). Si \(r^a\) divide a \(q-1\), la condición correspondiente a \(r\) se evalúa una sola vez, porque la órbita depende del exponente primo \(r\) y no de su multiplicidad dentro de \(q-1\).
Módulo \(q\) solo existen \(q\) residuos, así que toda órbita es un proceso finito. Por tanto solo pueden ocurrir dos cosas:
$$\text{o bien existe }k\text{ con }x_k^{(q,r)}=0,\qquad\text{o bien un estado no nulo se repite antes de ver }0.$$
Si se repite un valor no nulo, la evolución futura se vuelve periódica y \(0\) ya no podrá aparecer. Esa es exactamente la razón por la que basta una detección de ciclos con memoria constante; no hace falta guardar todos los residuos visitados.
Además, en el instante de éxito hay una invariante muy simple. Si \(x_k^{(q,r)}=0\), entonces
$$x_{k+1}^{(q,r)}\equiv 0^r+1\equiv 1 \pmod q.$$
Así, alcanzar \(0\) significa que la órbita iniciada en \(1\) se ha cerrado en un ciclo que contiene a la vez a \(1\) y a \(0\). El código explota exactamente esa dicotomía entre “tocar \(0\)” y “quedar atrapado en otro ciclo”.
Sea \(\mathcal G\) el conjunto de primos que superan todas las pruebas de órbita requeridas. Las implementaciones tratan entonces los enteros admisibles hasta \(N\) como
$$\mathcal S(N)=\left\{\prod_{q\in T} q:\ T\subseteq\mathcal G,\ \prod_{q\in T} q\le N\right\}.$$
El subconjunto vacío aporta el producto vacío \(1\), así que \(1\) siempre forma parte del conjunto. En consecuencia, la suma pedida es
$$A(N)=\sum_{n\in\mathcal S(N)} n=\sum_{\substack{T\subseteq\mathcal G\\ \prod_{q\in T}\le N}}\prod_{q\in T} q.$$
Esta descripción es libre de cuadrados por construcción: cada primo aceptado puede aparecer como mucho una vez. Las implementaciones compiladas incluso incluyen comprobaciones puntuales contra la extensión ingenua de un primo aceptado a \(q^2\), lo que refuerza que las potencias repetidas de un mismo primo no pertenecen al espacio de búsqueda final.
Los primeros primos ya muestran con claridad cómo funciona el criterio.
Para \(q=2\), se tiene \(q-1=1\), de modo que \(\mathcal P(q-1)=\varnothing\). La condición es vacía y por tanto \(2\in\mathcal G\).
Para \(q=3\), solo importa \(r=2\), y la órbita es
$$1\to 2\to 2\to 2\to\cdots \pmod 3,$$
así que \(0\) nunca aparece. Por eso \(3\notin\mathcal G\).
Para \(q=5\), otra vez solo importa \(r=2\), pero ahora
$$1\to 2\to 0\to 1\to\cdots \pmod 5,$$
y por consiguiente \(5\in\mathcal G\).
Para \(q=7\), hay que probar \(2\) y \(3\). La órbita correspondiente a \(r=3\) es
$$1\to 2\to 2\to 2\to\cdots \pmod 7,$$
así que \(7\) queda descartado inmediatamente.
De este modo, hasta \(20\), los primos aceptados son exactamente \(\{2,5\}\). Los productos admisibles libres de cuadrados son
$$1,\ 2,\ 5,\ 10,$$
y por tanto
$$A(20)=1+2+5+10=18.$$
Ese es el primer punto de control incorporado en las implementaciones. El segundo es \(A(1000)=2089\), que prueba la misma reducción en un intervalo más amplio.
Los tres caminos de implementación siguen la misma descomposición matemática: primero construyen la infraestructura aritmética, luego clasifican los primos y al final enumeran los productos libres de cuadrados.
La primera etapa es un cribado lineal hasta \(N\). Produce la lista de primos y, al mismo tiempo, el menor factor primo de cada entero hasta el límite, de modo que factorizar \(q-1\) para cada primo candidato \(q\) es rápido.
Para cada \(q\), la implementación extrae los primos distintos de \(\mathcal P(q-1)\) y ejecuta el test de órbita módulo \(q\) para cada uno. La transición \(x\mapsto x^r+1\pmod q\) se calcula directamente cuando \(r=2\) y mediante exponenciación modular cuando \(r\) es mayor. Como la órbita solo puede alcanzar \(0\) o entrar en un ciclo disjunto, basta detección de ciclos con memoria constante.
La implementación en C++ paraleliza esta fase de cribado de primos entre varios trabajadores. La implementación en Java realiza la misma lógica de forma secuencial. El punto de entrada en Python reutiliza el mismo cálculo compilado en vez de reescribir toda la búsqueda en Python puro.
Una vez construida \(\mathcal G\), lo que queda es una enumeración en profundidad sobre índices de primos crecientes. En cada estado recursivo se añade el producto actual a la suma, y la búsqueda continúa solo con primos aceptados posteriores. Esa regla de orden por sí sola impide reutilizar un mismo primo.
La desigualdad de poda esencial es
$$\text{current} \gt \frac{N}{q_{\text{next}}}.$$
Cuando se cumple, multiplicar por el siguiente primo disponible ya superaría \(N\), de modo que puede descartarse toda la cola de esa rama. Las implementaciones compiladas también conservan los controles \(A(20)=18\) y \(A(1000)=2089\), junto con pequeñas comprobaciones sobre \(q^2\), antes de ejecutar el cálculo completo con \(N=10^7\).
La etapa del cribado cuesta \(O(N)\) tiempo y \(O(N)\) memoria en el modelo implementado, porque almacena el menor factor primo de cada entero hasta \(N\). Una vez disponible esa tabla, obtener \(\mathcal P(q-1)\) resulta barato.
Para un par fijo \((q,r)\), la fase de órbita inspecciona como máximo \(q\) residuos antes de hallar \(0\) o demostrar que la órbita cicla en otro lugar. Cada paso cuesta \(O(1)\) cuando \(r=2\) y \(O(\log r)\) multiplicaciones modulares en caso contrario. Por tanto, el coste del cribado puede escribirse como
$$O\!\left(N+\sum_{\substack{q\le N\\ q\text{ prime}}}\ \sum_{r\in\mathcal P(q-1)} q\log r\right).$$
La búsqueda en profundidad final es sensible a la salida real y no al tamaño completo del conjunto potencia, porque solo explora ramas cuyo producto libre de cuadrados sigue siendo como mucho \(N\). Su memoria es la profundidad de recursión más la lista de primos aceptados, ambas muy inferiores al tamaño del cribado.
这些实现并不是把 \(1\) 到 \(N\) 的每个整数都单独拿出来检查，而是先把 prime-ary tree 的结构压缩成一个更容易处理的筛选问题：先判定哪些素数 \(q\) 通过题目要求的轨道条件，再把这些素数组成的不重复乘积加起来。完整题目的上界是 \(N=10^7\)。
与一个素数模数 \(q\) 和一个素数指数 \(r\) 对应的动力系统是
$$x_0=1,\qquad x_{k+1}\equiv x_k^r+1 \pmod q.$$
只有当 \(q-1\) 的每一个不同素因子 \(r\) 都让这条轨道在有限步内碰到 \(0\) 时，素数 \(q\) 才会被保留下来。找出这些素数以后，答案就是所有不超过 \(N\) 的可行平方自由乘积之和。
记 \(\mathcal P(m)\) 为 \(m\) 的不同素因子集合。整个计算自然分成两层：先筛出通过轨道判定的素数，再枚举由这些素数构成且不重复使用素因子的整数。
对于素数 \(q\) 以及属于 \(\mathcal P(q-1)\) 的素数 \(r\)，定义
$$x_0^{(q,r)}=1,\qquad x_{k+1}^{(q,r)}\equiv \left(x_k^{(q,r)}\right)^r+1 \pmod q.$$
实现采用的接受条件可以写成
$$q\in\mathcal G \iff \forall r\in\mathcal P(q-1),\ \exists k\ge 0\text{ 使得 }x_k^{(q,r)}=0.$$
这里真正重要的是 \(q-1\) 的不同素因子，而不是它们在分解中出现了多少次。即使 \(r^a\mid(q-1)\)，程序也只对这个素数 \(r\) 做一次轨道测试，因为轨道由指数 \(r\) 决定，而不是由幂次 \(a\) 决定。
模 \(q\) 只有 \(q\) 个剩余类，所以轨道一定是有限状态过程。于是只能发生两种情况：
$$\text{要么存在某个 }k\text{ 使 }x_k^{(q,r)}=0,\qquad\text{要么在看到 }0\text{ 之前先重复了一个非零状态。}$$
一旦某个非零状态重复，后面的演化就会进入周期，因此以后再也不可能碰到 \(0\)。这正是代码可以使用常数内存判圈法的原因；它不需要保存完整的访问集合。
成功命中 \(0\) 时还存在一个简单不变量。如果 \(x_k^{(q,r)}=0\)，那么立刻有
$$x_{k+1}^{(q,r)}\equiv 0^r+1\equiv 1 \pmod q.$$
这说明“命中 \(0\)”并不是一次孤立事件，而是意味着从 \(1\) 出发的轨道闭合成了一个同时包含 \(1\) 和 \(0\) 的循环。代码利用的正是这种“碰到 \(0\) 或者落入别的周期”二分结构。
设 \(\mathcal G\) 为所有通过所需轨道测试的素数集合。随后实现把不超过 \(N\) 的可行整数写成
$$\mathcal S(N)=\left\{\prod_{q\in T} q:\ T\subseteq\mathcal G,\ \prod_{q\in T} q\le N\right\}.$$
空子集贡献空乘积 \(1\)，因此 \(1\) 总是在答案中。于是目标和就是
$$A(N)=\sum_{n\in\mathcal S(N)} n=\sum_{\substack{T\subseteq\mathcal G\\ \prod_{q\in T}\le N}}\prod_{q\in T} q.$$
这个表示天然就是平方自由的，因为每个通过筛选的素数最多只能出现一次。编译型实现里还专门加入了针对 \(q^2\) 的小型校验，用来防止把“素数 \(q\) 可用”误解成“\(q^2\) 也自动可用”；这进一步支持了最终搜索空间确实只由平方自由乘积组成。
最前面的几个素数已经足够展示整个判定机制。
当 \(q=2\) 时，\(q-1=1\)，所以 \(\mathcal P(q-1)=\varnothing\)。条件真空成立，因此 \(2\in\mathcal G\)。
当 \(q=3\) 时，只需要检查 \(r=2\)，轨道为
$$1\to 2\to 2\to 2\to\cdots \pmod 3,$$
所以永远不会到达 \(0\)，因此 \(3\notin\mathcal G\)。
当 \(q=5\) 时，仍然只需要检查 \(r=2\)，但这时
$$1\to 2\to 0\to 1\to\cdots \pmod 5,$$
于是 \(5\in\mathcal G\)。
当 \(q=7\) 时，需要检查 \(2\) 和 \(3\)。其中 \(r=3\) 的轨道是
$$1\to 2\to 2\to 2\to\cdots \pmod 7,$$
因此 \(7\) 会被直接淘汰。
所以在 \(20\) 以内，通过筛选的素数恰好是 \(\{2,5\}\)。对应的可行平方自由乘积为
$$1,\ 2,\ 5,\ 10,$$
从而
$$A(20)=1+2+5+10=18.$$
这就是实现中内置的第一个检查点。第二个检查点是 \(A(1000)=2089\)，它在更大的范围上同时检验素数筛选和乘积枚举两个阶段。
三种语言路径遵循的是同一条数学流水线：先建立算术基础设施，再筛出合格素数，最后枚举平方自由乘积并求和。
第一步是做到 \(N\) 的线性筛。它不仅给出所有素数，还给出每个整数的最小素因子，因此对每个候选素数 \(q\) 来说，分解 \(q-1\) 都很快。
对每个 \(q\)，实现先提取 \(\mathcal P(q-1)\) 里的不同素数，再逐个运行模 \(q\) 的轨道测试。映射 \(x\mapsto x^r+1\pmod q\) 在 \(r=2\) 时直接计算，在更大 \(r\) 时使用模幂。由于轨道只可能命中 \(0\) 或落入一个不含 \(0\) 的周期，所以常数内存的判圈方法已经足够。
C++ 实现把这一步的素数筛选分配到多个工作线程上。Java 实现按同样的逻辑串行执行。Python 入口并没有在纯 Python 中重写整套搜索，而是复用相同的已编译计算。
当 \(\mathcal G\) 构造完成以后，剩下的就是按照递增素数下标做深度优先搜索。每到一个递归状态，当前乘积都会加入答案，然后搜索只会继续尝试更靠后的合格素数。这条顺序规则自动保证同一个素数不会被重复使用。
关键剪枝不等式是
$$\text{current} \gt \frac{N}{q_{\text{next}}}.$$
一旦它成立，乘上下一个可选素数就已经超过 \(N\)，因此这一整条后缀分支都可以跳过。编译型实现还会在真正求解 \(N=10^7\) 之前保留 \(A(20)=18\)、\(A(1000)=2089\) 以及若干 \(q^2\) 的小校验。
在线性筛这个实现模型下，筛法阶段的时间复杂度是 \(O(N)\)，空间复杂度也是 \(O(N)\)，因为它保存了 \(1\) 到 \(N\) 每个整数的最小素因子。这个表一旦建立，提取 \(\mathcal P(q-1)\) 的成本就很低。
对固定的测试对 \((q,r)\)，轨道阶段在找到 \(0\) 或证明轨道落入其他周期之前，最多只会查看 \(q\) 个剩余类。每一步在 \(r=2\) 时花费 \(O(1)\)，在其他情况下花费 \(O(\log r)\) 次模乘。因此筛选阶段可以直接写成
$$O\!\left(N+\sum_{\substack{q\le N\\ q\text{ prime}}}\ \sum_{r\in\mathcal P(q-1)} q\log r\right).$$
最后的深度优先搜索在实践中是输出相关的，而不是完整幂集规模，因为它只扩展当前平方自由乘积仍然不超过 \(N\) 的分支。它的额外内存只包括递归深度和合格素数列表，两者都明显小于筛表本身。
Реализации не обходят prime-ary tree, проверяя по отдельности каждое число до \(N\). Вместо этого используется структурное упрощение: сначала выделяются те простые \(q\), которые удовлетворяют нужному орбитальному условию, а затем суммируются квадратсвободные произведения, составленные из этих простых. В полной задаче верхняя граница равна \(N=10^7\).
Динамический объект, связанный с простым модулем \(q\) и простым показателем \(r\), задается орбитой
$$x_0=1,\qquad x_{k+1}\equiv x_k^r+1 \pmod q.$$
Простое \(q\) сохраняется тогда и только тогда, когда эта орбита достигает \(0\) для каждого различного простого делителя \(r\mid(q-1)\). После того как такие простые найдены, ответом становится сумма всех допустимых квадратсвободных произведений, не превосходящих \(N\).
Обозначим через \(\mathcal P(m)\) множество различных простых делителей числа \(m\). Тогда вычисление естественно распадается на два слоя: сначала классификация простых, проходящих орбитальный тест, затем перечисление чисел, которые получаются из них без повторения множителей.
Для простого \(q\) и простого \(r\in\mathcal P(q-1)\) положим
$$x_0^{(q,r)}=1,\qquad x_{k+1}^{(q,r)}\equiv \left(x_k^{(q,r)}\right)^r+1 \pmod q.$$
Критерий принятия, используемый в реализациях, имеет вид
$$q\in\mathcal G \iff \forall r\in\mathcal P(q-1),\ \exists k\ge 0\text{ такое, что }x_k^{(q,r)}=0.$$
Существенны только различные простые делители числа \(q-1\). Если \(r^a\mid(q-1)\), никакой новый тест не возникает: орбита зависит от самого простого показателя \(r\), а не от его кратности в разложении \(q-1\).
По модулю \(q\) существует лишь \(q\) классов вычетов, значит любая орбита является конечным процессом. Следовательно, возможно только одно из двух:
$$\text{либо для некоторого }k\text{ выполнено }x_k^{(q,r)}=0,\qquad\text{либо до появления }0\text{ повторяется ненулевое состояние.}$$
Если повторился ненулевой элемент, дальнейшая эволюция становится периодической, и \(0\) уже никогда не встретится. Именно поэтому достаточно обнаружения цикла с постоянной памятью; хранить все посещенные вычеты не нужно.
В момент успеха есть и простой инвариант. Если \(x_k^{(q,r)}=0\), то сразу следует
$$x_{k+1}^{(q,r)}\equiv 0^r+1\equiv 1 \pmod q.$$
То есть попадание в \(0\) означает, что орбита, стартовавшая из \(1\), замкнулась в цикл, содержащий и \(1\), и \(0\). Код как раз и опирается на эту альтернативу: либо достижение \(0\), либо уход в чужой цикл.
Пусть \(\mathcal G\) обозначает множество всех простых, прошедших обязательные орбитальные проверки. Тогда реализации рассматривают допустимые числа до \(N\) как
$$\mathcal S(N)=\left\{\prod_{q\in T} q:\ T\subseteq\mathcal G,\ \prod_{q\in T} q\le N\right\}.$$
Пустое подмножество дает пустое произведение \(1\), поэтому число \(1\) всегда входит в ответ. Следовательно, искомая сумма равна
$$A(N)=\sum_{n\in\mathcal S(N)} n=\sum_{\substack{T\subseteq\mathcal G\\ \prod_{q\in T}\le N}}\prod_{q\in T} q.$$
Это описание по построению квадратсвободно: каждый принятый простой множитель используется не более одного раза. В компилируемых реализациях даже есть точечные проверки против наивного продолжения принятого простого \(q\) до \(q^2\), что дополнительно подтверждает: повторные степени простых не входят в окончательное пространство поиска.
Уже самые маленькие простые хорошо показывают, как работает критерий.
Для \(q=2\) имеем \(q-1=1\), значит \(\mathcal P(q-1)=\varnothing\). Условие пусто, поэтому \(2\in\mathcal G\).
Для \(q=3\) существен только \(r=2\), и орбита имеет вид
$$1\to 2\to 2\to 2\to\cdots \pmod 3,$$
следовательно, \(0\) никогда не достигается и \(3\notin\mathcal G\).
Для \(q=5\) снова нужен только \(r=2\), но теперь
$$1\to 2\to 0\to 1\to\cdots \pmod 5,$$
так что \(5\in\mathcal G\).
Для \(q=7\) необходимо проверить \(2\) и \(3\). Орбита для \(r=3\) такова:
$$1\to 2\to 2\to 2\to\cdots \pmod 7,$$
поэтому \(7\) немедленно отбрасывается.
Тем самым до \(20\) принимаются ровно \(\{2,5\}\). Допустимые квадратсвободные произведения равны
$$1,\ 2,\ 5,\ 10,$$
и, значит,
$$A(20)=1+2+5+10=18.$$
Это первая встроенная контрольная точка в реализациях. Вторая равна \(A(1000)=2089\); она проверяет ту же схему уже на более широком диапазоне.
Все три языковые версии следуют одной и той же математической декомпозиции: сначала строится арифметическая инфраструктура, затем классифицируются простые, и только после этого перечисляются квадратсвободные произведения.
Первый этап - линейное решето до \(N\). Оно выдает список простых и одновременно наименьший простой делитель каждого числа до предела, поэтому факторизация \(q-1\) для каждого кандидата \(q\) выполняется быстро.
Для каждого \(q\) реализация извлекает различные простые из \(\mathcal P(q-1)\) и запускает для каждого из них орбитальный тест по модулю \(q\). Переход \(x\mapsto x^r+1\pmod q\) вычисляется напрямую при \(r=2\) и через модульное возведение в степень при больших \(r\). Поскольку орбита может либо попасть в \(0\), либо войти в цикл без \(0\), достаточно обнаружения цикла с постоянной памятью.
Реализация на C++ распараллеливает эту фазу фильтрации простых по нескольким рабочим потокам. Реализация на Java выполняет ту же логику последовательно. Python-вход использует то же компилируемое вычисление, а не переписывает весь поиск на чистом Python.
После построения \(\mathcal G\) остается поиск в глубину по возрастающим индексам простых. В каждом рекурсивном состоянии текущее произведение добавляется к ответу, а затем поиск продолжается только с более поздними принятыми простыми. Это правило порядка автоматически запрещает повторное использование одного и того же простого.
Ключевое условие отсечения имеет вид
$$\text{current} \gt \frac{N}{q_{\text{next}}}.$$
Когда оно выполнено, умножение даже на следующий доступный простой уже превышает \(N\), поэтому вся оставшаяся ветвь отбрасывается целиком. Перед полным запуском при \(N=10^7\) компилируемые реализации также сохраняют проверки \(A(20)=18\), \(A(1000)=2089\) и несколько небольших тестов, связанных с \(q^2\).
На этапе решета используется \(O(N)\) времени и \(O(N)\) памяти в реализованной модели, потому что хранится наименьший простой делитель каждого целого до \(N\). После построения этой таблицы извлекать \(\mathcal P(q-1)\) уже дешево.
Для фиксированной пары \((q,r)\) орбитальная фаза просматривает не более \(q\) вычетов, прежде чем либо найдет \(0\), либо докажет, что орбита циклически вращается в другом месте. Каждый шаг стоит \(O(1)\) при \(r=2\) и \(O(\log r)\) модульных умножений в остальных случаях. Поэтому стоимость фильтрации можно записать как
$$O\!\left(N+\sum_{\substack{q\le N\\ q\text{ prime}}}\ \sum_{r\in\mathcal P(q-1)} q\log r\right).$$
Финальный поиск в глубину на практике зависит от числа реально достижимых ветвей, а не от полного размера множества всех подмножеств, поскольку продолжаются только те ветви, у которых текущее квадратсвободное произведение не превосходит \(N\). Его память - это глубина рекурсии и список принятых простых, что существенно меньше размера решета.
التنفيذات لا تجوب prime-ary tree بفحص كل عدد حتى \(N\) على حدة. بدلا من ذلك تستخدم اختزالا بنيويا: تحدد اولا الاعداد الاولية \(q\) التي تحقق شرط المدار الخاص بالمسألة، ثم تجمع الجداءات الخالية من المربعات المبنية من هذه الاعداد الاولية. في المسألة الكاملة يكون الحد \(N=10^7\).
الكائن الديناميكي المرتبط بمعامل اولي \(q\) واس اولي \(r\) هو المدار
$$x_0=1,\qquad x_{k+1}\equiv x_k^r+1 \pmod q.$$
ويحتفظ بالعدد الاولي \(q\) فقط عندما يصل هذا المدار الى \(0\) لكل قاسم اولي مميز \(r\mid(q-1)\). وبعد معرفة هذه الاعداد الاولية، يصبح الجواب هو مجموع كل الجداءات الخالية من المربعات المسموح بها والتي لا تتجاوز \(N\).
لنكتب \(\mathcal P(m)\) لمجموعة القواسم الاولية المميزة للعدد \(m\). وعندئذ ينقسم الحساب طبيعيا الى مستويين: اولا تصنيف الاعداد الاولية التي تنجح في اختبار المدار، ثم تعداد الاعداد الناتجة من ضربها من دون تكرار اي عامل اولي.
لكل عدد اولي \(q\) ولكل عدد اولي \(r\in\mathcal P(q-1)\) نعرف
$$x_0^{(q,r)}=1,\qquad x_{k+1}^{(q,r)}\equiv \left(x_k^{(q,r)}\right)^r+1 \pmod q.$$
ومعيار القبول المستخدم في التنفيذات هو
$$q\in\mathcal G \iff \forall r\in\mathcal P(q-1),\ \exists k\ge 0:\ x_k^{(q,r)}=0.$$
المهم هنا هو القواسم الاولية المميزة للعدد \(q-1\) فقط. فاذا كان \(r^a\mid(q-1)\)، يبقى اختبار \(r\) نفسه مرة واحدة لا غير، لان المدار يعتمد على الاولي \(r\) ذاته لا على اسه داخل تحليل \(q-1\).
بترديد \(q\) لا يوجد سوى \(q\) بواقي ممكنة، ولذلك فكل مدار هو عملية ذات عدد حالات منته. ومن ثم لا بد من حدوث احد امرين فقط:
$$\bigl(\exists k\ge 0:\ x_k^{(q,r)}=0\bigr)\ \lor\ \bigl(\exists i<j:\ x_i^{(q,r)}=x_j^{(q,r)}\ne 0\bigr).$$
اذا تكررت قيمة غير صفرية، يصبح السلوك اللاحق دوريا، ولن يمكن الوصول الى \(0\) بعد ذلك ابدا. ولهذا تكفي طريقة كشف الدورات بذاكرة ثابتة، ولا حاجة الى تخزين مجموعة كاملة من القيم المزارة.
وهناك ايضا ثابت بسيط عند النجاح. اذا كان \(x_k^{(q,r)}=0\)، فسنحصل فورا على
$$x_{k+1}^{(q,r)}\equiv 0^r+1\equiv 1 \pmod q.$$
اي ان الوصول الى \(0\) يعني ان المدار الذي بدأ من \(1\) اغلق دورة تحتوي \(1\) و\(0\) معا. وهذه بالضبط هي الثنائية التي يستغلها الكود: اما ملامسة \(0\)، واما الوقوع في دورة اخرى منفصلة.
لتكن \(\mathcal G\) مجموعة الاعداد الاولية التي تنجح في جميع اختبارات المدار المطلوبة. بعدها تتعامل التنفيذات مع الاعداد المسموح بها حتى \(N\) على الصورة
$$\mathcal S(N)=\left\{\prod_{q\in T} q:\ T\subseteq\mathcal G,\ \prod_{q\in T} q\le N\right\}.$$
المجموعة الخالية تعطي الجداء الخالي \(1\)، ولذلك يكون \(1\) داخلا في الجواب دائما. ومن ثم تصبح الصيغة المطلوبة
$$A(N)=\sum_{n\in\mathcal S(N)} n=\sum_{\substack{T\subseteq\mathcal G\\ \prod_{q\in T}\le N}}\prod_{q\in T} q.$$
وهذا الوصف خال من المربعات بحكم بنائه: كل عدد اولي مقبول يمكن ان يظهر مرة واحدة فقط. كما ان التنفيذات المترجمة تتضمن اختبارات صغيرة ضد التمديد الساذج من \(q\) المقبول الى \(q^2\)، وهذا يدعم فكرة ان القوى المكررة للعامل الاولي ليست جزءا من فضاء البحث النهائي.
الاعداد الاولية الاولى تكشف الية المعيار بوضوح.
عند \(q=2\) نجد \(q-1=1\)، وبالتالي \(\mathcal P(q-1)=\varnothing\). الشرط فارغ، ولذلك \(2\in\mathcal G\).
عند \(q=3\) يكون \(r=2\) هو الوحيد المهم، ويصبح المدار
$$1\to 2\to 2\to 2\to\cdots \pmod 3,$$
لذلك لا يظهر \(0\) مطلقا، ومن ثم \(3\notin\mathcal G\).
عند \(q=5\) يبقى \(r=2\) هو الوحيد المطلوب، لكننا نحصل على
$$1\to 2\to 0\to 1\to\cdots \pmod 5,$$
وبالتالي \(5\in\mathcal G\).
وعند \(q=7\) يجب فحص \(2\) و\(3\). مدار \(r=3\) هو
$$1\to 2\to 2\to 2\to\cdots \pmod 7,$$
ولذلك يرفض \(7\) مباشرة.
وهكذا تكون الاعداد الاولية المقبولة حتى \(20\) هي بالضبط \(\{2,5\}\). والجداءات الخالية من المربعات المسموح بها هي
$$1,\ 2,\ 5,\ 10,$$
ومن ثم
$$A(20)=1+2+5+10=18.$$
وهذه هي نقطة التحقق الاولى المضمنة في التنفيذات. اما نقطة التحقق الثانية فهي \(A(1000)=2089\)، وهي تختبر المنطق نفسه على مجال اوسع.
المسارات الثلاثة تتبع التفكيك الرياضي نفسه: بناء البنية الحسابية اولا، ثم تصنيف الاعداد الاولية، ثم تعداد الجداءات الخالية من المربعات في النهاية.
المرحلة الاولى هي غربال خطي حتى \(N\). وهو ينتج قائمة الاعداد الاولية ويخزن في الوقت نفسه اصغر عامل اولي لكل عدد حتى الحد، ولذلك يصبح تحليل \(q-1\) سريعا لكل عدد اولي مرشح \(q\).
لكل \(q\)، يستخرج التنفيذ الاعداد الاولية المميزة في \(\mathcal P(q-1)\) ثم يشغل اختبار المدار modulo \(q\) لكل واحد منها. والانتقال \(x\mapsto x^r+1\pmod q\) يحسب مباشرة عندما يكون \(r=2\)، ويحسب بالاسس المعيارية عندما يكون \(r\) اكبر. وبما ان المدار لا يفعل الا واحدا من امرين، الوصول الى \(0\) او الدخول في دورة منفصلة، فان كشف الدورات بذاكرة ثابتة يكفي تماما.
تنفيذ C++ يوازي مرحلة ترشيح الاعداد الاولية هذه على عدة عمال. تنفيذ Java ينفذ المنطق نفسه على نحو تسلسلي. اما مدخل Python فيعيد استخدام الحساب المترجم نفسه بدلا من اعادة كتابة البحث كله بلغة Python الصرفة.
بعد بناء \(\mathcal G\)، يبقى بحث عمقي على مؤشرات اولية متزايدة. في كل حالة عودية يضاف الجداء الحالي الى المجموع، ثم يتابع البحث فقط مع الاعداد الاولية المقبولة اللاحقة. هذه القاعدة الترتيبية تمنع تلقائيا استخدام العامل الاولي نفسه مرتين.
ومتراجحة التقليم الاساسية هي
$$\text{current} \gt \frac{N}{q_{\text{next}}}.$$
متى تحققت، فان الضرب حتى في الاولي المتاح التالي سيتجاوز \(N\)، ولذلك يمكن حذف كل ما تبقى من ذلك الفرع دفعة واحدة. وقبل تشغيل الحساب الكامل عند \(N=10^7\)، تحتفظ التنفيذات المترجمة ايضا بفحوص \(A(20)=18\) و\(A(1000)=2089\) وبعض الفحوص الصغيرة المتعلقة ب \(q^2\).
في النموذج المطبق هنا، تكلف مرحلة الغربال \(O(N)\) زمنا و\(O(N)\) ذاكرة، لانها تخزن اصغر عامل اولي لكل عدد حتى \(N\). وبعد بناء هذا الجدول يصبح استخراج \(\mathcal P(q-1)\) رخيصا.
بالنسبة الى زوج اختبار ثابت \((q,r)\)، تفحص مرحلة المدار في حد اقصى \(q\) بواقي قبل ان تجد \(0\) او تثبت ان المدار صار دوريا في مكان اخر. كل خطوة تكلف \(O(1)\) عندما يكون \(r=2\)، وتكلف \(O(\log r)\) ضربات معيارية في غير ذلك. ولهذا يمكن كتابة كلفة الترشيح على الصورة
$$O\!\left(N+\sum_{\substack{q\le N\\ q\text{ prime}}}\ \sum_{r\in\mathcal P(q-1)} q\log r\right).$$
اما البحث العمقي النهائي فهو حساس للمخرجات الفعلية وليس بحجم مجموعة الاجزاء كلها، لانه لا يوسع الا الفروع التي يبقى فيها الجداء الحالي الخالي من المربعات \(\le N\). وذاكرته لا تتعدى عمق العودية مع قائمة الاعداد الاولية المقبولة، وكلاهما اصغر كثيرا من جدول الغربال.