We seek the unique prime \(p\) such that the decimal expansion of \(1/p\) begins with the digits \(00000000137\) and the full repetend defines a cyclic number whose last five digits are \(56789\). Once that prime is identified, the required Project Euler quantity is the sum of the digits of the cyclic number.
For a prime \(p \neq 2,5\), the decimal expansion of \(1/p\) is purely repeating. If the period is maximal, then its length is \(p-1\), and the repeating block can be written as
$$N=\frac{10^{p-1}-1}{p}.$$
The number \(N\) is the integer formed by the repeating digits of \(1/p\). When \(p\) is a full reptend prime in base \(10\), the multiples \(N,2N,\dots,(p-1)N\) are cyclic rotations of the same digit string, which is exactly why the problem is about cyclic numbers.
The first eleven digits after the decimal point are \(00000000137\). Multiplying \(1/p\) by \(10^{11}\) therefore gives a number whose integer part is \(137\):
$$137 \le \frac{10^{11}}{p} \lt 138.$$
Rearranging yields the narrow interval
$$\frac{10^{11}}{138} \lt p \le \frac{10^{11}}{137}.$$
This is implemented directly as
$$\texttt{low}=\left\lfloor\frac{10^{11}}{138}\right\rfloor+1,\qquad \texttt{high}=\left\lfloor\frac{10^{11}}{137}\right\rfloor.$$
Numerically, this is \(724637682 \lt p \le 729927007\), so the prefix already limits the search to a window of about \(5.29\times 10^6\).
The problem also tells us that the cyclic number ends in \(56789\). Therefore
$$N \equiv 56789 \pmod{10^5}.$$
Since \(pN=10^{p-1}-1\), reducing modulo \(10^5\) gives
$$pN \equiv -1 \pmod{10^5}.$$
Substituting the known suffix of \(N\),
$$p \cdot 56789 \equiv -1 \pmod{10^5}.$$
Solving this congruence yields
$$p \equiv 9891 \pmod{10^5}.$$
So every valid prime must lie in one arithmetic progression inside the interval. In the actual search window, that leaves exactly \(53\) candidates.
Not every prime in that progression has a repetend of length \(p-1\). For primes \(p \neq 2,5\), the period of \(1/p\) in base \(10\) is the multiplicative order
$$\operatorname{ord}_p(10).$$
By Fermat's little theorem, this order divides \(p-1\). Therefore the period is maximal exactly when
$$\operatorname{ord}_p(10)=p-1.$$
The standard test used by all three local solutions is: factor \(p-1\) into distinct prime divisors \(q\), and verify that
$$10^{(p-1)/q} \not\equiv 1 \pmod p$$
for every such \(q\). If any one of these congruences equals \(1\), then the order is a proper divisor of \(p-1\), so the candidate is rejected. In this repository's search, the arithmetic progression gives \(53\) values, only \(3\) of them are prime, and only one survives the order test:
$$p=729809891.$$
Let \(s\) be the sum of the digits of the cyclic number \(N\). Because \(N,2N,\dots,(p-1)N\) are cyclic rotations, each of these numbers has the same digit sum \(s\). Summing them as multiples gives
$$\sum_{k=1}^{p-1} kN = N \cdot \frac{p(p-1)}{2}.$$
Summing the same set column by column gives a repunit times the digit sum:
$$\sum_{k=1}^{p-1} kN = s \cdot R_{p-1},\qquad R_{p-1}=\frac{10^{p-1}-1}{9}.$$
Since \(pN=10^{p-1}-1\), we also have \(R_{p-1}=pN/9\). Cancelling \(N\) yields
$$s=\frac{9(p-1)}{2}.$$
Substituting the unique prime found above gives
$$s=\frac{9(729809891-1)}{2}=3284144505.$$
This is the value returned by the local implementations.
The C++, Python, and Java solutions follow the same structure. First, mod_pow performs binary modular exponentiation, which is needed for the order test. The C++ code uses __int128 during multiplication to avoid overflow, Java uses BigInteger for the same reason, and Python relies on native arbitrary-precision integers.
Second, is_prime performs trial division up to \(\sqrt{p}\). That would be too slow for a wide brute-force scan, but after the interval and congruence filters the candidate set is tiny, so the simple implementation is entirely sufficient here. Third, prime_factors_distinct strips repeated factors from \(p-1\), because the order test only needs the distinct prime divisors.
Finally, find_prime_p computes the interval bounds, aligns the first candidate to the residue class \(9891 \bmod 100000\), and scans by steps of \(100000\). The extra guard
$$\left\lfloor\frac{10^{11}}{p}\right\rfloor=137$$
keeps the prefix condition exact. The C++ version also runs checkpoints: \(p=7\) must be full reptend in base \(10\), the unique candidate must be \(729809891\), and the digit-sum formula must produce \(3284144505\).
Let \(C\) be the number of candidates after the interval and congruence filters. In this instance \(C=53\). Each primality check uses naive trial division, so the worst-case cost per candidate is \(O(\sqrt{p})\). Factoring \(p-1\) by trial division has the same asymptotic bound, and the order test then uses one modular exponentiation for each distinct prime factor of \(p-1\), costing \(O(\log p)\) modular multiplications per factor.
So the repository implementation is asymptotically a small number of \(O(\sqrt{p})\) checks plus a few \(O(\log p)\) exponentiations. Practically, the search is tiny: \(53\) arithmetic-progression candidates, \(3\) primes, and \(1\) full-reptend prime.
Gesucht ist das eindeutige Primzahl-\(p\), so dass die Dezimalentwicklung von \(1/p\) mit den Ziffern \(00000000137\) beginnt und die volle Periode eine zyklische Zahl mit den Endziffern \(56789\) bildet. Sobald \(p\) feststeht, ist die gesuchte Euler-Groesse einfach die Ziffernsumme dieser zyklischen Zahl.
Fuer eine Primzahl \(p \neq 2,5\) ist die Dezimaldarstellung von \(1/p\) rein periodisch. Hat die Periode maximale Laenge, dann ist ihre Laenge gleich \(p-1\), und der Periodenblock kann als
$$N=\frac{10^{p-1}-1}{p}$$
geschrieben werden. \(N\) ist also genau die ganze Zahl, die aus den Periodenziffern besteht. Ist \(p\) eine vollperiodische Primzahl zur Basis \(10\), dann sind \(N,2N,\dots,(p-1)N\) zyklische Rotationen derselben Ziffernfolge.
Die ersten elf Nachkommastellen sind \(00000000137\). Also hat \(10^{11}/p\) ganzzahligen Anteil \(137\):
$$137 \le \frac{10^{11}}{p} \lt 138.$$
Nach Umstellen folgt
$$\frac{10^{11}}{138} \lt p \le \frac{10^{11}}{137}.$$
Genau das implementiert der Code mit
$$\texttt{low}=\left\lfloor\frac{10^{11}}{138}\right\rfloor+1,\qquad \texttt{high}=\left\lfloor\frac{10^{11}}{137}\right\rfloor.$$
Numerisch bleibt damit nur noch das Fenster \(724637682 \lt p \le 729927007\), also ein Bereich von ungefaehr \(5.29\times 10^6\) Zahlen.
Die zyklische Zahl endet auf \(56789\). Daher gilt
$$N \equiv 56789 \pmod{10^5}.$$
Aus \(pN=10^{p-1}-1\) folgt modulo \(10^5\)
$$pN \equiv -1 \pmod{10^5}.$$
Setzt man den bekannten Rest von \(N\) ein, erhaelt man
$$p \cdot 56789 \equiv -1 \pmod{10^5}.$$
Die Loesung dieser Kongruenz ist
$$p \equiv 9891 \pmod{10^5}.$$
Damit muessen alle Kandidaten in genau einer arithmetischen Progression liegen. Im tatsaechlichen Intervall bleiben so exakt \(53\) Werte uebrig.
Nicht jede Primzahl in dieser Progression hat wirklich Periodenlaenge \(p-1\). Fuer \(p \neq 2,5\) ist die Periodenlaenge von \(1/p\) zur Basis \(10\) gleich der multiplikativen Ordnung
$$\operatorname{ord}_p(10).$$
Nach dem kleinen Satz von Fermat teilt diese Ordnung stets \(p-1\). Also gilt genau dann volle Periodenlaenge, wenn
$$\operatorname{ord}_p(10)=p-1.$$
Der in allen drei lokalen Loesungen verwendete Test faktorisiert \(p-1\) in seine verschiedenen Primteiler \(q\) und prueft fuer jeden davon, dass
$$10^{(p-1)/q} \not\equiv 1 \pmod p$$
gilt. Sobald fuer ein \(q\) der Wert \(1\) herauskommt, ist die Ordnung ein echter Teiler von \(p-1\), und der Kandidat faellt weg. In diesem Repository gibt es in der Progression \(53\) Kandidaten, davon sind nur \(3\) prim, und genau einer ueberlebt den Ordnungstest:
$$p=729809891.$$
Sei \(s\) die Ziffernsumme von \(N\). Weil \(N,2N,\dots,(p-1)N\) zyklische Rotationen sind, haben alle diese Zahlen dieselbe Ziffernsumme \(s\). Summiert man sie als Vielfache, so erhaelt man
$$\sum_{k=1}^{p-1} kN = N \cdot \frac{p(p-1)}{2}.$$
Summiert man dieselbe Menge spaltenweise, entsteht ein Repunit mal Ziffernsumme:
$$\sum_{k=1}^{p-1} kN = s \cdot R_{p-1},\qquad R_{p-1}=\frac{10^{p-1}-1}{9}.$$
Aus \(pN=10^{p-1}-1\) folgt zugleich \(R_{p-1}=pN/9\). Nach Kuerzen von \(N\) bleibt
$$s=\frac{9(p-1)}{2}.$$
Mit der gefundenen Primzahl ergibt sich
$$s=\frac{9(729809891-1)}{2}=3284144505.$$
Genau dieser Wert wird von den lokalen Implementierungen ausgegeben.
Die C++-, Python- und Java-Loesungen verwenden dieselbe Pipeline. Zunaechst berechnet mod_pow Potenzen modulo \(p\) per binaerer Exponentiation. Dabei nutzt C++ __int128 fuer sichere Multiplikationen, Java verwendet an dieser Stelle BigInteger, und Python profitiert von seinen eingebauten Ganzzahlen mit beliebiger Praezision.
Danach testet is_prime Kandidaten per Probedivision bis \(\sqrt{p}\). Fuer eine breite Vollsuche waere das unguenstig, aber nach Intervall- und Kongruenzfilter bleiben nur sehr wenige Kandidaten, daher ist diese einfache Methode voellig ausreichend. Die Funktion prime_factors_distinct entfernt Wiederholungen in der Zerlegung von \(p-1\), weil fuer den Ordnungstest nur die verschiedenen Primteiler benoetigt werden.
Schliesslich berechnet find_prime_p die Schranken, richtet den Startwert auf die Restklasse \(9891 \bmod 100000\) aus und durchlaeuft die Kandidaten in Schritten von \(100000\). Die zusaetzliche Bedingung
$$\left\lfloor\frac{10^{11}}{p}\right\rfloor=137$$
sichert das Dezimalpraefix exakt ab. Die C++-Version fuehrt ausserdem Checkpoints aus: \(7\) muss vollperiodisch in Basis \(10\) sein, der eindeutige Kandidat muss \(729809891\) sein, und die Ziffernsummenformel muss \(3284144505\) liefern.
Sei \(C\) die Anzahl der Kandidaten nach Intervall- und Kongruenzfilter. Hier ist \(C=53\). Jeder Primzahltest per Probedivision kostet im Worst Case \(O(\sqrt{p})\). Das Faktorisieren von \(p-1\) hat dieselbe asymptotische Groessenordnung, und der Ordnungstest benoetigt fuer jeden verschiedenen Primteiler eine modulare Exponentiation mit \(O(\log p)\) Multiplikationen.
Asymptotisch besteht die Implementierung also aus wenigen \(O(\sqrt{p})\)-Pruefungen plus einigen \(O(\log p)\)-Exponentiationen. Praktisch ist die Suche sehr klein: \(53\) Kandidaten in der Progression, \(3\) Primzahlen und \(1\) vollperiodische Primzahl.
Aranan sey, \(1/p\) ondalik aciliminin \(00000000137\) ile basladigi ve tam devir blogunun olusturdugu dongusel sayinin son bes basamaginin \(56789\) oldugu tek asal \(p\)'yi bulmaktir. Bu asal belirlendikten sonra istenen Euler degeri, bu dongusel sayinin rakam toplami olur.
\(p \neq 2,5\) olan bir asal icin \(1/p\) ondalik acilimi tamamen devirlidir. Devir uzunlugu maksimum ise uzunluk \(p-1\) olur ve tekrar eden blok
$$N=\frac{10^{p-1}-1}{p}$$
seklinde yazilir. Buradaki \(N\), \(1/p\)'nin tekrar eden rakamlarindan olusan tam sayidir. \(p\), taban \(10\) icin full reptend asal ise \(N,2N,\dots,(p-1)N\) ayni rakam dizisinin dongusel kaydirmalaridir.
Virgulden sonraki ilk on bir basamak \(00000000137\) oldugundan \(10^{11}/p\) sayisinin tam kismi \(137\) olmalidir:
$$137 \le \frac{10^{11}}{p} \lt 138.$$
Buradan
$$\frac{10^{11}}{138} \lt p \le \frac{10^{11}}{137}$$
elde edilir. Kod bunu dogrudan
$$\texttt{low}=\left\lfloor\frac{10^{11}}{138}\right\rfloor+1,\qquad \texttt{high}=\left\lfloor\frac{10^{11}}{137}\right\rfloor$$
olarak kurar. Sayisal olarak bu, \(724637682 \lt p \le 729927007\) araligidir; yani on ek kosulu taramayi yaklasik \(5.29\times 10^6\) sayilik dar bir pencereye indirir.
Dongusel sayinin sonu \(56789\) ile bittigi icin
$$N \equiv 56789 \pmod{10^5}$$
olur. Ayrica \(pN=10^{p-1}-1\) oldugundan modulo \(10^5\) altinda
$$pN \equiv -1 \pmod{10^5}$$
elde edilir. Bilinen son bes basamagi yerine koyarsak
$$p \cdot 56789 \equiv -1 \pmod{10^5}$$
ve buradan
$$p \equiv 9891 \pmod{10^5}$$
sonucu cikar. Boylece gecerli olabilecek her asal, araligin icindeki tek bir aritmetik dizide yer alir. Bu pencerede yalnizca \(53\) aday kalir.
Bu dizideki her asal icin periyot uzunlugu mutlaka \(p-1\) degildir. \(p \neq 2,5\) iken taban \(10\)'daki devir uzunlugu,
$$\operatorname{ord}_p(10)$$
carpimsel mertebesidir. Fermat'nin kucuk teoremine gore bu mertebe \(p-1\)'i boler. Dolayisiyla maksimum periyot kosulu tam olarak
$$\operatorname{ord}_p(10)=p-1$$
olmasidir. Uc yerel cozumun de kullandigi standart test, \(p-1\)'in ayri asal carpanlarini \(q\) olarak bulup her biri icin
$$10^{(p-1)/q} \not\equiv 1 \pmod p$$
oldugunu dogrulamaktir. Eger bu degerlerden biri \(1\) cikarsa mertebe \(p-1\)'in uygun bir bolenidir ve aday elenir. Bu depoda, aritmetik dizideki \(53\) adaydan sadece \(3\) tanesi asaldir ve mertebe testini yalnizca biri gecer:
$$p=729809891.$$
\(N\)'nin rakam toplami \(s\) olsun. \(N,2N,\dots,(p-1)N\) sayilari dongusel kaydirmalar oldugu icin hepsinin rakam toplami ayni, yani \(s\)'dir. Bunlari katlar olarak toplarsak
$$\sum_{k=1}^{p-1} kN = N \cdot \frac{p(p-1)}{2}$$
olur. Ayni toplami sutun sutun dusunursek bir repunit ile rakam toplaminin carpimini elde ederiz:
$$\sum_{k=1}^{p-1} kN = s \cdot R_{p-1},\qquad R_{p-1}=\frac{10^{p-1}-1}{9}.$$
Ayrica \(pN=10^{p-1}-1\) oldugundan \(R_{p-1}=pN/9\) yazabiliriz. \(N\) sadeleşince
$$s=\frac{9(p-1)}{2}$$
kalir. Bulunan asal yerine yazildiginda
$$s=\frac{9(729809891-1)}{2}=3284144505$$
elde edilir. Yerel cozumlerin dondurdugu deger budur.
C++, Python ve Java cozumleri ayni is akisina sahiptir. Ilk olarak mod_pow, ikili us alma ile moduler kuvvet hesaplar. C++ carpim tasmasini engellemek icin __int128 kullanir, Java ayni noktada BigInteger'a basvurur, Python ise yerlesik buyuk tam sayilarla bunu dogal olarak halleder.
Daha sonra is_prime, \(\sqrt{p}\)'ye kadar deneme bolmesi yapar. Genis bir kaba kuvvet taramasi icin bu yontem zayif olurdu; ancak aralik ve kongruans filtrelerinden sonra aday sayisi cok az kaldigi icin burada gayet yeterlidir. prime_factors_distinct fonksiyonu da \(p-1\)'in tekrarli carpanlarini temizler; mertebe testi yalnizca ayri asal carpanlari ister.
Son adimda find_prime_p alt ve ust sinirlari hesaplar, ilk adayi \(9891 \bmod 100000\) kalaniyla hizalar ve \(100000\) adimlarla ilerler. Kod icindeki ek kosul
$$\left\lfloor\frac{10^{11}}{p}\right\rfloor=137$$
ondalik on ek kosulunu tam olarak korur. C++ surumu ayrica kontrol noktalarini calistirir: \(7\) sayisi taban \(10\)'da full reptend olmali, tek aday \(729809891\) olmali ve rakam toplami formulu \(3284144505\) vermelidir.
\(C\), aralik ve kongruans filtrelerinden sonra kalan aday sayisi olsun. Bu problemde \(C=53\). Her asal testi deneme bolmesiyle yapildigi icin en kotu durumda aday basina \(O(\sqrt{p})\) maliyet vardir. \(p-1\)'in carpanlara ayrilmasi da ayni asimptotik sinira sahiptir. Mertebe testi ise \(p-1\)'in her ayri asal carpani icin bir moduler us alma yapar; bu da carpan basi \(O(\log p)\) moduler carpim demektir.
Dolayisiyla depodaki uygulama, az sayida \(O(\sqrt{p})\) kontrol ve birkac \(O(\log p)\) us almasindan olusur. Pratikte arama cok kucuktur: \(53\) aday, \(3\) asal ve \(1\) tane full reptend asal.
Buscamos el primo unico \(p\) tal que la expansion decimal de \(1/p\) empieza con \(00000000137\) y cuyo repetendo completo forma un numero ciclico terminado en \(56789\). Una vez hallado ese primo, la cantidad pedida por Project Euler es la suma de los digitos de dicho numero ciclico.
Para un primo \(p \neq 2,5\), la expansion decimal de \(1/p\) es puramente periodica. Si la longitud del periodo es maxima, entonces vale \(p-1\), y el bloque repetido puede escribirse como
$$N=\frac{10^{p-1}-1}{p}.$$
El entero \(N\) es exactamente el numero formado por las cifras repetidas de \(1/p\). Cuando \(p\) es un full reptend prime en base \(10\), los multiplos \(N,2N,\dots,(p-1)N\) son rotaciones ciclicas de la misma cadena de digitos.
Las primeras once cifras despues del punto decimal son \(00000000137\). Por tanto, la parte entera de \(10^{11}/p\) debe ser \(137\):
$$137 \le \frac{10^{11}}{p} \lt 138.$$
Al despejar, obtenemos
$$\frac{10^{11}}{138} \lt p \le \frac{10^{11}}{137}.$$
El codigo implementa esto con
$$\texttt{low}=\left\lfloor\frac{10^{11}}{138}\right\rfloor+1,\qquad \texttt{high}=\left\lfloor\frac{10^{11}}{137}\right\rfloor.$$
Numericamente queda el intervalo \(724637682 \lt p \le 729927007\), asi que el prefijo ya reduce la busqueda a una ventana de alrededor de \(5.29\times 10^6\) enteros.
El numero ciclico termina en \(56789\), luego
$$N \equiv 56789 \pmod{10^5}.$$
Como \(pN=10^{p-1}-1\), al reducir modulo \(10^5\) se obtiene
$$pN \equiv -1 \pmod{10^5}.$$
Sustituyendo el sufijo conocido de \(N\),
$$p \cdot 56789 \equiv -1 \pmod{10^5}.$$
La solucion de esta congruencia es
$$p \equiv 9891 \pmod{10^5}.$$
Asi, todo primo valido pertenece a una sola progresion aritmetica dentro del intervalo. En la ventana real quedan exactamente \(53\) candidatos.
No todo primo de esa progresion produce un repetendo de longitud \(p-1\). Para \(p \neq 2,5\), la longitud del periodo de \(1/p\) en base \(10\) es el orden multiplicativo
$$\operatorname{ord}_p(10).$$
Por el pequeno teorema de Fermat, este orden divide a \(p-1\). Por tanto, el periodo es maximo exactamente cuando
$$\operatorname{ord}_p(10)=p-1.$$
La prueba usada en las tres soluciones locales factoriza \(p-1\) en sus divisores primos distintos \(q\) y verifica que
$$10^{(p-1)/q} \not\equiv 1 \pmod p$$
para todos ellos. Si alguna de esas potencias vale \(1\), entonces el orden es un divisor propio de \(p-1\) y el candidato se descarta. En este repositorio, la progresion contiene \(53\) valores, solo \(3\) son primos, y unicamente uno supera la prueba de orden:
$$p=729809891.$$
Sea \(s\) la suma de los digitos de \(N\). Como \(N,2N,\dots,(p-1)N\) son rotaciones ciclicas, todas esas cantidades tienen la misma suma de digitos \(s\). Si las sumamos como multiplos, resulta
$$\sum_{k=1}^{p-1} kN = N \cdot \frac{p(p-1)}{2}.$$
Si sumamos la misma coleccion columna por columna, obtenemos un repunit multiplicado por la suma de digitos:
$$\sum_{k=1}^{p-1} kN = s \cdot R_{p-1},\qquad R_{p-1}=\frac{10^{p-1}-1}{9}.$$
Ademas, de \(pN=10^{p-1}-1\) se sigue que \(R_{p-1}=pN/9\). Al cancelar \(N\) queda
$$s=\frac{9(p-1)}{2}.$$
Con el primo encontrado, esto da
$$s=\frac{9(729809891-1)}{2}=3284144505.$$
Ese es exactamente el valor devuelto por las implementaciones locales.
Las soluciones en C++, Python y Java siguen la misma estructura. Primero, mod_pow calcula potencias modulares mediante exponenciacion binaria. C++ usa __int128 para evitar desbordamientos en las multiplicaciones, Java emplea BigInteger con el mismo fin, y Python se apoya en enteros de precision arbitraria.
Despues, is_prime aplica division de prueba hasta \(\sqrt{p}\). Eso seria demasiado lento para un barrido enorme, pero aqui los filtros de intervalo y congruencia dejan tan pocos candidatos que la version sencilla es suficiente. La funcion prime_factors_distinct elimina repeticiones en la factorizacion de \(p-1\), porque la prueba del orden solo necesita los factores primos distintos.
Por ultimo, find_prime_p calcula las cotas, alinea el primer candidato con la clase residual \(9891 \bmod 100000\) y avanza en pasos de \(100000\). La comprobacion extra
$$\left\lfloor\frac{10^{11}}{p}\right\rfloor=137$$
mantiene exacta la condicion del prefijo. La version en C++ ademas ejecuta checkpoints: \(7\) debe ser full reptend en base \(10\), el candidato unico debe ser \(729809891\), y la formula de la suma de digitos debe dar \(3284144505\).
Sea \(C\) el numero de candidatos despues de aplicar el intervalo y la congruencia. En este problema \(C=53\). Cada prueba de primalidad por division de prueba cuesta en el peor caso \(O(\sqrt{p})\). Factorizar \(p-1\) por el mismo metodo tiene la misma cota asintotica, y la comprobacion del orden requiere una exponenciacion modular por cada factor primo distinto de \(p-1\), con costo \(O(\log p)\) multiplicaciones modulares por factor.
En consecuencia, la implementacion del repositorio realiza unas pocas comprobaciones \(O(\sqrt{p})\) y unas pocas exponenciaciones \(O(\log p)\). En la practica, la busqueda es muy pequena: \(53\) candidatos, \(3\) primos y \(1\) primo full reptend.
题目要求找出唯一的素数 \(p\)，使得 \(1/p\) 的十进制展开以前缀 \(00000000137\) 开头，并且它的完整循环节对应的循环数以 \(56789\) 结尾。找到这个素数以后，Project Euler 要求的量就是该循环数的各位数字之和。
对素数 \(p \neq 2,5\)，\(1/p\) 的十进制展开是纯循环小数。如果循环长度达到最大值，那么长度就是 \(p-1\)，循环节可以写成
$$N=\frac{10^{p-1}-1}{p}.$$
这里的 \(N\) 就是由循环节数字组成的整数。当 \(p\) 是十进制下的 full reptend prime 时，\(N,2N,\dots,(p-1)N\) 恰好是同一串数字的循环位移，因此这正是题目里“cyclic number”的来源。
小数点后的前十一位是 \(00000000137\)，因此 \(10^{11}/p\) 的整数部分必须等于 \(137\)：
$$137 \le \frac{10^{11}}{p} \lt 138.$$
整理后得到
$$\frac{10^{11}}{138} \lt p \le \frac{10^{11}}{137}.$$
代码直接把它写成
$$\texttt{low}=\left\lfloor\frac{10^{11}}{138}\right\rfloor+1,\qquad \texttt{high}=\left\lfloor\frac{10^{11}}{137}\right\rfloor.$$
数值上就是 \(724637682 \lt p \le 729927007\)，前缀条件已经把搜索压缩到大约 \(5.29\times 10^6\) 个整数的窄区间内。
循环数的最后五位是 \(56789\)，所以
$$N \equiv 56789 \pmod{10^5}.$$
又因为 \(pN=10^{p-1}-1\)，模 \(10^5\) 化简可得
$$pN \equiv -1 \pmod{10^5}.$$
把 \(N\) 的已知后缀代入，得到
$$p \cdot 56789 \equiv -1 \pmod{10^5}.$$
解这个同余方程，得到
$$p \equiv 9891 \pmod{10^5}.$$
于是所有可能的素数都落在该区间内的一条等差数列上。实际窗口里只剩下 \(53\) 个候选值。
这 \(53\) 个候选并不一定都满足循环长度等于 \(p-1\)。当 \(p \neq 2,5\) 时，\(1/p\) 在十进制下的循环长度等于乘法阶
$$\operatorname{ord}_p(10).$$
由费马小定理可知，这个阶一定整除 \(p-1\)。因此最大循环长度条件等价于
$$\operatorname{ord}_p(10)=p-1.$$
三个本地解法都采用同一个标准判定：先把 \(p-1\) 分解出不同的素因子 \(q\)，再验证
$$10^{(p-1)/q} \not\equiv 1 \pmod p$$
对每个这样的 \(q\) 都成立。只要其中某一个结果等于 \(1\)，说明阶是 \(p-1\) 的真因子，该候选立刻淘汰。在这个仓库的实际搜索中，等差数列共有 \(53\) 个值，其中只有 \(3\) 个是素数，最终只有一个通过阶检验：
$$p=729809891.$$
设循环数 \(N\) 的数字和为 \(s\)。因为 \(N,2N,\dots,(p-1)N\) 都是循环位移，它们的数字和都等于 \(s\)。把这些数按“倍数”方式相加，有
$$\sum_{k=1}^{p-1} kN = N \cdot \frac{p(p-1)}{2}.$$
如果把同一批数按列相加，则每一列都会出现全部数字一次，因此得到一个 repunit 乘以数字和：
$$\sum_{k=1}^{p-1} kN = s \cdot R_{p-1},\qquad R_{p-1}=\frac{10^{p-1}-1}{9}.$$
同时由 \(pN=10^{p-1}-1\) 可知 \(R_{p-1}=pN/9\)。约去 \(N\) 以后得到
$$s=\frac{9(p-1)}{2}.$$
把唯一素数代入，得到
$$s=\frac{9(729809891-1)}{2}=3284144505.$$
这正是本地实现输出的结果。
C++、Python 和 Java 三个解法的流程完全一致。首先，mod_pow 用二进制快速幂计算模幂。C++ 在乘法处使用 __int128 避免溢出，Java 通过 BigInteger 完成安全乘法取模，Python 则直接依赖原生大整数。
其次，is_prime 用试除法检查到 \(\sqrt{p}\)。如果没有前面的数学筛选，这样做会很慢；但在区间和同余条件之后，只剩极少量候选，所以这种直接实现完全够用。prime_factors_distinct 会去掉 \(p-1\) 分解中的重复因子，因为阶检验只需要不同的素因子。
最后，find_prime_p 计算上下界，把起点对齐到 \(9891 \bmod 100000\) 的同余类，然后以 \(100000\) 为步长扫描。代码中的额外条件
$$\left\lfloor\frac{10^{11}}{p}\right\rfloor=137$$
保证前缀条件是精确匹配。C++ 版本还带有检查点：\(7\) 必须是十进制 full reptend prime，唯一候选必须是 \(729809891\)，数字和公式必须得到 \(3284144505\)。
设经过区间和同余过滤后还剩 \(C\) 个候选，本题中 \(C=53\)。每次试除素性检测的最坏复杂度是 \(O(\sqrt{p})\)。对 \(p-1\) 的试除分解也有相同数量级，而阶检验对 \(p-1\) 的每个不同素因子做一次模幂计算，每次需要 \(O(\log p)\) 次模乘。
因此，这份仓库实现的渐近成本可以看成少量 \(O(\sqrt{p})\) 检查加上少量 \(O(\log p)\) 快速幂。实际规模非常小：\(53\) 个候选，\(3\) 个素数，\(1\) 个满足 full reptend 条件的素数。
Нужно найти единственное простое число \(p\), для которого десятичная запись \(1/p\) начинается с цифр \(00000000137\), а полная периодическая часть задает циклическое число, оканчивающееся на \(56789\). После нахождения этого простого числа искомая величина из Project Euler равна сумме цифр полученного циклического числа.
Для простого \(p \neq 2,5\) десятичная запись \(1/p\) является чисто периодической. Если длина периода максимальна, то она равна \(p-1\), а сам период можно записать так:
$$N=\frac{10^{p-1}-1}{p}.$$
Число \(N\) состоит ровно из цифр периода. Если \(p\) является full reptend prime в базе \(10\), то числа \(N,2N,\dots,(p-1)N\) представляют собой циклические сдвиги одной и той же строки цифр.
Первые одиннадцать цифр после запятой равны \(00000000137\). Значит, целая часть числа \(10^{11}/p\) должна быть равна \(137\):
$$137 \le \frac{10^{11}}{p} \lt 138.$$
После преобразования получаем
$$\frac{10^{11}}{138} \lt p \le \frac{10^{11}}{137}.$$
Именно это кодирует программа через
$$\texttt{low}=\left\lfloor\frac{10^{11}}{138}\right\rfloor+1,\qquad \texttt{high}=\left\lfloor\frac{10^{11}}{137}\right\rfloor.$$
Численно остается интервал \(724637682 \lt p \le 729927007\), то есть префикс сразу сужает поиск до окна примерно из \(5.29\times 10^6\) чисел.
Так как циклическое число оканчивается на \(56789\), имеем
$$N \equiv 56789 \pmod{10^5}.$$
Из равенства \(pN=10^{p-1}-1\) по модулю \(10^5\) следует
$$pN \equiv -1 \pmod{10^5}.$$
Подставляя известный остаток числа \(N\), получаем
$$p \cdot 56789 \equiv -1 \pmod{10^5}.$$
Решение этого сравнения:
$$p \equiv 9891 \pmod{10^5}.$$
Следовательно, все возможные простые лежат в одной арифметической прогрессии внутри найденного интервала. В реальном диапазоне это оставляет ровно \(53\) кандидата.
Не каждое простое из этой прогрессии дает период длины \(p-1\). Для \(p \neq 2,5\) длина периода десятичной дроби \(1/p\) равна мультипликативному порядку
$$\operatorname{ord}_p(10).$$
По малой теореме Ферма этот порядок всегда делит \(p-1\). Поэтому максимальный период выполняется тогда и только тогда, когда
$$\operatorname{ord}_p(10)=p-1.$$
Тест, который используют все три локальные реализации, таков: разложить \(p-1\) на различные простые делители \(q\) и убедиться, что
$$10^{(p-1)/q} \not\equiv 1 \pmod p$$
для каждого такого \(q\). Если хотя бы для одного делителя получается \(1\), значит порядок является собственным делителем числа \(p-1\), и кандидат отбрасывается. В этом репозитории арифметическая прогрессия содержит \(53\) числа, из них только \(3\) простые, и лишь одно проходит проверку порядка:
$$p=729809891.$$
Пусть \(s\) обозначает сумму цифр числа \(N\). Поскольку \(N,2N,\dots,(p-1)N\) являются циклическими сдвигами, сумма цифр у всех этих чисел одинакова и равна \(s\). Если сложить их как кратные \(N\), получим
$$\sum_{k=1}^{p-1} kN = N \cdot \frac{p(p-1)}{2}.$$
Если же сложить тот же набор поразрядно, получится репъюнит, умноженный на сумму цифр:
$$\sum_{k=1}^{p-1} kN = s \cdot R_{p-1},\qquad R_{p-1}=\frac{10^{p-1}-1}{9}.$$
Так как \(pN=10^{p-1}-1\), имеем также \(R_{p-1}=pN/9\). После сокращения \(N\) остается
$$s=\frac{9(p-1)}{2}.$$
Подставляя найденное простое число, получаем
$$s=\frac{9(729809891-1)}{2}=3284144505.$$
Именно это значение возвращают локальные решения.
Реализации на C++, Python и Java следуют одной и той же схеме. Сначала функция mod_pow выполняет быстрое бинарное возведение в степень по модулю. В C++ для безопасного умножения используется __int128, в Java для той же цели применяется BigInteger, а Python опирается на встроенные длинные целые числа.
Далее is_prime проверяет простоту пробным делением до \(\sqrt{p}\). Для широкого полного перебора это было бы неудачно, но после фильтра по интервалу и сравнению по модулю кандидатов остается очень мало, поэтому простая реализация здесь оправданна. Функция prime_factors_distinct удаляет повторяющиеся множители в разложении \(p-1\), потому что в тесте порядка нужны только различные простые делители.
Наконец, find_prime_p вычисляет границы, выравнивает стартовое значение по классу вычетов \(9891 \bmod 100000\) и перебирает кандидаты с шагом \(100000\). Дополнительная проверка
$$\left\lfloor\frac{10^{11}}{p}\right\rfloor=137$$
обеспечивает точное выполнение условия на префикс. Версия на C++ еще и запускает контрольные проверки: число \(7\) должно быть full reptend prime в базе \(10\), единственный кандидат должен равняться \(729809891\), а формула суммы цифр должна дать \(3284144505\).
Пусть \(C\) обозначает число кандидатов после применения фильтра по интервалу и по сравнению. В этой задаче \(C=53\). Каждая проверка на простоту пробным делением имеет в худшем случае стоимость \(O(\sqrt{p})\). Разложение числа \(p-1\) тем же методом имеет ту же асимптотику, а тест порядка требует по одному модульному возведению в степень для каждого различного простого делителя \(p-1\), то есть \(O(\log p)\) модульных умножений на делитель.
Следовательно, реализация из репозитория асимптотически состоит из небольшого числа проверок \(O(\sqrt{p})\) и нескольких быстрых степеней \(O(\log p)\). Практически поиск очень мал: \(53\) кандидата, \(3\) простых числа и \(1\) full reptend prime.
المطلوب هو إيجاد العدد الأولي الوحيد \(p\) بحيث يبدأ التوسع العشري للكسر \(1/p\) بالمقدمة \(00000000137\)، ويكون التكرار الكامل عددا دوريا تنتهي آخر خمس خانات فيه بالعدد \(56789\). بعد تحديد هذا الأولي، تصبح القيمة المطلوبة في Project Euler هي مجموع أرقام ذلك العدد الدوري.
إذا كان \(p \neq 2,5\) وعددا أوليا، فإن التوسع العشري لـ \(1/p\) يكون دوريا خالصا. وإذا كانت الدورة بطولها الأعظمي، فطولها يساوي \(p-1\)، ويمكن كتابة الكتلة الدورية على الصورة
$$N=\frac{10^{p-1}-1}{p}.$$
العدد \(N\) هو العدد الصحيح المكوَّن من أرقام الدورة نفسها. وعندما يكون \(p\) من نوع full reptend prime في الأساس \(10\)، فإن الأعداد \(N,2N,\dots,(p-1)N\) تكون مجرد إزاحات دورية للسلسلة الرقمية نفسها.
أول إحدى عشرة خانة بعد الفاصلة هي \(00000000137\)، ولذلك يجب أن يكون الجزء الصحيح من \(10^{11}/p\) مساويا لـ \(137\):
$$137 \le \frac{10^{11}}{p} \lt 138.$$
وبإعادة الترتيب نحصل على
$$\frac{10^{11}}{138} \lt p \le \frac{10^{11}}{137}.$$
ولهذا يحدد الكود الحدين بالشكل
$$\texttt{low}=\left\lfloor\frac{10^{11}}{138}\right\rfloor+1,\qquad \texttt{high}=\left\lfloor\frac{10^{11}}{137}\right\rfloor.$$
عدديا يصبح المجال \(724637682 \lt p \le 729927007\)، أي إن شرط المقدمة وحده يضغط البحث إلى نافذة ضيقة طولها يقارب \(5.29\times 10^6\).
بما أن العدد الدوري ينتهي بالخانات \(56789\)، فهذا يعني أن
$$N \equiv 56789 \pmod{10^5}.$$
ومن العلاقة \(pN=10^{p-1}-1\) نحصل عند الاختزال modulo \(10^5\) على
$$pN \equiv -1 \pmod{10^5}.$$
وبالتعويض عن النهاية المعروفة للعدد \(N\) يصبح لدينا
$$p \cdot 56789 \equiv -1 \pmod{10^5}.$$
وحل هذا التطابق هو
$$p \equiv 9891 \pmod{10^5}.$$
إذن كل عدد أولي صالح يجب أن يقع في متتالية حسابية واحدة داخل المجال السابق. وفي النافذة الفعلية لا يبقى إلا \(53\) مرشحا.
ليس كل أولي في هذه المتتالية يعطي فترة بطول \(p-1\). فعندما يكون \(p \neq 2,5\)، فإن طول دورة \(1/p\) في الأساس \(10\) يساوي الرتبة الضربية
$$\operatorname{ord}_p(10).$$
وبحسب مبرهنة فيرما الصغرى فإن هذه الرتبة تقسم \(p-1\). لذلك يكون طول الدورة أعظميا بالضبط عندما
$$\operatorname{ord}_p(10)=p-1.$$
الاختبار المستخدم في الحلول المحلية الثلاثة هو تحليل \(p-1\) إلى عوامله الأولية المختلفة \(q\)، ثم التحقق من أن
$$10^{(p-1)/q} \not\equiv 1 \pmod p$$
لكل عامل من هذه العوامل. فإذا ظهر \(1\) لأي عامل، فهذا يعني أن الرتبة قاسم حقيقي لـ \(p-1\)، فيُرفض المرشح. في هذا المستودع تعطي المتتالية الحسابية \(53\) قيمة، منها \(3\) أعداد أولية فقط، وواحد فقط ينجح في اختبار الرتبة:
$$p=729809891.$$
لنرمز إلى مجموع أرقام \(N\) بالرمز \(s\). وبما أن الأعداد \(N,2N,\dots,(p-1)N\) هي تدويرات دورية، فإن مجموع الأرقام فيها جميعا يساوي \(s\). وإذا جمعناها باعتبارها مضاعفات لـ \(N\)، نحصل على
$$\sum_{k=1}^{p-1} kN = N \cdot \frac{p(p-1)}{2}.$$
أما إذا جمعنا المجموعة نفسها عموديا خانة بخانة، فسنحصل على repunit مضروبا في مجموع الأرقام:
$$\sum_{k=1}^{p-1} kN = s \cdot R_{p-1},\qquad R_{p-1}=\frac{10^{p-1}-1}{9}.$$
ومن \(pN=10^{p-1}-1\) نستنتج أيضا أن \(R_{p-1}=pN/9\). وبعد اختزال \(N\) نحصل على
$$s=\frac{9(p-1)}{2}.$$
وبالتعويض عن الأولي الوحيد نجد
$$s=\frac{9(729809891-1)}{2}=3284144505.$$
وهذه هي القيمة التي تعيدها الحلول المحلية في المستودع.
حلول C++ وPython وJava تتبع البنية نفسها. أولا تنفذ الدالة mod_pow الأس السريع الثنائي modulo \(p\). يستخدم كود C++ النوع __int128 لحماية الضرب من الفيض، بينما يستخدم Java كائنا من BigInteger للغرض نفسه، أما Python فيعتمد على الأعداد الصحيحة كبيرة الدقة المدمجة.
بعد ذلك تختبر الدالة is_prime الأولية بالقسمة التجريبية حتى \(\sqrt{p}\). هذا الأسلوب سيكون ضعيفا لو كانت المساحة المرشحة كبيرة، لكن بعد فلتر المجال وفلتر التطابق لا يبقى إلا عدد قليل جدا من القيم، لذلك يكون هذا التنفيذ البسيط كافيا تماما. أما الدالة prime_factors_distinct فتزيل تكرار العوامل في تحليل \(p-1\)، لأن اختبار الرتبة يحتاج فقط إلى العوامل الأولية المختلفة.
وأخيرا تحسب الدالة find_prime_p الحدين، وتضبط أول مرشح على فئة البواقي \(9891 \bmod 100000\)، ثم تمشي بخطوة مقدارها \(100000\). والتحقق الإضافي
$$\left\lfloor\frac{10^{11}}{p}\right\rfloor=137$$
يضمن أن شرط المقدمة العشرية محقق بدقة. كما أن نسخة C++ تشغل نقاط تحقق: يجب أن يكون \(7\) عددا full reptend prime في الأساس \(10\)، ويجب أن يكون المرشح الوحيد هو \(729809891\)، ويجب أن تعطي صيغة مجموع الأرقام القيمة \(3284144505\).
لتكن \(C\) عدد المرشحين بعد تطبيق فلتر المجال وفلتر التطابق. في هذه المسألة لدينا \(C=53\). كل اختبار أولية بالقسمة التجريبية يكلف في أسوأ حالة \(O(\sqrt{p})\). وتحليل \(p-1\) بالقسمة التجريبية له السلوك نفسه، ثم يحتاج اختبار الرتبة إلى عملية أس modular exponentiation واحدة لكل عامل أولي مختلف من عوامل \(p-1\)، أي \(O(\log p)\) ضربات معيارية لكل عامل.
إذن فالتنفيذ الموجود في المستودع يتكون نظريا من عدد صغير من اختبارات \(O(\sqrt{p})\) وعدد صغير من عمليات الأس السريع \(O(\log p)\). وعمليا البحث صغير جدا: \(53\) مرشحا، \(3\) أعداد أولية، و\(1\) عدد أولي full reptend فقط.