The problem asks for all positive integers \(n\) such that
$$\varphi(n)=13!,$$
then orders those integers increasingly and asks for the \(150000\)-th entry of that list. This is an inverse-totient problem: instead of evaluating \(\varphi(n)\) for a known \(n\), we must recover every \(n\) whose totient equals the fixed target
$$13!=6227020800=2^{10}\cdot 3^5\cdot 5^2\cdot 7\cdot 11\cdot 13.$$
A brute-force scan over \(n\) is not realistic. The workable route is to use the multiplicative structure of \(\varphi\), restrict the possible prime divisors of \(n\), and enumerate only exact factorizations of the target totient.
If
$$n=\prod_{k=1}^{m} p_k^{e_k},$$
then Euler's product formula gives
$$\varphi(n)=\prod_{k=1}^{m}\varphi\!\left(p_k^{e_k}\right)=\prod_{k=1}^{m}(p_k-1)p_k^{e_k-1}.$$
The entire search can therefore be phrased as: find every collection of prime powers whose individual totient contributions multiply exactly to \(13!\).
The fixed target
$$T=13!=2^{10}\cdot 3^5\cdot 5^2\cdot 7\cdot 11\cdot 13$$
already tells us that every admissible contribution to \(\varphi(n)\) must divide \(T\). Because the prime factorization of \(T\) is tiny, all divisor-based pruning is cheap. In particular, \(T\) has
$$\tau(T)=(10+1)(5+1)(2+1)(1+1)^3=1584$$
positive divisors, so the raw candidate space is finite from the start.
If a prime \(p\) divides \(n\), then the factor \((p-1)\) appears inside \(\varphi(n)\). Therefore
$$p\mid n \quad\Longrightarrow\quad p-1\mid T.$$
So every prime divisor of a solution must have the form
$$p=d+1\qquad\text{for some divisor }d\text{ of }T,$$
with the additional requirement that \(p\) itself be prime. The implementations generate exactly this finite set by enumerating the divisors of \(T\) and testing \(d+1\) for primality.
There is a second, even sharper restriction. If \(p^e\) divides \(n\) with \(e\ge 2\), then
$$\varphi(p^e)=(p-1)p^{e-1}\mid T,$$
so \(p^{e-1}\mid T\). Hence only primes already dividing \(T\), namely \(2,3,5,7,11,13\), can appear with exponent greater than \(1\). Any larger candidate prime can only appear to the first power.
For a fixed admissible prime \(p\), the possible totient contributions are
$$\varphi(p)=p-1,\qquad \varphi(p^2)=(p-1)p,\qquad \varphi(p^3)=(p-1)p^2,\ \dots$$
Each choice of exponent \(e\) contributes one factor
$$c(p,e)=(p-1)p^{e-1}$$
to the target \(T\), while the corresponding factor inserted into \(n\) is \(p^e\). The algorithm never guesses arbitrary integers. It only tries these prime-power building blocks, and only when the current remaining totient budget is divisible by the chosen contribution.
Let the admissible primes be ordered as
$$q_0\lt q_1\lt \cdots \lt q_{m-1}.$$
Define \(\mathcal{S}(r,i)\) to be the set of integers built from the primes \(q_i,q_{i+1},\dots,q_{m-1}\) whose totient equals \(r\). Then the recursion used by the implementations is
$$\mathcal{S}(1,i)=\{1\},$$
and for \(r\gt 1\), define
$$E_j(r)=\{e\ge 1:(q_j-1)q_j^{e-1}\mid r\}.$$
Then
$$\mathcal{S}(r,i)=\bigcup_{j\ge i}\ \bigcup_{e\in E_j(r)} q_j^e\cdot \mathcal{S}\!\left(\frac{r}{(q_j-1)q_j^{e-1}},\,j+1\right).$$
This formula is not just a mathematical reformulation of the code; it is the code's search tree. At each node, the state is the remaining totient factor \(r\), the next usable prime index \(i\), and the partial value of \(n\) accumulated so far.
During the recursion, the following invariant is maintained:
$$\varphi(N)\cdot r=T,$$
where \(N\) is the partial integer already chosen and \(r\) is the remaining totient budget. Every recursive step replaces \(r\) by \(r/c(p,e)\) and multiplies \(N\) by \(p^e\), so the invariant continues to hold.
The second invariant is ordering: once the search moves past a prime \(q_j\), it never returns to smaller primes. That matters because the prime factorization of \(n\) is unique. Every valid solution has one increasing list of distinct primes and one exponent attached to each of them, so this monotone prime order guarantees that each solution is generated exactly once.
The implementations validate the search on the smaller target \(120\), and it is a good example of the mechanics. Here the admissible primes are those with \(p-1\mid 120\), namely
$$2,3,5,7,11,13,31,41,61.$$
One branch chooses \(p=13\). Since \(\varphi(13)=12\), the remaining budget becomes \(120/12=10\). Then it chooses \(p=11\), whose contribution is \(\varphi(11)=10\). The remainder is now \(1\), so this branch produces
$$n=13\cdot 11=143,$$
and indeed
$$\varphi(143)=\varphi(11)\varphi(13)=10\cdot 12=120.$$
Another branch chooses \(p=31\), using the contribution \(30\), and then \(p=5\), using the contribution \(4\), which gives
$$n=31\cdot 5=155,\qquad \varphi(155)=30\cdot 4=120.$$
The full problem uses the same search pattern, just with the larger target \(13!\) and a correspondingly larger, but still sharply pruned, recursion tree.
The C++, Python, and Java implementations first factor \(13!\), generate all of its divisors, and test each value \(d+1\) for primality. That step produces the complete admissible prime set. The primality testing is deterministic for 64-bit inputs, so no probabilistic uncertainty enters the search.
The search state stores three pieces of information: the remaining totient factor, the first prime that may still be used, and the partial integer \(n\). For each candidate prime, the implementation starts with the contribution \(p-1\) and repeatedly multiplies by \(p\) while divisibility still holds. That loop tries exactly the contributions
$$ (p-1),\ (p-1)p,\ (p-1)p^2,\dots $$
that correspond to \(p,p^2,p^3,\dots\). Whenever the remaining totient factor becomes \(1\), the current integer is a complete solution and is recorded.
Because solutions can be much larger than \(13!\), the implementations store candidate values in wide integer types rather than assuming 64-bit signed arithmetic is always sufficient.
After enumeration, the solution list is sorted, normalized by removing duplicates defensively, and indexed to extract the \(150000\)-th value. The C++ implementation also includes additional validation layers: it compares the recursive search against brute force for the small target \(120\), checks the known first solution for the main target, recomputes \(\varphi(n)\) from each discovered factorization, and confirms that the multi-threaded and single-threaded searches agree.
When multiple threads are used, the search is split by first-level prime-power choices. Each worker then explores a disjoint subtree of the same recursion, so the mathematical enumeration stays unchanged; only the traversal schedule changes. The Python and Java implementations use the same recursive logic serially.
The preprocessing is small. Factoring \(13!\), generating its \(1584\) divisors, and testing the corresponding values \(d+1\) for primality is negligible compared with the recursive enumeration.
The dominant cost is output-sensitive. If \(B\) is the number of recursive branches visited and \(M\) is the number of solutions found, then the enumeration cost is \(O(B)\), followed by \(O(M\log M)\) for sorting and normalization. There is no simple closed form for \(B\), because it depends on how often divisibility tests succeed, but the search is heavily pruned by the two main restrictions:
$$p-1\mid 13! \qquad\text{and}\qquad (p-1)p^{e-1}\mid 13!.$$
The recursion depth is modest because every accepted step divides the remaining totient budget by at least \(2\). Memory usage is \(O(M)\) for the stored solutions plus the recursion stack and, in the threaded C++ version, per-worker output buffers.
Gesucht sind alle positiven ganzen Zahlen \(n\) mit
$$\varphi(n)=13!,$$
die anschließend aufsteigend sortiert werden; daraus wird das \(150000\)-te Element entnommen. Das ist ein inverses Totientenproblem: Nicht \(\varphi(n)\) soll für gegebenes \(n\) berechnet werden, sondern alle \(n\), deren Totient gleich dem festen Zielwert ist, müssen rekonstruiert werden.
Der Zielwert ist
$$13!=6227020800=2^{10}\cdot 3^5\cdot 5^2\cdot 7\cdot 11\cdot 13.$$
Ein naiver Durchlauf über alle \(n\) ist unbrauchbar. Die Lösung nutzt stattdessen die multiplikative Struktur von \(\varphi\), schränkt die möglichen Primteiler von \(n\) stark ein und durchsucht nur exakte Zerlegungen des Zielwerts.
Für
$$n=\prod_{k=1}^{m} p_k^{e_k}$$
gilt
$$\varphi(n)=\prod_{k=1}^{m}\varphi\!\left(p_k^{e_k}\right)=\prod_{k=1}^{m}(p_k-1)p_k^{e_k-1}.$$
Die Aufgabe besteht also darin, alle Mengen von Primzahlpotenzen zu finden, deren Totientenbeiträge genau \(13!\) ergeben.
Mit
$$T=13!=2^{10}\cdot 3^5\cdot 5^2\cdot 7\cdot 11\cdot 13$$
muss jeder zulässige Baustein ein Teiler von \(T\) sein. Da diese Primfaktorzerlegung klein ist, sind auch alle Teiler-basierten Vorrechnungen klein. Insbesondere besitzt \(T\)
$$\tau(T)=(10+1)(5+1)(2+1)(1+1)^3=1584$$
positive Teiler. Die rohe Kandidatenmenge ist also von Anfang an endlich und überschaubar.
Wenn \(p\mid n\), dann enthält \(\varphi(n)\) den Faktor \(p-1\). Daher gilt notwendig
$$p\mid n \quad\Longrightarrow\quad p-1\mid T.$$
Jeder Primteiler einer Lösung hat also die Form
$$p=d+1\qquad\text{mit }d\mid T,$$
wobei zusätzlich \(p\) prim sein muss. Genau diese endliche Menge wird in den Implementierungen erzeugt, indem alle Teiler von \(T\) gebildet und die Werte \(d+1\) auf Primheit getestet werden.
Es gibt noch eine feinere Bedingung. Falls \(p^e\mid n\) mit \(e\ge 2\), dann ist
$$\varphi(p^e)=(p-1)p^{e-1}\mid T,$$
also insbesondere \(p^{e-1}\mid T\). Das bedeutet: Nur die Primzahlen, die selbst in \(T\) vorkommen, also \(2,3,5,7,11,13\), können mit Exponent größer als \(1\) auftreten. Jeder größere Kandidat kann höchstens einfach vorkommen.
Für eine feste zulässige Primzahl \(p\) lauten die möglichen Totientenbeiträge
$$\varphi(p)=p-1,\qquad \varphi(p^2)=(p-1)p,\qquad \varphi(p^3)=(p-1)p^2,\ \dots$$
Die Wahl des Exponenten \(e\) liefert also den Beitrag
$$c(p,e)=(p-1)p^{e-1}$$
zum Ziel \(T\), während in \(n\) der Faktor \(p^e\) erscheint. Das Verfahren rät niemals beliebige Zahlen. Es probiert nur solche Primzahlpotenzen aus, deren Totientenbeitrag den jeweils verbleibenden Rest des Ziels exakt teilt.
Ordne die zulässigen Primzahlen als
$$q_0\lt q_1\lt \cdots \lt q_{m-1}.$$
Sei \(\mathcal{S}(r,i)\) die Menge aller Zahlen, die nur aus \(q_i,q_{i+1},\dots,q_{m-1}\) aufgebaut werden und Totient \(r\) besitzen. Dann lautet die Rekursion
$$\mathcal{S}(1,i)=\{1\},$$
und für \(r\gt 1\), definiere
$$E_j(r)=\{e\ge 1:(q_j-1)q_j^{e-1}\mid r\}.$$
Dann gilt
$$\mathcal{S}(r,i)=\bigcup_{j\ge i}\ \bigcup_{e\in E_j(r)} q_j^e\cdot \mathcal{S}\!\left(\frac{r}{(q_j-1)q_j^{e-1}},\,j+1\right).$$
Genau diese Rekursion implementiert die Tiefensuche. Der Zustand besteht aus dem verbleibenden Totientenfaktor \(r\), dem kleinsten noch erlaubten Primindex \(i\) und dem bisher aufgebauten Teil von \(n\).
Während der gesamten Rekursion bleibt die Beziehung
$$\varphi(N)\cdot r=T$$
erhalten, wobei \(N\) der bereits konstruierte Teilkandidat und \(r\) der verbleibende Rest ist. Jeder Rekursionsschritt ersetzt \(r\) durch \(r/c(p,e)\) und multipliziert \(N\) mit \(p^e\), daher bleibt das Produkt unverändert.
Dazu kommt ein Ordnungsinvariant: Nachdem die Suche eine Primzahl \(q_j\) passiert hat, kehrt sie nie zu kleineren Primzahlen zurück. Wegen der Eindeutigkeit der Primfaktorzerlegung besitzt jede Lösung genau eine streng wachsende Primliste mit zugehörigen Exponenten. Deshalb wird jede gültige Lösung genau einmal erzeugt.
Die Implementierungen prüfen ihre Logik am kleineren Ziel \(120\); daran lässt sich das Verfahren gut von Hand sehen. Hier sind die zulässigen Primzahlen diejenigen mit \(p-1\mid 120\), also
$$2,3,5,7,11,13,31,41,61.$$
Ein Suchzweig wählt zuerst \(p=13\). Weil \(\varphi(13)=12\), bleibt der Rest \(120/12=10\). Danach wählt derselbe Zweig \(p=11\), dessen Beitrag \(\varphi(11)=10\) ist. Der Rest wird zu \(1\), also liefert dieser Pfad
$$n=13\cdot 11=143,$$
und tatsächlich gilt
$$\varphi(143)=\varphi(11)\varphi(13)=10\cdot 12=120.$$
Ein anderer Zweig nimmt \(p=31\) mit Beitrag \(30\) und danach \(p=5\) mit Beitrag \(4\). Das ergibt
$$n=31\cdot 5=155,\qquad \varphi(155)=30\cdot 4=120.$$
Für \(13!\) ist der Suchbaum größer, aber mathematisch identisch aufgebaut und durch dieselben Teilbarkeitskriterien stark beschnitten.
Die C++-, Python- und Java-Implementierungen faktorisieren zuerst \(13!\), erzeugen alle Teiler und testen dann jede Zahl \(d+1\) auf Primheit. So entsteht die vollständige zulässige Primmenge. Der eingesetzte Primzahltest ist für 64-Bit-Eingaben deterministisch, es gibt also keine probabilistische Unsicherheit.
Der Rekursionszustand speichert den verbleibenden Totientenfaktor, den ersten noch erlaubten Primindex und den bisher aufgebauten Wert \(n\). Für jede Kandidatenprimzahl beginnt die Implementierung mit dem Beitrag \(p-1\) und multipliziert diesen so lange mit \(p\), wie die Teilbarkeit erhalten bleibt. Dadurch werden genau die Beiträge
$$ (p-1),\ (p-1)p,\ (p-1)p^2,\dots $$
durchlaufen, die zu \(p,p^2,p^3,\dots\) gehören. Sobald der verbleibende Faktor den Wert \(1\) erreicht, ist ein vollständiger Kandidat gefunden und wird gespeichert.
Da gefundene Lösungen deutlich größer als \(13!\) sein können, werden für die aufgebauten Kandidaten breite Ganzzahltypen verwendet.
Nach der Enumeration wird die Lösungsliste sortiert, defensiv dedupliziert und anschließend an der Stelle \(150000\) abgefragt. Die C++-Version ergänzt mehrere Validierungen: Sie vergleicht die rekursive Suche für \(\varphi(n)=120\) mit einer Brute-Force-Liste, überprüft die bekannte erste Lösung des Hauptproblems, berechnet \(\varphi(n)\) für jeden gefundenen Kandidaten noch einmal nach und vergleicht Mehrthread- und Einzelthread-Ausgabe.
Wenn mehrere Threads benutzt werden, wird die Suche nach den möglichen Primzahlpotenz-Wahlen auf der ersten Ebene aufgeteilt. Jeder Arbeiter bearbeitet dann einen disjunkten Teilbaum derselben Rekursion. Die Mathematik der Enumeration bleibt also gleich; nur die Traversierung wird parallelisiert. Die Python- und Java-Versionen verwenden dieselbe Logik seriell.
Die Vorverarbeitung ist klein. Das Faktorisieren von \(13!\), das Erzeugen seiner \(1584\) Teiler und das Testen der Werte \(d+1\) auf Primheit fällt gegenüber der eigentlichen Suche kaum ins Gewicht.
Dominant ist eine ausgabeabhängige Rekursion. Bezeichnet \(B\) die Zahl der besuchten Rekursionszweige und \(M\) die Zahl der gefundenen Lösungen, dann kostet die Enumeration \(O(B)\), gefolgt von \(O(M\log M)\) für Sortierung und Normalisierung. Für \(B\) gibt es keine einfache geschlossene Formel, weil es davon abhängt, wie oft die Teilbarkeitstests erfolgreich sind. Entscheidend ist aber, dass zwei harte Filter fast alle Äste entfernen:
$$p-1\mid 13! \qquad\text{und}\qquad (p-1)p^{e-1}\mid 13!.$$
Die Rekursionstiefe bleibt klein, weil jeder akzeptierte Schritt den Rest mindestens halbiert. Der Speicherbedarf beträgt \(O(M)\) für die gespeicherten Lösungen plus Rekursionsstack und, in der parallelen C++-Version, thread-lokale Ausgabepuffer.
Problem,
$$\varphi(n)=13!$$
eşitliğini sağlayan tüm pozitif tamsayıları bulup bunları artan sıraya dizmeyi ve bu sıralı listenin \(150000\). elemanını seçmeyi ister. Bu, doğrudan bir \(\varphi\) hesaplama problemi değil, ters totient problemidir: verilen bir \(n\) için \(\varphi(n)\) hesaplamak yerine, totienti sabit hedefe eşit olan bütün \(n\) değerlerini üretmemiz gerekir.
Hedef değer
$$13!=6227020800=2^{10}\cdot 3^5\cdot 5^2\cdot 7\cdot 11\cdot 13$$
olduğundan, kaba kuvvetle \(n\) taramak gerçekçi değildir. Etkili çözüm, \(\varphi\)'nin çarpımsal yapısını kullanıp \(n\)'in olası asal bölenlerini ciddi biçimde daraltmak ve yalnızca hedef totienti tam olarak oluşturan çarpanlaşmaları dolaşmaktır.
Eğer
$$n=\prod_{k=1}^{m} p_k^{e_k}$$
ise Euler formülü
$$\varphi(n)=\prod_{k=1}^{m}\varphi\!\left(p_k^{e_k}\right)=\prod_{k=1}^{m}(p_k-1)p_k^{e_k-1}$$
şeklindedir. Dolayısıyla arama, totient katkıları çarpımı tam olarak \(13!\) olan bütün asal kuvvet koleksiyonlarını bulma problemine dönüşür.
Sabit hedefi
$$T=13!=2^{10}\cdot 3^5\cdot 5^2\cdot 7\cdot 11\cdot 13$$
olarak yazalım. Geçerli herhangi bir katkı \(T\)'nin böleni olmak zorundadır. Bu çarpanlaşma küçük olduğu için bölen tabanlı bütün ön hesaplamalar da küçüktür. Özellikle \(T\)'nin pozitif bölen sayısı
$$\tau(T)=(10+1)(5+1)(2+1)(1+1)^3=1584$$
olduğundan, ham aday uzayı baştan itibaren sonludur.
Eğer \(p\mid n\) ise, \(\varphi(n)\) içinde mutlaka \(p-1\) çarpanı bulunur. O halde
$$p\mid n \quad\Longrightarrow\quad p-1\mid T.$$
Demek ki çözümde görülebilecek her asal
$$p=d+1\qquad\text{ve }d\mid T$$
biçimindedir; ayrıca \(p\)'nin gerçekten asal olması gerekir. Uygulamalar tam olarak bu sonlu kümeyi üretir: önce \(T\)'nin bütün bölenleri bulunur, sonra her \(d+1\) değeri asal testiyle süzülür.
Daha keskin bir gözlem daha vardır. Eğer \(p^e\mid n\) ve \(e\ge 2\) ise
$$\varphi(p^e)=(p-1)p^{e-1}\mid T,$$
dolayısıyla \(p^{e-1}\mid T\) olmalıdır. Bu da şu anlama gelir: yalnızca zaten \(T\)'yi bölen asallar, yani \(2,3,5,7,11,13\), üsleri \(1\)'den büyük olacak şekilde görünebilir. Daha büyük aday asallar en fazla birinci kuvvetten kullanılabilir.
Sabit bir uygun asal \(p\) için olası katkılar
$$\varphi(p)=p-1,\qquad \varphi(p^2)=(p-1)p,\qquad \varphi(p^3)=(p-1)p^2,\ \dots$$
şeklindedir. Yani üs \(e\) seçimi, hedefe
$$c(p,e)=(p-1)p^{e-1}$$
katkısını yapar; \(n\)'e eklenen karşılık ise \(p^e\)'dir. Algoritma rastgele sayılar denemez. Yalnızca bu asal-kuvvet bloklarını dener ve ancak ilgili katkı mevcut kalan totient bütçesini tam bölüyorsa o dalı açar.
Uygun asalları
$$q_0\lt q_1\lt \cdots \lt q_{m-1}$$
şeklinde sıralayalım. \(\mathcal{S}(r,i)\), yalnızca \(q_i,q_{i+1},\dots,q_{m-1}\) kullanılarak kurulabilen ve totienti \(r\) olan sayıların kümesi olsun. O zaman kullanılan özyineleme
$$\mathcal{S}(1,i)=\{1\},$$
ve \(r\gt 1\) için
$$E_j(r)=\{e\ge 1:(q_j-1)q_j^{e-1}\mid r\}$$
tanımıyla
$$\mathcal{S}(r,i)=\bigcup_{j\ge i}\ \bigcup_{e\in E_j(r)} q_j^e\cdot \mathcal{S}\!\left(\frac{r}{(q_j-1)q_j^{e-1}},\,j+1\right)$$
olur. Bu ifade yalnızca kodun matematiksel özeti değildir; doğrudan arama ağacının kendisidir. Her düğümde durum, kalan totient çarpanı \(r\), kullanılabilecek ilk asal indeksi \(i\) ve şimdiye kadar oluşturulmuş kısmi \(n\) değeridir.
Özyineleme boyunca şu invariant korunur:
$$\varphi(N)\cdot r=T,$$
burada \(N\) şimdiye kadar seçilmiş asal kuvvetlerin çarpımı, \(r\) ise henüz karşılanmamış totient bütçesidir. Her adımda \(r\), seçilen katkıya bölünür; \(N\) ise karşılık gelen \(p^e\) ile çarpılır. Böylece çarpım değişmez.
İkinci invariant sıralamadır: arama bir kez \(q_j\) asalını geçince daha küçük asallara geri dönmez. Çünkü asal çarpanlara ayrışım tektir. Geçerli her çözümün tek bir artan asal listesi ve bu asallara bağlı tek üs dizisi vardır. Bu yüzden sıkı artan asal sırası, her çözümün tam olarak bir kez üretilmesini garanti eder.
Uygulamalar mantığı küçük hedef \(120\) üzerinde doğrular; bu örnek yöntemi elle görmek için idealdir. Burada uygun asallar, \(p-1\mid 120\) koşulunu sağlayan
$$2,3,5,7,11,13,31,41,61$$
değerleridir. Bir dal ilk olarak \(p=13\) seçsin. \(\varphi(13)=12\) olduğundan kalan bütçe \(120/12=10\) olur. Sonra aynı dal \(p=11\) seçer; bunun katkısı \(\varphi(11)=10\)'dur. Kalan değer \(1\)'e indiği için bu yol
$$n=13\cdot 11=143$$
çözümünü üretir ve gerçekten
$$\varphi(143)=\varphi(11)\varphi(13)=10\cdot 12=120$$
olur. Başka bir dal \(p=31\) ile \(30\) katkısını, ardından \(p=5\) ile \(4\) katkısını seçip
$$n=31\cdot 5=155,\qquad \varphi(155)=30\cdot 4=120$$
sonucuna ulaşır. \(13!\) hedefinde ağaç daha büyüktür ama mekanizma bütünüyle aynıdır.
C++, Python ve Java uygulamaları önce \(13!\)'ı asal çarpanlarına ayırır, bütün bölenlerini üretir ve her \(d+1\) değeri için asal testi yapar. Böylece izin verilen asal kümesinin tamamı elde edilir. Kullanılan asal testi 64 bit aralığında deterministiktir; yani bu aşamada olasılıksal bir belirsizlik yoktur.
Arama durumu üç bilgi taşır: kalan totient çarpanı, bundan sonra kullanılabilecek ilk asal indeksi ve o ana kadar oluşmuş aday \(n\). Her aday asal için uygulama önce \(p-1\) katkısıyla başlar; bu katkı kalan bütçeyi bölmeye devam ettiği sürece birer \(p\) ile çarpılır. Böylece tam olarak
$$ (p-1),\ (p-1)p,\ (p-1)p^2,\dots $$
katkıları denenmiş olur; bunlar da sırasıyla \(p,p^2,p^3,\dots\) faktörlerine karşılık gelir. Kalan totient çarpanı \(1\) olduğunda, eldeki sayı tam bir çözümdür ve kaydedilir.
Çözümler \(13!\)'dan çok daha büyük olabildiği için uygulamalar aday değerleri dar 64 bit tamsayılarla sınırlamayan geniş sayı türlerinde tutar.
Numaralandırma tamamlandıktan sonra çözüm listesi sıralanır, güvenlik amaçlı olarak yinelenen kayıtlar temizlenir ve \(150000\). eleman alınır. C++ sürümü buna ek olarak birkaç doğrulama adımı içerir: \(\varphi(n)=120\) için özyineli aramayı kaba kuvvet listesiyle karşılaştırır, ana problem için bilinen ilk çözümü kontrol eder, bulunan her adayın totientini yeniden hesaplar ve çok iş parçacıklı sonuçla tek iş parçacıklı sonucu karşılaştırır.
Birden fazla iş parçacığı kullanıldığında arama, ilk seviyedeki asal-kuvvet seçimlerine göre parçalanır. Her işçi aynı özyinelemenin ayrık bir alt ağacını gezer. Yani matematik değişmez; yalnızca aramanın çalışma takvimi paralelleşir. Python ve Java sürümleri aynı mantığı seri olarak uygular.
Ön işleme küçüktür. \(13!\)'ın çarpanlara ayrılması, \(1584\) böleninin üretilmesi ve karşılık gelen \(d+1\) değerlerinin asallık testinden geçirilmesi, asıl aramaya kıyasla çok ucuz kalır.
Baskın maliyet çıktı-duyarlıdır. \(B\) ziyaret edilen özyinelemeli dal sayısı, \(M\) bulunan çözüm sayısı olsun. O zaman arama maliyeti \(O(B)\), sıralama ve normalleştirme maliyeti ise \(O(M\log M)\) olur. \(B\) için basit bir kapalı form yoktur; çünkü belirleyici olan şey bölüm testlerinin kaç kez başarılı olduğudur. Ama iki sert filtre aramayı büyük ölçüde küçültür:
$$p-1\mid 13! \qquad\text{ve}\qquad (p-1)p^{e-1}\mid 13!.$$
Her kabul edilen adım kalan bütçeyi en az \(2\)'ye böldüğü için özyineleme derinliği küçüktür. Bellek kullanımı, saklanan çözümler için \(O(M)\), buna ek olarak özyineleme yığını ve paralel C++ sürümünde işçi başına yerel çıktı tamponlarıdır.
El problema pide encontrar todos los enteros positivos \(n\) que satisfacen
$$\varphi(n)=13!,$$
ordenarlos de menor a mayor y tomar la entrada número \(150000\) de esa lista. Se trata de un problema de totiente inversa: no partimos de \(n\) para calcular \(\varphi(n)\), sino que debemos reconstruir todos los \(n\) cuyo totiente coincide con un valor objetivo fijo.
Ese objetivo es
$$13!=6227020800=2^{10}\cdot 3^5\cdot 5^2\cdot 7\cdot 11\cdot 13.$$
Recorrer \(n\) por fuerza bruta no es viable. La estrategia correcta aprovecha la estructura multiplicativa de \(\varphi\), restringe mucho los primos que pueden dividir a \(n\) y recorre solo descomposiciones exactas del totiente objetivo.
Si
$$n=\prod_{k=1}^{m} p_k^{e_k},$$
entonces
$$\varphi(n)=\prod_{k=1}^{m}\varphi\!\left(p_k^{e_k}\right)=\prod_{k=1}^{m}(p_k-1)p_k^{e_k-1}.$$
Así, el problema consiste en encontrar todas las colecciones de potencias primas cuyos aportes al totiente multiplican exactamente hasta \(13!\).
Escribamos
$$T=13!=2^{10}\cdot 3^5\cdot 5^2\cdot 7\cdot 11\cdot 13.$$
Cualquier aporte admisible a \(\varphi(n)\) debe dividir a \(T\). Como la factorización prima de \(T\) es pequeña, todo el preprocesamiento basado en divisores también lo es. En particular, \(T\) tiene
$$\tau(T)=(10+1)(5+1)(2+1)(1+1)^3=1584$$
divisores positivos, de modo que el espacio bruto de candidatos ya es finito desde el comienzo.
Si \(p\mid n\), entonces el factor \(p-1\) aparece dentro de \(\varphi(n)\). Por tanto, necesariamente
$$p\mid n \quad\Longrightarrow\quad p-1\mid T.$$
Todo primo de una solución debe tener la forma
$$p=d+1\qquad\text{con }d\mid T,$$
y además \(p\) debe ser primo de verdad. Las implementaciones generan exactamente este conjunto finito: enumeran los divisores de \(T\) y comprueban la primalidad de cada \(d+1\).
Hay una poda aún más fuerte. Si \(p^e\mid n\) con \(e\ge 2\), entonces
$$\varphi(p^e)=(p-1)p^{e-1}\mid T,$$
así que \(p^{e-1}\mid T\). En consecuencia, solo los primos que ya dividen a \(T\), es decir \(2,3,5,7,11,13\), pueden aparecer con exponente mayor que \(1\). Cualquier primo candidato mayor solo puede aparecer a la primera potencia.
Para un primo admisible fijo \(p\), los aportes posibles al totiente son
$$\varphi(p)=p-1,\qquad \varphi(p^2)=(p-1)p,\qquad \varphi(p^3)=(p-1)p^2,\ \dots$$
Elegir el exponente \(e\) significa aportar
$$c(p,e)=(p-1)p^{e-1}$$
al objetivo \(T\), mientras que el factor correspondiente en \(n\) es \(p^e\). El algoritmo no prueba enteros arbitrarios. Solo prueba estos bloques de potencia prima, y únicamente cuando el aporte elegido divide exactamente el presupuesto restante del totiente.
Ordenemos los primos admisibles como
$$q_0\lt q_1\lt \cdots \lt q_{m-1}.$$
Sea \(\mathcal{S}(r,i)\) el conjunto de enteros construidos con \(q_i,q_{i+1},\dots,q_{m-1}\) cuyo totiente vale \(r\). Entonces la recursión usada por las implementaciones es
$$\mathcal{S}(1,i)=\{1\},$$
y para \(r\gt 1\), definimos
$$E_j(r)=\{e\ge 1:(q_j-1)q_j^{e-1}\mid r\}.$$
Entonces
$$\mathcal{S}(r,i)=\bigcup_{j\ge i}\ \bigcup_{e\in E_j(r)} q_j^e\cdot \mathcal{S}\!\left(\frac{r}{(q_j-1)q_j^{e-1}},\,j+1\right).$$
Esta fórmula no es solo una explicación matemática del código; es exactamente el árbol de búsqueda que el código recorre. En cada nodo, el estado está formado por el factor restante del totiente, el primer índice primo todavía disponible y el valor parcial de \(n\).
Durante toda la recursión se mantiene el invariante
$$\varphi(N)\cdot r=T,$$
donde \(N\) es el entero parcial ya construido y \(r\) es el presupuesto restante del totiente. Cada paso divide \(r\) por un aporte \(c(p,e)\) y multiplica \(N\) por \(p^e\), de modo que el producto permanece constante.
El segundo invariante es el orden. Una vez que la búsqueda ha avanzado más allá de un primo \(q_j\), no vuelve a primos menores. Como la factorización prima de \(n\) es única, cada solución válida tiene una única lista creciente de primos distintos y un único exponente asociado a cada uno. Por eso el recorrido produce cada solución exactamente una vez.
Las implementaciones verifican la lógica con el objetivo menor \(120\), y ese caso es perfecto para ver el mecanismo. Aquí los primos admisibles son los que cumplen \(p-1\mid 120\):
$$2,3,5,7,11,13,31,41,61.$$
Una rama elige primero \(p=13\). Como \(\varphi(13)=12\), el resto pasa a ser \(120/12=10\). Luego esa misma rama elige \(p=11\), cuyo aporte es \(\varphi(11)=10\). El resto queda en \(1\), así que esa rama produce
$$n=13\cdot 11=143,$$
y en efecto
$$\varphi(143)=\varphi(11)\varphi(13)=10\cdot 12=120.$$
Otra rama toma \(p=31\), con aporte \(30\), y luego \(p=5\), con aporte \(4\), obteniendo
$$n=31\cdot 5=155,\qquad \varphi(155)=30\cdot 4=120.$$
Para \(13!\) el árbol es más grande, pero el patrón matemático es exactamente el mismo y las mismas pruebas de divisibilidad lo podan con fuerza.
Las implementaciones en C++, Python y Java empiezan factorizando \(13!\), generando todos sus divisores y comprobando si cada valor \(d+1\) es primo. Eso produce el conjunto completo de primos admisibles. La prueba de primalidad utilizada es determinista en el rango de 64 bits, así que esta fase no introduce incertidumbre probabilística.
El estado de búsqueda guarda tres datos: el factor restante del totiente, el primer primo que todavía puede usarse y el valor parcial de \(n\). Para cada primo candidato, la implementación comienza con el aporte \(p-1\) y lo multiplica repetidamente por \(p\) mientras la divisibilidad siga siendo válida. Así recorre exactamente los aportes
$$ (p-1),\ (p-1)p,\ (p-1)p^2,\dots $$
que corresponden a \(p,p^2,p^3,\dots\). Cuando el factor restante llega a \(1\), el entero acumulado es una solución completa y se almacena.
Como las soluciones pueden ser bastante mayores que \(13!\), las implementaciones guardan los candidatos en tipos enteros amplios, no en un entero firmado de 64 bits asumido por defecto.
Una vez terminada la enumeración, la lista de soluciones se ordena, se normaliza eliminando duplicados de forma defensiva y se toma la entrada número \(150000\). La implementación en C++ añade además varias comprobaciones: compara la búsqueda recursiva con fuerza bruta en el caso pequeño \(\varphi(n)=120\), verifica la primera solución conocida del objetivo principal, vuelve a calcular \(\varphi(n)\) para cada candidato hallado y comprueba que la salida con varios hilos coincide con la salida en un solo hilo.
Cuando se usan varios hilos, la búsqueda se divide según las elecciones de potencia prima en el primer nivel. Cada trabajador explora un subárbol disjunto de la misma recursión. La enumeración matemática no cambia; solo cambia el calendario de recorrido. Las versiones de Python y Java ejecutan la misma lógica en serie.
El preprocesamiento es pequeño. Factorizar \(13!\), generar sus \(1584\) divisores y comprobar la primalidad de los valores \(d+1\) cuesta muy poco en comparación con la enumeración recursiva.
El coste dominante depende de la salida. Si \(B\) es el número de ramas recursivas visitadas y \(M\) el número de soluciones encontradas, la búsqueda cuesta \(O(B)\), seguida de \(O(M\log M)\) para ordenar y normalizar. No hay una fórmula cerrada simple para \(B\), porque depende de cuántas veces tengan éxito las pruebas de divisibilidad. Aun así, dos filtros duros eliminan la mayor parte del árbol:
$$p-1\mid 13! \qquad\text{y}\qquad (p-1)p^{e-1}\mid 13!.$$
La profundidad de la recursión es modesta porque cada paso aceptado divide el presupuesto restante al menos por \(2\). El uso de memoria es \(O(M)\) para almacenar las soluciones, más la pila recursiva y, en la versión paralela de C++, los búferes locales de cada trabajador.
题目要求找出所有满足
$$\varphi(n)=13!$$
的正整数 \(n\)，按从小到大的顺序排列，然后取这个有序列表中的第 \(150000\) 个元素。这不是通常的“给定 \(n\) 求 \(\varphi(n)\)”问题，而是一个逆欧拉函数问题：已知 totient 的值，反过来恢复所有可能的 \(n\)。
固定目标为
$$13!=6227020800=2^{10}\cdot 3^5\cdot 5^2\cdot 7\cdot 11\cdot 13.$$
如果直接从 \(1,2,3,\dots\) 开始暴力扫描 \(n\)，几乎不可能完成。可行的方法必须利用 \(\varphi\) 的乘法结构，把可能出现的素因子限制到一个很小的集合里，再只枚举那些能够把目标值恰好分解出来的分支。
若
$$n=\prod_{k=1}^{m} p_k^{e_k},$$
则 Euler 公式给出
$$\varphi(n)=\prod_{k=1}^{m}\varphi\!\left(p_k^{e_k}\right)=\prod_{k=1}^{m}(p_k-1)p_k^{e_k-1}.$$
因此，整个问题可以改写成：找出所有素数幂的组合，使得它们各自的 totient 贡献之积恰好等于 \(13!\)。
记
$$T=13!=2^{10}\cdot 3^5\cdot 5^2\cdot 7\cdot 11\cdot 13.$$
任何合法的 totient 贡献都必须整除 \(T\)。由于 \(T\) 的素因子结构很小，所有基于“枚举约数”的预处理都会很轻。特别地，\(T\) 的正约数个数为
$$\tau(T)=(10+1)(5+1)(2+1)(1+1)^3=1584,$$
所以最原始的候选空间从一开始就是有限的。
如果某个素数 \(p\) 整除 \(n\)，那么 \(\varphi(n)\) 中一定包含因子 \(p-1\)。因此必有
$$p\mid n \quad\Longrightarrow\quad p-1\mid T.$$
这说明解中的每个素因子都必须写成
$$p=d+1\qquad\text{其中 }d\mid T,$$
并且 \(p\) 本身还必须是素数。实现正是这样做的：先生成 \(T\) 的全部约数，再检查每个 \(d+1\) 是否为素数，从而得到完整的候选素数集合。
还有一个更强的限制。如果 \(p^e\mid n\) 且 \(e\ge 2\)，则
$$\varphi(p^e)=(p-1)p^{e-1}\mid T,$$
所以必然有 \(p^{e-1}\mid T\)。这意味着只有已经出现在 \(T\) 的素数，也就是 \(2,3,5,7,11,13\)，才可能以二次幂、三次幂等形式出现。任何更大的候选素数最多只能出现一次。
对一个固定的候选素数 \(p\)，可能的 totient 贡献是
$$\varphi(p)=p-1,\qquad \varphi(p^2)=(p-1)p,\qquad \varphi(p^3)=(p-1)p^2,\ \dots$$
也就是说，指数 \(e\) 的选择对应于贡献
$$c(p,e)=(p-1)p^{e-1},$$
而在 \(n\) 中加入的因子则是 \(p^e\)。算法并不会随意尝试整数，而是只尝试这些由素数幂产生的合法块，并且只有当该贡献能够整除当前剩余的 totient 预算时，才继续向下递归。
将候选素数按升序记为
$$q_0\lt q_1\lt \cdots \lt q_{m-1}.$$
定义 \(\mathcal{S}(r,i)\) 为：仅使用 \(q_i,q_{i+1},\dots,q_{m-1}\) 这些素数时，所有满足 totient 等于 \(r\) 的整数集合。则递归关系是
$$\mathcal{S}(1,i)=\{1\},$$
并且当 \(r\gt 1\) 时，先定义
$$E_j(r)=\{e\ge 1:(q_j-1)q_j^{e-1}\mid r\}.$$
于是
$$\mathcal{S}(r,i)=\bigcup_{j\ge i}\ \bigcup_{e\in E_j(r)} q_j^e\cdot \mathcal{S}\!\left(\frac{r}{(q_j-1)q_j^{e-1}},\,j+1\right).$$
这不仅仅是对代码的数学概括，它本身就是代码所遍历的搜索树。每个节点的状态由三部分组成：剩余的 totient 因子 \(r\)、还允许使用的最小素数下标 \(i\)、以及已经构造出的部分 \(n\)。
递归过程中始终保持下面的不变量：
$$\varphi(N)\cdot r=T,$$
其中 \(N\) 是当前已经选出的部分整数，\(r\) 是还未匹配掉的 totient 预算。每走一步，\(r\) 会除以一个合法贡献 \(c(p,e)\)，同时 \(N\) 乘上相应的 \(p^e\)，所以这个乘积保持不变。
第二个不变量是顺序。搜索一旦越过某个素数 \(q_j\)，之后就不会再回到更小的素数。由于整数的素因子分解是唯一的，每个有效解都只对应一条按素数递增的路径：每个不同素数恰好选择一次，并附带唯一的指数。因此这种“严格递增的素数顺序”天然消除了重复生成。
实现里会先用较小的目标 \(120\) 做校验，这个例子也很适合手算。此时满足 \(p-1\mid 120\) 的候选素数为
$$2,3,5,7,11,13,31,41,61.$$
其中一条分支先选 \(p=13\)。因为 \(\varphi(13)=12\)，所以剩余预算变成 \(120/12=10\)。接着同一条分支再选 \(p=11\)，它的贡献是 \(\varphi(11)=10\)。这时剩余预算降为 \(1\)，于是得到
$$n=13\cdot 11=143,$$
并且确实有
$$\varphi(143)=\varphi(11)\varphi(13)=10\cdot 12=120.$$
另一条分支可以先选 \(p=31\)，贡献 \(30\)，再选 \(p=5\)，贡献 \(4\)，得到
$$n=31\cdot 5=155,\qquad \varphi(155)=30\cdot 4=120.$$
真正的 \(13!\) 目标当然会有更大的搜索树，但数学机制完全相同，仍然依靠这些整除条件把大量无效分支提前剪掉。
C++、Python 和 Java 实现都会先分解 \(13!\)，生成它的全部约数，然后测试每个 \(d+1\) 是否为素数，从而得到完整的候选素数集合。这里使用的是对 64 位整数确定性的素性测试，因此这一阶段不会引入随机误判。
搜索状态记录三个量：剩余 totient 因子、接下来允许使用的最小素数下标，以及当前已经构成的候选整数 \(n\)。对每个候选素数 \(p\)，实现先从 \(p-1\) 开始，只要它还能整除剩余预算，就不断再乘一个 \(p\)。这样枚举到的正是
$$ (p-1),\ (p-1)p,\ (p-1)p^2,\dots $$
这些对应 \(p,p^2,p^3,\dots\) 的合法贡献。当剩余预算变成 \(1\) 时，当前累计出的整数就是一个完整解，会被保存下来。
由于解本身可能明显大于 \(13!\)，实现不会把候选值局限在普通 64 位有符号整数里，而是使用更宽的整数表示。
全部枚举结束后，解列表会被排序，并以防御性方式去重，然后取第 \(150000\) 个元素。C++ 版本还额外加入了多层校验：它会把 \(\varphi(n)=120\) 的递归结果与暴力枚举进行比较，检查主问题已知的最小解，对每个找到的候选重新计算 \(\varphi(n)\)，并验证多线程结果与单线程结果完全一致。
当启用多线程时，搜索会按照第一层的素数幂选择拆成若干种子任务，每个工作线程处理一个互不重叠的子树。数学上的枚举对象完全没有变化，变化的只是遍历顺序。Python 和 Java 版本则以串行方式执行同样的递归。
预处理很小。分解 \(13!\)、生成它的 \(1584\) 个约数，再测试对应的 \(d+1\) 是否为素数，相比后面的递归搜索几乎可以忽略。
主要成本是输出敏感的。若 \(B\) 表示访问过的递归分支数，\(M\) 表示最终找到的解的数量，那么枚举本身的成本是 \(O(B)\)，之后排序和归一化的成本是 \(O(M\log M)\)。\(B\) 没有一个简单的闭式公式，因为它取决于“整除测试到底成功多少次”。但有两个非常强的剪枝条件：
$$p-1\mid 13! \qquad\text{以及}\qquad (p-1)p^{e-1}\mid 13!.$$
每接受一个递归步骤，剩余预算至少会减半，因此递归深度并不大。内存消耗主要是存储 \(M\) 个解，再加上递归栈；在并行的 C++ 版本里，还要加上各个工作线程各自的输出缓冲区。
Нужно найти все положительные целые \(n\), для которых
$$\varphi(n)=13!,$$
затем отсортировать их по возрастанию и взять \(150000\)-й элемент этого упорядоченного списка. Это задача об обратной функции Эйлера: не вычислить \(\varphi(n)\) для данного \(n\), а восстановить все \(n\), чей totient равен фиксированному значению.
Это фиксированное значение равно
$$13!=6227020800=2^{10}\cdot 3^5\cdot 5^2\cdot 7\cdot 11\cdot 13.$$
Полный перебор по \(n\) бесполезен. Рабочий подход использует мультипликативность \(\varphi\), резко сужает множество допустимых простых делителей числа \(n\) и перебирает только точные разложения целевого totient.
Если
$$n=\prod_{k=1}^{m} p_k^{e_k},$$
то
$$\varphi(n)=\prod_{k=1}^{m}\varphi\!\left(p_k^{e_k}\right)=\prod_{k=1}^{m}(p_k-1)p_k^{e_k-1}.$$
Значит, задача сводится к поиску всех наборов простых степеней, чьи вклад в totient перемножается ровно в \(13!\).
Обозначим
$$T=13!=2^{10}\cdot 3^5\cdot 5^2\cdot 7\cdot 11\cdot 13.$$
Любой допустимый множитель totient обязан делить \(T\). Поскольку факторизация \(T\) мала, все предварительные вычисления на основе делителей тоже малы. В частности, число положительных делителей равно
$$\tau(T)=(10+1)(5+1)(2+1)(1+1)^3=1584.$$
То есть исходное пространство кандидатов конечно и довольно компактно.
Если \(p\mid n\), то внутри \(\varphi(n)\) обязательно присутствует множитель \(p-1\). Следовательно, необходимо
$$p\mid n \quad\Longrightarrow\quad p-1\mid T.$$
Значит, каждый простой делитель решения имеет вид
$$p=d+1\qquad\text{при }d\mid T,$$
и дополнительно сам \(p\) должен быть простым. Именно так и строится конечное множество кандидатов: перечисляются все делители \(T\), после чего проверяется простота чисел \(d+1\).
Есть еще более сильное наблюдение. Если \(p^e\mid n\) и \(e\ge 2\), то
$$\varphi(p^e)=(p-1)p^{e-1}\mid T,$$
а значит, \(p^{e-1}\mid T\). Поэтому только простые числа \(2,3,5,7,11,13\), уже входящие в факторизацию \(T\), могут появляться с показателем больше единицы. Любой больший кандидат может входить лишь в первой степени.
Для фиксированного допустимого простого \(p\) возможные вклады в totient таковы:
$$\varphi(p)=p-1,\qquad \varphi(p^2)=(p-1)p,\qquad \varphi(p^3)=(p-1)p^2,\ \dots$$
Выбор показателя \(e\) дает вклад
$$c(p,e)=(p-1)p^{e-1}$$
в целевое значение \(T\), а соответствующий множитель в самом \(n\) равен \(p^e\). Алгоритм не перебирает произвольные числа. Он рассматривает только такие блоки, порожденные простыми степенями, и только если выбранный вклад точно делит текущий остаток totient.
Упорядочим допустимые простые так:
$$q_0\lt q_1\lt \cdots \lt q_{m-1}.$$
Пусть \(\mathcal{S}(r,i)\) обозначает множество чисел, построенных только из \(q_i,q_{i+1},\dots,q_{m-1}\), чей totient равен \(r\). Тогда рекурсия имеет вид
$$\mathcal{S}(1,i)=\{1\},$$
а при \(r\gt 1\) введем
$$E_j(r)=\{e\ge 1:(q_j-1)q_j^{e-1}\mid r\}.$$
Тогда
$$\mathcal{S}(r,i)=\bigcup_{j\ge i}\ \bigcup_{e\in E_j(r)} q_j^e\cdot \mathcal{S}\!\left(\frac{r}{(q_j-1)q_j^{e-1}},\,j+1\right).$$
Это не просто красивая формула, а точное описание дерева поиска, которое обходят реализации. Состояние вершины состоит из оставшегося фактора totient, индекса первого еще допустимого простого и уже накопленного частичного значения \(n\).
Во время всей рекурсии сохраняется инвариант
$$\varphi(N)\cdot r=T,$$
где \(N\) — уже построенная часть кандидата, а \(r\) — оставшийся бюджет totient. Каждый шаг делит \(r\) на выбранный вклад \(c(p,e)\) и умножает \(N\) на \(p^e\), так что произведение остается постоянным.
Второй инвариант — порядок. Как только поиск проходит некоторый простой \(q_j\), он больше не возвращается к меньшим простым. Поскольку разложение числа на простые множители единственно, у каждого корректного решения есть ровно один возрастающий список различных простых и ровно один набор показателей. Поэтому каждое решение порождается ровно один раз.
Реализации проверяют себя на меньшей цели \(120\), и этот пример удобно разобрать вручную. Здесь допустимы все простые \(p\), для которых \(p-1\mid 120\):
$$2,3,5,7,11,13,31,41,61.$$
Одна ветвь сначала выбирает \(p=13\). Поскольку \(\varphi(13)=12\), остаток становится равным \(120/12=10\). Затем выбирается \(p=11\), чей вклад равен \(\varphi(11)=10\). Остаток падает до \(1\), и эта ветвь дает
$$n=13\cdot 11=143,$$
причем действительно
$$\varphi(143)=\varphi(11)\varphi(13)=10\cdot 12=120.$$
Другая ветвь берет \(p=31\) с вкладом \(30\), а затем \(p=5\) с вкладом \(4\), получая
$$n=31\cdot 5=155,\qquad \varphi(155)=30\cdot 4=120.$$
Для цели \(13!\) дерево поиска больше, но математический механизм полностью тот же, и те же проверки делимости отсекают большую часть ветвей.
Реализации на C++, Python и Java сначала факторизуют \(13!\), строят все его делители, а затем проверяют на простоту каждое число \(d+1\). Так получается полное множество допустимых простых. Используемый тест простоты детерминирован для 64-битных входов, поэтому на этом шаге нет вероятностной ошибки.
Состояние поиска хранит три величины: оставшийся множитель totient, индекс первого простого, который еще разрешено использовать, и текущее частичное значение \(n\). Для каждого кандидата \(p\) реализация начинает с вклада \(p-1\) и затем умножает его на \(p\) столько раз, сколько сохраняется делимость. Таким образом перебираются ровно вклады
$$ (p-1),\ (p-1)p,\ (p-1)p^2,\dots $$
которые соответствуют \(p,p^2,p^3,\dots\). Как только оставшийся множитель становится равным \(1\), накопленное число записывается как полное решение.
Поскольку решения могут быть заметно больше, чем \(13!\), для хранения кандидатов используются широкие целочисленные типы, а не предположение, что всегда хватит обычного 64-битного signed integer.
После завершения перебора список решений сортируется, защитно дедуплицируется и затем индексируется по позиции \(150000\). В версии на C++ есть дополнительные проверки: сравнение с brute force для малого случая \(\varphi(n)=120\), проверка известного первого решения основной задачи, повторное вычисление \(\varphi(n)\) для каждого найденного кандидата и сверка многопоточного результата с однопоточным.
При использовании нескольких потоков поиск разбивается по выбору простых степеней на первом уровне. Каждый поток обходит свой непересекающийся поддерев дерева рекурсии. С математической точки зрения перечисляется тот же самый набор; меняется только расписание обхода. Версии на Python и Java выполняют ту же рекурсивную логику последовательно.
Предварительная обработка мала. Факторизация \(13!\), построение его \(1584\) делителей и тестирование чисел \(d+1\) на простоту стоят очень мало по сравнению с собственно рекурсивным перебором.
Главная стоимость зависит от числа реально пройденных ветвей. Если \(B\) — количество посещенных рекурсивных ветвей, а \(M\) — количество найденных решений, то сам перебор требует \(O(B)\), после чего сортировка и нормализация стоят \(O(M\log M)\). Для \(B\) нет простой замкнутой формулы: все определяется тем, как часто проходят проверки делимости. Но два жестких фильтра радикально сужают дерево:
$$p-1\mid 13! \qquad\text{и}\qquad (p-1)p^{e-1}\mid 13!.$$
Глубина рекурсии остается умеренной, потому что каждый принятый шаг делит оставшийся бюджет как минимум на \(2\). Память равна \(O(M)\) для хранения решений плюс рекурсивный стек и, в многопоточной версии C++, локальные буферы результатов у рабочих потоков.
المطلوب هو إيجاد جميع الأعداد الصحيحة الموجبة \(n\) التي تحقق
$$\varphi(n)=13!,$$
ثم ترتيبها تصاعديًا وأخذ العنصر رقم \(150000\) من هذه القائمة المرتبة. هذه ليست مسألة من نوع "احسب \(\varphi(n)\) لعدد معلوم"، بل هي مسألة معكوس دالة أويلر: نعرف قيمة التوتينت ونريد استرجاع كل القيم الممكنة لـ \(n\) التي تعطي هذه القيمة.
القيمة الهدف هي
$$13!=6227020800=2^{10}\cdot 3^5\cdot 5^2\cdot 7\cdot 11\cdot 13.$$
الفحص المباشر لكل \(n\) غير عملي تمامًا. الطريق المناسب هو استغلال البنية الضربية للدالة \(\varphi\)، وتقييد مجموعة الأوليات التي يمكن أن تقسم \(n\)، ثم تعداد التفكيكات الدقيقة فقط التي تعطي \(13!\) بالضبط.
إذا كتبنا
$$n=\prod_{k=1}^{m} p_k^{e_k},$$
فإن صيغة أويلر تعطي
$$\varphi(n)=\prod_{k=1}^{m}\varphi\!\left(p_k^{e_k}\right)=\prod_{k=1}^{m}(p_k-1)p_k^{e_k-1}.$$
إذًا يمكن إعادة صياغة المسألة كلها هكذا: ابحث عن كل مجموعات قوى الأوليات التي يكون حاصل ضرب مساهماتها في التوتينت مساويًا تمامًا لـ \(13!\).
لنرمز إلى الهدف بـ
$$T=13!=2^{10}\cdot 3^5\cdot 5^2\cdot 7\cdot 11\cdot 13.$$
أي مساهمة صالحة في \(\varphi(n)\) لا بد أن تقسم \(T\). وبما أن تحليل \(T\) إلى عوامل أولية صغير، فإن كل الحسابات المسبقة المعتمدة على القواسم تكون صغيرة أيضًا. على وجه الخصوص فإن عدد قواسم \(T\) الموجبة هو
$$\tau(T)=(10+1)(5+1)(2+1)(1+1)^3=1584,$$
ولذلك فإن فضاء المرشحين الخام محدود منذ البداية.
إذا كان \(p\mid n\)، فإن العامل \(p-1\) يظهر بالضرورة داخل \(\varphi(n)\). لذلك يلزم أن
$$p\mid n \quad\Longrightarrow\quad p-1\mid T.$$
أي أن كل أولي يقسم حلًا محتملًا يجب أن يكون على الصورة
$$p=d+1\qquad\text{حيث }d\mid T,$$
مع شرط إضافي هو أن \(p\) نفسه أولي. لهذا السبب تبني التطبيقات مجموعة المرشحين بالطريقة نفسها تمامًا: تُحصى جميع قواسم \(T\)، ثم يُختبر كل عدد من الشكل \(d+1\) من حيث الأولية.
وهناك تقييد أدق من ذلك. إذا كان \(p^e\mid n\) مع \(e\ge 2\)، فحينئذ
$$\varphi(p^e)=(p-1)p^{e-1}\mid T,$$
ومن ثم لا بد أن \(p^{e-1}\mid T\). وهذا يعني أن الأوليات الوحيدة التي يمكن أن تظهر بأس أكبر من \(1\) هي تلك التي تقسم \(T\) أصلًا، أي \(2,3,5,7,11,13\). أما أي أولي مرشح أكبر من ذلك فلا يمكن أن يظهر إلا بالقوة الأولى.
بالنسبة إلى أولي مسموح ثابت \(p\)، فإن المساهمات الممكنة في التوتينت هي
$$\varphi(p)=p-1,\qquad \varphi(p^2)=(p-1)p,\qquad \varphi(p^3)=(p-1)p^2,\ \dots$$
اختيار الأس \(e\) يعني أننا نأخذ المساهمة
$$c(p,e)=(p-1)p^{e-1}$$
من الهدف \(T\)، بينما العامل الموافق في \(n\) هو \(p^e\). الخوارزمية لا تجرب أعدادًا عشوائية، بل تجرب فقط هذه اللبنات الناتجة عن قوى الأوليات، ولا تتابع الفرع إلا إذا كانت هذه المساهمة تقسم الميزانية المتبقية من التوتينت قسمة تامة.
لنرتب الأوليات المسموح بها على الصورة
$$q_0\lt q_1\lt \cdots \lt q_{m-1}.$$
ولتكن \(\mathcal{S}(r,i)\) هي مجموعة الأعداد المبنية فقط من \(q_i,q_{i+1},\dots,q_{m-1}\) والتي يكون توتينتها مساويًا لـ \(r\). عندئذ تكون العلاقة التكرارية
$$\mathcal{S}(1,i)=\{1\},$$
ولكل \(r\gt 1\)، نعرّف أولًا
$$E_j(r)=\{e\ge 1:(q_j-1)q_j^{e-1}\mid r\}.$$
وعندئذ
$$\mathcal{S}(r,i)=\bigcup_{j\ge i}\ \bigcup_{e\in E_j(r)} q_j^e\cdot \mathcal{S}\!\left(\frac{r}{(q_j-1)q_j^{e-1}},\,j+1\right).$$
هذه ليست مجرد صياغة نظرية للكود، بل هي الشجرة نفسها التي يستكشفها التنفيذ. حالة البحث تتكون من العامل المتبقي من التوتينت \(r\)، ومن أول فهرس أولي ما زال مسموحًا به \(i\)، ومن القيمة الجزئية لـ \(n\) التي تم بناؤها حتى تلك اللحظة.
أثناء الاستكشاف كله يبقى الثابت التالي صحيحًا:
$$\varphi(N)\cdot r=T,$$
حيث \(N\) هو الجزء الذي بُني من العدد حتى الآن و\(r\) هو ما بقي من ميزانية التوتينت. في كل خطوة يُقسم \(r\) على مساهمة صالحة \(c(p,e)\)، ويُضرب \(N\) في \(p^e\)، ولذلك يبقى حاصل الضرب ثابتًا.
وهناك ثابت ثانٍ يتعلق بالترتيب. بعد أن يتجاوز البحث أوليًا معينًا \(q_j\)، فإنه لا يعود أبدًا إلى أوليات أصغر منه. وبما أن تحليل العدد إلى عوامل أولية فريد، فإن كل حل صحيح يملك قائمة وحيدة متزايدة من الأوليات المختلفة مع أس وحيد مرتبط بكل واحد منها. لهذا السبب يُنتج كل حل مرة واحدة فقط.
التنفيذات تتحقق أولًا من صحة المنهج على الهدف الأصغر \(120\)، وهذا المثال مناسب جدًا لشرح الفكرة. في هذه الحالة تكون الأوليات المسموح بها هي جميع \(p\) التي تحقق \(p-1\mid 120\)، أي
$$2,3,5,7,11,13,31,41,61.$$
أحد الفروع يختار أولًا \(p=13\). بما أن \(\varphi(13)=12\)، تصبح الميزانية المتبقية \(120/12=10\). بعد ذلك يختار الفرع نفسه \(p=11\)، ومساهمته هي \(\varphi(11)=10\). الآن يصل الباقي إلى \(1\)، ومن ثم ينتج هذا المسار
$$n=13\cdot 11=143,$$
وفعلًا لدينا
$$\varphi(143)=\varphi(11)\varphi(13)=10\cdot 12=120.$$
وفرع آخر يختار \(p=31\) بمساهمة \(30\)، ثم \(p=5\) بمساهمة \(4\)، ليعطي
$$n=31\cdot 5=155,\qquad \varphi(155)=30\cdot 4=120.$$
بالنسبة إلى الهدف \(13!\) تصبح الشجرة أكبر، لكن النمط الرياضي نفسه لا يتغير، والاختبارات القائمة على القسمة هي التي تزيل معظم الفروع غير الممكنة.
تبدأ تطبيقات C++ وPython وJava بتحليل \(13!\) إلى عوامله الأولية، ثم توليد جميع قواسمه، ثم اختبار كل قيمة من الشكل \(d+1\) من حيث الأولية. بهذه الطريقة نحصل على المجموعة الكاملة من الأوليات المرشحة. اختبار الأولية المستخدم حتمي على مجال أعداد 64-بت، لذلك لا توجد هنا مخاطرة احتمالية.
حالة البحث تخزن ثلاث قيم: العامل المتبقي من التوتينت، وفهرس أول أولي ما زال يمكن استخدامه، والقيمة الجزئية لـ \(n\). لكل أولي مرشح \(p\)، يبدأ التنفيذ بالمساهمة \(p-1\)، ثم يواصل ضربها في \(p\) ما دامت القسمة على الميزانية المتبقية ممكنة. وهكذا تُجرب بالضبط المساهمات
$$ (p-1),\ (p-1)p,\ (p-1)p^2,\dots $$
التي تقابل العوامل \(p,p^2,p^3,\dots\). وعندما تصل الميزانية المتبقية إلى \(1\)، تكون القيمة المتراكمة عددًا كاملًا من الحلول فيُسجَّل.
ولأن القيم الناتجة لـ \(n\) قد تكون أكبر بكثير من \(13!\)، فإن التنفيذات تستخدم أنواع أعداد صحيحة واسعة بدل الافتراض أن 64-بت الموقعة تكفي دائمًا.
بعد انتهاء التعداد تُرتب قائمة الحلول، ويُزال التكرار منها احتياطيًا، ثم يُؤخذ العنصر رقم \(150000\). ويضيف تنفيذ C++ طبقات تحقق إضافية: فهو يقارن البحث التكراري مع brute force في الحالة الصغيرة \(\varphi(n)=120\)، ويفحص أول حل معروف للمسألة الرئيسية، ويعيد حساب \(\varphi(n)\) لكل مرشح تم العثور عليه، ويتأكد من تطابق المخرجات بين التشغيل متعدد الخيوط والتشغيل أحادي الخيط.
وعندما يُستخدم أكثر من خيط واحد، تُقسَّم الشجرة بحسب اختيارات القوة الأولية في المستوى الأول. كل عامل يعالج تحت شجرة منفصلة من نفس العلاقة التكرارية. المجموعة الرياضية المحصاة لا تتغير إطلاقًا؛ الذي يتغير فقط هو جدول التنفيذ. نسختا Python وJava تنفذان المنطق نفسه بشكل تسلسلي.
المعالجة المسبقة صغيرة. تحليل \(13!\) وتوليد قواسمه الـ \(1584\) واختبار أولية القيم \(d+1\) خطوات زهيدة مقارنة بالبحث التكراري نفسه.
الكلفة الأساسية تعتمد على عدد الفروع التي يجري الوصول إليها فعليًا. إذا رمزنا بـ \(B\) إلى عدد الفروع التكرارية المزارة، وبـ \(M\) إلى عدد الحلول المكتشفة، فإن التعداد نفسه يكلف \(O(B)\)، ثم تأتي كلفة \(O(M\log M)\) لفرز النتائج وتوحيدها. لا توجد صيغة مغلقة بسيطة لـ \(B\)، لأن ذلك يعتمد على عدد مرات نجاح اختبارات القسمة. لكن هناك مرشحين قويين جدًا يقلصان الشجرة:
$$p-1\mid 13! \qquad\text{و}\qquad (p-1)p^{e-1}\mid 13!.$$
عمق التكرار محدود لأن كل خطوة مقبولة تقسم الميزانية المتبقية على الأقل على \(2\). واستهلاك الذاكرة هو \(O(M)\) لتخزين الحلول، إضافة إلى مكدس التكرار، ومع النسخة المتوازية في C++ توجد كذلك مخازن محلية خاصة بكل عامل.