Let \(R(k)=\frac{10^k-1}{9}=11\ldots1\) be the repunit with \(k\) digits. The problem asks for the sum of all primes \(p<10^5\) such that there is no exponent \(n\ge 1\) with \(p\mid R(10^n)\).
The key point is that one never has to build the enormous numbers \(R(10^n)\) themselves. For each prime, the question can be decided entirely from the multiplicative behavior of \(10\) modulo that prime.
The implementations reduce the whole problem to a yes-or-no test on the multiplicative order of \(10\) modulo \(p\). Once that order is known, the classification is immediate.
For every integer \(k\ge 1\),
$$R(k)=1+10+10^2+\cdots+10^{k-1}=\frac{10^k-1}{9}.$$
If \(p\notin\{2,3,5\}\), then \(9\) is invertible modulo \(p\), so multiplying by \(9\) does not change divisibility by \(p\). Therefore
$$p\mid R(k)\iff 10^k\equiv 1 \pmod p.$$
In this problem the length is not an arbitrary \(k\), but specifically \(k=10^n\). So for primes other than \(2\), \(3\), and \(5\), we are asking whether
$$10^{10^n}\equiv 1 \pmod p$$
holds for at least one \(n\ge 1\).
Let
$$t=\operatorname{ord}_p(10),$$
the smallest positive integer such that \(10^t\equiv 1\pmod p\). By definition, \(10^m\equiv 1\pmod p\) happens exactly when \(t\mid m\). Hence
$$p\mid R(10^n)\iff t\mid 10^n.$$
Now \(10^n=2^n5^n\), so its only prime divisors are \(2\) and \(5\). Therefore \(t\mid 10^n\) for some \(n\) if and only if every prime divisor of \(t\) is either \(2\) or \(5\). Equivalently, after removing all factors \(2\) and \(5\) from \(t\), nothing remains.
So for every prime \(p\notin\{2,3,5\}\),
$$p\text{ divides some }R(10^n)\iff \operatorname{ord}_p(10)=2^a5^b\text{ for some }a,b\ge 0.$$
The converse is just as important as the forward implication: if \(t=2^a5^b\), then choosing \(n\ge \max(a,b)\) gives \(t\mid 10^n\), so such a prime really does divide one of the required repunits.
The primes \(2\) and \(5\) are immediate. Every repunit ends in the digit \(1\), so it is divisible by neither \(2\) nor \(5\). Both must therefore be included in the final sum.
The prime \(3\) is special for a different reason: \(9\) is not invertible modulo \(3\), so the previous equivalence must not be used. Instead,
$$R(k)=1+10+\cdots+10^{k-1}\equiv 1+1+\cdots+1\equiv k \pmod 3.$$
Since \(10^n\equiv 1\pmod 3\), we get \(R(10^n)\equiv 1\pmod 3\). Thus \(3\) never divides any \(R(10^n)\), even though it does divide other repunits such as \(R(3)\).
For a typical nontrivial example, \(p=17\) has \(\operatorname{ord}_{17}(10)=16=2^4\). Because \(16\mid 10^4\), the prime \(17\) divides \(R(10^4)\), so it is excluded from the sum.
By contrast, \(p=19\) has \(\operatorname{ord}_{19}(10)=18=2\cdot 3^2\). The extra factor \(3\) means \(18\nmid 10^n\) for every \(n\), so \(19\) never divides any \(R(10^n)\) and must be included.
A useful sanity check is \(p=7\). Its order is \(6=2\cdot 3\), so \(7\) divides \(R(6)\) but never divides \(R(10^n)\). That is exactly the distinction this problem is testing.
For every prime \(p\notin\{2,5\}\), Fermat's little theorem gives \(10^{p-1}\equiv 1\pmod p\). Therefore \(\operatorname{ord}_p(10)\) is a divisor of \(p-1\). This is why the implementations start from the candidate value \(p-1\) instead of searching upward from \(1\).
Suppose the current candidate is \(d\), and \(q\) is a prime divisor of \(d\). If
$$10^{d/q}\equiv 1 \pmod p,$$
then the true order already divides \(d/q\), so the factor \(q\) can be removed. Repeating that test as long as it succeeds preserves the invariant that the true order divides the current candidate.
When no prime factor can be removed any further, the remaining candidate is the smallest positive exponent producing \(1\), hence it is exactly \(\operatorname{ord}_p(10)\). After that, the final classification is obtained by stripping powers of \(2\) and \(5\) from this order and checking whether the remainder is \(1\).
The C++, Python, and Java implementations first generate all primes below the limit with a sieve. As each prime is processed, the primes \(2\), \(3\), and \(5\) are handled immediately as guaranteed nonfactors of every \(R(10^n)\).
For every other prime \(p\), the implementation starts from \(p-1\), factors that number into its distinct prime divisors, and repeatedly lowers the candidate order whenever a modular-exponentiation test shows that a smaller divisor still works. This produces the exact multiplicative order of \(10\) modulo \(p\).
Once the order has been found, the code removes factors of \(2\) and \(5\). If the reduced value is \(1\), then the prime can divide some \(R(10^n)\) and is skipped. Otherwise the prime is added to the running total. The C++ and Python versions perform modular exponentiation by repeated squaring; the Java version uses the standard big-integer modular power routine, but the mathematical test is the same in all three languages.
If the search limit is \(L\), the sieve phase costs \(O(L\log\log L)\) time and \(O(L)\) space. Here \(L=10^5\), so this part is tiny.
For a prime \(p\), the order computation factors \(p-1\) by trial division up to \(\sqrt{p-1}\), and each successful or failed reduction test uses modular exponentiation in \(O(\log p)\) multiplications. Since there are only \(9592\) primes below \(10^5\), the total running time is comfortably small, and the memory usage is dominated by the sieve array.
Sei \(R(k)=\frac{10^k-1}{9}=11\ldots1\) die Repunit mit \(k\) Stellen. Gesucht ist die Summe aller Primzahlen \(p<10^5\), für die es kein \(n\ge 1\) gibt mit \(p\mid R(10^n)\).
Man muss die riesigen Zahlen \(R(10^n)\) nicht explizit bilden. Für jede Primzahl lässt sich die Frage allein über das multiplikative Verhalten von \(10\) modulo \(p\) entscheiden.
Die Implementierungen führen das Problem auf einen Ja-Nein-Test für die multiplikative Ordnung von \(10\) modulo \(p\) zurück. Sobald diese Ordnung bekannt ist, ist die Einordnung der Primzahl direkt klar.
Für jedes \(k\ge 1\) gilt
$$R(k)=1+10+10^2+\cdots+10^{k-1}=\frac{10^k-1}{9}.$$
Ist \(p\notin\{2,3,5\}\), dann ist \(9\) modulo \(p\) invertierbar. Daher ändert Multiplikation mit \(9\) die Teilbarkeit durch \(p\) nicht, also
$$p\mid R(k)\iff 10^k\equiv 1 \pmod p.$$
Hier ist die Länge nicht irgendein \(k\), sondern speziell \(k=10^n\). Für alle Primzahlen außer \(2\), \(3\) und \(5\) lautet die Frage also, ob
$$10^{10^n}\equiv 1 \pmod p$$
für mindestens ein \(n\ge 1\) gilt.
Setze
$$t=\operatorname{ord}_p(10),$$
also den kleinsten positiven Exponenten mit \(10^t\equiv 1\pmod p\). Per Definition gilt \(10^m\equiv 1\pmod p\) genau dann, wenn \(t\mid m\). Somit erhält man
$$p\mid R(10^n)\iff t\mid 10^n.$$
Nun ist \(10^n=2^n5^n\), also besitzt diese Zahl nur die Primfaktoren \(2\) und \(5\). Folglich kann \(t\) genau dann einen Teiler von \(10^n\) bilden, wenn auch \(t\) selbst nur aus Primfaktoren \(2\) und \(5\) besteht. Anders gesagt: Entfernt man aus \(t\) alle Faktoren \(2\) und \(5\), darf nichts übrig bleiben.
Für jede Primzahl \(p\notin\{2,3,5\}\) gilt damit
$$p\text{ teilt ein }R(10^n)\iff \operatorname{ord}_p(10)=2^a5^b\text{ für gewisse }a,b\ge 0.$$
Die Umkehrung ist wesentlich: Falls \(t=2^a5^b\), dann genügt \(n\ge \max(a,b)\), damit \(t\mid 10^n\) und die Primzahl tatsächlich einen der gesuchten Repunits teilt.
Die Primzahlen \(2\) und \(5\) sind sofort erledigt. Jede Repunit endet auf die Ziffer \(1\) und ist daher weder durch \(2\) noch durch \(5\) teilbar. Beide gehören also sicher zur Endsumme.
Die Primzahl \(3\) ist aus einem anderen Grund speziell: Hier darf die vorige Äquivalenz nicht benutzt werden, weil \(9\) modulo \(3\) nicht invertierbar ist. Stattdessen gilt
$$R(k)=1+10+\cdots+10^{k-1}\equiv 1+1+\cdots+1\equiv k \pmod 3.$$
Da \(10^n\equiv 1\pmod 3\), folgt \(R(10^n)\equiv 1\pmod 3\). Also teilt \(3\) kein einziges \(R(10^n)\), obwohl \(3\) andere Repunits wie \(R(3)\) sehr wohl teilt.
Ein typisches Beispiel ist \(p=17\). Man erhält \(\operatorname{ord}_{17}(10)=16=2^4\). Weil \(16\mid 10^4\), teilt \(17\) den Repunit \(R(10^4)\) und wird daher nicht zur Summe addiert.
Dagegen hat \(p=19\) die Ordnung \(\operatorname{ord}_{19}(10)=18=2\cdot 3^2\). Der zusätzliche Faktor \(3\) verhindert, dass \(18\) irgendein \(10^n\) teilt. Also ist \(19\) ein echter Nichtfaktor und gehört zur Summe.
Ein nützlicher Kontrollfall ist \(p=7\). Hier ist die Ordnung \(6=2\cdot 3\). Deshalb teilt \(7\) zwar \(R(6)\), aber niemals ein \(R(10^n)\). Genau diesen Unterschied prüft die Aufgabe.
Für jede Primzahl \(p\notin\{2,5\}\) liefert der kleine Satz von Fermat die Kongruenz \(10^{p-1}\equiv 1\pmod p\). Also ist \(\operatorname{ord}_p(10)\) ein Teiler von \(p-1\). Deshalb beginnen die Implementierungen mit dem Kandidaten \(p-1\), statt von \(1\) aus nach oben zu suchen.
Sei \(d\) der aktuelle Kandidat und \(q\) ein Primteiler von \(d\). Gilt
$$10^{d/q}\equiv 1 \pmod p,$$
dann teilt die wahre Ordnung bereits \(d/q\), also kann der Faktor \(q\) entfernt werden. Wiederholt man diesen Test so lange wie möglich, bleibt die Invariante erhalten, dass die wahre Ordnung den aktuellen Kandidaten teilt.
Wenn kein weiterer Primfaktor entfernt werden kann, ist der verbleibende Kandidat der kleinste positive Exponent mit Wert \(1\), also genau \(\operatorname{ord}_p(10)\). Anschließend werden nur noch alle Zweier- und Fünferpotenzen herausgekürzt; bleibt danach mehr als \(1\) übrig, gehört die Primzahl zur gesuchten Summe.
Die Implementierungen in C++, Python und Java erzeugen zunächst mit einem Sieb alle Primzahlen unterhalb der Schranke. Während des Durchlaufs werden \(2\), \(3\) und \(5\) sofort als sichere Nichtfaktoren aller \(R(10^n)\) behandelt.
Für jede andere Primzahl \(p\) startet der Code mit \(p-1\), faktorisiert diese Zahl in ihre verschiedenen Primteiler und verkleinert die Kandidatenordnung immer dann, wenn ein Modularexponentiationstest zeigt, dass auch ein kleinerer Teiler noch funktioniert. So entsteht die exakte multiplikative Ordnung von \(10\) modulo \(p\).
Danach entfernt die Implementierung alle Faktoren \(2\) und \(5\) aus dieser Ordnung. Ist das Resultat \(1\), dann teilt die Primzahl irgendein \(R(10^n)\) und wird übersprungen. Andernfalls wird sie zur Summe addiert. C++ und Python benutzen dafür wiederholtes Quadrieren; Java verwendet die eingebaute Modulpotenz auf großen Ganzzahlen. Der mathematische Test ist in allen drei Sprachen identisch.
Bei einer Suchgrenze \(L\) kostet das Sieb \(O(L\log\log L)\) Zeit und \(O(L)\) Speicher. Hier ist \(L=10^5\), also ist dieser Teil praktisch vernachlässigbar.
Für eine Primzahl \(p\) wird \(p-1\) per Probedivision bis \(\sqrt{p-1}\) faktorisiert, und jeder Reduktionsversuch benötigt eine Modularexponentiation in \(O(\log p)\) Multiplikationen. Unterhalb von \(10^5\) gibt es nur \(9592\) Primzahlen, deshalb bleibt die Gesamtlaufzeit klein; der Speicherbedarf wird vom Sieb dominiert.
\(R(k)=\frac{10^k-1}{9}=11\ldots1\) ile \(k\) basamaklı repunit sayı gösterilsin. İstenen şey, \(p<10^5\) olan asallar arasında hiçbir \(n\ge 1\) için \(p\mid R(10^n)\) sağlamayanların toplamıdır.
Buradaki asıl fikir, devasa \(R(10^n)\) sayılarını üretmek zorunda olmamamızdır. Her asal için karar, yalnızca \(10\) sayısının o asal modundaki çarpımsal davranışından çıkar.
Uygulamalar bütün problemi, \(10\)'un \(p\) modundaki çarpımsal mertebesi üzerine kurulu tek bir teste indirger. Bu mertebe bulunduktan sonra asalın sınıfı hemen belirlenir.
Her \(k\ge 1\) için
$$R(k)=1+10+10^2+\cdots+10^{k-1}=\frac{10^k-1}{9}$$
eşitliği vardır. Eğer \(p\notin\{2,3,5\}\) ise \(9\), \(p\) modunda tersinir olduğundan \(9\) ile çarpmak bölünebilirliği değiştirmez. Dolayısıyla
$$p\mid R(k)\iff 10^k\equiv 1 \pmod p.$$
Bu problemde uzunluk keyfi bir \(k\) değil, özellikle \(k=10^n\) biçimindedir. O halde \(2\), \(3\) ve \(5\) dışındaki asallar için sorduğumuz şey, en az bir \(n\ge 1\) için
$$10^{10^n}\equiv 1 \pmod p$$
olup olmadığıdır.
$$t=\operatorname{ord}_p(10)$$
olsun; yani \(10^t\equiv 1\pmod p\) yapan en küçük pozitif üs olsun. Tanım gereği \(10^m\equiv 1\pmod p\) ancak ve ancak \(t\mid m\) olduğunda gerçekleşir. Bu yüzden
$$p\mid R(10^n)\iff t\mid 10^n.$$
Şimdi \(10^n=2^n5^n\) olduğundan bu sayının tek asal çarpanları \(2\) ve \(5\)'tir. Demek ki \(t\), ancak kendi asal çarpanları da sadece \(2\) ve \(5\) ise bir \(10^n\)'yi bölebilir. Eşdeğer biçimde, \(t\)'den bütün \(2\) ve \(5\) çarpanlarını attıktan sonra geriye bir şey kalmamalıdır.
Böylece \(p\notin\{2,3,5\}\) için tam ölçüt şudur: \(p\), bazı \(R(10^n)\) değerlerini ancak ve ancak \(\operatorname{ord}_p(10)=2^a5^b\) olacak biçimde \(a,b\ge 0\) bulunduğunda böler.
Ters yön de önemlidir: eğer \(t=2^a5^b\) ise \(n\ge \max(a,b)\) seçildiğinde \(t\mid 10^n\) olur ve asal gerçekten istenen biçimdeki bir repuniti böler.
\(2\) ve \(5\) hemen çözülür. Her repunitin son basamağı \(1\) olduğu için ne \(2\)'ye ne de \(5\)'e bölünür. Bu iki asal kesin olarak son toplamda yer alır.
\(3\) ise başka bir nedenle özeldir: burada önceki eşdeğerliği kullanamayız, çünkü \(9\) sayısı \(3\) modunda tersinir değildir. Onun yerine
$$R(k)=1+10+\cdots+10^{k-1}\equiv 1+1+\cdots+1\equiv k \pmod 3$$
yazarız. \(10^n\equiv 1\pmod 3\) olduğundan \(R(10^n)\equiv 1\pmod 3\) elde edilir. Yani \(3\), \(R(3)\) gibi başka repunitleri bölebilse de hiçbir \(R(10^n)\)'yi bölmez.
Tipik bir örnek olarak \(p=17\) için \(\operatorname{ord}_{17}(10)=16=2^4\) bulunur. \(16\mid 10^4\) olduğundan \(17\), \(R(10^4)\)'ü böler; bu yüzden toplama eklenmez.
Buna karşılık \(p=19\) için \(\operatorname{ord}_{19}(10)=18=2\cdot 3^2\) olur. İçeride kalan \(3\) çarpanı yüzünden \(18\), hiçbir \(10^n\)'yi bölmez. Dolayısıyla \(19\), problemde aranan asallardan biridir.
Bir başka yararlı kontrol de \(p=7\)'dir. Mertebe \(6=2\cdot 3\) olduğundan \(7\), \(R(6)\)'yı böler ama hiçbir zaman \(R(10^n)\)'yi bölmez. Problem tam olarak bu farkı ayırt eder.
\(p\notin\{2,5\}\) olan her asal için Fermat'nın küçük teoremi \(10^{p-1}\equiv 1\pmod p\) sonucunu verir. Bu nedenle \(\operatorname{ord}_p(10)\), \(p-1\)'in bir bölenidir. Uygulamalar bu yüzden yukarı doğru arama yapmak yerine aday değeri doğrudan \(p-1\) ile başlatır.
Güncel aday \(d\) ve \(d\)'nin bir asal böleni \(q\) olsun. Eğer
$$10^{d/q}\equiv 1 \pmod p$$
ise gerçek mertebe zaten \(d/q\)'yu da böler; dolayısıyla \(q\) çarpanı atılabilir. Bu test mümkün olduğu sürece tekrarlandığında, “gerçek mertebe mevcut adayı böler” değişmezi korunur.
Hiçbir asal çarpan daha fazla atılamadığında elde kalan aday, \(1\) sonucunu veren en küçük pozitif üs olur; yani tam olarak \(\operatorname{ord}_p(10)\)'dur. Son adımda bundan bütün \(2\) ve \(5\) çarpanları çıkarılır; geriye \(1\)'den büyük bir değer kalıyorsa asal toplama eklenir.
C++, Python ve Java uygulamaları önce bir elek yardımıyla sınırın altındaki bütün asalları üretir. Tarama sırasında \(2\), \(3\) ve \(5\) doğrudan her \(R(10^n)\) için kesinkes uygun olmayan asallar olarak işaretlenir.
Diğer her asal \(p\) için kod \(p-1\) ile başlar, bu sayının farklı asal bölenlerini çıkarır ve modüler üs alma testi daha küçük bir bölenin de işe yaradığını gösterdikçe aday mertebeyi küçültür. Böylece \(10\)'un \(p\) modundaki gerçek çarpımsal mertebesi bulunur.
Ardından bu mertebeden tüm \(2\) ve \(5\) çarpanları temizlenir. Sonuç \(1\) ise asal, bazı \(R(10^n)\) değerlerini bölebilir ve atlanır; değilse toplama eklenir. C++ ve Python sürümleri hızlı üs alma için tekrar karesini alma yöntemini kullanır; Java sürümü standart büyük tamsayı modüler üs alma yordamını kullanır. Üçünde de matematiksel test aynıdır.
Arama üst sınırı \(L\) ise elek aşaması \(O(L\log\log L)\) zaman ve \(O(L)\) bellek kullanır. Bu problemde \(L=10^5\) olduğundan bu bölüm son derece küçüktür.
Bir asal \(p\) için \(p-1\), \(\sqrt{p-1}\)'e kadar deneme bölmesiyle çarpanlara ayrılır; her küçültme denemesi de \(O(\log p)\) çarpma gerektiren modüler üs alma yapar. \(10^5\)'in altında yalnızca \(9592\) asal olduğu için toplam çalışma süresi rahattır; bellek tüketiminin ana kısmı elek dizisidir.
Sea \(R(k)=\frac{10^k-1}{9}=11\ldots1\) el repunit de \(k\) cifras. El problema pide la suma de todos los primos \(p<10^5\) para los que no existe ningún \(n\ge 1\) con \(p\mid R(10^n)\).
La idea central es que nunca hace falta construir explícitamente los enormes números \(R(10^n)\). Para cada primo, la decisión sale únicamente del comportamiento multiplicativo de \(10\) módulo \(p\).
Las implementaciones reducen toda la cuestión a una prueba binaria sobre el orden multiplicativo de \(10\) módulo \(p\). Una vez conocido ese orden, la clasificación del primo es inmediata.
Para todo \(k\ge 1\),
$$R(k)=1+10+10^2+\cdots+10^{k-1}=\frac{10^k-1}{9}.$$
Si \(p\notin\{2,3,5\}\), entonces \(9\) es invertible módulo \(p\), así que multiplicar por \(9\) no cambia la divisibilidad por \(p\). Por tanto,
$$p\mid R(k)\iff 10^k\equiv 1 \pmod p.$$
En este problema la longitud no es un \(k\) arbitrario, sino \(k=10^n\). Para todos los primos distintos de \(2\), \(3\) y \(5\), la pregunta pasa a ser si existe al menos un \(n\ge 1\) tal que
$$10^{10^n}\equiv 1 \pmod p.$$
Sea
$$t=\operatorname{ord}_p(10),$$
el menor entero positivo con \(10^t\equiv 1\pmod p\). Por definición, \(10^m\equiv 1\pmod p\) ocurre exactamente cuando \(t\mid m\). En consecuencia,
$$p\mid R(10^n)\iff t\mid 10^n.$$
Ahora bien, \(10^n=2^n5^n\), de modo que sus únicos factores primos son \(2\) y \(5\). Así, \(t\) puede dividir a algún \(10^n\) si y solo si todos los factores primos de \(t\) también son \(2\) o \(5\). Equivalentemente, al eliminar todas las potencias de \(2\) y \(5\) de \(t\), no debe quedar nada.
Por ello, para todo primo \(p\notin\{2,3,5\}\),
$$p\text{ divide algún }R(10^n)\iff \operatorname{ord}_p(10)=2^a5^b\text{ para ciertos }a,b\ge 0.$$
La implicación recíproca también importa: si \(t=2^a5^b\), basta elegir \(n\ge \max(a,b)\) para obtener \(t\mid 10^n\), y entonces el primo sí divide uno de los repunits pedidos.
Los primos \(2\) y \(5\) se resuelven al instante. Todo repunit termina en la cifra \(1\), así que no puede ser divisible ni por \(2\) ni por \(5\). Ambos pertenecen necesariamente a la suma final.
El primo \(3\) es especial por otra razón: aquí no puede usarse la equivalencia anterior, porque \(9\) no es invertible módulo \(3\). En cambio,
$$R(k)=1+10+\cdots+10^{k-1}\equiv 1+1+\cdots+1\equiv k \pmod 3.$$
Como \(10^n\equiv 1\pmod 3\), resulta \(R(10^n)\equiv 1\pmod 3\). Por tanto, \(3\) nunca divide ningún \(R(10^n)\), aunque sí divide otros repunits como \(R(3)\).
Un ejemplo típico es \(p=17\). Se tiene \(\operatorname{ord}_{17}(10)=16=2^4\). Como \(16\mid 10^4\), el primo \(17\) divide \(R(10^4)\) y por eso no se suma.
En cambio, para \(p=19\) se obtiene \(\operatorname{ord}_{19}(10)=18=2\cdot 3^2\). El factor adicional \(3\) impide que \(18\) divida a cualquier \(10^n\). Así, \(19\) nunca divide un \(R(10^n)\) y sí debe sumarse.
Otro control útil es \(p=7\). Su orden es \(6=2\cdot 3\). Eso significa que \(7\) divide \(R(6)\), pero jamás divide un \(R(10^n)\). Justamente esa diferencia es la que explota el problema.
Para todo primo \(p\notin\{2,5\}\), el pequeño teorema de Fermat da \(10^{p-1}\equiv 1\pmod p\). En consecuencia, \(\operatorname{ord}_p(10)\) divide a \(p-1\). Por eso las implementaciones empiezan con el candidato \(p-1\) en lugar de buscar desde \(1\) hacia arriba.
Supongamos que el candidato actual es \(d\), y que \(q\) es un factor primo de \(d\). Si
$$10^{d/q}\equiv 1 \pmod p,$$
entonces el orden real ya divide a \(d/q\), de modo que el factor \(q\) puede eliminarse. Repetir la prueba mientras siga funcionando mantiene el invariante de que el orden verdadero divide al candidato actual.
Cuando ya no puede quitarse ningún factor primo más, el candidato restante es el menor exponente positivo que produce \(1\), y por tanto coincide exactamente con \(\operatorname{ord}_p(10)\). Después solo queda eliminar las potencias de \(2\) y \(5\): si queda algo mayor que \(1\), el primo pertenece a la suma buscada.
Las implementaciones en C++, Python y Java generan primero todos los primos menores que el límite mediante un tamiz. Durante ese recorrido, los primos \(2\), \(3\) y \(5\) se tratan de forma inmediata como no divisores seguros de todo \(R(10^n)\).
Para cada otro primo \(p\), la implementación empieza con \(p-1\), factoriza ese valor en sus divisores primos distintos y va reduciendo el candidato al orden siempre que una prueba de exponenciación modular demuestre que un divisor más pequeño sigue siendo válido. Así se obtiene el orden multiplicativo exacto de \(10\) módulo \(p\).
Después, el código elimina de ese orden todos los factores \(2\) y \(5\). Si el valor reducido es \(1\), entonces el primo sí puede dividir algún \(R(10^n)\) y se descarta; si no, se añade al total. Las versiones de C++ y Python usan exponenciación binaria; la de Java utiliza la rutina estándar de potencias modulares con enteros grandes. El criterio matemático es exactamente el mismo en los tres casos.
Si el límite de búsqueda es \(L\), el tamiz cuesta \(O(L\log\log L)\) tiempo y \(O(L)\) memoria. En este problema \(L=10^5\), así que esa parte es muy pequeña.
Para un primo \(p\), el cálculo del orden factoriza \(p-1\) por división de prueba hasta \(\sqrt{p-1}\), y cada intento de reducción requiere una exponenciación modular en \(O(\log p)\) multiplicaciones. Como por debajo de \(10^5\) solo hay \(9592\) primos, el tiempo total es sobradamente cómodo, y la memoria está dominada por el arreglo del tamiz.
设 \(R(k)=\frac{10^k-1}{9}=11\ldots1\) 为长度为 \(k\) 的 repunit。题目要求求出所有满足 \(p<10^5\) 的质数 \(p\) 之和，其中不存在任何 \(n\ge 1\) 使得 \(p\mid R(10^n)\)。
这道题的关键不是去构造巨大的 \(R(10^n)\)，而是判断对每个质数 \(p\) 而言，是否存在某个 \(10^n\) 作为合适的长度。这个判断可以完全转化为模 \(p\) 下 \(10\) 的乘法性质。
三种实现都把问题压缩成一个同样的判定：求出 \(10\) 在模 \(p\) 下的乘法阶，然后看这个阶是否只由 \(2\) 和 \(5\) 组成。一旦这一点明确，题目就已经解决了。
对任意 \(k\ge 1\)，都有
$$R(k)=1+10+10^2+\cdots+10^{k-1}=\frac{10^k-1}{9}.$$
如果 \(p\notin\{2,3,5\}\)，那么 \(9\) 在模 \(p\) 下可逆，因此乘以 \(9\) 不会改变是否被 \(p\) 整除。于是
$$p\mid R(k)\iff 10^k\equiv 1 \pmod p.$$
本题中的长度不是任意的 \(k\)，而是严格限制为 \(k=10^n\)。所以对于除 \(2\)、\(3\)、\(5\) 之外的质数，问题就变成：是否存在某个 \(n\ge 1\)，使得
$$10^{10^n}\equiv 1 \pmod p$$
成立。
记
$$t=\operatorname{ord}_p(10),$$
即满足 \(10^t\equiv 1\pmod p\) 的最小正整数。按照乘法阶的定义，\(10^m\equiv 1\pmod p\) 当且仅当 \(t\mid m\)。因此
$$p\mid R(10^n)\iff t\mid 10^n.$$
而 \(10^n=2^n5^n\)，它的质因子只有 \(2\) 与 \(5\)。所以，只有当 \(t\) 的全部质因子也都属于 \(\{2,5\}\) 时，\(t\) 才可能整除某个 \(10^n\)。换句话说，把 \(t\) 里的所有 \(2\) 和 \(5\) 因子全部去掉以后，必须正好剩下 \(1\)。
于是对于每个 \(p\notin\{2,3,5\}\)，有精确判据
$$p\text{ 能整除某个 }R(10^n)\iff \operatorname{ord}_p(10)=2^a5^b\text{，其中 }a,b\ge 0.$$
反方向同样重要：如果 \(t=2^a5^b\)，只要取 \(n\ge \max(a,b)\)，就有 \(t\mid 10^n\)，因此这个质数确实会整除某个题目要求的 repunit。
\(2\) 和 \(5\) 最容易处理。任何 repunit 的最后一位都是 \(1\)，所以它绝不可能被 \(2\) 或 \(5\) 整除。这两个质数一定要计入答案。
\(3\) 的情况不同。这里不能直接使用前面的等价式，因为 \(9\) 在模 \(3\) 下不可逆。应当直接写出
$$R(k)=1+10+\cdots+10^{k-1}\equiv 1+1+\cdots+1\equiv k \pmod 3.$$
由于 \(10^n\equiv 1\pmod 3\)，可得 \(R(10^n)\equiv 1\pmod 3\)。因此 \(3\) 永远不会整除任何 \(R(10^n)\)，尽管它确实会整除别的 repunit，例如 \(R(3)\)。
看一个典型的正反例。对 \(p=17\)，有 \(\operatorname{ord}_{17}(10)=16=2^4\)。因为 \(16\mid 10^4\)，所以 \(17\mid R(10^4)\)，因此 \(17\) 不应计入答案。
再看 \(p=19\)。这里 \(\operatorname{ord}_{19}(10)=18=2\cdot 3^2\)。多出来的因子 \(3\) 使得 \(18\) 不可能整除任何 \(10^n\)，所以 \(19\) 永远不会整除 \(R(10^n)\)，必须计入答案。
还有一个很好的检查例子是 \(p=7\)。它的乘法阶是 \(6=2\cdot 3\)。因此 \(7\) 的确整除 \(R(6)\)，但从不整除任何 \(R(10^n)\)。题目要区分的正是“会整除某个 repunit”和“会整除某个长度恰好为 \(10^n\) 的 repunit”这两件事。
对任意 \(p\notin\{2,5\}\) 的质数，费马小定理给出 \(10^{p-1}\equiv 1\pmod p\)。这说明 \(\operatorname{ord}_p(10)\) 必定整除 \(p-1\)。因此实现里不是从小到大试探，而是直接把 \(p-1\) 当作初始候选值。
设当前候选值为 \(d\)，\(q\) 是 \(d\) 的一个质因子。如果
$$10^{d/q}\equiv 1 \pmod p,$$
那么真正的乘法阶其实已经整除 \(d/q\)，所以这个 \(q\) 可以去掉。只要该测试继续成立，就可以继续约掉这个因子。整个过程中保持的不变量是：真正的乘法阶始终整除当前候选值。
当再也不能去掉任何质因子时，剩下的候选值就是最小的正指数，也就正是 \(\operatorname{ord}_p(10)\)。随后再把其中所有的 \(2\) 和 \(5\) 因子去掉；如果剩余结果不是 \(1\)，这个质数就属于题目要求的“永远不会整除 \(R(10^n)\)”的集合。
C++、Python 和 Java 的实现首先都用筛法生成上界以下的全部质数。遍历时，\(2\)、\(3\)、\(5\) 会立刻作为必然不会整除任何 \(R(10^n)\) 的质数加入统计。
对其他每个质数 \(p\)，实现都从 \(p-1\) 出发，对它做质因数分解，并不断利用模幂测试判断某个更小的除数是否依然可以作为候选阶。如果可以，就继续把该质因子约掉。这样最终得到的就是 \(10\) 在模 \(p\) 下的精确乘法阶。
找到这个阶之后，代码会继续剥去所有 \(2\) 和 \(5\) 的因子。若最后剩下 \(1\)，说明该质数能整除某个 \(R(10^n)\)，因此不计入和；若剩下的值大于 \(1\)，则把该质数加入答案。C++ 与 Python 使用二进制快速幂，Java 使用标准的大整数模幂接口，但三者做的是完全相同的数学判断。
若搜索上界为 \(L\)，筛法部分的时间复杂度是 \(O(L\log\log L)\)，空间复杂度是 \(O(L)\)。本题中 \(L=10^5\)，这一部分非常轻量。
对每个质数 \(p\)，阶的计算需要对 \(p-1\) 做到 \(\sqrt{p-1}\) 为止的试除分解，而每次尝试缩小候选阶时都要进行一次 \(O(\log p)\) 次乘法的模幂运算。由于 \(10^5\) 以下只有 \(9592\) 个质数，总运行时间十分宽松，内存开销主要由筛数组构成。
Пусть \(R(k)=\frac{10^k-1}{9}=11\ldots1\) обозначает репьюнит из \(k\) цифр. Требуется найти сумму всех простых чисел \(p<10^5\), для которых не существует ни одного \(n\ge 1\) с условием \(p\mid R(10^n)\).
Строить сами гигантские числа \(R(10^n)\) не нужно. Для каждого простого числа вопрос решается только через мультипликативное поведение числа \(10\) по модулю \(p\).
Во всех реализациях задача сводится к одному и тому же критерию: нужно найти мультипликативный порядок числа \(10\) по модулю \(p\), а затем проверить, состоят ли его простые множители только из \(2\) и \(5\).
Для любого \(k\ge 1\) имеем
$$R(k)=1+10+10^2+\cdots+10^{k-1}=\frac{10^k-1}{9}.$$
Если \(p\notin\{2,3,5\}\), то число \(9\) обратимо по модулю \(p\), поэтому умножение на \(9\) не меняет делимость на \(p\). Отсюда
$$p\mid R(k)\iff 10^k\equiv 1 \pmod p.$$
В нашей задаче длина не произвольна, а имеет вид \(k=10^n\). Значит, для всех простых чисел, кроме \(2\), \(3\) и \(5\), нужно понять, существует ли \(n\ge 1\), для которого
$$10^{10^n}\equiv 1 \pmod p.$$
Обозначим через
$$t=\operatorname{ord}_p(10)$$
наименьшее положительное число, для которого \(10^t\equiv 1\pmod p\). По определению, сравнение \(10^m\equiv 1\pmod p\) выполняется тогда и только тогда, когда \(t\mid m\). Следовательно,
$$p\mid R(10^n)\iff t\mid 10^n.$$
Но \(10^n=2^n5^n\), а значит, его простые делители могут быть только \(2\) и \(5\). Поэтому \(t\) делит некоторое \(10^n\) тогда и только тогда, когда все простые делители самого \(t\) тоже принадлежат множеству \(\{2,5\}\). Эквивалентно: если удалить из \(t\) все множители \(2\) и \(5\), должен остаться ровно \(1\).
Итак, для любого простого \(p\notin\{2,3,5\}\),
$$p\text{ делит некоторое }R(10^n)\iff \operatorname{ord}_p(10)=2^a5^b\text{ для некоторых }a,b\ge 0.$$
Обратное утверждение тоже существенно: если \(t=2^a5^b\), то при выборе \(n\ge \max(a,b)\) получаем \(t\mid 10^n\), и такой простой действительно делит один из нужных репьюнитов.
С числами \(2\) и \(5\) всё сразу ясно. Любой репьюнит оканчивается цифрой \(1\), поэтому он не делится ни на \(2\), ни на \(5\). Оба этих простых числа обязательно входят в итоговую сумму.
Число \(3\) является особым по другой причине: здесь нельзя применять предыдущую эквивалентность, потому что \(9\) не обратимо по модулю \(3\). Вместо этого надо записать
$$R(k)=1+10+\cdots+10^{k-1}\equiv 1+1+\cdots+1\equiv k \pmod 3.$$
Так как \(10^n\equiv 1\pmod 3\), имеем \(R(10^n)\equiv 1\pmod 3\). Значит, \(3\) никогда не делит ни один \(R(10^n)\), хотя делит другие репьюниты, например \(R(3)\).
Хороший пример обычного случая: \(p=17\). Для него \(\operatorname{ord}_{17}(10)=16=2^4\). Поскольку \(16\mid 10^4\), число \(17\) делит \(R(10^4)\), поэтому в сумму оно не входит.
Для \(p=19\) получаем \(\operatorname{ord}_{19}(10)=18=2\cdot 3^2\). Лишний множитель \(3\) означает, что \(18\) не делит ни одно число вида \(10^n\). Поэтому \(19\) никогда не делит \(R(10^n)\) и должно быть включено в ответ.
Полезная проверка — \(p=7\). Его порядок равен \(6=2\cdot 3\). Значит, \(7\) делит \(R(6)\), но не делит ни один \(R(10^n)\). Именно это различие и составляет суть задачи.
Для любого простого \(p\notin\{2,5\}\) малая теорема Ферма даёт \(10^{p-1}\equiv 1\pmod p\). Следовательно, \(\operatorname{ord}_p(10)\) является делителем числа \(p-1\). Поэтому реализации начинают не с перебора вверх от \(1\), а сразу с кандидата \(p-1\).
Пусть текущий кандидат равен \(d\), а \(q\) — простой делитель числа \(d\). Если выполняется
$$10^{d/q}\equiv 1 \pmod p,$$
то истинный порядок уже делит \(d/q\), и множитель \(q\) можно удалить. Повторяя проверку, пока она успешна, мы сохраняем инвариант: настоящий порядок всегда делит текущий кандидат.
Когда ни один простой множитель уже нельзя убрать, остаётся минимальный положительный показатель, дающий значение \(1\), то есть ровно \(\operatorname{ord}_p(10)\). После этого из него удаляются все множители \(2\) и \(5\); если остаётся не \(1\), простой входит в искомую сумму.
Реализации на C++, Python и Java сначала строят все простые числа ниже предела с помощью решета. Во время этого прохода числа \(2\), \(3\) и \(5\) сразу классифицируются как гарантированные неделители любого \(R(10^n)\).
Для каждого другого простого \(p\) программа начинает с \(p-1\), раскладывает это число на различные простые множители и уменьшает кандидат на порядок всякий раз, когда проверка модульным возведением в степень показывает, что меньший делитель всё ещё подходит. В результате получается точный мультипликативный порядок числа \(10\) по модулю \(p\).
Затем из найденного порядка удаляются все множители \(2\) и \(5\). Если после этого остаётся \(1\), значит, простой делит некоторое \(R(10^n)\), и его пропускают. Иначе он добавляется к сумме. В версиях на C++ и Python используется двоичное возведение в степень; в Java — стандартная модульная степень для больших целых. Математический критерий везде одинаков.
Если верхняя граница поиска равна \(L\), то решето работает за \(O(L\log\log L)\) времени и требует \(O(L)\) памяти. Здесь \(L=10^5\), поэтому эта часть очень мала.
Для простого \(p\) вычисление порядка требует разложения числа \(p-1\) пробным делением до \(\sqrt{p-1}\), а каждая попытка уменьшить кандидат использует модульное возведение в степень за \(O(\log p)\) умножений. Ниже \(10^5\) находится только \(9592\) простых числа, поэтому общее время работы невелико; память в основном уходит на массив решета.
لنكتب \(R(k)=\frac{10^k-1}{9}=11\ldots1\) لعدد الـ repunit ذي \(k\) أرقام. المطلوب هو إيجاد مجموع جميع الأعداد الأولية \(p<10^5\) التي لا يوجد لأي منها عدد صحيح \(n\ge 1\) يحقق \(p\mid R(10^n)\).
الفكرة الأساسية هي أننا لا نحتاج إلى بناء الأعداد الهائلة \(R(10^n)\) نفسها. القرار لكل عدد أولي يعتمد فقط على السلوك الضربي للعدد \(10\) بترديد ذلك العدد الأولي.
كل تنفيذ من التنفيذات الثلاثة يحول المسألة إلى اختبار واحد واضح: نحسب الرتبة الضربية للعدد \(10\) modulo \(p\)، ثم نرى هل تتكوّن هذه الرتبة من العوامل الأولية \(2\) و\(5\) فقط أم لا.
لكل \(k\ge 1\) لدينا
$$R(k)=1+10+10^2+\cdots+10^{k-1}=\frac{10^k-1}{9}.$$
إذا كان \(p\notin\{2,3,5\}\)، فإن \(9\) يملك معكوسًا modulo \(p\)، ولذلك فإن الضرب في \(9\) لا يغيّر قابلية القسمة على \(p\). ومن ثم
$$p\mid R(k)\iff 10^k\equiv 1 \pmod p.$$
في هذه المسألة طول الـ repunit ليس \(k\) عامًا، بل هو على الصورة \(k=10^n\). إذن، بالنسبة إلى جميع الأعداد الأولية ما عدا \(2\) و\(3\) و\(5\)، يصبح السؤال: هل يوجد \(n\ge 1\) بحيث
$$10^{10^n}\equiv 1 \pmod p$$
؟
ليكن
$$t=\operatorname{ord}_p(10),$$
أي أصغر عدد صحيح موجب يحقق \(10^t\equiv 1\pmod p\). بحسب التعريف، يتحقق \(10^m\equiv 1\pmod p\) إذا وفقط إذا كان \(t\mid m\). لذلك نحصل على
$$p\mid R(10^n)\iff t\mid 10^n.$$
لكن \(10^n=2^n5^n\)، ولذلك فإن عوامله الأولية الوحيدة هي \(2\) و\(5\). من هنا يكون \(t\) قاسمًا لبعض \(10^n\) إذا وفقط إذا كانت جميع عوامله الأولية هي أيضًا \(2\) أو \(5\). وبصياغة مكافئة: بعد حذف كل عوامل \(2\) و\(5\) من \(t\)، يجب ألا يبقى شيء سوى \(1\).
إذن المعيار الدقيق لكل عدد أولي \(p\notin\{2,3,5\}\) هو الآتي: العدد \(p\) يقسم بعض \(R(10^n)\) إذا وفقط إذا كانت \(\operatorname{ord}_p(10)=2^a5^b\) لبعض \(a,b\ge 0\).
والاتجاه العكسي مهم أيضًا: إذا كانت \(t=2^a5^b\)، فإن اختيار \(n\ge \max(a,b)\) يضمن \(t\mid 10^n\)، وبالتالي فإن هذا العدد الأولي يقسم فعلًا أحد أعداد repunit المطلوبة.
الحالتان \(2\) و\(5\) مباشرتان. كل repunit ينتهي بالرقم \(1\)، ولهذا فهو لا يقبل القسمة على \(2\) ولا على \(5\). لذلك يجب إدخال هذين العددين في المجموع النهائي.
أما \(3\) فهو حالة خاصة لسبب مختلف: لا يجوز استخدام التكافؤ السابق هنا لأن \(9\) ليس قابلاً للعكس modulo \(3\). بدلًا من ذلك نكتب
$$R(k)=1+10+\cdots+10^{k-1}\equiv 1+1+\cdots+1\equiv k \pmod 3.$$
وبما أن \(10^n\equiv 1\pmod 3\)، نحصل على \(R(10^n)\equiv 1\pmod 3\). إذن \(3\) لا يقسم أي \(R(10^n)\) على الإطلاق، رغم أنه يقسم repunits أخرى مثل \(R(3)\).
مثال نموذجي هو \(p=17\). هنا نجد أن \(\operatorname{ord}_{17}(10)=16=2^4\). وبما أن \(16\mid 10^4\)، فإن \(17\) يقسم \(R(10^4)\)، ولذلك لا يدخل في المجموع.
بالمقابل، عند \(p=19\) تكون الرتبة \(\operatorname{ord}_{19}(10)=18=2\cdot 3^2\). وجود العامل \(3\) يعني أن \(18\) لا يقسم أي \(10^n\)، ومن ثم فإن \(19\) لا يقسم أي \(R(10^n)\) ويجب إضافته إلى الجواب.
وهناك فحص مفيد آخر هو \(p=7\). رتبته هي \(6=2\cdot 3\). لذا فإن \(7\) يقسم \(R(6)\)، لكنه لا يقسم أي \(R(10^n)\). وهذا بالتحديد هو الفرق الذي تختبره المسألة.
لكل عدد أولي \(p\notin\{2,5\}\)، تعطينا مبرهنة فيرما الصغرى العلاقة \(10^{p-1}\equiv 1\pmod p\). وهذا يعني أن \(\operatorname{ord}_p(10)\) يقسم \(p-1\). لذلك تبدأ التنفيذات من المرشح \(p-1\) بدل البحث تصاعديًا من \(1\).
لنفرض أن المرشح الحالي هو \(d\)، وأن \(q\) عامل أولي لـ \(d\). إذا تحقق
$$10^{d/q}\equiv 1 \pmod p,$$
فإن الرتبة الحقيقية تقسم بالفعل \(d/q\)، وبالتالي يمكن حذف العامل \(q\). تكرار هذا الاختبار كلما نجح يحافظ على ثابت أساسي: الرتبة الحقيقية دائمًا تقسم المرشح الحالي.
وعندما لا يعود من الممكن حذف أي عامل أولي إضافي، يكون المرشح المتبقي هو أصغر أس موجب يعطي القيمة \(1\)، أي أنه يساوي بالضبط \(\operatorname{ord}_p(10)\). بعد ذلك تُزال جميع عوامل \(2\) و\(5\) من هذه الرتبة؛ فإذا بقي شيء غير \(1\)، فإن العدد الأولي يُضاف إلى المجموع المطلوب.
تنفيذات C++ وPython وJava تبدأ أولًا بتوليد جميع الأعداد الأولية الأصغر من الحد باستخدام الغربال. وأثناء المرور عليها، تُعامل الأعداد \(2\) و\(3\) و\(5\) مباشرة بوصفها أعدادًا لا يمكن أن تقسم أي \(R(10^n)\).
بالنسبة إلى كل عدد أولي آخر \(p\)، يبدأ التنفيذ من \(p-1\)، ويفكك هذا العدد إلى عوامله الأولية المختلفة، ثم يقلل مرشح الرتبة كلما أثبت اختبار الأس المعياري أن قاسمًا أصغر ما زال صالحًا. بهذه الطريقة نحصل على الرتبة الضربية الدقيقة للعدد \(10\) modulo \(p\).
بعد إيجاد الرتبة، يزيل الكود منها جميع عوامل \(2\) و\(5\). إذا أصبحت النتيجة \(1\)، فهذا يعني أن العدد الأولي يقسم بعض \(R(10^n)\) فيُستبعد. أما إذا بقيت قيمة أكبر من \(1\)، فيُضاف هذا العدد الأولي إلى المجموع. تستعمل نسختا C++ وPython الأس السريع بالتربيع المتكرر، بينما تستخدم نسخة Java الدالة القياسية لرفع الأعداد الكبيرة modulo. الاختبار الرياضي نفسه واحد في اللغات الثلاث.
إذا كان حد البحث هو \(L\)، فإن مرحلة الغربال تكلف \(O(L\log\log L)\) زمنًا و\(O(L)\) مساحة. وهنا \(L=10^5\)، لذا فهذه الكلفة صغيرة جدًا.
لكل عدد أولي \(p\)، يتطلب حساب الرتبة تحليل \(p-1\) بالقسمة التجريبية حتى \(\sqrt{p-1}\)، كما أن كل محاولة لتقليل المرشح تحتاج إلى رفع معياري بكلفة \(O(\log p)\) من الضربات. وبما أن عدد الأعداد الأولية تحت \(10^5\) هو فقط \(9592\)، فإن الزمن الإجمالي مريح جدًا، بينما تهيمن مصفوفة الغربال على استهلاك الذاكرة.