For a given limit \(L\), define \(S(L)\) as the sum of all integers \(n\le L\) such that Euler's totient \(\varphi(n)\) is 5-smooth, meaning that every prime factor of \(\varphi(n)\) belongs to \(\{2,3,5\}\). The target value is \(S(10^{12}) \bmod 2^{32}\), so a direct scan of all \(n\le 10^{12}\) is completely infeasible.
The key observation is that the condition on \(\varphi(n)\) forces a very rigid prime factorization for \(n\). Once that structure is identified, the sum can be reorganized into a much smaller search over 5-smooth numbers and a recursively generated family of admissible prime products.
Write
$$n=2^a3^b5^c\prod_{i=1}^r p_i^{e_i},\qquad p_i>5.$$
Euler's product formula gives
$$\varphi(n)=\varphi(2^a)\varphi(3^b)\varphi(5^c)\prod_{i=1}^r p_i^{e_i-1}(p_i-1).$$
The factors coming from \(2,3,5\) are always 5-smooth:
$$\varphi(2^a)\in\{1,2,4,8,\dots\},\qquad \varphi(3^b)\in\{1,2,6,18,\dots\},\qquad \varphi(5^c)\in\{1,4,20,100,\dots\}.$$
So every possible obstruction comes from primes \(p_i>5\).
If some prime \(p_i>5\) appears with exponent \(e_i\ge 2\), then the factor \(p_i^{e_i-1}\) divides \(\varphi(n)\). That would force a prime factor larger than \(5\) into \(\varphi(n)\), which is impossible. Therefore every prime \(p>5\) may appear in \(n\) at most once.
Moreover, when \(p>5\) does appear, the factor \(p-1\) divides \(\varphi(n)\). Hence \(p-1\) itself must be 5-smooth. This proves that every valid number has the shape
$$n=hq,$$
where \(h=2^a3^b5^c\) is a 5-smooth number and \(q\) is a squarefree product of distinct primes \(p>5\) satisfying
$$p-1=2^\alpha 3^\beta 5^\gamma,\qquad \alpha,\beta,\gamma\ge 0.$$
The converse is also true. If \(h\) is 5-smooth and \(q=\prod p\) is a squarefree product of distinct primes with \(p-1\) 5-smooth, then \(h\) and \(q\) are coprime, so
$$\varphi(hq)=\varphi(h)\prod_{p\mid q}(p-1),$$
which is again 5-smooth. Thus the decomposition is exact.
Let
$$\mathcal{H}(x)=\left\{2^a3^b5^c\le x:\ a,b,c\ge 0\right\}$$
be the set of 5-smooth numbers up to \(x\), and define the prefix-sum function
$$A(x)=\sum_{h\in\mathcal{H}(x)} h.$$
Also define the admissible primes
$$\mathcal{P}(L)=\left\{p\le L:\ p>5,\ p\text{ prime},\ p-1\in\mathcal{H}(L)\right\}.$$
Every valid \(n\le L\) is uniquely obtained by choosing a squarefree product \(q\) of distinct primes from \(\mathcal{P}(L)\), then choosing a 5-smooth multiplier \(h\le L/q\). Therefore
$$S(L)=\sum_{q\in\mathcal{Q}(L)} \sum_{\substack{h\in\mathcal{H}(L)\\ h\le L/q}} qh,$$
where \(\mathcal{Q}(L)\) is the set of squarefree products \(q\le L\) built from distinct primes in \(\mathcal{P}(L)\), including the empty product \(q=1\).
Pulling \(q\) outside the inner sum gives the main formula
$$\boxed{S(L)=\sum_{q\in\mathcal{Q}(L)} q\,A\left(\left\lfloor\frac{L}{q}\right\rfloor\right)\pmod{2^{32}}.}$$
The previous step shows that admissible primes are exactly the primes of the form
$$p=h+1,\qquad h\in\mathcal{H}(L).$$
So instead of searching through all primes up to \(L\), we only generate 5-smooth numbers and test \(h+1\) for primality. This is the decisive reduction: the 5-smooth list is tiny compared with the interval \([1,L]\).
After sorting the 5-smooth numbers, the values \(A(x)\) can be answered by binary search and prefix sums. The remaining task is then to enumerate all feasible subset products \(q\in\mathcal{Q}(L)\), which is done naturally by depth-first search with the pruning rule \(q p\le L\).
For \(L=100\), the 5-smooth numbers are
$$\{1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36,40,45,48,50,54,60,64,72,75,80,81,90,96,100\}.$$
The admissible primes \(p=h+1\) are
$$\{7,11,13,17,19,31,37,41,61,73,97\}.$$
Among their squarefree products, the only ones not exceeding \(100\) are
$$1,\ 7,\ 11,\ 13,\ 17,\ 19,\ 31,\ 37,\ 41,\ 61,\ 73,\ 97,\ 77,\ 91.$$
The needed prefix sums are
$$A(100)=1258,\quad A(14)=60,\quad A(9)=38,\quad A(7)=21,\quad A(5)=15,\quad A(3)=6,\quad A(2)=3,\quad A(1)=1.$$
So the contributions are
$$\begin{aligned} q=1&:&&1\cdot A(100)=1258,\\ q=7&:&&7\cdot A(14)=420,\\ q=11&:&&11\cdot A(9)=418,\\ q=13&:&&13\cdot A(7)=273,\\ q=17&:&&17\cdot A(5)=255,\\ q=19&:&&19\cdot A(5)=285,\\ q=31&:&&31\cdot A(3)=186,\\ q=37&:&&37\cdot A(2)=111,\\ q=41&:&&41\cdot A(2)=123,\\ q=61&:&&61\cdot A(1)=61,\\ q=73&:&&73\cdot A(1)=73,\\ q=97&:&&97\cdot A(1)=97,\\ q=77&:&&77\cdot A(1)=77,\\ q=91&:&&91\cdot A(1)=91. \end{aligned}$$
Adding them gives
$$1258+420+418+273+255+285+186+111+123+61+73+97+77+91=3728,$$
which matches the checkpoint used by the implementation.
The C++, Python, and Java implementations all use the same algorithm.
First, they generate every number of the form \(2^a3^b5^c\le L\) by nested multiplicative loops. The resulting list is sorted, duplicates are removed, and a prefix-sum array modulo \(2^{32}\) is built so that \(A(x)\) can be queried quickly.
Next, for each 5-smooth number \(h\), the implementation tests whether \(h+1\) is prime. It uses fast modular exponentiation and a Miller-Rabin primality test with fixed small bases, which is sufficient for the numeric range of this problem. Every prime \(h+1>5\) is stored as an admissible prime.
Finally, a depth-first search enumerates subset products \(q\) of admissible primes in increasing order. At each recursive state it adds
$$q\,A\left(\left\lfloor\frac{L}{q}\right\rfloor\right)\pmod{2^{32}}$$
to the answer, then tries to append later admissible primes as long as the product stays at most \(L\). Because the search only moves forward through the sorted prime list, each squarefree subset is visited exactly once.
Let \(H=|\mathcal{H}(L)|\), let \(P=|\mathcal{P}(L)|\), and let \(T=|\mathcal{Q}(L)|\), the number of subset products actually visited by the depth-first search. Generating the 5-smooth list takes \(O(H)\) multiplicative steps, while sorting and deduplicating costs \(O(H\log H)\). Building prefix sums is linear in \(H\).
Primality is tested only on the \(H\) candidates \(h+1\), not on every integer up to \(L\). With a fixed-base Miller-Rabin test, this contributes roughly \(O(H\log L)\) modular-arithmetic work. The depth-first search visits each feasible subset product once and performs one binary search on the 5-smooth list per node, so the summation phase costs \(O(T\log H)\).
Thus the algorithm is dominated by the sizes of the 5-smooth list and the feasible subset-product tree, both of which are tiny compared with \(L\) itself. Memory usage is \(O(H+P)\), plus recursion depth proportional to the number of primes currently selected.
Für eine gegebene Grenze \(L\) sei \(S(L)\) die Summe aller Zahlen \(n\le L\), für die Eulers Phi-Funktion \(\varphi(n)\) 5-glatt ist, also nur die Primfaktoren \(\{2,3,5\}\) besitzt. Gesucht ist \(S(10^{12}) \bmod 2^{32}\). Ein direkter Test aller \(n\le 10^{12}\) ist unmöglich, daher braucht man eine strukturelle Beschreibung der zulässigen Zahlen.
Der entscheidende Punkt ist, dass die Bedingung an \(\varphi(n)\) die Primfaktorzerlegung von \(n\) stark einschränkt. Dadurch lässt sich die gesuchte Summe in eine kleine Menge von 5-glatten Zahlen und eine rekursiv erzeugte Menge zulässiger Primzahlprodukte zerlegen.
Schreibe
$$n=2^a3^b5^c\prod_{i=1}^r p_i^{e_i},\qquad p_i>5.$$
Mit der Produktformel für die Phi-Funktion gilt
$$\varphi(n)=\varphi(2^a)\varphi(3^b)\varphi(5^c)\prod_{i=1}^r p_i^{e_i-1}(p_i-1).$$
Die Faktoren zu \(2,3,5\) sind immer 5-glatt:
$$\varphi(2^a)\in\{1,2,4,8,\dots\},\qquad \varphi(3^b)\in\{1,2,6,18,\dots\},\qquad \varphi(5^c)\in\{1,4,20,100,\dots\}.$$
Alle echten Einschränkungen kommen also nur von Primzahlen \(p_i>5\).
Tritt eine Primzahl \(p_i>5\) mit Exponent \(e_i\ge 2\) auf, dann teilt \(p_i^{e_i-1}\) die Zahl \(\varphi(n)\). Das würde einen Primfaktor größer als \(5\) in \(\varphi(n)\) erzwingen und ist daher unmöglich. Also darf jede Primzahl \(p>5\) in \(n\) höchstens einmal vorkommen.
Außerdem teilt für jedes solche \(p\) der Ausdruck \(p-1\) die Phi-Funktion. Deshalb muss bereits \(p-1\) selbst 5-glatt sein. Damit hat jede gültige Zahl die Form
$$n=hq,$$
wobei \(h=2^a3^b5^c\) eine 5-glatte Zahl ist und \(q\) ein quadratfreies Produkt verschiedener Primzahlen \(p>5\) mit
$$p-1=2^\alpha 3^\beta 5^\gamma,\qquad \alpha,\beta,\gamma\ge 0$$
darstellt.
Die Umkehrung gilt ebenfalls. Ist \(h\) 5-glatt und \(q=\prod p\) ein quadratfreies Produkt verschiedener Primzahlen mit 5-glattem \(p-1\), dann sind \(h\) und \(q\) teilerfremd, also
$$\varphi(hq)=\varphi(h)\prod_{p\mid q}(p-1),$$
und damit wieder 5-glatt. Die Charakterisierung ist also exakt.
Definiere
$$\mathcal{H}(x)=\left\{2^a3^b5^c\le x:\ a,b,c\ge 0\right\}$$
als Menge der 5-glatten Zahlen bis \(x\), und weiter die Präfixsumme
$$A(x)=\sum_{h\in\mathcal{H}(x)} h.$$
Außerdem sei
$$\mathcal{P}(L)=\left\{p\le L:\ p>5,\ p\text{ prime},\ p-1\in\mathcal{H}(L)\right\}$$
die Menge der zulässigen großen Primzahlen.
Jede gültige Zahl \(n\le L\) entsteht eindeutig durch die Wahl eines quadratfreien Produkts \(q\) aus verschiedenen Primzahlen aus \(\mathcal{P}(L)\) und einer 5-glatten Zahl \(h\le L/q\). Daher gilt
$$S(L)=\sum_{q\in\mathcal{Q}(L)} \sum_{\substack{h\in\mathcal{H}(L)\\ h\le L/q}} qh,$$
wobei \(\mathcal{Q}(L)\) die Menge aller quadratfreien Produkte \(q\le L\) aus verschiedenen Primzahlen aus \(\mathcal{P}(L)\) einschließlich des leeren Produkts \(q=1\) ist.
Damit folgt die zentrale Formel
$$\boxed{S(L)=\sum_{q\in\mathcal{Q}(L)} q\,A\left(\left\lfloor\frac{L}{q}\right\rfloor\right)\pmod{2^{32}}.}$$
Die vorherige Beschreibung zeigt: Zulässige Primzahlen sind genau die Primzahlen der Form
$$p=h+1,\qquad h\in\mathcal{H}(L).$$
Man muss also nicht alle Primzahlen bis \(L\) durchsuchen, sondern nur jede 5-glatte Zahl \(h\) erzeugen und \(h+1\) auf Primzahleigenschaft testen. Genau diese Reduktion macht das Problem handhabbar.
Nach dem Sortieren der 5-glatten Zahlen lassen sich die Werte \(A(x)\) per Binärsuche und Präfixsummen schnell bestimmen. Danach bleibt nur noch, alle zulässigen Teilmengenprodukte \(q\in\mathcal{Q}(L)\) per Tiefensuche zu erzeugen und Zweige mit \(qp>L\) sofort abzuschneiden.
Für \(L=100\) sind die 5-glatten Zahlen
$$\{1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36,40,45,48,50,54,60,64,72,75,80,81,90,96,100\}.$$
Die zulässigen Primzahlen \(p=h+1\) sind
$$\{7,11,13,17,19,31,37,41,61,73,97\}.$$
Unter ihren quadratfreien Produkten bleiben höchstens \(100\) genau die Werte
$$1,\ 7,\ 11,\ 13,\ 17,\ 19,\ 31,\ 37,\ 41,\ 61,\ 73,\ 97,\ 77,\ 91.$$
Die benötigten Präfixsummen lauten
$$A(100)=1258,\quad A(14)=60,\quad A(9)=38,\quad A(7)=21,\quad A(5)=15,\quad A(3)=6,\quad A(2)=3,\quad A(1)=1.$$
Damit ergeben sich die Beiträge
$$\begin{aligned} q=1&:&&1\cdot A(100)=1258,\\ q=7&:&&7\cdot A(14)=420,\\ q=11&:&&11\cdot A(9)=418,\\ q=13&:&&13\cdot A(7)=273,\\ q=17&:&&17\cdot A(5)=255,\\ q=19&:&&19\cdot A(5)=285,\\ q=31&:&&31\cdot A(3)=186,\\ q=37&:&&37\cdot A(2)=111,\\ q=41&:&&41\cdot A(2)=123,\\ q=61&:&&61\cdot A(1)=61,\\ q=73&:&&73\cdot A(1)=73,\\ q=97&:&&97\cdot A(1)=97,\\ q=77&:&&77\cdot A(1)=77,\\ q=91&:&&91\cdot A(1)=91. \end{aligned}$$
Die Summe ist
$$1258+420+418+273+255+285+186+111+123+61+73+97+77+91=3728,$$
genau der Kontrollwert der Implementierung.
Die C++-, Python- und Java-Implementierungen verwenden dieselbe Pipeline.
Zuerst erzeugen sie mit drei verschachtelten Multiplikationsschleifen alle Zahlen der Form \(2^a3^b5^c\le L\). Diese Liste wird sortiert, dedupliziert und anschließend zu einer Präfixsummenliste modulo \(2^{32}\) verarbeitet, damit sich \(A(x)\) schnell per Binärsuche abfragen lässt.
Dann wird für jede 5-glatte Zahl \(h\) geprüft, ob \(h+1\) prim ist. Dazu werden schnelle modulare Exponentiation und ein Miller-Rabin-Primzahltest mit festen kleinen Basen verwendet; für den Zahlenbereich dieser Aufgabe reicht das aus. Jede Primzahl \(h+1>5\) wird als zulässige Primzahl gespeichert.
Zum Schluss erzeugt eine Tiefensuche alle Teilmengenprodukte \(q\) der zulässigen Primzahlen in aufsteigender Reihenfolge. In jedem Rekursionszustand wird
$$q\,A\left(\left\lfloor\frac{L}{q}\right\rfloor\right)\pmod{2^{32}}$$
zum Ergebnis addiert. Danach versucht der Code, spätere Primzahlen anzuhängen, solange das Produkt höchstens \(L\) bleibt. Weil die Suche nur nach vorne durch die sortierte Primzahlliste läuft, wird jede quadratfreie Teilmenge genau einmal besucht.
Sei \(H=|\mathcal{H}(L)|\), \(P=|\mathcal{P}(L)|\) und \(T=|\mathcal{Q}(L)|\), also die Zahl der tatsächlich besuchten Teilmengenprodukte. Das Erzeugen der 5-glatten Zahlen benötigt \(O(H)\) Multiplikationsschritte; Sortieren und Deduplizieren kosten \(O(H\log H)\). Die Präfixsummen werden in \(O(H)\) aufgebaut.
Primzahltests werden nur auf den \(H\) Kandidaten \(h+1\) ausgeführt und nicht auf allen ganzen Zahlen bis \(L\). Mit einem Miller-Rabin-Test mit festen Basen ergibt sich dafür grob \(O(H\log L)\) Aufwand in modularer Arithmetik. Die Tiefensuche besucht jedes zulässige Teilmengenprodukt genau einmal und führt pro Knoten eine Binärsuche in der 5-glatten Liste aus, also kostet die Summationsphase \(O(T\log H)\).
Damit wird die Laufzeit nicht von \(L\) selbst bestimmt, sondern von den viel kleineren Mengen 5-glatter Zahlen und zulässiger Teilmengenprodukte. Der Speicherbedarf beträgt \(O(H+P)\), zuzüglich Rekursionstiefe entsprechend der aktuell gewählten Primzahlen.
Verilen bir \(L\) sınırı için \(S(L)\), \(\varphi(n)\) değeri 5-smooth olan, yani asal çarpanları yalnızca \(\{2,3,5\}\) kümesinden gelen tüm \(n\le L\) sayılarının toplamı olarak tanımlanır. Amaç \(S(10^{12}) \bmod 2^{32}\) değerini bulmaktır. \(10^{12}\) seviyesinde tüm sayıları tek tek denemek mümkün olmadığı için, çözüm önce uygun sayıların yapısını çıkarır.
Ana gözlem şudur: \(\varphi(n)\)'nin 5-smooth olması, \(n\)'nin asal çarpanlarına çok güçlü kısıtlar getirir. Bu yapı netleşince problem, küçük bir 5-smooth sayı listesi ile uygun asal altküme çarpımlarını toplamaya indirgenir.
Şöyle yazalım:
$$n=2^a3^b5^c\prod_{i=1}^r p_i^{e_i},\qquad p_i>5.$$
Euler çarpım formülü ile
$$\varphi(n)=\varphi(2^a)\varphi(3^b)\varphi(5^c)\prod_{i=1}^r p_i^{e_i-1}(p_i-1)$$
elde edilir. \(2,3,5\)'ten gelen parçalar zaten her zaman 5-smooth'tur:
$$\varphi(2^a)\in\{1,2,4,8,\dots\},\qquad \varphi(3^b)\in\{1,2,6,18,\dots\},\qquad \varphi(5^c)\in\{1,4,20,100,\dots\}.$$
Dolayısıyla gerçek kısıt, yalnızca \(p_i>5\) olan asallardan gelir.
Eğer \(p_i>5\) asalının üssü \(e_i\ge 2\) ise, \(\varphi(n)\) içinde \(p_i^{e_i-1}\) çarpanı bulunur. Bu da \(5\)'ten büyük bir asalın \(\varphi(n)\)'yi bölmesi demektir ve 5-smooth koşulunu bozar. O halde \(p>5\) olan her asal, \(n\)'de en fazla bir kez yer alabilir.
Ayrıca böyle bir asal \(n\)'yi bölüyorsa, \(p-1\) de \(\varphi(n)\)'yi böler. Bu yüzden \(p-1\)'in kendisi 5-smooth olmak zorundadır. Sonuç olarak her geçerli sayı
$$n=hq$$
şeklindedir; burada \(h=2^a3^b5^c\) bir 5-smooth sayıdır ve \(q\),
$$p-1=2^\alpha 3^\beta 5^\gamma,\qquad \alpha,\beta,\gamma\ge 0$$
koşulunu sağlayan, \(5\)'ten büyük farklı asalların karefree çarpımıdır.
Tersi de doğrudur. \(h\) 5-smooth ve \(q=\prod p\) böyle asalların karefree çarpımı ise, \(h\) ile \(q\) aralarında asaldır. Bu nedenle
$$\varphi(hq)=\varphi(h)\prod_{p\mid q}(p-1)$$
yeniden 5-smooth olur. Yani elde edilen karakterizasyon tamdır.
Şunu tanımlayalım:
$$\mathcal{H}(x)=\left\{2^a3^b5^c\le x:\ a,b,c\ge 0\right\}$$
ve buna ait önek toplamı
$$A(x)=\sum_{h\in\mathcal{H}(x)} h.$$
Ayrıca uygun büyük asallar kümesi
$$\mathcal{P}(L)=\left\{p\le L:\ p>5,\ p\text{ prime},\ p-1\in\mathcal{H}(L)\right\}$$
olsun.
Her geçerli \(n\le L\), \(\mathcal{P}(L)\) içinden seçilen farklı asalların karefree bir çarpımı \(q\) ve \(h\le L/q\) koşulunu sağlayan bir 5-smooth sayı \(h\) ile tekil olarak elde edilir. Bu yüzden
$$S(L)=\sum_{q\in\mathcal{Q}(L)} \sum_{\substack{h\in\mathcal{H}(L)\\ h\le L/q}} qh,$$
burada \(\mathcal{Q}(L)\), \(\mathcal{P}(L)\) içindeki farklı asallardan kurulan ve \(L\)'yi aşmayan tüm karefree çarpımlar kümesidir; boş çarpım \(q=1\) de buna dahildir.
Böylece temel formül elde edilir:
$$\boxed{S(L)=\sum_{q\in\mathcal{Q}(L)} q\,A\left(\left\lfloor\frac{L}{q}\right\rfloor\right)\pmod{2^{32}}.}$$
Yukarıdaki tanım, uygun asalların tam olarak
$$p=h+1,\qquad h\in\mathcal{H}(L)$$
biçimindeki asallar olduğunu söyler. Yani \(1\) ile \(L\) arasındaki tüm asalları taramak yerine, yalnızca 5-smooth sayıları üretip \(h+1\)'i asal mı diye test etmek yeterlidir. Asıl hız kazancı burada gelir.
5-smooth listesi sıralandıktan sonra \(A(x)\) değerleri ikili arama ve önek toplamlarla hızlıca bulunur. Geriye, \(q p\le L\) budamasıyla tüm uygun altküme çarpımlarını derinlik öncelikli aramayla gezmek kalır.
\(L=100\) için 5-smooth sayılar
$$\{1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36,40,45,48,50,54,60,64,72,75,80,81,90,96,100\}$$
olur. Uygun asallar ise
$$\{7,11,13,17,19,31,37,41,61,73,97\}.$$
Bunların \(100\)'ü aşmayan karefree çarpımları yalnızca
$$1,\ 7,\ 11,\ 13,\ 17,\ 19,\ 31,\ 37,\ 41,\ 61,\ 73,\ 97,\ 77,\ 91$$
değerleridir.
Gereken önek toplamlar şunlardır:
$$A(100)=1258,\quad A(14)=60,\quad A(9)=38,\quad A(7)=21,\quad A(5)=15,\quad A(3)=6,\quad A(2)=3,\quad A(1)=1.$$
Dolayısıyla katkılar
$$\begin{aligned} q=1&:&&1\cdot A(100)=1258,\\ q=7&:&&7\cdot A(14)=420,\\ q=11&:&&11\cdot A(9)=418,\\ q=13&:&&13\cdot A(7)=273,\\ q=17&:&&17\cdot A(5)=255,\\ q=19&:&&19\cdot A(5)=285,\\ q=31&:&&31\cdot A(3)=186,\\ q=37&:&&37\cdot A(2)=111,\\ q=41&:&&41\cdot A(2)=123,\\ q=61&:&&61\cdot A(1)=61,\\ q=73&:&&73\cdot A(1)=73,\\ q=97&:&&97\cdot A(1)=97,\\ q=77&:&&77\cdot A(1)=77,\\ q=91&:&&91\cdot A(1)=91. \end{aligned}$$
Toplam
$$1258+420+418+273+255+285+186+111+123+61+73+97+77+91=3728$$
olur; bu da uygulamanın kontrol değeriyle aynıdır.
C++, Python ve Java implementasyonları aynı algoritmik akışı izler.
Önce iç içe üç çarpma döngüsüyle \(2^a3^b5^c\le L\) biçimindeki tüm sayılar üretilir. Bu liste sıralanır, tekrarlar silinir ve \(2^{32}\) modunda önek toplam dizisi hazırlanır; böylece \(A(x)\) hızlıca sorgulanabilir.
Ardından her 5-smooth sayı \(h\) için \(h+1\)'in asal olup olmadığı test edilir. Bunun için hızlı modüler üs alma ve sabit küçük tabanlarla çalışan bir Miller-Rabin asal testi kullanılır; problemdeki sayı aralığı için bu yeterlidir. \(h+1>5\) olan her asal, uygun asal listesine eklenir.
Son adımda derinlik öncelikli arama, uygun asalların altküme çarpımlarını artan sırayla gezer. Her durumda
$$q\,A\left(\left\lfloor\frac{L}{q}\right\rfloor\right)\pmod{2^{32}}$$
cevaba eklenir. Daha sonra yalnızca ürünü \(L\)'yi aşmayan sonraki asallar eklenerek dallar genişletilir. Arama listede hep ileri doğru gittiği için her karefree altküme tam olarak bir kez sayılır.
\(H=|\mathcal{H}(L)|\), \(P=|\mathcal{P}(L)|\) ve \(T=|\mathcal{Q}(L)|\) olsun. 5-smooth listeyi üretmek \(O(H)\) çarpma adımı gerektirir; sıralama ve tekrarsızlaştırma maliyeti \(O(H\log H)\)'dir. Önek toplamlar \(O(H)\) zamanda kurulur.
Asallık testi yalnızca \(H\) adet \(h+1\) adayına uygulanır; \(1\) ile \(L\) arasındaki tüm sayılar denenmez. Sabit tabanlı Miller-Rabin ile bu bölüm yaklaşık \(O(H\log L)\) modüler aritmetik işi yapar. Derinlik öncelikli arama, her uygun altküme çarpımını bir kez ziyaret eder ve düğüm başına 5-smooth listesinde bir ikili arama yapar; bu nedenle toplama aşaması \(O(T\log H)\) zaman alır.
Böylece yöntem \(L\)'nin büyüklüğüne değil, çok daha küçük olan 5-smooth liste boyutuna ve mümkün altküme çarpımlarının sayısına bağlıdır. Bellek kullanımı \(O(H+P)\), ek olarak da seçili asal sayısı kadar özyineleme derinliğidir.
Para un límite dado \(L\), se define \(S(L)\) como la suma de todos los enteros \(n\le L\) tales que la función phi de Euler \(\varphi(n)\) es 5-suave, es decir, todos los factores primos de \(\varphi(n)\) pertenecen a \(\{2,3,5\}\). El objetivo es calcular \(S(10^{12}) \bmod 2^{32}\). Recorrer uno por uno todos los \(n\le 10^{12}\) es inviable, así que primero hay que describir con precisión la forma de los \(n\) válidos.
La observación decisiva es que la condición sobre \(\varphi(n)\) impone una estructura muy rígida a la factorización prima de \(n\). Una vez identificada esa estructura, la suma se reorganiza en una búsqueda mucho más pequeña sobre números 5-suaves y productos admisibles de primos.
Escribimos
$$n=2^a3^b5^c\prod_{i=1}^r p_i^{e_i},\qquad p_i>5.$$
La fórmula multiplicativa de Euler da
$$\varphi(n)=\varphi(2^a)\varphi(3^b)\varphi(5^c)\prod_{i=1}^r p_i^{e_i-1}(p_i-1).$$
Las contribuciones de \(2,3,5\) siempre son 5-suaves:
$$\varphi(2^a)\in\{1,2,4,8,\dots\},\qquad \varphi(3^b)\in\{1,2,6,18,\dots\},\qquad \varphi(5^c)\in\{1,4,20,100,\dots\}.$$
Por tanto, todas las restricciones reales vienen de los primos \(p_i>5\).
Si un primo \(p_i>5\) aparece con exponente \(e_i\ge 2\), entonces el factor \(p_i^{e_i-1}\) divide a \(\varphi(n)\). Eso obligaría a que \(\varphi(n)\) tuviera un factor primo mayor que \(5\), contradiciendo la condición 5-suave. Luego cada primo \(p>5\) puede aparecer como mucho una vez.
Además, cuando tal primo aparece, \(p-1\) divide a \(\varphi(n)\). En consecuencia, \(p-1\) debe ser 5-suave. Así, todo número válido tiene la forma
$$n=hq,$$
donde \(h=2^a3^b5^c\) es 5-suave y \(q\) es un producto libre de cuadrados de primos distintos \(p>5\) que cumplen
$$p-1=2^\alpha 3^\beta 5^\gamma,\qquad \alpha,\beta,\gamma\ge 0.$$
La recíproca también vale. Si \(h\) es 5-suave y \(q=\prod p\) es un producto libre de cuadrados de primos distintos con \(p-1\) 5-suave, entonces \(h\) y \(q\) son coprimos, y
$$\varphi(hq)=\varphi(h)\prod_{p\mid q}(p-1),$$
que vuelve a ser 5-suave. Por lo tanto, la descripción es exacta.
Definimos
$$\mathcal{H}(x)=\left\{2^a3^b5^c\le x:\ a,b,c\ge 0\right\}$$
como el conjunto de números 5-suaves hasta \(x\), y también
$$A(x)=\sum_{h\in\mathcal{H}(x)} h.$$
Asimismo, definimos el conjunto de primos admisibles
$$\mathcal{P}(L)=\left\{p\le L:\ p>5,\ p\text{ prime},\ p-1\in\mathcal{H}(L)\right\}.$$
Cada \(n\le L\) válido se obtiene de manera única eligiendo un producto libre de cuadrados \(q\) formado por primos distintos de \(\mathcal{P}(L)\), y luego un multiplicador 5-suave \(h\le L/q\). Por eso
$$S(L)=\sum_{q\in\mathcal{Q}(L)} \sum_{\substack{h\in\mathcal{H}(L)\\ h\le L/q}} qh,$$
donde \(\mathcal{Q}(L)\) es el conjunto de todos los productos libres de cuadrados \(q\le L\) construidos con primos distintos de \(\mathcal{P}(L)\), incluyendo el producto vacío \(q=1\).
Extrayendo \(q\) de la suma interior, obtenemos la fórmula central
$$\boxed{S(L)=\sum_{q\in\mathcal{Q}(L)} q\,A\left(\left\lfloor\frac{L}{q}\right\rfloor\right)\pmod{2^{32}}.}$$
La caracterización anterior muestra que los primos admisibles son exactamente los primos de la forma
$$p=h+1,\qquad h\in\mathcal{H}(L).$$
Así que no hace falta buscar entre todos los primos hasta \(L\); basta generar todos los números 5-suaves y probar si \(h+1\) es primo. Esa reducción es la que hace factible el problema.
Una vez ordenada la lista de números 5-suaves, los valores \(A(x)\) se obtienen rápidamente mediante búsqueda binaria y sumas prefijas. Después solo queda recorrer por profundidad todos los productos de subconjuntos \(q\in\mathcal{Q}(L)\), cortando una rama tan pronto como \(qp>L\).
Para \(L=100\), los números 5-suaves son
$$\{1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36,40,45,48,50,54,60,64,72,75,80,81,90,96,100\}.$$
Los primos admisibles \(p=h+1\) son
$$\{7,11,13,17,19,31,37,41,61,73,97\}.$$
Entre sus productos libres de cuadrados, los únicos que no superan \(100\) son
$$1,\ 7,\ 11,\ 13,\ 17,\ 19,\ 31,\ 37,\ 41,\ 61,\ 73,\ 97,\ 77,\ 91.$$
Las sumas prefijas necesarias son
$$A(100)=1258,\quad A(14)=60,\quad A(9)=38,\quad A(7)=21,\quad A(5)=15,\quad A(3)=6,\quad A(2)=3,\quad A(1)=1.$$
Por tanto, las contribuciones son
$$\begin{aligned} q=1&:&&1\cdot A(100)=1258,\\ q=7&:&&7\cdot A(14)=420,\\ q=11&:&&11\cdot A(9)=418,\\ q=13&:&&13\cdot A(7)=273,\\ q=17&:&&17\cdot A(5)=255,\\ q=19&:&&19\cdot A(5)=285,\\ q=31&:&&31\cdot A(3)=186,\\ q=37&:&&37\cdot A(2)=111,\\ q=41&:&&41\cdot A(2)=123,\\ q=61&:&&61\cdot A(1)=61,\\ q=73&:&&73\cdot A(1)=73,\\ q=97&:&&97\cdot A(1)=97,\\ q=77&:&&77\cdot A(1)=77,\\ q=91&:&&91\cdot A(1)=91. \end{aligned}$$
La suma total es
$$1258+420+418+273+255+285+186+111+123+61+73+97+77+91=3728,$$
exactamente el valor de comprobación usado por la implementación.
Las implementaciones en C++, Python y Java siguen la misma idea.
Primero generan todos los números de la forma \(2^a3^b5^c\le L\) mediante tres bucles multiplicativos anidados. Esa lista se ordena, se eliminan repetidos y se construye un arreglo de sumas prefijas módulo \(2^{32}\), de modo que \(A(x)\) pueda consultarse con una búsqueda binaria.
Después, para cada número 5-suave \(h\), la implementación comprueba si \(h+1\) es primo. Para ello utiliza exponenciación modular rápida y un test de primalidad de Miller-Rabin con bases fijas pequeñas, suficiente para el rango numérico del problema. Cada primo \(h+1>5\) se guarda como primo admisible.
Por último, una búsqueda en profundidad enumera los productos \(q\) de subconjuntos de primos admisibles en orden creciente. En cada estado recursivo añade
$$q\,A\left(\left\lfloor\frac{L}{q}\right\rfloor\right)\pmod{2^{32}}$$
a la respuesta, y luego intenta extender la rama con primos posteriores mientras el producto siga siendo como mucho \(L\). Como el recorrido siempre avanza hacia adelante en la lista ordenada, cada subconjunto libre de cuadrados se visita una sola vez.
Sea \(H=|\mathcal{H}(L)|\), \(P=|\mathcal{P}(L)|\) y \(T=|\mathcal{Q}(L)|\), el número de productos de subconjuntos que realmente visita la DFS. Generar la lista 5-suave requiere \(O(H)\) pasos multiplicativos; ordenarla y eliminar duplicados cuesta \(O(H\log H)\). Las sumas prefijas se construyen en \(O(H)\).
La primalidad se comprueba solo para los \(H\) candidatos \(h+1\), no para todos los enteros hasta \(L\). Con Miller-Rabin de bases fijas, eso aporta aproximadamente \(O(H\log L)\) trabajo de aritmética modular. La DFS visita cada producto factible una vez y hace una búsqueda binaria en la lista 5-suave en cada nodo, por lo que la fase de suma cuesta \(O(T\log H)\).
En consecuencia, el algoritmo depende del tamaño de la lista 5-suave y del árbol de productos factibles, no de \(L\) como intervalo bruto. La memoria es \(O(H+P)\), más la profundidad de recursión correspondiente a los primos seleccionados en la rama actual.
对给定上界 \(L\)，记 \(S(L)\) 为所有满足 \(n\le L\) 且欧拉函数 \(\varphi(n)\) 是 5-smooth 的整数 \(n\) 之和。这里 5-smooth 的意思是：\(\varphi(n)\) 的所有素因子都属于 \(\{2,3,5\}\)。目标是求出 \(S(10^{12}) \bmod 2^{32}\)。显然，不可能对 \(1\) 到 \(10^{12}\) 的每个整数逐个计算 \(\varphi(n)\) 再检查条件，因此必须先找出满足条件的 \(n\) 到底长什么样。
核心思想是先从素因子分解出发，证明合法的 \(n\) 只能由两部分组成：一部分完全由 \(2,3,5\) 的幂构成，另一部分则是某些特殊大素数的无平方因子乘积。这样就可以把原问题改写成对一小批 5-smooth 数和若干可行素数乘积的求和。
设
$$n=2^a3^b5^c\prod_{i=1}^r p_i^{e_i},\qquad p_i>5.$$
由欧拉函数的乘法公式可得
$$\varphi(n)=\varphi(2^a)\varphi(3^b)\varphi(5^c)\prod_{i=1}^r p_i^{e_i-1}(p_i-1).$$
注意，来自 \(2,3,5\) 的三部分天然就是 5-smooth：
$$\varphi(2^a)\in\{1,2,4,8,\dots\},\qquad \varphi(3^b)\in\{1,2,6,18,\dots\},\qquad \varphi(5^c)\in\{1,4,20,100,\dots\}.$$
因此，真正需要限制的是那些大于 \(5\) 的素数因子。
如果某个素数 \(p_i>5\) 在 \(n\) 中出现的指数满足 \(e_i\ge 2\)，那么 \(\varphi(n)\) 中就会出现因子 \(p_i^{e_i-1}\)。这意味着 \(\varphi(n)\) 一定含有一个大于 \(5\) 的素因子，与 5-smooth 条件矛盾。所以所有 \(p>5\) 的素数在 \(n\) 中都只能出现一次。
另外，只要 \(p>5\) 整除 \(n\)，那么 \(p-1\) 就一定整除 \(\varphi(n)\)。既然 \(\varphi(n)\) 必须是 5-smooth，那么 \(p-1\) 本身也必须是 5-smooth。由此得到：
$$n=hq,$$
其中 \(h=2^a3^b5^c\) 是一个 5-smooth 数，而 \(q\) 是若干互不相同、且都大于 \(5\) 的素数的无平方因子乘积，并且每个素数都满足
$$p-1=2^\alpha 3^\beta 5^\gamma,\qquad \alpha,\beta,\gamma\ge 0.$$
反过来这也足够。若 \(h\) 是 5-smooth，而 \(q=\prod p\) 是这样的无平方因子乘积，那么 \(h\) 只含素因子 \(2,3,5\)，而 \(q\) 只含大于 \(5\) 的素因子，所以二者互素。于是
$$\varphi(hq)=\varphi(h)\prod_{p\mid q}(p-1),$$
右边是若干个 5-smooth 数的乘积，仍然 5-smooth。这说明上面的结构刻画是充要的。
定义
$$\mathcal{H}(x)=\left\{2^a3^b5^c\le x:\ a,b,c\ge 0\right\}$$
表示不超过 \(x\) 的所有 5-smooth 数，并定义前缀求和函数
$$A(x)=\sum_{h\in\mathcal{H}(x)} h.$$
再定义可用的大素数集合
$$\mathcal{P}(L)=\left\{p\le L:\ p>5,\ p\text{ prime},\ p-1\in\mathcal{H}(L)\right\}.$$
任何一个合法的 \(n\le L\) 都可以唯一地表示成“一个由 \(\mathcal{P}(L)\) 中不同素数组成的无平方因子乘积 \(q\)”乘上“一个不超过 \(L/q\) 的 5-smooth 数 \(h\)”。因此
$$S(L)=\sum_{q\in\mathcal{Q}(L)} \sum_{\substack{h\in\mathcal{H}(L)\\ h\le L/q}} qh,$$
其中 \(\mathcal{Q}(L)\) 表示所有满足 \(q\le L\) 的可行无平方因子乘积，空乘积 \(q=1\) 也包含在内。
把 \(q\) 从内层求和中提出，就得到整个算法真正实现的公式：
$$\boxed{S(L)=\sum_{q\in\mathcal{Q}(L)} q\,A\left(\left\lfloor\frac{L}{q}\right\rfloor\right)\pmod{2^{32}}.}$$
从定义可以直接看出：可用的大素数恰好就是
$$p=h+1,\qquad h\in\mathcal{H}(L)$$
中那些为素数的值。也就是说，我们不需要在 \(1\) 到 \(L\) 的所有素数里筛选，只需要先生成所有 5-smooth 数，再测试 \(h+1\) 是否为素数即可。这一步把搜索空间从“整个区间”缩小到了“5-smooth 列表”，规模差别极大。
当 5-smooth 数按升序排列后，\(A(x)\) 可以通过二分查找加前缀和在很短时间内算出。剩下的就是对可用素数做深度优先搜索，枚举所有满足 \(q\le L\) 的子集乘积，并在 \(qp>L\) 时立即剪枝。
当 \(L=100\) 时，5-smooth 数的完整列表为
$$\{1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36,40,45,48,50,54,60,64,72,75,80,81,90,96,100\}.$$
由 \(p=h+1\) 得到的可用素数是
$$\{7,11,13,17,19,31,37,41,61,73,97\}.$$
这些素数的无平方因子乘积中，不超过 \(100\) 的只有
$$1,\ 7,\ 11,\ 13,\ 17,\ 19,\ 31,\ 37,\ 41,\ 61,\ 73,\ 97,\ 77,\ 91.$$
需要用到的前缀和是
$$A(100)=1258,\quad A(14)=60,\quad A(9)=38,\quad A(7)=21,\quad A(5)=15,\quad A(3)=6,\quad A(2)=3,\quad A(1)=1.$$
于是各项贡献为
$$\begin{aligned} q=1&:&&1\cdot A(100)=1258,\\ q=7&:&&7\cdot A(14)=420,\\ q=11&:&&11\cdot A(9)=418,\\ q=13&:&&13\cdot A(7)=273,\\ q=17&:&&17\cdot A(5)=255,\\ q=19&:&&19\cdot A(5)=285,\\ q=31&:&&31\cdot A(3)=186,\\ q=37&:&&37\cdot A(2)=111,\\ q=41&:&&41\cdot A(2)=123,\\ q=61&:&&61\cdot A(1)=61,\\ q=73&:&&73\cdot A(1)=73,\\ q=97&:&&97\cdot A(1)=97,\\ q=77&:&&77\cdot A(1)=77,\\ q=91&:&&91\cdot A(1)=91. \end{aligned}$$
把这些数加起来就得到
$$1258+420+418+273+255+285+186+111+123+61+73+97+77+91=3728,$$
这正好与实现中的校验值一致。
C++、Python 和 Java 三个实现遵循完全相同的流程。
第一步，用三层乘法循环生成所有满足 \(2^a3^b5^c\le L\) 的数。随后将这份列表排序、去重，并建立模 \(2^{32}\) 的前缀和数组，这样就能通过一次二分查找快速得到 \(A(x)\) 的模值。
第二步，对每个 5-smooth 数 \(h\) 检查 \(h+1\) 是否为素数。实现中使用快速模幂和固定小底数的 Miller-Rabin 素性测试，这对于本题的数值范围已经足够。所有满足 \(h+1>5\) 且为素数的值都会被保留下来，作为可用的大素数。
第三步，深度优先搜索按升序枚举这些可用素数的子集乘积 \(q\)。每到一个递归状态，就把
$$q\,A\left(\left\lfloor\frac{L}{q}\right\rfloor\right)\pmod{2^{32}}$$
加入答案，然后继续尝试加入后面的素数；如果乘积会超过 \(L\)，就立即停止这一分支。由于搜索始终只向后扩展，任意一个无平方因子子集都恰好只会出现一次。
记 \(H=|\mathcal{H}(L)|\)、\(P=|\mathcal{P}(L)|\)、\(T=|\mathcal{Q}(L)|\)，其中 \(T\) 是深度优先搜索实际访问到的子集乘积个数。生成 5-smooth 列表需要 \(O(H)\) 次乘法操作，排序和去重需要 \(O(H\log H)\)，构建前缀和需要 \(O(H)\) 时间。
素性测试只会在这 \(H\) 个候选值 \(h+1\) 上进行，而不会在整个 \([1,L]\) 区间上进行。固定底数的 Miller-Rabin 大致带来 \(O(H\log L)\) 的模运算工作量。之后的深度优先搜索会对每个可行乘积访问一次，并在每个节点上执行一次 5-smooth 列表的二分查找，因此求和阶段的代价是 \(O(T\log H)\)。
因此，整体效率取决于 5-smooth 列表和可行子集乘积树的规模，而不是直接取决于 \(L\) 本身。空间复杂度为 \(O(H+P)\)，外加当前递归路径所需要的栈空间。
Для заданного предела \(L\) обозначим через \(S(L)\) сумму всех целых чисел \(n\le L\), для которых функция Эйлера \(\varphi(n)\) является 5-гладкой, то есть все простые делители \(\varphi(n)\) принадлежат множеству \(\{2,3,5\}\). Требуется найти \(S(10^{12}) \bmod 2^{32}\). Полный перебор всех \(n\le 10^{12}\) невозможен, поэтому сначала нужно понять точную структуру допустимых чисел.
Главная идея состоит в том, что условие 5-гладкости для \(\varphi(n)\) очень жёстко ограничивает простое разложение числа \(n\). После этого задача сводится к суммированию по небольшому списку 5-гладких чисел и по допустимым произведениям специальных простых чисел.
Запишем
$$n=2^a3^b5^c\prod_{i=1}^r p_i^{e_i},\qquad p_i>5.$$
По мультипликативной формуле Эйлера
$$\varphi(n)=\varphi(2^a)\varphi(3^b)\varphi(5^c)\prod_{i=1}^r p_i^{e_i-1}(p_i-1).$$
Вклады от \(2,3,5\) всегда 5-гладкие:
$$\varphi(2^a)\in\{1,2,4,8,\dots\},\qquad \varphi(3^b)\in\{1,2,6,18,\dots\},\qquad \varphi(5^c)\in\{1,4,20,100,\dots\}.$$
Значит, все ограничения приходят только от простых \(p_i>5\).
Если некоторый простой \(p_i>5\) входит в разложение \(n\) с показателем \(e_i\ge 2\), то множитель \(p_i^{e_i-1}\) обязательно входит в \(\varphi(n)\). Тогда \(\varphi(n)\) имела бы простой делитель больше \(5\), что запрещено. Следовательно, каждый простой \(p>5\) может появляться в \(n\) не более одного раза.
Кроме того, если такой простой \(p\) входит в \(n\), то \(p-1\) делит \(\varphi(n)\). Поэтому само число \(p-1\) тоже должно быть 5-гладким. Мы получаем точную форму любого допустимого числа:
$$n=hq,$$
где \(h=2^a3^b5^c\) является 5-гладким числом, а \(q\) есть свободное от квадратов произведение различных простых \(p>5\), удовлетворяющих условию
$$p-1=2^\alpha 3^\beta 5^\gamma,\qquad \alpha,\beta,\gamma\ge 0.$$
Обратное тоже верно. Если \(h\) 5-гладкое, а \(q=\prod p\) является таким произведением, то \(h\) и \(q\) взаимно просты, поэтому
$$\varphi(hq)=\varphi(h)\prod_{p\mid q}(p-1),$$
а правая часть снова 5-гладкая. Значит, описанная структура является необходимой и достаточной.
Введём обозначения
$$\mathcal{H}(x)=\left\{2^a3^b5^c\le x:\ a,b,c\ge 0\right\}$$
для множества 5-гладких чисел, не превосходящих \(x\), и
$$A(x)=\sum_{h\in\mathcal{H}(x)} h$$
для их префиксной суммы.
Также определим множество допустимых простых
$$\mathcal{P}(L)=\left\{p\le L:\ p>5,\ p\text{ prime},\ p-1\in\mathcal{H}(L)\right\}.$$
Любое допустимое число \(n\le L\) единственным образом получается выбором свободного от квадратов произведения \(q\) из различных простых из \(\mathcal{P}(L)\) и выбором 5-гладкого множителя \(h\le L/q\). Поэтому
$$S(L)=\sum_{q\in\mathcal{Q}(L)} \sum_{\substack{h\in\mathcal{H}(L)\\ h\le L/q}} qh,$$
где \(\mathcal{Q}(L)\) обозначает множество всех допустимых произведений \(q\le L\), включая пустое произведение \(q=1\).
Вынося \(q\) из внутренней суммы, получаем основную формулу:
$$\boxed{S(L)=\sum_{q\in\mathcal{Q}(L)} q\,A\left(\left\lfloor\frac{L}{q}\right\rfloor\right)\pmod{2^{32}}.}$$
Из определения следует, что допустимые большие простые — это в точности простые числа вида
$$p=h+1,\qquad h\in\mathcal{H}(L).$$
То есть нет необходимости рассматривать все простые до \(L\). Достаточно породить все 5-гладкие числа и проверить на простоту только значения \(h+1\). Именно это и сокращает пространство поиска до разумного размера.
После сортировки списка 5-гладких чисел функция \(A(x)\) вычисляется быстро с помощью двоичного поиска и префиксных сумм. Остаётся перечислить глубинным поиском все допустимые произведения \(q\), обрезая ветвь сразу, как только \(qp>L\).
При \(L=100\) список 5-гладких чисел равен
$$\{1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36,40,45,48,50,54,60,64,72,75,80,81,90,96,100\}.$$
Допустимые простые \(p=h+1\) имеют вид
$$\{7,11,13,17,19,31,37,41,61,73,97\}.$$
Среди их произведений без повторов не превосходят \(100\) только
$$1,\ 7,\ 11,\ 13,\ 17,\ 19,\ 31,\ 37,\ 41,\ 61,\ 73,\ 97,\ 77,\ 91.$$
Нужные префиксные суммы таковы:
$$A(100)=1258,\quad A(14)=60,\quad A(9)=38,\quad A(7)=21,\quad A(5)=15,\quad A(3)=6,\quad A(2)=3,\quad A(1)=1.$$
Соответствующие вклады равны
$$\begin{aligned} q=1&:&&1\cdot A(100)=1258,\\ q=7&:&&7\cdot A(14)=420,\\ q=11&:&&11\cdot A(9)=418,\\ q=13&:&&13\cdot A(7)=273,\\ q=17&:&&17\cdot A(5)=255,\\ q=19&:&&19\cdot A(5)=285,\\ q=31&:&&31\cdot A(3)=186,\\ q=37&:&&37\cdot A(2)=111,\\ q=41&:&&41\cdot A(2)=123,\\ q=61&:&&61\cdot A(1)=61,\\ q=73&:&&73\cdot A(1)=73,\\ q=97&:&&97\cdot A(1)=97,\\ q=77&:&&77\cdot A(1)=77,\\ q=91&:&&91\cdot A(1)=91. \end{aligned}$$
Сумма равна
$$1258+420+418+273+255+285+186+111+123+61+73+97+77+91=3728,$$
что совпадает с проверочным значением реализации.
Реализации на C++, Python и Java следуют одной и той же схеме.
Сначала они порождают все числа вида \(2^a3^b5^c\le L\) с помощью трёх вложенных циклов умножения. Полученный список сортируется, очищается от повторов, после чего по нему строится массив префиксных сумм по модулю \(2^{32}\). Это позволяет быстро получать значение \(A(x)\) через двоичный поиск.
Затем для каждого 5-гладкого числа \(h\) проверяется, является ли \(h+1\) простым. Для этого используются быстрое модульное возведение в степень и тест Миллера-Рабина с фиксированным набором малых оснований, достаточным для диапазона чисел в этой задаче. Все простые \(h+1>5\) сохраняются как допустимые.
После этого глубинный поиск перебирает произведения \(q\) из допустимых простых в возрастающем порядке. В каждом рекурсивном состоянии к ответу прибавляется
$$q\,A\left(\left\lfloor\frac{L}{q}\right\rfloor\right)\pmod{2^{32}},$$
а затем предпринимается попытка умножить \(q\) на более поздние допустимые простые, пока произведение не превысит \(L\). Поскольку поиск всегда движется только вперёд по отсортированному списку, каждое свободное от квадратов подмножество учитывается ровно один раз.
Обозначим через \(H=|\mathcal{H}(L)|\) число 5-гладких чисел, через \(P=|\mathcal{P}(L)|\) число допустимых простых, а через \(T=|\mathcal{Q}(L)|\) число произведений подмножеств, реально посещаемых глубинным поиском. Генерация списка 5-гладких чисел требует \(O(H)\) мультипликативных шагов, сортировка и удаление повторов стоят \(O(H\log H)\), а построение префиксных сумм — \(O(H)\).
Проверка на простоту выполняется только для \(H\) кандидатов вида \(h+1\), а не для всех чисел до \(L\). При фиксированном наборе оснований Миллера-Рабина это даёт примерно \(O(H\log L)\) работы модульной арифметики. Глубинный поиск посещает каждый допустимый продукт один раз и делает по одному двоичному поиску в списке 5-гладких чисел на вершину, поэтому фаза суммирования стоит \(O(T\log H)\).
Итак, алгоритм зависит не от самого \(L\), а от значительно меньших размеров множества 5-гладких чисел и дерева допустимых произведений. Память составляет \(O(H+P)\), плюс стек рекурсии глубины текущей выбранной цепочки простых.
لحدٍّ معطى \(L\)، نعرّف \(S(L)\) بأنه مجموع جميع الأعداد الصحيحة \(n\le L\) التي تكون فيها دالة أويلر \(\varphi(n)\) عددًا 5-smooth، أي إن جميع العوامل الأولية لـ \(\varphi(n)\) تنتمي إلى المجموعة \(\{2,3,5\}\). المطلوب هو حساب \(S(10^{12}) \bmod 2^{32}\). ومن الواضح أن فحص كل \(n\le 10^{12}\) مباشرة غير ممكن، لذلك يجب أولًا استخراج البنية الدقيقة للأعداد المسموح بها.
الفكرة الحاسمة هي أن شرط كون \(\varphi(n)\) عددًا 5-smooth يفرض قيودًا صارمة جدًا على التحليل الأولي لـ \(n\). وبعد إثبات هذه البنية، يمكن إعادة كتابة المجموع على صورة بحث صغير فوق أعداد 5-smooth ومنتجات معيّنة من الأعداد الأولية المقبولة.
لنكتب
$$n=2^a3^b5^c\prod_{i=1}^r p_i^{e_i},\qquad p_i>5.$$
وباستخدام صيغة أويلر الضربية نحصل على
$$\varphi(n)=\varphi(2^a)\varphi(3^b)\varphi(5^c)\prod_{i=1}^r p_i^{e_i-1}(p_i-1).$$
أما العوامل القادمة من \(2,3,5\) فهي دائمًا 5-smooth:
$$\varphi(2^a)\in\{1,2,4,8,\dots\},\qquad \varphi(3^b)\in\{1,2,6,18,\dots\},\qquad \varphi(5^c)\in\{1,4,20,100,\dots\}.$$
إذًا كل القيود المهمة تأتي فقط من الأعداد الأولية \(p_i>5\).
إذا ظهر عدد أولي \(p_i>5\) في \(n\) بأس \(e_i\ge 2\)، فإن العامل \(p_i^{e_i-1}\) سيقسّم \(\varphi(n)\). وهذا يفرض وجود عامل أولي أكبر من \(5\) داخل \(\varphi(n)\)، وهو أمر ممنوع. لذلك لا يمكن لأي عدد أولي \(p>5\) أن يظهر في \(n\) إلا مرة واحدة فقط.
وفوق ذلك، إذا كان \(p>5\) يقسم \(n\)، فإن \(p-1\) يقسم \(\varphi(n)\). وبالتالي يجب أن يكون \(p-1\) نفسه عددًا 5-smooth. ومن هنا نحصل على الشكل العام لكل عدد صالح:
$$n=hq,$$
حيث إن \(h=2^a3^b5^c\) عدد 5-smooth، و\(q\) حاصل ضرب خالٍ من المربعات لأعداد أولية مختلفة أكبر من \(5\) تحقق الشرط
$$p-1=2^\alpha 3^\beta 5^\gamma,\qquad \alpha,\beta,\gamma\ge 0.$$
والعكس صحيح أيضًا. فإذا كان \(h\) عددًا 5-smooth، وكان \(q=\prod p\) حاصل ضرب خالٍ من المربعات لهذه الأعداد الأولية، فإن \(h\) و\(q\) أوليان فيما بينهما، ومن ثم
$$\varphi(hq)=\varphi(h)\prod_{p\mid q}(p-1),$$
وهذا حاصل ضرب لأعداد 5-smooth، فيبقى 5-smooth. إذن هذا التوصيف لازم وكافٍ معًا.
لنعرّف
$$\mathcal{H}(x)=\left\{2^a3^b5^c\le x:\ a,b,c\ge 0\right\}$$
وهي مجموعة الأعداد 5-smooth التي لا تتجاوز \(x\)، ثم نعرّف دالة المجموع التراكمي
$$A(x)=\sum_{h\in\mathcal{H}(x)} h.$$
كما نعرّف مجموعة الأعداد الأولية المقبولة
$$\mathcal{P}(L)=\left\{p\le L:\ p>5,\ p\text{ prime},\ p-1\in\mathcal{H}(L)\right\}.$$
كل عدد صالح \(n\le L\) يُكتب بصورة وحيدة على شكل حاصل ضرب \(q\) من عناصر مختلفة من \(\mathcal{P}(L)\) مضروبًا في عدد 5-smooth هو \(h\le L/q\). لذلك
$$S(L)=\sum_{q\in\mathcal{Q}(L)} \sum_{\substack{h\in\mathcal{H}(L)\\ h\le L/q}} qh,$$
حيث إن \(\mathcal{Q}(L)\) تمثل جميع المنتجات الخالية من المربعات التي لا تتجاوز \(L\)، بما في ذلك الضرب الفارغ \(q=1\).
وبإخراج \(q\) من المجموع الداخلي نحصل على الصيغة الأساسية:
$$\boxed{S(L)=\sum_{q\in\mathcal{Q}(L)} q\,A\left(\left\lfloor\frac{L}{q}\right\rfloor\right)\pmod{2^{32}}.}$$
من التعريف السابق يتبين أن الأعداد الأولية المقبولة هي بالضبط الأعداد الأولية من الشكل
$$p=h+1,\qquad h\in\mathcal{H}(L).$$
وبالتالي لسنا بحاجة إلى المرور على جميع الأعداد الأولية حتى \(L\)، بل يكفي أن نولّد جميع الأعداد 5-smooth ثم نختبر أولية \(h+1\). هذا هو الاختزال الذي يجعل المسألة عملية.
بعد ترتيب قائمة الأعداد 5-smooth، يمكن حساب \(A(x)\) بسرعة بواسطة بحث ثنائي مع مجاميع تراكمية. وبعد ذلك يبقى تعداد جميع منتجات المجموعات الجزئية الممكنة \(q\) باستخدام بحث عمقي، مع قطع الفرع فورًا عندما يؤدي الضرب في أولي جديد إلى تجاوز \(L\).
عندما يكون \(L=100\)، تكون الأعداد 5-smooth هي
$$\{1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36,40,45,48,50,54,60,64,72,75,80,81,90,96,100\}.$$
والأعداد الأولية المقبولة من الشكل \(p=h+1\) هي
$$\{7,11,13,17,19,31,37,41,61,73,97\}.$$
ومن بين جميع منتجاتها الخالية من المربعات، لا يبقى تحت \(100\) إلا
$$1,\ 7,\ 11,\ 13,\ 17,\ 19,\ 31,\ 37,\ 41,\ 61,\ 73,\ 97,\ 77,\ 91.$$
أما مجاميع السوابق المطلوبة فهي
$$A(100)=1258,\quad A(14)=60,\quad A(9)=38,\quad A(7)=21,\quad A(5)=15,\quad A(3)=6,\quad A(2)=3,\quad A(1)=1.$$
ومن ثم تكون المساهمات
$$\begin{aligned} q=1&:&&1\cdot A(100)=1258,\\ q=7&:&&7\cdot A(14)=420,\\ q=11&:&&11\cdot A(9)=418,\\ q=13&:&&13\cdot A(7)=273,\\ q=17&:&&17\cdot A(5)=255,\\ q=19&:&&19\cdot A(5)=285,\\ q=31&:&&31\cdot A(3)=186,\\ q=37&:&&37\cdot A(2)=111,\\ q=41&:&&41\cdot A(2)=123,\\ q=61&:&&61\cdot A(1)=61,\\ q=73&:&&73\cdot A(1)=73,\\ q=97&:&&97\cdot A(1)=97,\\ q=77&:&&77\cdot A(1)=77,\\ q=91&:&&91\cdot A(1)=91. \end{aligned}$$
وبجمعها نحصل على
$$1258+420+418+273+255+285+186+111+123+61+73+97+77+91=3728,$$
وهو نفس مقدار التحقق الذي تستخدمه الشيفرة.
تتبع تطبيقات C++ وPython وJava الخطة نفسها تمامًا.
أولًا، تولّد جميع الأعداد من الصورة \(2^a3^b5^c\le L\) باستخدام ثلاث حلقات ضرب متداخلة. ثم تُرتَّب هذه القائمة، وتُحذف التكرارات، ويُبنى لها مجموع تراكمي بترديد \(2^{32}\) حتى يمكن الحصول على \(A(x)\) سريعًا بواسطة بحث ثنائي.
ثانيًا، لكل عدد 5-smooth مقداره \(h\)، تختبر الشيفرة ما إذا كان \(h+1\) أوليًا. ويُستخدم لهذا الغرض الرفع المعياري السريع واختبار ميلر-رابين للأولية مع مجموعة ثابتة من القواعد الصغيرة، وهو كافٍ للمدى العددي في هذه المسألة. وكل عدد أولي \(h+1>5\) يُحفظ ضمن قائمة الأعداد الأولية المقبولة.
ثالثًا، ينفّذ بحث عمقي تعدادًا لجميع منتجات المجموعات الجزئية \(q\) لهذه الأعداد الأولية بترتيب متزايد. وفي كل حالة عودية يضيف المقدار
$$q\,A\left(\left\lfloor\frac{L}{q}\right\rfloor\right)\pmod{2^{32}}$$
إلى الجواب، ثم يحاول توسيع الفرع بإضافة أعداد أولية لاحقة ما دام الناتج لا يتجاوز \(L\). ولأن المرور يتم دائمًا إلى الأمام داخل القائمة المرتبة، فإن كل مجموعة خالية من المربعات تُزار مرة واحدة فقط.
لنكتب \(H=|\mathcal{H}(L)|\)، و\(P=|\mathcal{P}(L)|\)، و\(T=|\mathcal{Q}(L)|\)، حيث يمثل \(T\) عدد منتجات المجموعات الجزئية التي يزورها البحث العمقي فعلًا. توليد قائمة الأعداد 5-smooth يحتاج إلى \(O(H)\) خطوة ضرب، بينما الترتيب وإزالة التكرار يكلفان \(O(H\log H)\)، وبناء المجاميع التراكمية يتم في \(O(H)\).
اختبار الأولية لا يطبَّق إلا على \(H\) قيم من الشكل \(h+1\)، وليس على جميع الأعداد حتى \(L\). ومع اختبار ميلر-رابين ذي القواعد الثابتة يكون هذا الجزء تقريبًا \(O(H\log L)\) من عمل الحسابات المعيارية. أما البحث العمقي فيزور كل منتج ممكن مرة واحدة، ويجري في كل عقدة بحثًا ثنائيًا واحدًا في قائمة الأعداد 5-smooth، لذا فإن مرحلة الجمع تكلف \(O(T\log H)\).
وبذلك لا تعتمد الكلفة على \(L\) بوصفه فترة خام، بل على حجم قائمة الأعداد 5-smooth وعلى شجرة المنتجات الممكنة، وهما أصغر بكثير عمليًا. واستهلاك الذاكرة هو \(O(H+P)\)، مع عمق مكدس إضافي يساوي عدد الأعداد الأولية المختارة في المسار الحالي.