A strong Achilles number is an integer \(n\) such that both \(n\) and \(\varphi(n)\) are Achilles numbers. An integer is Achilles when it is powerful, but not a perfect power. The problem asks for the number of such \(n\) below \(10^{18}\).
Write
$$n=\prod_{i=1}^r p_i^{a_i},\qquad a_i\ge 1.$$
The number \(n\) is powerful exactly when every exponent is at least \(2\):
$$a_i\ge 2\qquad \text{for all }i.$$
It is a perfect \(k\)-th power exactly when all exponents are divisible by the same \(k \ge 2\), equivalently when
$$\gcd(a_1,a_2,\dots,a_r)\ge 2.$$
Therefore
$$n\text{ is Achilles}\iff a_i\ge 2\ \forall i\quad\text{and}\quad \gcd(a_1,\dots,a_r)=1.$$
This turns the first half of the problem into a statement about exponent vectors rather than about the decimal value of \(n\).
Euler's product formula gives
$$\varphi(n)=\prod_{i=1}^r p_i^{a_i-1}(p_i-1).$$
Fix a prime \(q\). Its exponent inside \(\varphi(n)\) is
$$v_q(\varphi(n))=\sum_{i=1}^r v_q(p_i-1)+\sum_{\substack{1\le i\le r\\p_i=q}}(a_i-1).$$
So every exponent of \(\varphi(n)\) comes from two sources:
1. factors already forced by the numbers \(p_i-1\);
2. the self-contribution \(a_i-1\) when the prime \(q\) itself appears in \(n\).
Thus \(\varphi(n)\) is Achilles exactly when all final values \(v_q(\varphi(n))\) are at least \(2\) and their gcd is \(1\).
Take
$$500=2^2\cdot 5^3.$$
The exponent vector of \(n\) is \((2,3)\), so \(500\) is powerful and
$$\gcd(2,3)=1.$$
Hence \(500\) is Achilles.
Now compute the totient:
$$\varphi(500)=500\left(1-\frac12\right)\left(1-\frac15\right)=200=2^3\cdot 5^2.$$
The exponent vector of \(\varphi(500)\) is \((3,2)\), again all exponents are at least \(2\) and
$$\gcd(3,2)=1.$$
So \(500\) is a strong Achilles number. This is the smallest example, and it is a good mental model for what the recursion is building.
The factorization of \(p-1\) uses only primes strictly smaller than \(p\). Therefore, if the recursion processes prime bases in descending order, then once we move below a prime \(q\), no future decision can increase the exponent of \(q\) inside \(\varphi(n)\).
That means the exponent of \(q\) is now final. The code immediately folds that final exponent into a running gcd for \(\varphi(n)\) and removes \(q\) from the active state. This is the key structural idea that makes the recursion manageable.
active_factorsThe array active_factors is a sorted multiset of prime indices. If the index of a prime \(q\) appears there exactly \(t\) times, then \(t\) is the part of the exponent of \(q\) in \(\varphi(n)\) that has already been created by factors of the form \(p-1\) from larger chosen primes.
Those copies are not finalized yet because the recursion may still decide to include \(q\) itself as a prime factor of \(n\), which would add the extra term \(a_q-1\) to \(v_q(\varphi(n))\).
Alongside that multiset, the code stores two gcd summaries:
$$g_n=\gcd(\text{chosen exponents in }n),\qquad g_\varphi=\gcd(\text{already finalized exponents in }\varphi(n)).$$
Suppose the recursion introduces a prime \(p\) that does not yet occur in active_factors. Then larger primes have contributed no copy of \(p\) to \(\varphi(n)\). The only guaranteed contribution of \(p\) is the self-term \(a-1\) coming from \(p^{a-1}\) in Euler's formula.
To make \(\varphi(n)\) powerful we need
$$a-1\ge 2,$$
hence
$$a\ge 3.$$
That is exactly why the code tries deg = 3,4,5,\dots for a genuinely new prime. This also explains the cube-root pruning later on: every fresh prime costs at least \(p^3\).
Now suppose \(p\) already appears in active_factors with multiplicity \(t\ge 1\). Then larger primes have already forced a factor \(p^t\) into \(\varphi(n)\). If we now choose \(p^a\) in \(n\), the final exponent of \(p\) in \(\varphi(n)\) becomes
$$t+(a-1).$$
The powerful condition is only
$$t+(a-1)\ge 2.$$
Since \(t\ge 1\), the smallest legal exponent is already \(a=2\). This is why the code has a separate branch where an already active prime is tried with deg = 2,3,4,\dots.
The example \(500=2^2\cdot 5^3\) shows this mechanism clearly: after choosing \(5^3\), the factor \(5-1=4=2^2\) places two copies of the prime \(2\) into active_factors. Then choosing \(2^2\) is enough, because the exponent of \(2\) in \(\varphi(500)\) becomes \(2+(2-1)=3\).
A recursive state already represents a complete candidate \(n\). It is counted exactly when:
$$g_n=1,$$
every remaining multiplicity inside active_factors is at least \(2\), and
$$\gcd\bigl(g_\varphi,\text{all remaining multiplicities}\bigr)=1.$$
The meaning is direct:
1. \(g_n=1\) means \(n\) is not a perfect power.
2. Remaining multiplicities at least \(2\) mean \(\varphi(n)\) is powerful.
3. The final gcd equal to \(1\) means \(\varphi(n)\) is not a perfect power.
If we still want to insert a completely new prime \(p\), we must spend at least \(p^3\). Therefore a fresh prime can only be used when
$$p^3\le \text{remaining limit}.$$
Equivalently,
$$p\le \left\lfloor\sqrt[3]{\text{remaining limit}}\right\rfloor.$$
This is why the solver computes a cube-root upper bound before opening the “new prime” branch. It removes almost all hopeless candidates very early.
The implementation contains two explicit tests:
$$\text{count}(10^4)=7,\qquad \text{count}(10^8)=656.$$
The first seven strong Achilles numbers are
$$500,\ 864,\ 1944,\ 2000,\ 2592,\ 3456,\ 5000.$$
These checkpoints are important because the full target \(10^{18}\) is far too large for brute force.
The sieve first generates primes up to a safe bound. Then, for every integer \(m\) in the sieve range, it precomputes the prime factorization of \(m\) as a multiset of prime indices. This lets the recursion merge in the factors of \(p-1\) very cheaply.
The function count_recursive(...) performs three tasks at each state:
1. test whether the current state already forms a strong Achilles number;
2. try primes that already appear in active_factors;
3. try genuinely new primes, subject to the exponent-\(3\) rule and the cube-root bound.
Because the search order is canonical and descending, each valid \(n\) is generated exactly once.
There is no clean closed formula for the running time, because the search tree depends on the arithmetic structure of the numbers \(p-1\). In the worst case the recursion is exponential, but in practice it is kept under control by four strong filters: prime exponents must be large, gcd conditions kill many states, fresh primes satisfy the cube-root bound, and finalized totient exponents are removed from the active state immediately.
The memory usage is modest: recursion depth, a short active multiset, and the sieve/factor tables.
Eine starke Achilles-Zahl ist eine Zahl \(n\), für die sowohl \(n\) als auch \(\varphi(n)\) Achilles-Zahlen sind. Eine Zahl ist Achilles, wenn sie powerful ist, aber keine perfekte Potenz. Gesucht ist die Anzahl solcher \(n\) unterhalb von \(10^{18}\).
Schreibe
$$n=\prod_{i=1}^r p_i^{a_i},\qquad a_i\ge 1.$$
Die Zahl \(n\) ist genau dann powerful, wenn alle Exponenten mindestens \(2\) sind:
$$a_i\ge 2\qquad \text{für alle }i.$$
Sie ist genau dann eine perfekte \(k\)-te Potenz, wenn alle Exponenten durch dasselbe \(k\ge 2\) teilbar sind, also äquivalent zu
$$\gcd(a_1,a_2,\dots,a_r)\ge 2.$$
Damit gilt
$$n\text{ ist Achilles}\iff a_i\ge 2\ \forall i\quad\text{und}\quad \gcd(a_1,\dots,a_r)=1.$$
Die erste Hälfte des Problems ist also vollständig eine Aussage über Exponentenvektoren.
Aus Eulers Produktformel folgt
$$\varphi(n)=\prod_{i=1}^r p_i^{a_i-1}(p_i-1).$$
Für eine feste Primzahl \(q\) ist ihr Exponent in \(\varphi(n)\)
$$v_q(\varphi(n))=\sum_{i=1}^r v_q(p_i-1)+\sum_{\substack{1\le i\le r\\p_i=q}}(a_i-1).$$
Jeder Exponent in \(\varphi(n)\) hat also zwei Quellen:
1. Faktoren, die bereits durch die Zahlen \(p_i-1\) erzwungen werden;
2. den Eigenbeitrag \(a_i-1\), falls die Primzahl \(q\) selbst in \(n\) vorkommt.
Also ist \(\varphi(n)\) genau dann Achilles, wenn alle endgültigen Werte \(v_q(\varphi(n))\) mindestens \(2\) sind und ihr ggT gleich \(1\) ist.
Nimm
$$500=2^2\cdot 5^3.$$
Der Exponentenvektor von \(n\) ist \((2,3)\), also ist \(500\) powerful und
$$\gcd(2,3)=1.$$
Damit ist \(500\) eine Achilles-Zahl.
Nun der Totient:
$$\varphi(500)=500\left(1-\frac12\right)\left(1-\frac15\right)=200=2^3\cdot 5^2.$$
Der Exponentenvektor von \(\varphi(500)\) ist \((3,2)\), wieder sind alle Exponenten mindestens \(2\) und
$$\gcd(3,2)=1.$$
Also ist \(500\) eine starke Achilles-Zahl. Dieses Beispiel ist zugleich die kleinste Lösung und ein gutes Modell für die Rekursion.
Die Zerlegung von \(p-1\) benutzt nur Primzahlen, die strikt kleiner als \(p\) sind. Wenn die Rekursion Primzahlbasen also in absteigender Reihenfolge verarbeitet, dann kann nach dem Unterschreiten einer Primzahl \(q\) keine spätere Entscheidung ihren Exponenten in \(\varphi(n)\) mehr erhöhen.
Damit ist dieser Exponent endgültig. Der Code faltet ihn sofort in einen laufenden ggT für \(\varphi(n)\) ein und entfernt \(q\) aus dem aktiven Zustand. Genau diese Struktur macht die Suche praktikabel.
active_factors bedeutetDas Array active_factors ist eine sortierte Multimenge von Primzahlindizes. Wenn der Index einer Primzahl \(q\) dort genau \(t\)-mal vorkommt, dann ist \(t\) gerade der Teil des Exponenten von \(q\) in \(\varphi(n)\), der bereits durch Faktoren der Form \(p-1\) von größeren gewählten Primzahlen entstanden ist.
Diese Kopien sind noch nicht endgültig, weil die Rekursion später vielleicht noch entscheidet, \(q\) selbst als Primfaktor von \(n\) aufzunehmen. Dann käme der zusätzliche Term \(a_q-1\) hinzu.
Daneben speichert der Code zwei ggT-Zusammenfassungen:
$$g_n=\gcd(\text{gewählte Exponenten in }n),\qquad g_\varphi=\gcd(\text{bereits finalisierte Exponenten in }\varphi(n)).$$
Angenommen, die Rekursion führt eine Primzahl \(p\) ein, die in active_factors noch nicht vorkommt. Dann haben größere Primzahlen noch keinen einzigen Faktor \(p\) zu \(\varphi(n)\) beigetragen. Der einzige sichere Beitrag von \(p\) ist dann der Eigenanteil \(a-1\) aus \(p^{a-1}\) in der Euler-Formel.
Damit \(\varphi(n)\) powerful ist, braucht man
$$a-1\ge 2,$$
also
$$a\ge 3.$$
Darum testet der Code für eine echte neue Primzahl genau deg = 3,4,5,\dots. Daraus folgt auch das Kubikwurzel-Pruning: jede frische Primzahl kostet mindestens \(p^3\).
Angenommen, \(p\) steht bereits mit Multiplizität \(t\ge 1\) in active_factors. Dann haben größere Primzahlen schon einen Faktor \(p^t\) in \(\varphi(n)\) erzwungen. Wenn wir nun \(p^a\) in \(n\) wählen, wird der endgültige Exponent von \(p\) in \(\varphi(n)\)
$$t+(a-1).$$
Die Powerful-Bedingung ist nur
$$t+(a-1)\ge 2.$$
Da \(t\ge 1\), ist bereits \(a=2\) zulässig. Genau deshalb besitzt der Code einen zweiten Zweig, in dem eine bereits aktive Primzahl mit deg = 2,3,4,\dots ausprobiert wird.
Das Beispiel \(500=2^2\cdot 5^3\) zeigt den Mechanismus deutlich: Nach der Wahl von \(5^3\) legt der Faktor \(5-1=4=2^2\) zwei Kopien der Primzahl \(2\) in active_factors. Dann genügt \(2^2\), denn der Exponent von \(2\) in \(\varphi(500)\) wird zu \(2+(2-1)=3\).
Ein Rekursionszustand repräsentiert bereits einen vollständigen Kandidaten \(n\). Er wird genau dann gezählt, wenn
$$g_n=1,$$
jede verbleibende Multiplizität in active_factors mindestens \(2\) ist und außerdem
$$\gcd\bigl(g_\varphi,\text{alle verbleibenden Multiplizitäten}\bigr)=1.$$
Die Bedeutung ist direkt:
1. \(g_n=1\) bedeutet, dass \(n\) keine perfekte Potenz ist.
2. Verbleibende Multiplizitäten ab \(2\) bedeuten, dass \(\varphi(n)\) powerful ist.
3. End-ggT \(=1\) bedeutet, dass \(\varphi(n)\) keine perfekte Potenz ist.
Wenn wir noch eine völlig neue Primzahl \(p\) einführen wollen, müssen wir mindestens \(p^3\) investieren. Deshalb darf eine frische Primzahl nur verwendet werden, wenn
$$p^3\le \text{verbleibendes Limit}.$$
Äquivalent dazu:
$$p\le \left\lfloor\sqrt[3]{\text{verbleibendes Limit}}\right\rfloor.$$
Darum berechnet der Solver vor dem Zweig „neue Primzahl“ eine Kubikwurzel-Schranke. Fast alle unmöglichen Kandidaten werden dadurch sehr früh abgeschnitten.
Die Implementierung enthält zwei explizite Tests:
$$\text{count}(10^4)=7,\qquad \text{count}(10^8)=656.$$
Die ersten sieben starken Achilles-Zahlen sind
$$500,\ 864,\ 1944,\ 2000,\ 2592,\ 3456,\ 5000.$$
Diese Kontrollwerte sind wichtig, weil das eigentliche Ziel \(10^{18}\) für brute force völlig außer Reichweite liegt.
Das Sieb erzeugt zuerst alle Primzahlen bis zu einer sicheren Schranke. Danach wird für jedes \(m\) im Siebbereich die Primfaktorzerlegung von \(m\) als Multimenge von Primzahlindizes vorab berechnet. Genau das benötigt die Rekursion für die Faktoren von \(p-1\).
Die Funktion count_recursive(...) erledigt in jedem Zustand drei Dinge:
1. prüfen, ob der aktuelle Zustand bereits eine starke Achilles-Zahl bildet;
2. Primzahlen probieren, die schon in active_factors vorkommen;
3. wirklich neue Primzahlen probieren, unter Beachtung der Exponent-\(3\)-Regel und der Kubikwurzel-Schranke.
Weil die Suchreihenfolge kanonisch und absteigend ist, wird jedes zulässige \(n\) genau einmal erzeugt.
Es gibt keine saubere geschlossene Formel für die Laufzeit, weil der Suchbaum von der arithmetischen Struktur der Zahlen \(p-1\) abhängt. Im Worst Case ist die Rekursion exponentiell, aber praktisch wird sie durch vier starke Filter beherrscht: große Exponenten, ggT-Bedingungen, die Kubikwurzel-Schranke für frische Primzahlen und das sofortige Finalisieren großer Totient-Exponenten.
Der Speicherbedarf bleibt klein: Rekursionstiefe, eine kurze aktive Multimenge und die vorberechneten Sieb-/Faktortabellen.
Strong Achilles sayı, hem \(n\) hem de \(\varphi(n)\) Achilles olan bir sayıdır. Bir sayı Achilles ise powerful'dır ama perfect power değildir. Problem, \(10^{18}\) altındaki böyle sayıların adedini soruyor.
Şöyle yazalım:
$$n=\prod_{i=1}^r p_i^{a_i},\qquad a_i\ge 1.$$
\(n\) sayısı tam olarak şu durumda powerful olur:
$$a_i\ge 2\qquad \text{tüm }i\text{ için}.$$
\(n\) sayısı tam olarak şu durumda bir perfect \(k\). kuvvettir: bütün üsler aynı \(k\ge 2\) ile bölünür. Bu da
$$\gcd(a_1,a_2,\dots,a_r)\ge 2$$
ile eşdeğerdir. Dolayısıyla
$$n\text{ Achilles}\iff a_i\ge 2\ \forall i\quad\text{ve}\quad \gcd(a_1,\dots,a_r)=1.$$
Böylece problemin ilk yarısı sayının kendisinden çok üs vektörü problemi haline gelir.
Euler çarpım formülü
$$\varphi(n)=\prod_{i=1}^r p_i^{a_i-1}(p_i-1)$$
der. Sabit bir asal \(q\) için \(\varphi(n)\) içindeki üs
$$v_q(\varphi(n))=\sum_{i=1}^r v_q(p_i-1)+\sum_{\substack{1\le i\le r\\p_i=q}}(a_i-1)$$
olur. Yani \(\varphi(n)\)'deki her üs iki kaynaktan gelir:
1. daha önce seçilmiş asalların \(p_i-1\) çarpanlarından gelen katkılar;
2. \(q\) asalı bizzat \(n\)'de varsa, onun kendi katkısı olan \(a_i-1\).
Bu yüzden \(\varphi(n)\)'in Achilles olması, tüm son üslerin en az \(2\) olması ve bu üslerin ebobunun \(1\) olması demektir.
Şunu alalım:
$$500=2^2\cdot 5^3.$$
\(n\)'in üs vektörü \((2,3)\)'tür; dolayısıyla \(500\) powerful'dır ve
$$\gcd(2,3)=1.$$
Demek ki \(500\) Achilles'tir.
Şimdi totient:
$$\varphi(500)=500\left(1-\frac12\right)\left(1-\frac15\right)=200=2^3\cdot 5^2.$$
\(\varphi(500)\)'ün üs vektörü \((3,2)\)'dir; yine tüm üsler en az \(2\) ve
$$\gcd(3,2)=1.$$
Yani \(500\) bir strong Achilles sayıdır. Bu en küçük örnektir ve recursion'ın ne kurduğunu görmek için çok iyi bir kontroldür.
\(p-1\)'in asal çarpanları her zaman \(p\)'den küçüktür. Bu nedenle recursion asal tabanları büyükten küçüğe gezerse, bir asal \(q\)'nun altına indikten sonra artık hiçbir sonraki seçim \(\varphi(n)\) içindeki \(q\) üssünü artıramaz.
Bu da o üssün artık kesinleştiği anlamına gelir. Kod bu kesinleşmiş üssü hemen \(\varphi(n)\) için tuttuğu koşan eboba ekler ve \(q\)'yu aktif durumdan çıkarır. Algoritmanın kilit fikri budur.
active_factors tam olarak ne tutuyoractive_factors dizisi, asal indekslerinden oluşan sıralı bir çoklu kümedir. Bir asal \(q\)'nun indeksi burada tam \(t\) kez görünüyorsa, bu \(t\), \(\varphi(n)\) içindeki \(q\) üssünün daha büyük seçilmiş asalların \(p-1\) çarpanlarından gelmiş kısmıdır.
Bu kopyalar henüz finalize edilmez; çünkü recursion biraz sonra \(q\)'nun kendisini de \(n\)'in bir asal çarpanı olarak seçebilir ve o zaman \(a_q-1\) kadar ek katkı gelir.
Kod ayrıca iki ebob özeti tutar:
$$g_n=\gcd(\text{\(n\) içindeki seçilmiş üsler}),\qquad g_\varphi=\gcd(\text{\(\varphi(n)\) içindeki finalize olmuş üsler}).$$
Diyelim ki recursion, active_factors içinde henüz görünmeyen yeni bir asal \(p\) ekliyor. Bu durumda daha büyük seçilmiş asallar \(\varphi(n)\)'e hiç \(p\) katkısı yapmamıştır. Garantili tek katkı Euler formülündeki \(p^{a-1}\) teriminden gelen \(a-1\)'dir.
\(\varphi(n)\)'in powerful olması için
$$a-1\ge 2$$
olmalı, yani
$$a\ge 3.$$
Kodun gerçek anlamda yeni bir asal için deg = 3,4,5,\dots denemesinin sebebi tam olarak budur. Aynı nedenle cube-root pruning de doğar: her yeni asal en az \(p^3\) maliyetlidir.
Şimdi \(p\)'nin active_factors içinde \(t\ge 1\) çokluğu ile zaten bulunduğunu düşünelim. O zaman daha büyük asallar \(\varphi(n)\)'e zaten \(p^t\) katkısı yapmıştır. Eğer şimdi \(n\)'e \(p^a\) eklersek, \(\varphi(n)\)'deki son üs
$$t+(a-1)$$
olur. Powerful şartı yalnızca
$$t+(a-1)\ge 2$$
diyor. \(t\ge 1\) olduğundan, en küçük geçerli seçim zaten \(a=2\)'dir. Kodun ayrı bir dalda aktif asallar için deg = 2,3,4,\dots denemesinin nedeni budur.
\(500=2^2\cdot 5^3\) örneği bunu çok güzel gösterir: önce \(5^3\) seçilirse, \(5-1=4=2^2\) olduğu için active_factors içine iki tane \(2\) kopyası girer. Sonra \(2^2\) seçmek yeterlidir; çünkü \(\varphi(500)\)'de \(2\)'nin üssü \(2+(2-1)=3\) olur.
Bir recursive state zaten tam bir aday \(n\)'yi temsil eder. Şu koşullarda sayılır:
$$g_n=1,$$
active_factors içindeki kalan her çokluk en az \(2\) ve ayrıca
$$\gcd\bigl(g_\varphi,\text{kalan tüm çokluklar}\bigr)=1.$$
Bunların anlamı doğrudandır:
1. \(g_n=1\) demek \(n\) perfect power değil demektir.
2. Kalan çoklukların en az \(2\) olması \(\varphi(n)\)'in powerful olduğunu söyler.
3. Son ebobun \(1\) olması \(\varphi(n)\)'in perfect power olmadığını söyler.
Eğer hâlâ tamamen yeni bir asal \(p\) eklemek istiyorsak, en az \(p^3\) harcamamız gerekir. O yüzden yeni bir asal ancak şu durumda kullanılabilir:
$$p^3\le \text{kalan limit}.$$
Bu da
$$p\le \left\lfloor\sqrt[3]{\text{kalan limit}}\right\rfloor$$
ile aynıdır. Kod “yeni asal” dalını açmadan önce bu cube-root sınırını hesaplar ve umutsuz adayların çoğunu çok erken eler.
Uygulamada iki açık kontrol var:
$$\text{count}(10^4)=7,\qquad \text{count}(10^8)=656.$$
İlk yedi strong Achilles sayı şunlardır:
$$500,\ 864,\ 1944,\ 2000,\ 2592,\ 3456,\ 5000.$$
Bu checkpoint'ler önemlidir; çünkü gerçek hedef olan \(10^{18}\) brute-force ile ulaşılamayacak kadar büyüktür.
Önce sieve ile güvenli bir üst sınıra kadar tüm asallar üretilir. Sonra sieve aralığındaki her \(m\) için, \(m\)'in asal çarpan ayrışımı asal indekslerinden oluşan bir çoklu küme olarak önceden hazırlanır. Recursion, \(p-1\)'in çarpanlarını bu hazır yapıdan çok ucuz biçimde birleştirir.
count_recursive(...) her durumda üç iş yapar:
1. mevcut durumun zaten bir strong Achilles sayı olup olmadığını test eder;
2. active_factors içinde zaten bulunan asalları dener;
3. gerçekten yeni asalları, üs-\(3\) kuralı ve cube-root sınırı altında dener.
Arama sırası kanonik ve azalan olduğu için her geçerli \(n\) tam bir kez üretilir.
Çalışma süresi için temiz bir kapalı formül yoktur; çünkü arama ağacı \(p-1\) sayıların aritmetik yapısına bağlıdır. En kötü durumda recursion üstsel dallanır, fakat pratikte dört güçlü filtre işi kontrol altında tutar: büyük üs zorunluluğu, ebob koşulları, yeni asallar için cube-root sınırı ve kesinleşen totient üslerinin aktif durumdan hemen atılması.
Bellek kullanımı düşüktür: recursion derinliği, kısa bir aktif çoklu küme ve sieve/factor tabloları.
Un número de Achilles fuerte es un entero \(n\) tal que tanto \(n\) como \(\varphi(n)\) son números de Achilles. Un número es de Achilles cuando es powerful, pero no una potencia perfecta. El problema pide contar cuántos de esos \(n\) hay por debajo de \(10^{18}\).
Escribimos
$$n=\prod_{i=1}^r p_i^{a_i},\qquad a_i\ge 1.$$
El número \(n\) es powerful exactamente cuando todos sus exponentes son al menos \(2\):
$$a_i\ge 2\qquad \text{para todo }i.$$
Es una potencia perfecta de orden \(k\) exactamente cuando todos los exponentes son divisibles por el mismo \(k\ge 2\), es decir, cuando
$$\gcd(a_1,a_2,\dots,a_r)\ge 2.$$
Por tanto,
$$n\text{ es de Achilles}\iff a_i\ge 2\ \forall i\quad\text{y}\quad \gcd(a_1,\dots,a_r)=1.$$
La primera mitad del problema se convierte así en una condición pura sobre el vector de exponentes.
La fórmula producto de Euler dice
$$\varphi(n)=\prod_{i=1}^r p_i^{a_i-1}(p_i-1).$$
Si fijamos un primo \(q\), su exponente en \(\varphi(n)\) es
$$v_q(\varphi(n))=\sum_{i=1}^r v_q(p_i-1)+\sum_{\substack{1\le i\le r\\p_i=q}}(a_i-1).$$
Así, cada exponente de \(\varphi(n)\) tiene dos fuentes:
1. factores ya forzados por los términos \(p_i-1\);
2. la contribución propia \(a_i-1\) cuando el primo \(q\) también aparece en \(n\).
Por eso \(\varphi(n)\) es de Achilles exactamente cuando todos los exponentes finales son al menos \(2\) y su gcd vale \(1\).
Tomemos
$$500=2^2\cdot 5^3.$$
El vector de exponentes de \(n\) es \((2,3)\), así que \(500\) es powerful y además
$$\gcd(2,3)=1.$$
Por lo tanto, \(500\) es de Achilles.
Ahora el totiente:
$$\varphi(500)=500\left(1-\frac12\right)\left(1-\frac15\right)=200=2^3\cdot 5^2.$$
El vector de exponentes de \(\varphi(500)\) es \((3,2)\); otra vez todos son al menos \(2\) y
$$\gcd(3,2)=1.$$
Luego \(500\) es un número de Achilles fuerte. Es el ejemplo más pequeño y sirve como guía mental para entender la recursión.
La factorización de \(p-1\) solo usa primos estrictamente menores que \(p\). Entonces, si la recursión procesa las bases primas en orden descendente, una vez que pasamos por debajo de un primo \(q\), ninguna decisión futura puede aumentar el exponente de \(q\) dentro de \(\varphi(n)\).
Eso significa que dicho exponente ya es definitivo. El código lo incorpora enseguida al gcd acumulado de \(\varphi(n)\) y lo elimina del estado activo. Esa es la idea estructural central del algoritmo.
active_factorsEl arreglo active_factors es un multiconjunto ordenado de índices de primos. Si el índice de un primo \(q\) aparece exactamente \(t\) veces, entonces \(t\) es la parte del exponente de \(q\) en \(\varphi(n)\) que ya fue creada por factores \(p-1\) provenientes de primos mayores ya elegidos.
Esas copias aún no están cerradas porque la recursión todavía podría decidir incluir al propio \(q\) como factor primo de \(n\), y eso añadiría el término extra \(a_q-1\).
Además, el código mantiene dos resúmenes por gcd:
$$g_n=\gcd(\text{exponentes elegidos en }n),\qquad g_\varphi=\gcd(\text{exponentes ya cerrados en }\varphi(n)).$$
Supongamos que la recursión introduce un primo \(p\) que todavía no aparece en active_factors. Entonces los primos mayores no han contribuido ninguna copia de \(p\) a \(\varphi(n)\). La única contribución garantizada es el término propio \(a-1\) procedente de \(p^{a-1}\) en la fórmula de Euler.
Para que \(\varphi(n)\) sea powerful necesitamos
$$a-1\ge 2,$$
y por tanto
$$a\ge 3.$$
Eso explica exactamente por qué el código prueba deg = 3,4,5,\dots para un primo genuinamente nuevo. También de aquí sale la poda por raíz cúbica: cada primo nuevo cuesta al menos \(p^3\).
Supongamos ahora que \(p\) ya aparece en active_factors con multiplicidad \(t\ge 1\). Entonces los primos mayores ya han forzado un factor \(p^t\) dentro de \(\varphi(n)\). Si ahora elegimos \(p^a\) en \(n\), el exponente final de \(p\) en \(\varphi(n)\) pasa a ser
$$t+(a-1).$$
La condición de powerful solo exige
$$t+(a-1)\ge 2.$$
Como \(t\ge 1\), el menor valor permitido ya es \(a=2\). Por eso el código tiene una rama separada en la que un primo ya activo se prueba con deg = 2,3,4,\dots.
El ejemplo \(500=2^2\cdot 5^3\) lo muestra bien: tras elegir \(5^3\), el factor \(5-1=4=2^2\) coloca dos copias del primo \(2\) dentro de active_factors. Después basta elegir \(2^2\), porque el exponente de \(2\) en \(\varphi(500)\) se vuelve \(2+(2-1)=3\).
Un estado recursivo ya representa un candidato completo \(n\). Se cuenta exactamente cuando
$$g_n=1,$$
toda multiplicidad restante en active_factors es al menos \(2\), y además
$$\gcd\bigl(g_\varphi,\text{todas las multiplicidades restantes}\bigr)=1.$$
La interpretación es directa:
1. \(g_n=1\) significa que \(n\) no es potencia perfecta.
2. Multiplicidades restantes al menos \(2\) significan que \(\varphi(n)\) es powerful.
3. El gcd final igual a \(1\) significa que \(\varphi(n)\) no es potencia perfecta.
Si todavía queremos introducir un primo completamente nuevo \(p\), debemos pagar al menos \(p^3\). Por eso un primo fresco solo puede usarse cuando
$$p^3\le \text{límite restante}.$$
Equivalentemente,
$$p\le \left\lfloor\sqrt[3]{\text{límite restante}}\right\rfloor.$$
Por eso el solver calcula una cota por raíz cúbica antes de abrir la rama de “primo nuevo”. Elimina muy pronto casi todos los candidatos imposibles.
La implementación contiene dos comprobaciones explícitas:
$$\text{count}(10^4)=7,\qquad \text{count}(10^8)=656.$$
Los primeros siete números de Achilles fuertes son
$$500,\ 864,\ 1944,\ 2000,\ 2592,\ 3456,\ 5000.$$
Estos checkpoints son importantes porque el objetivo real \(10^{18}\) está muy lejos de cualquier búsqueda por fuerza bruta.
Primero, una criba genera todos los primos hasta una cota segura. Después, para cada entero \(m\) dentro del rango de la criba, se precomputa la factorización prima de \(m\) como un multiconjunto de índices de primos. Eso permite fusionar muy rápido los factores de \(p-1\) dentro de la recursión.
La función count_recursive(...) hace tres cosas en cada estado:
1. comprobar si el estado actual ya forma un número de Achilles fuerte;
2. probar primos que ya aparecen en active_factors;
3. probar primos realmente nuevos, sujetos a la regla de exponente \(3\) y a la cota de raíz cúbica.
Como el orden de búsqueda es canónico y descendente, cada \(n\) válido se genera exactamente una vez.
No hay una fórmula cerrada simple para el tiempo de ejecución, porque el árbol de búsqueda depende de la estructura aritmética de los números \(p-1\). En el peor caso la recursión es exponencial, pero en la práctica queda controlada por cuatro filtros fuertes: exponentes grandes, condiciones de gcd, la cota de raíz cúbica para primos nuevos y la finalización inmediata de exponentes grandes de \(\varphi(n)\).
El uso de memoria es moderado: profundidad de recursión, un multiconjunto activo corto y las tablas precalculadas de criba y factorización.
强 Achilles 数指的是：\(n\) 本身是 Achilles 数，并且 \(\varphi(n)\) 也是 Achilles 数。一个整数是 Achilles 数，当且仅当它是 powerful number，但又不是完全幂。题目要求统计所有小于 \(10^{18}\) 的这类 \(n\)。
写成
$$n=\prod_{i=1}^r p_i^{a_i},\qquad a_i\ge 1.$$
\(n\) 是 powerful，等价于每个指数都至少为 \(2\)：
$$a_i\ge 2\qquad \text{对所有 }i.$$
\(n\) 是某个 \(k\) 次完全幂，当且仅当所有指数都被同一个 \(k\ge 2\) 整除，也就是
$$\gcd(a_1,a_2,\dots,a_r)\ge 2.$$
因此
$$n\text{ 是 Achilles 数}\iff a_i\ge 2\ \forall i\quad\text{且}\quad \gcd(a_1,\dots,a_r)=1.$$
这样一来，问题的第一部分就变成了一个纯粹的指数向量条件。
Euler 乘积公式给出
$$\varphi(n)=\prod_{i=1}^r p_i^{a_i-1}(p_i-1).$$
固定一个素数 \(q\)，它在 \(\varphi(n)\) 中的指数是
$$v_q(\varphi(n))=\sum_{i=1}^r v_q(p_i-1)+\sum_{\substack{1\le i\le r\\p_i=q}}(a_i-1).$$
所以 \(\varphi(n)\) 中的每个指数都有两类来源：
1. 来自各个 \(p_i-1\) 分解强制产生的贡献；
2. 如果 \(q\) 本身也出现在 \(n\) 中，那么还会额外得到自贡献 \(a_i-1\)。
于是 \(\varphi(n)\) 是 Achilles 数，当且仅当所有最终指数都至少为 \(2\)，并且这些最终指数的 gcd 等于 \(1\)。
取
$$500=2^2\cdot 5^3.$$
\(n\) 的指数向量是 \((2,3)\)，因此 \(500\) 是 powerful，而且
$$\gcd(2,3)=1.$$
所以 \(500\) 是 Achilles 数。
再看 totient：
$$\varphi(500)=500\left(1-\frac12\right)\left(1-\frac15\right)=200=2^3\cdot 5^2.$$
\(\varphi(500)\) 的指数向量是 \((3,2)\)，同样都至少为 \(2\)，并且
$$\gcd(3,2)=1.$$
因此 \(500\) 是一个强 Achilles 数。它也是最小的例子，很适合用来理解递归到底在构造什么。
\(p-1\) 的素因子只可能严格小于 \(p\)。因此，如果递归按素数底数从大到小处理，那么一旦搜索顺序下降到某个素数 \(q\) 以下，后续任何选择都不可能再增加 \(q\) 在 \(\varphi(n)\) 中的指数。
这意味着 \(q\) 的指数已经最终确定。代码会立刻把这个最终指数并入 \(\varphi(n)\) 的运行 gcd，并把 \(q\) 从活动状态中移除。这正是整套递归能够成立的核心结构。
active_factors 的真正含义active_factors 是一个按序保存的素数下标多重集。如果某个素数 \(q\) 的下标在其中恰好出现 \(t\) 次，那么这个 \(t\) 就表示：在目前为止，由更大的已选素数的 \(p-1\) 因子已经给 \(\varphi(n)\) 中的 \(q\) 指数贡献了 \(t\)。
之所以说它“尚未最终确定”，是因为递归后面仍然可能决定把 \(q\) 本身也选进 \(n\)，这样还会额外增加 \(a_q-1\)。
代码同时维护两个 gcd 汇总量：
$$g_n=\gcd(\text{\(n\) 中已选指数}),\qquad g_\varphi=\gcd(\text{\(\varphi(n)\) 中已最终确定的指数}).$$
假设递归准备引入一个在 active_factors 中还 没有 出现过的素数 \(p\)。那么更大的素数此前并没有给 \(\varphi(n)\) 提供任何 \(p\) 的贡献。唯一确定存在的贡献，就是 Euler 公式里 \(p^{a-1}\) 带来的 \(a-1\)。
要让 \(\varphi(n)\) 成为 powerful，必须有
$$a-1\ge 2,$$
也就是
$$a\ge 3.$$
这正是代码对真正的新素数只尝试 deg = 3,4,5,\dots 的原因。由此也直接得到立方根剪枝：每个新素数至少要花掉 \(p^3\) 的预算。
现在假设 \(p\) 已经在 active_factors 中出现，并且重数为 \(t\ge 1\)。这说明更大的素数已经强制在 \(\varphi(n)\) 中产生了一个 \(p^t\) 因子。如果此时再把 \(p^a\) 放进 \(n\)，那么 \(p\) 在 \(\varphi(n)\) 中的最终指数就会变成
$$t+(a-1).$$
powerful 条件只要求
$$t+(a-1)\ge 2.$$
由于 \(t\ge 1\)，最小合法选择已经可以是 \(a=2\)。这就是为什么代码为“已激活素数”单独开了一支，从 deg = 2,3,4,\dots 开始枚举。
\(500=2^2\cdot 5^3\) 这个例子很清楚：先选 \(5^3\) 后，因为 \(5-1=4=2^2\)，所以 active_factors 中会先放入两个 \(2\)。这时再选 \(2^2\) 就足够了，因为 \(\varphi(500)\) 中 \(2\) 的指数变成 \(2+(2-1)=3\)。
一个递归状态已经对应一个完整候选 \(n\)。它在且仅在以下条件下被计数：
$$g_n=1,$$
active_factors 中剩余的每个重数都至少是 \(2\)，并且
$$\gcd\bigl(g_\varphi,\text{所有剩余重数}\bigr)=1.$$
含义非常直接：
1. \(g_n=1\) 表示 \(n\) 不是完全幂。
2. 剩余重数都至少为 \(2\) 表示 \(\varphi(n)\) 是 powerful。
3. 最终 gcd 为 \(1\) 表示 \(\varphi(n)\) 也不是完全幂。
如果还要再加入一个全新的素数 \(p\)，那么至少要消耗 \(p^3\)。因此新素数只有在
$$p^3\le \text{剩余上界}$$
时才有可能被使用。等价地，
$$p\le \left\lfloor\sqrt[3]{\text{剩余上界}}\right\rfloor.$$
这就是求解器在打开“新素数分支”之前先算立方根上界的原因。它可以极早地砍掉几乎所有无望分支。
实现中包含两个明确的检查：
$$\text{count}(10^4)=7,\qquad \text{count}(10^8)=656.$$
前七个强 Achilles 数是
$$500,\ 864,\ 1944,\ 2000,\ 2592,\ 3456,\ 5000.$$
这些校验点很重要，因为真正目标 \(10^{18}\) 已经远远超出暴力枚举范围。
首先通过筛法生成一个安全范围内的全部素数。接着，对筛范围内的每个整数 \(m\)，预先把 \(m\) 的素因子分解存成“素数下标多重集”。这样递归在处理 \(p-1\) 时，就能非常快地把这些因子并入状态。
count_recursive(...) 在每个状态做三件事：
1. 检查当前状态是否已经构成一个强 Achilles 数；
2. 尝试那些已经出现在 active_factors 里的素数；
3. 尝试真正的新素数，但要满足指数至少 \(3\) 和立方根上界这两个条件。
由于搜索顺序是规范化且递减的，每个合法的 \(n\) 都只会被生成一次。
运行时间没有一个简单闭式，因为搜索树高度依赖于各个 \(p-1\) 的算术结构。最坏情况下递归仍然是指数级，但在实际中它被四个强过滤器压得很低：指数必须足够大、gcd 条件会大量剪枝、新素数必须满足立方根上界、而且一旦某些 totient 指数不再可能变化就会立刻从活动状态中移除。
空间消耗不大，主要是递归深度、一个很短的活动多重集，以及预计算的筛表和因子表。
Сильное число Ахиллеса — это такое число \(n\), что и \(n\), и \(\varphi(n)\) являются числами Ахиллеса. Число называется числом Ахиллеса, если оно powerful, но не является совершенной степенью. Нужно посчитать количество таких \(n\) меньше \(10^{18}\).
Пишем
$$n=\prod_{i=1}^r p_i^{a_i},\qquad a_i\ge 1.$$
Число \(n\) является powerful тогда и только тогда, когда каждый показатель не меньше \(2\):
$$a_i\ge 2\qquad \text{для всех }i.$$
Оно является совершенной \(k\)-й степенью тогда и только тогда, когда все показатели делятся на одно и то же \(k\ge 2\), то есть когда
$$\gcd(a_1,a_2,\dots,a_r)\ge 2.$$
Следовательно,
$$n\text{ — число Ахиллеса}\iff a_i\ge 2\ \forall i\quad\text{и}\quad \gcd(a_1,\dots,a_r)=1.$$
Первая половина задачи тем самым сводится к условию на вектор показателей.
Формула Эйлера даёт
$$\varphi(n)=\prod_{i=1}^r p_i^{a_i-1}(p_i-1).$$
Для фиксированного простого \(q\) его показатель в \(\varphi(n)\) равен
$$v_q(\varphi(n))=\sum_{i=1}^r v_q(p_i-1)+\sum_{\substack{1\le i\le r\\p_i=q}}(a_i-1).$$
То есть каждый показатель в \(\varphi(n)\) складывается из двух источников:
1. вкладов из разложений чисел \(p_i-1\);
2. собственного вклада \(a_i-1\), если сам простой \(q\) входит в \(n\).
Значит, \(\varphi(n)\) является числом Ахиллеса тогда и только тогда, когда все конечные показатели не меньше \(2\), а их gcd равен \(1\).
Возьмём
$$500=2^2\cdot 5^3.$$
Вектор показателей у \(n\) равен \((2,3)\), значит \(500\) — powerful и
$$\gcd(2,3)=1.$$
Следовательно, \(500\) — число Ахиллеса.
Теперь тотиент:
$$\varphi(500)=500\left(1-\frac12\right)\left(1-\frac15\right)=200=2^3\cdot 5^2.$$
Вектор показателей у \(\varphi(500)\) — \((3,2)\); снова все показатели не меньше \(2\), и
$$\gcd(3,2)=1.$$
Значит, \(500\) — сильное число Ахиллеса. Это минимальный пример, и он хорошо показывает, что именно строит рекурсия.
Разложение числа \(p-1\) использует только простые, строго меньшие \(p\). Поэтому если рекурсия перебирает простые основания в убывающем порядке, то после того как мы опустились ниже простого \(q\), никакой дальнейший выбор уже не сможет увеличить показатель \(q\) в \(\varphi(n)\).
Это означает, что показатель \(q\) окончательно зафиксирован. Код сразу включает его в накопленный gcd для \(\varphi(n)\) и удаляет \(q\) из активного состояния. Именно это делает перебор управляемым.
active_factorsМассив active_factors — это отсортированное мультимножество индексов простых чисел. Если индекс простого \(q\) встречается там ровно \(t\) раз, то \(t\) — это та часть показателя \(q\) в \(\varphi(n)\), которая уже создана множителями вида \(p-1\) от более крупных выбранных простых.
Эти копии ещё не окончательны, потому что рекурсия позже может решить включить сам \(q\) в разложение \(n\), а это добавит ещё \(a_q-1\).
Параллельно код хранит два gcd-инварианта:
$$g_n=\gcd(\text{выбранные показатели в }n),\qquad g_\varphi=\gcd(\text{уже финализированные показатели в }\varphi(n)).$$
Предположим, рекурсия вводит простой \(p\), который ещё не встречается в active_factors. Тогда более крупные простые не внесли ни одной копии \(p\) в \(\varphi(n)\). Единственный гарантированный вклад — собственный член \(a-1\), идущий из \(p^{a-1}\) в формуле Эйлера.
Чтобы \(\varphi(n)\) было powerful, необходимо
$$a-1\ge 2,$$
то есть
$$a\ge 3.$$
Именно поэтому для действительно нового простого код перебирает deg = 3,4,5,\dots. Отсюда же возникает отсечение по кубическому корню: каждый новый простой требует как минимум множителя \(p^3\).
Пусть теперь \(p\) уже встречается в active_factors с кратностью \(t\ge 1\). Значит, более крупные простые уже заставили появиться множитель \(p^t\) внутри \(\varphi(n)\). Если теперь добавить в \(n\) множитель \(p^a\), то конечный показатель \(p\) в \(\varphi(n)\) станет
$$t+(a-1).$$
Условие powerful требует только
$$t+(a-1)\ge 2.$$
Так как \(t\ge 1\), минимально допустимый выбор уже \(a=2\). Поэтому в коде есть отдельная ветка, где для уже активного простого пробуются значения deg = 2,3,4,\dots.
Пример \(500=2^2\cdot 5^3\) показывает это особенно наглядно: после выбора \(5^3\) число \(5-1=4=2^2\) помещает две копии простого \(2\) в active_factors. После этого достаточно выбрать \(2^2\), потому что показатель \(2\) в \(\varphi(500)\) станет \(2+(2-1)=3\).
Рекурсивное состояние уже представляет полный кандидат \(n\). Оно засчитывается тогда и только тогда, когда
$$g_n=1,$$
каждая оставшаяся кратность в active_factors не меньше \(2\), и при этом
$$\gcd\bigl(g_\varphi,\text{все оставшиеся кратности}\bigr)=1.$$
Смысл прямой:
1. \(g_n=1\) означает, что \(n\) не является совершенной степенью.
2. Оставшиеся кратности не меньше \(2\) означают, что \(\varphi(n)\) является powerful.
3. Финальный gcd, равный \(1\), означает, что \(\varphi(n)\) не является совершенной степенью.
Если мы ещё хотим добавить совершенно новый простой \(p\), то должны заплатить как минимум \(p^3\). Поэтому новый простой можно использовать только если
$$p^3\le \text{оставшийся лимит}.$$
Эквивалентно,
$$p\le \left\lfloor\sqrt[3]{\text{оставшийся лимит}}\right\rfloor.$$
Именно поэтому решатель вычисляет кубический корень перед открытием ветки «новый простой». Это очень рано отсекает почти все безнадёжные варианты.
В реализации есть две явные проверки:
$$\text{count}(10^4)=7,\qquad \text{count}(10^8)=656.$$
Первые семь сильных чисел Ахиллеса:
$$500,\ 864,\ 1944,\ 2000,\ 2592,\ 3456,\ 5000.$$
Эти контрольные точки важны, потому что полная цель \(10^{18}\) слишком велика для прямого перебора.
Сначала решето генерирует все простые до безопасной границы. Затем для каждого числа \(m\) в диапазоне решета заранее вычисляется его разложение на простые в виде мультимножества индексов простых. Именно это и нужно рекурсии для обработки множителей \(p-1\).
Функция count_recursive(...) на каждом состоянии делает три вещи:
1. проверяет, образует ли текущее состояние уже сильное число Ахиллеса;
2. пробует простые, которые уже есть в active_factors;
3. пробует действительно новые простые с учётом правила про показатель \(3\) и оценки через кубический корень.
Поскольку порядок поиска канонический и убывающий, каждое допустимое \(n\) генерируется ровно один раз.
Простой замкнутой формулы для времени работы нет, потому что дерево поиска зависит от арифметической структуры чисел \(p-1\). В худшем случае рекурсия экспоненциальна, но на практике её резко сокращают четыре сильных фильтра: большие показатели, gcd-условия, ограничение по кубическому корню для новых простых и немедленная финализация тех показателей totient, которые уже не могут измениться.
Память расходуется умеренно: глубина рекурсии, короткое активное мультимножество и предварительно вычисленные таблицы решета и факторизаций.
العدد Achilles القوي هو عدد صحيح \(n\) يكون فيه كل من \(n\) و\(\varphi(n)\) عدد Achilles. والعدد يكون Achilles إذا كان powerful لكنه ليس قوة تامة. المطلوب هو عدّ جميع هذه الأعداد الأصغر من \(10^{18}\).
نكتب
$$n=\prod_{i=1}^r p_i^{a_i},\qquad a_i\ge 1.$$
يكون \(n\) عددًا powerful إذا وفقط إذا كان كل أسّ لا يقل عن \(2\):
$$a_i\ge 2\qquad \text{لكل }i.$$
ويكون قوة تامة من الرتبة \(k\) إذا وفقط إذا كانت كل الأسس تقبل القسمة على نفس \(k\ge 2\)، وهذا يكافئ
$$\gcd(a_1,a_2,\dots,a_r)\ge 2.$$
إذًا
$$n\text{ هو Achilles}\iff a_i\ge 2\ \forall i\quad\text{و}\quad \gcd(a_1,\dots,a_r)=1.$$
وهكذا يتحول نصف المسألة الأول إلى مسألة على متجه الأسس فقط.
تعطينا صيغة أويلر الضربية
$$\varphi(n)=\prod_{i=1}^r p_i^{a_i-1}(p_i-1).$$
ولكل عدد أولي ثابت \(q\)، فإن أسّه داخل \(\varphi(n)\) يساوي
$$v_q(\varphi(n))=\sum_{i=1}^r v_q(p_i-1)+\sum_{\substack{1\le i\le r\\p_i=q}}(a_i-1).$$
إذن كل أسّ في \(\varphi(n)\) يأتي من مصدرين:
1. مساهمات مفروضة مسبقًا من العوامل \(p_i-1\)؛
2. المساهمة الذاتية \(a_i-1\) إذا كان \(q\) نفسه يظهر ضمن تحليل \(n\).
لذلك تكون \(\varphi(n)\) عدد Achilles إذا وفقط إذا كانت جميع الأسس النهائية على الأقل \(2\)، وكان القاسم المشترك الأكبر لها يساوي \(1\).
خذ
$$500=2^2\cdot 5^3.$$
متجه الأسس لـ \(n\) هو \((2,3)\)، وبالتالي فإن \(500\) عدد powerful، كما أن
$$\gcd(2,3)=1.$$
إذن \(500\) عدد Achilles.
والآن نحسب التوابع:
$$\varphi(500)=500\left(1-\frac12\right)\left(1-\frac15\right)=200=2^3\cdot 5^2.$$
متجه الأسس في \(\varphi(500)\) هو \((3,2)\)، ومرة أخرى كل الأسس لا تقل عن \(2\)، ولدينا
$$\gcd(3,2)=1.$$
إذن \(500\) عدد Achilles قوي. وهو أصغر مثال، لذلك فهو أفضل نقطة لفهم ما الذي تبنيه الخوارزمية التراجعية.
تحليل \(p-1\) إلى عوامل أولية يستخدم فقط أعدادًا أولية أصغر من \(p\) نفسه. لذلك إذا عالجت الخوارزمية قواعد الأعداد الأولية بترتيب تنازلي، فبمجرد أن نهبط أسفل عدد أولي \(q\)، فلن يتمكن أي اختيار لاحق من زيادة أسّ \(q\) داخل \(\varphi(n)\).
هذا يعني أن أسّ \(q\) صار نهائيًا. عندها يدمجه الكود فورًا في gcd الجاري الخاص بـ \(\varphi(n)\) ويزيل \(q\) من الحالة النشطة. هذه هي الفكرة البنيوية الأساسية التي تجعل البحث ممكنًا.
active_factors فعلًاالمصفوفة active_factors هي متعدد مجموعة مرتب من فهارس الأعداد الأولية. إذا ظهر فهرس عدد أولي \(q\) فيها بالضبط \(t\) مرات، فهذا يعني أن \(t\) هو الجزء من أسّ \(q\) داخل \(\varphi(n)\) الذي نشأ بالفعل من عوامل على الشكل \(p-1\) قادمة من أعداد أولية أكبر تم اختيارها من قبل.
وهذه النسخ لم تُغلق بعد، لأن الخوارزمية قد تقرر لاحقًا إدخال \(q\) نفسه كعامل أولي في \(n\)، وعندها نضيف الحد الإضافي \(a_q-1\).
وبالتوازي مع ذلك يحتفظ الكود بملخصين من نوع gcd:
$$g_n=\gcd(\text{الأسس المختارة في }n),\qquad g_\varphi=\gcd(\text{الأسس النهائية المغلقة في }\varphi(n)).$$
افترض أن الخوارزمية تريد إدخال عدد أولي \(p\) لا يظهر بعد في active_factors. عندئذ لم تضف الأعداد الأولية الأكبر أي نسخة من \(p\) إلى \(\varphi(n)\). والمساهمة الوحيدة المضمونة هي الحد الذاتي \(a-1\) الآتي من \(p^{a-1}\) في صيغة أويلر.
ولكي تكون \(\varphi(n)\) powerful يجب أن يتحقق
$$a-1\ge 2,$$
أي
$$a\ge 3.$$
ولهذا بالضبط يجرّب الكود deg = 3,4,5,\dots عندما يكون العدد الأولي جديدًا حقًا. ومن هنا يظهر أيضًا حد الجذر التكعيبي: كل عدد أولي جديد يكلف على الأقل \(p^3\).
الآن افترض أن \(p\) موجود أصلًا في active_factors بتكرار \(t\ge 1\). هذا يعني أن الأعداد الأولية الأكبر قد فرضت بالفعل وجود العامل \(p^t\) داخل \(\varphi(n)\). فإذا اخترنا الآن \(p^a\) داخل \(n\)، فإن الأس النهائي لـ \(p\) في \(\varphi(n)\) يصبح
$$t+(a-1).$$
وشرط powerful لا يطلب إلا
$$t+(a-1)\ge 2.$$
وبما أن \(t\ge 1\)، فإن أصغر اختيار قانوني صار بالفعل \(a=2\). لهذا يوجد في الكود فرع مستقل يجرّب العدد الأولي النشط مسبقًا مع deg = 2,3,4,\dots.
ومثال \(500=2^2\cdot 5^3\) يوضح ذلك جيدًا: بعد اختيار \(5^3\)، فإن \(5-1=4=2^2\) يضع نسختين من العدد الأولي \(2\) داخل active_factors. وبعد ذلك يكفي اختيار \(2^2\)، لأن أسّ \(2\) داخل \(\varphi(500)\) يصبح \(2+(2-1)=3\).
الوضع التراجعي يمثل بالفعل مرشحًا كاملًا \(n\). ويتم احتسابه إذا وفقط إذا تحقق ما يلي:
$$g_n=1,$$
وكانت كل التكرارات الباقية في active_factors لا تقل عن \(2\)، وكذلك
$$\gcd\bigl(g_\varphi,\text{كل التكرارات الباقية}\bigr)=1.$$
ومعنى ذلك مباشر:
1. \(g_n=1\) يعني أن \(n\) ليس قوة تامة.
2. كون التكرارات الباقية كلها على الأقل \(2\) يعني أن \(\varphi(n)\) powerful.
3. وأن يكون gcd النهائي مساويًا لـ \(1\) يعني أن \(\varphi(n)\) أيضًا ليست قوة تامة.
إذا أردنا ما زلنا إدخال عدد أولي جديد تمامًا \(p\)، فعلينا أن ندفع على الأقل \(p^3\). لذلك لا يمكن استخدام عدد أولي جديد إلا إذا تحقق
$$p^3\le \text{الحد المتبقي}.$$
وبشكل مكافئ،
$$p\le \left\lfloor\sqrt[3]{\text{الحد المتبقي}}\right\rfloor.$$
لهذا السبب يحسب البرنامج حدًا علويًا بجذر تكعيبي قبل فتح فرع "عدد أولي جديد". وهذا يقطع أغلب الفروع المستحيلة مبكرًا جدًا.
تحتوي الشيفرة على فحصين صريحين:
$$\text{count}(10^4)=7,\qquad \text{count}(10^8)=656.$$
وأول سبعة أعداد Achilles قوية هي
$$500,\ 864,\ 1944,\ 2000,\ 2592,\ 3456,\ 5000.$$
هذه نقاط تحقق مهمة، لأن الهدف الحقيقي \(10^{18}\) بعيد جدًا عن أي brute force مباشر.
أولًا، يقوم المنخل بتوليد جميع الأعداد الأولية حتى حد آمن. ثم يسبق الحساب بتحليل كل عدد \(m\) في مجال المنخل إلى عوامل أولية على شكل متعدد مجموعة من فهارس الأعداد الأولية. وهذا بالضبط ما تحتاجه الخوارزمية التراجعية عند دمج عوامل \(p-1\).
الدالة count_recursive(...) تنفذ ثلاث مهام في كل حالة:
1. تفحص هل الحالة الحالية تكوّن بالفعل عدد Achilles قويًا؛
2. تجرّب الأعداد الأولية الموجودة أصلًا في active_factors؛
3. تجرّب الأعداد الأولية الجديدة تمامًا، مع احترام قاعدة الأس \(3\) وحد الجذر التكعيبي.
وبما أن ترتيب البحث قانوني وتنازلي، فإن كل \(n\) صالح يُولد مرة واحدة فقط.
لا توجد صيغة مغلقة بسيطة لزمن التنفيذ، لأن شجرة البحث تعتمد على البنية الحسابية للأعداد \(p-1\). في أسوأ الحالات يكون التفرع أسيًا، لكن عمليًا يبقى تحت السيطرة بفضل أربعة مرشحات قوية: ضرورة كبر الأسس، شروط gcd، حد الجذر التكعيبي للأعداد الأولية الجديدة، وإغلاق أسس \(\varphi(n)\) الكبيرة فورًا عندما لا يعود بالإمكان تغييرها.
استهلاك الذاكرة محدود: عمق الاستدعاء التراجعي، ومتعدد مجموعة نشط قصير، وجداول المنخل والتحليل المسبقة.