Let \(R_n\) denote the base-10 repunit with \(n\) digits, so
$$R_n = 11\ldots1 = 1 + 10 + 10^2 + \cdots + 10^{n-1} = \frac{10^n - 1}{9}.$$
The task is to find the sum of the first 40 prime numbers dividing \(R_{10^9}\). Since \(R_{10^9}\) has a billion decimal digits, direct construction or factorization is completely out of the question. The solution works by testing primes through modular arithmetic instead of touching the gigantic integer itself.
The whole problem becomes manageable once divisibility of repunits is rewritten in terms of powers of 10 modulo a small number. After that, the only remaining job is to scan primes in increasing order and keep the first 40 that satisfy the derived condition.
Because \(R_n\) is a finite geometric sum, multiplying by 9 gives
$$10^n - 1 = 9R_n.$$
If \(p\) is a prime different from \(2\) and \(5\), then \(10\) is invertible modulo \(9p\), and the divisibility test becomes
$$p \mid R_n \iff 9p \mid (10^n - 1) \iff 10^n \equiv 1 \pmod{9p}.$$
This is exactly the condition used by the Python and Java implementations. The primes \(2\) and \(5\) can be discarded immediately, because every repunit ends in the digit 1 and therefore is divisible by neither 2 nor 5.
For \(p \neq 2,5\), define
$$a_p = \operatorname{ord}_{9p}(10),$$
the smallest positive exponent for which \(10^{a_p} \equiv 1 \pmod{9p}\). Then the previous congruence is equivalent to
$$p \mid R_n \iff a_p \mid n.$$
Now specialize to \(n = 10^9 = 2^9 \cdot 5^9\). Any admissible order \(a_p\) must divide \(10^9\), so the prime factors of \(a_p\) can only be 2 or 5. That immediately removes many primes. For example, \(10^2 \equiv 1 \pmod{99}\), so \(a_{11} = 2\), which means \(11 \mid R_{10^9}\). In contrast, \(10^6 \equiv 1 \pmod{63}\) and no smaller positive exponent works, so \(a_7 = 6\). Since \(6 \nmid 10^9\), the prime 7 cannot divide the target repunit.
Repunits also satisfy a composition identity:
$$R_{m+n} = R_m 10^n + R_n.$$
If \(n = qm\), repeated use of that formula gives
$$R_n = R_m\left(1 + 10^m + 10^{2m} + \cdots + 10^{(q-1)m}\right),$$
so \(R_m \mid R_n\) whenever \(m \mid n\). This is a convenient way to build examples. Since \(10 \mid 10^9\), every prime divisor of \(R_{10}\) is automatically a prime divisor of \(R_{10^9}\). The factorization
$$R_{10} = 1111111111 = 11 \cdot 41 \cdot 271 \cdot 9091$$
already provides four qualifying primes. The same idea explains why the small checkpoint \(R_6\) is useful: because \(R_6 = 3 \cdot 7 \cdot 11 \cdot 13 \cdot 37\), the first four prime factors sum to \(34\).
The prime 3 is not excluded for the same reason as 2 and 5, but it behaves differently from the generic order discussion because \(9\) already appears in the repunit formula. Here the simplest test is
$$R_n = 1 + 10 + \cdots + 10^{n-1} \equiv 1 + 1 + \cdots + 1 \equiv n \pmod{3}.$$
Therefore \(3 \mid R_n\) exactly when \(3 \mid n\). For \(n = 10^9\), we have \(10^9 \equiv 1 \pmod{3}\), so \(3\) is not a factor of \(R_{10^9}\). This matches the explicit checkpoint behavior in the C++ implementation: 3 divides \(R_3\), but it does not divide \(R_{10}\).
The C++ implementation checks divisibility in an equivalent way: instead of testing \(10^n \bmod 9p\), it computes \(R_n \bmod p\) directly. The key identities are
$$R_{2m} = R_m(10^m + 1), \qquad R_{2m+1} = 10R_{2m} + 1.$$
These come straight from the composition formula above. When reading the binary digits of \(n\), the algorithm maintains the invariant
$$\text{repunit} \equiv R_m \pmod{q}, \qquad \text{power} \equiv 10^m \pmod{q},$$
for the prefix length \(m\) processed so far. A doubling step moves from \(m\) to \(2m\); if the next bit is 1, one extra digit 1 is appended and the state moves from \(2m\) to \(2m+1\). That yields an \(O(\log n)\) test even though \(n = 10^9\) is enormous.
The implementations search upward through the primes in increasing order and stop as soon as 40 qualifying primes have been found. They all skip \(2\) and \(5\) immediately. The supplied C++, Python, and Java versions generate primes by trial division rather than by a sieve, which is perfectly adequate because the first 40 successful primes appear relatively early.
The Python and Java implementations use the congruence
$$10^{10^9} \equiv 1 \pmod{9p}.$$
They evaluate it with modular exponentiation by repeated squaring, so the billion-sized exponent only costs about \(\log_2(10^9)\) bit steps. The C++ implementation uses the equivalent test \(R_{10^9} \equiv 0 \pmod p\) and obtains that remainder with the doubling recurrence for repunits. Mathematically the two tests are the same; they just package the modular arithmetic in different ways.
Whenever a prime passes the divisibility test, it is added to the running sum and the counter of accepted primes is incremented. The C++ version also includes small checkpoint cases to validate the logic before running the full search: the first four prime factors of \(R_{10}\) sum to \(9414\), the first four prime factors of \(R_6\) sum to \(34\), and the prime 3 only divides repunits whose length is a multiple of 3.
For one candidate prime \(p\), the arithmetic test costs \(O(\log n)\) modular multiplications with \(n = 10^9\). In practice that is only about 30 binary steps, whether one uses modular exponentiation or the doubling recurrence for \(R_n\).
If \(M\) is the largest number examined before the 40th valid prime is found, then the overall running time is dominated by prime generation plus 40-odd successful or unsuccessful modular tests along the way. Because the implementations use trial division, a simple upper-bound model is roughly \(O(M\sqrt{M})\) for the search phase, with very small memory usage. The C++ version stores a short list of previously found primes, while the Python and Java versions use essentially constant auxiliary space beyond ordinary integer arithmetic.
Sei \(R_n\) die dezimale Repunit mit \(n\) Einsen, also
$$R_n = 11\ldots1 = 1 + 10 + 10^2 + \cdots + 10^{n-1} = \frac{10^n - 1}{9}.$$
Gesucht ist die Summe der ersten 40 Primzahlen, die \(R_{10^9}\) teilen. Da \(R_{10^9}\) eine Milliarde Stellen hat, ist weder eine direkte Konstruktion noch eine direkte Faktorisierung realistisch. Die Lösung ersetzt das riesige Objekt vollständig durch modulare Tests für einzelne Primzahlen.
Entscheidend ist, die Aussage „\(p\) ist ein Primfaktor von \(R_n\)“ in eine schnelle Kongruenz umzuschreiben. Danach genügt es, Primzahlen der Größe nach zu durchsuchen und die ersten 40 Treffer zu summieren.
Aus der Darstellung als endliche geometrische Summe folgt sofort
$$10^n - 1 = 9R_n.$$
Für eine Primzahl \(p \neq 2,5\) erhält man damit den Test
$$p \mid R_n \iff 9p \mid (10^n - 1) \iff 10^n \equiv 1 \pmod{9p}.$$
Genau diese Form verwenden die Python- und Java-Implementierungen. Die Primzahlen \(2\) und \(5\) scheiden sofort aus, weil jede Repunit auf die Ziffer 1 endet und daher weder durch 2 noch durch 5 teilbar ist.
Für \(p \neq 2,5\) sei
$$a_p = \operatorname{ord}_{9p}(10),$$
also der kleinste positive Exponent mit \(10^{a_p} \equiv 1 \pmod{9p}\). Dann gilt äquivalent
$$p \mid R_n \iff a_p \mid n.$$
Im vorliegenden Problem ist \(n = 10^9 = 2^9 \cdot 5^9\). Also darf \(a_p\) nur aus den Primfaktoren 2 und 5 bestehen. Das verwirft sehr viele Kandidaten. Zum Beispiel gilt \(10^2 \equiv 1 \pmod{99}\), also \(a_{11} = 2\), und deshalb teilt \(11\) die Zahl \(R_{10^9}\). Dagegen gilt \(10^6 \equiv 1 \pmod{63}\), aber kein kleinerer positiver Exponent funktioniert; daher ist \(a_7 = 6\). Weil \(6 \nmid 10^9\), kann 7 kein Faktor der Zielzahl sein.
Repunits erfüllen außerdem die Kompositionsformel
$$R_{m+n} = R_m 10^n + R_n.$$
Ist \(n = qm\), so folgt durch wiederholtes Anwenden
$$R_n = R_m\left(1 + 10^m + 10^{2m} + \cdots + 10^{(q-1)m}\right),$$
also \(R_m \mid R_n\), sobald \(m \mid n\) gilt. Damit lassen sich konkrete Beispiele sofort erzeugen. Weil \(10 \mid 10^9\), ist jeder Primfaktor von \(R_{10}\) automatisch auch ein Primfaktor von \(R_{10^9}\). Aus
$$R_{10} = 1111111111 = 11 \cdot 41 \cdot 271 \cdot 9091$$
kommen bereits vier gültige Primzahlen. Dieselbe Idee erklärt auch den kleinen Kontrollfall \(R_6\): Da \(R_6 = 3 \cdot 7 \cdot 11 \cdot 13 \cdot 37\), ist die Summe der ersten vier Primfaktoren gleich \(34\).
Die 3 wird nicht wie 2 und 5 ausgeschlossen, verhält sich aber wegen des Faktors 9 in der Formel etwas besonders. Der einfachste Test ist
$$R_n = 1 + 10 + \cdots + 10^{n-1} \equiv 1 + 1 + \cdots + 1 \equiv n \pmod{3}.$$
Daher gilt \(3 \mid R_n\) genau dann, wenn \(3 \mid n\). Für \(n = 10^9\) hat man \(10^9 \equiv 1 \pmod{3}\), also ist 3 kein Faktor von \(R_{10^9}\). Genau das bestätigt auch der Kontrolltest der C++-Implementierung: 3 teilt \(R_3\), aber nicht \(R_{10}\).
Die C++-Implementierung prüft dieselbe Bedingung in einer äquivalenten Form: Statt \(10^n \bmod 9p\) zu berechnen, bestimmt sie direkt \(R_n \bmod p\). Grundlage sind die Identitäten
$$R_{2m} = R_m(10^m + 1), \qquad R_{2m+1} = 10R_{2m} + 1.$$
Sie folgen direkt aus der allgemeinen Kompositionsformel. Beim Durchlaufen der Binärdarstellung von \(n\) hält der Algorithmus die Invariante
$$\text{Repunit-Rest} \equiv R_m \pmod{q}, \qquad \text{Potenzrest} \equiv 10^m \pmod{q},$$
wobei \(m\) die bereits verarbeitete Präfixlänge bezeichnet. Ein Verdopplungsschritt ersetzt \(m\) durch \(2m\); ist das nächste Bit gleich 1, wird eine weitere Ziffer 1 angehängt und der Zustand von \(2m\) auf \(2m+1\) erweitert. So entsteht ein \(O(\log n)\)-Test, ohne jemals die Milliardenzahl selbst zu erzeugen.
Alle Implementierungen durchsuchen die Primzahlen in aufsteigender Reihenfolge und stoppen, sobald 40 gültige Treffer gefunden sind. Die Zahlen \(2\) und \(5\) werden sofort übersprungen. Die gelieferten C++-, Python- und Java-Versionen verwenden Probeteilung statt eines Siebs, was hier völlig ausreicht, weil die ersten 40 passenden Primzahlen relativ früh auftreten.
Python und Java prüfen die Kongruenz
$$10^{10^9} \equiv 1 \pmod{9p}.$$
Dazu nutzen sie modulare Exponentiation per wiederholtem Quadrieren, sodass die Kosten nur von der Bitlänge des Exponenten abhängen. Die C++-Implementierung verwendet den äquivalenten Test \(R_{10^9} \equiv 0 \pmod p\) und berechnet diesen Rest mit der Verdopplungsrekurrenz für Repunits. Mathematisch ist beides identisch; nur die Verpackung der modularen Rechnung ist verschieden.
Besteht eine Primzahl den Test, wird sie zur laufenden Summe addiert und der Trefferzähler erhöht. Zusätzlich enthält die C++-Version kleine Kontrollfälle zur Absicherung der Herleitung: Die ersten vier Primfaktoren von \(R_{10}\) summieren sich zu \(9414\), die ersten vier Primfaktoren von \(R_6\) zu \(34\), und die Primzahl 3 teilt genau diejenigen Repunits, deren Länge ein Vielfaches von 3 ist.
Für einen einzelnen Primkandidaten kostet der arithmetische Test \(O(\log n)\) modulare Multiplikationen mit \(n = 10^9\). Praktisch bedeutet das nur ungefähr 30 Binärschritte, egal ob man modulare Exponentiation oder die Verdopplungsrekurrenz für \(R_n\) benutzt.
Sei \(M\) die größte geprüfte Zahl, bevor der 40. gültige Primfaktor gefunden wird. Dann wird die Gesamtlaufzeit von der Primzahlsuche plus den modularen Tests dominiert. Da die Implementierungen Primzahlen per Probeteilung erzeugen, liegt ein einfaches Obermodell für die Suchphase bei ungefähr \(O(M\sqrt{M})\), während der Speicherbedarf sehr klein bleibt. Die C++-Version speichert zusätzlich nur eine kurze Liste bereits gefundener Primzahlen; Python und Java benötigen darüber hinaus praktisch keinen nennenswerten Zusatzspeicher.
\(R_n\), onluk tabanda \(n\) tane 1 rakamından oluşan repunit olsun:
$$R_n = 11\ldots1 = 1 + 10 + 10^2 + \cdots + 10^{n-1} = \frac{10^n - 1}{9}.$$
İstenen şey, \(R_{10^9}\) sayısını bölen ilk 40 asalın toplamıdır. \(R_{10^9}\) bir milyar basamaklı olduğu için bu sayıyı doğrudan üretmek ya da klasik anlamda çarpanlara ayırmak mümkün değildir. Çözüm, dev sayının kendisiyle uğraşmak yerine asal adaylarını modüler aritmetik ile test eder.
Temel fikir, “\(p\) asalı \(R_n\)'i böler” ifadesini çok daha küçük modüller üzerinde kontrol edilebilen bir kongruansa dönüştürmektir. Bundan sonra iş, asalları artan sırayla tarayıp koşulu sağlayan ilk 40 tanesini toplamaktan ibarettir.
Repunit tanımından hemen
$$10^n - 1 = 9R_n$$
eşitliği gelir. \(p \neq 2,5\) olan bir asal için bundan şu test çıkar:
$$p \mid R_n \iff 9p \mid (10^n - 1) \iff 10^n \equiv 1 \pmod{9p}.$$
Python ve Java uygulamaları tam olarak bu koşulu kullanır. \(2\) ve \(5\) ise en baştan elenir; çünkü her repunit son basamağı 1 olan tek bir sayıdır ve dolayısıyla 2'ye de 5'e de bölünmez.
\(p \neq 2,5\) için
$$a_p = \operatorname{ord}_{9p}(10)$$
olsun; yani \(10^{a_p} \equiv 1 \pmod{9p}\) yapan en küçük pozitif üs. O zaman
$$p \mid R_n \iff a_p \mid n$$
olur. Bizim problemimizde \(n = 10^9 = 2^9 \cdot 5^9\). Demek ki uygun bir \(a_p\) yalnızca 2 ve 5 asal çarpanlarını içerebilir. Bu gözlem çok sayıda asalı anında dışarı atar. Örneğin \(10^2 \equiv 1 \pmod{99}\) olduğundan \(a_{11} = 2\) ve dolayısıyla \(11\), \(R_{10^9}\)'i böler. Buna karşılık \(10^6 \equiv 1 \pmod{63}\) ve daha küçük pozitif bir üs işe yaramaz; yani \(a_7 = 6\). \(6\), \(10^9\)'u bölmediği için 7 hedef sayının çarpanı olamaz.
Repunit'ler şu birleşim özdeşliğini sağlar:
$$R_{m+n} = R_m 10^n + R_n.$$
Eğer \(n = qm\) ise bunu tekrarlayarak
$$R_n = R_m\left(1 + 10^m + 10^{2m} + \cdots + 10^{(q-1)m}\right)$$
elde ederiz. Dolayısıyla \(m \mid n\) ise \(R_m \mid R_n\) olur. Bu, somut örnek üretmek için çok kullanışlıdır. \(10 \mid 10^9\) olduğundan \(R_{10}\)'un her asal böleni otomatik olarak \(R_{10^9}\)'un da asal bölenidir. Gerçekten
$$R_{10} = 1111111111 = 11 \cdot 41 \cdot 271 \cdot 9091$$
eşitliği hedef listedeki ilk örnekleri verir. Aynı fikir küçük kontrol örneği \(R_6\) için de geçerlidir: \(R_6 = 3 \cdot 7 \cdot 11 \cdot 13 \cdot 37\) olduğundan ilk dört asal çarpanın toplamı \(34\) olur.
3, 2 ve 5 gibi baştan dışlanmaz; fakat formüldeki 9 çarpanı yüzünden davranışı ayrı ele alınmaya değerdir. En kısa kontrol şudur:
$$R_n = 1 + 10 + \cdots + 10^{n-1} \equiv 1 + 1 + \cdots + 1 \equiv n \pmod{3}.$$
Böylece \(3 \mid R_n\) ancak ve ancak \(3 \mid n\) iken doğrudur. Burada \(10^9 \equiv 1 \pmod{3}\) olduğu için 3, \(R_{10^9}\)'un çarpanı değildir. C++ uygulamasındaki kontrol de tam olarak bunu doğrular: 3, \(R_3\)'ü böler ama \(R_{10}\)'u bölmez.
C++ uygulaması eşdeğer bir yol izler: \(10^n \bmod 9p\) yerine doğrudan \(R_n \bmod p\) hesaplanır. Bunun temelinde
$$R_{2m} = R_m(10^m + 1), \qquad R_{2m+1} = 10R_{2m} + 1$$
özdeşlikleri vardır. Bunlar yukarıdaki birleşim formülünden doğrudan çıkar. Algoritma, \(n\)'in ikili gösterimini soldan sağa işlerken şu değişmezi korur:
$$\text{repunit kalanı} \equiv R_m \pmod{q}, \qquad \text{kuvvet kalanı} \equiv 10^m \pmod{q}.$$
Burada \(m\), o ana kadar işlenmiş uzunluğu gösterir. Katlama adımı \(m\)'yi \(2m\)'ye çıkarır; sıradaki bit 1 ise bir tane daha 1 rakamı eklenir ve durum \(2m+1\)'e genişler. Böylece \(n = 10^9\) kadar büyük olsa bile test maliyeti yalnızca \(O(\log n)\) olur.
Uygulamaların üçü de asalları artan sırayla gezer ve 40 uygun asal bulunduğu anda durur. \(2\) ve \(5\) hemen atlanır. Verilen C++, Python ve Java sürümlerinin hepsi asal üretimini elek yerine deneme bölmesi ile yapar; burada bu yaklaşım yeterlidir, çünkü ilk 40 başarılı asal çok geçte kalmaz.
Python ve Java tarafı
$$10^{10^9} \equiv 1 \pmod{9p}$$
kongruansını kontrol eder. Bu kontrol, tekrar kare alma kullanan modüler üs alma sayesinde ucuzdur; maliyet yalnızca üssün ikili uzunluğuna bağlıdır. C++ tarafı ise eşdeğer biçimde \(R_{10^9} \equiv 0 \pmod p\) testini uygular ve bu kalanı repunit katlama bağıntılarıyla elde eder. Matematik aynıdır; sadece hesaplama biçimi farklıdır.
Bir asal testi geçtiğinde hem sayaç artırılır hem de asalın değeri toplama eklenir. C++ uygulamasında ayrıca küçük doğrulama örnekleri vardır: \(R_{10}\)'un ilk dört asal çarpanı \(9414\) eder, \(R_6\)'nın ilk dört asal çarpanı \(34\) eder ve 3 yalnızca uzunluğu 3'ün katı olan repunit'leri böler.
Tek bir asal aday için aritmetik testin maliyeti \(O(\log n)\) modüler çarpmadır; burada \(n = 10^9\). Pratikte bu, modüler üs alma da kullansanız repunit katlama bağıntılarını da kullansanız yaklaşık 30 ikili adım demektir.
\(M\), 40. uygun asal bulunana kadar bakılan en büyük sayı olsun. Toplam çalışma süresi, asal taraması ile yol üzerindeki modüler testlerin toplamından oluşur. Verilen uygulamalar asalları deneme bölmesiyle ürettiği için basit bir üst sınır modeli arama aşaması için yaklaşık \(O(M\sqrt{M})\) verir. Bellek kullanımı ise çok küçüktür; C++ sürümü ek olarak yalnızca kısa bir asal listesi tutar, Python ve Java sürümleri ise bunun ötesinde neredeyse sabit ek alan kullanır.
Sea \(R_n\) el repunit decimal con \(n\) cifras iguales a 1:
$$R_n = 11\ldots1 = 1 + 10 + 10^2 + \cdots + 10^{n-1} = \frac{10^n - 1}{9}.$$
El problema pide la suma de los primeros 40 números primos que dividen a \(R_{10^9}\). Como \(R_{10^9}\) tiene mil millones de dígitos, no se puede construir ni factorizar de forma directa. La idea correcta es probar primos candidatos usando congruencias, sin manipular nunca el entero gigantesco.
La clave es convertir la condición “\(p\) divide a \(R_n\)” en una afirmación sobre potencias de 10 módulo un número pequeño. Una vez hecho eso, solo queda recorrer los primos en orden creciente y sumar los primeros 40 que cumplan la condición.
De la definición se obtiene inmediatamente
$$10^n - 1 = 9R_n.$$
Si \(p\) es un primo distinto de \(2\) y \(5\), entonces
$$p \mid R_n \iff 9p \mid (10^n - 1) \iff 10^n \equiv 1 \pmod{9p}.$$
Esta es exactamente la prueba usada por las implementaciones en Python y Java. Los primos \(2\) y \(5\) se descartan de inmediato, porque todo repunit termina en 1 y por tanto no puede ser múltiplo de 2 ni de 5.
Para \(p \neq 2,5\), definimos
$$a_p = \operatorname{ord}_{9p}(10),$$
el menor entero positivo tal que \(10^{a_p} \equiv 1 \pmod{9p}\). Entonces
$$p \mid R_n \iff a_p \mid n.$$
Aquí \(n = 10^9 = 2^9 \cdot 5^9\), así que cualquier orden admisible solo puede contener factores primos 2 y 5. Eso elimina muchísimos candidatos. Por ejemplo, \(10^2 \equiv 1 \pmod{99}\), luego \(a_{11} = 2\), y por tanto \(11\) divide a \(R_{10^9}\). En cambio, \(10^6 \equiv 1 \pmod{63}\) y ningún exponente positivo menor funciona, así que \(a_7 = 6\). Como \(6 \nmid 10^9\), el primo 7 no puede dividir al repunit objetivo.
Los repunits también satisfacen la identidad
$$R_{m+n} = R_m 10^n + R_n.$$
Si \(n = qm\), al repetir la fórmula se obtiene
$$R_n = R_m\left(1 + 10^m + 10^{2m} + \cdots + 10^{(q-1)m}\right),$$
de modo que \(R_m \mid R_n\) siempre que \(m \mid n\). Esto permite construir ejemplos concretos. Como \(10 \mid 10^9\), cualquier primo que divida a \(R_{10}\) también divide a \(R_{10^9}\). En efecto,
$$R_{10} = 1111111111 = 11 \cdot 41 \cdot 271 \cdot 9091$$
ya nos da cuatro primos válidos. La misma idea explica el pequeño caso de control \(R_6\): como \(R_6 = 3 \cdot 7 \cdot 11 \cdot 13 \cdot 37\), la suma de sus cuatro primeros factores primos es \(34\).
El primo 3 no queda excluido por la misma razón que 2 y 5, pero sí merece un tratamiento aparte por el factor 9 presente en la fórmula del repunit. El test más corto es
$$R_n = 1 + 10 + \cdots + 10^{n-1} \equiv 1 + 1 + \cdots + 1 \equiv n \pmod{3}.$$
Por tanto, \(3 \mid R_n\) exactamente cuando \(3 \mid n\). Como \(10^9 \equiv 1 \pmod{3}\), el 3 no divide a \(R_{10^9}\). Eso coincide con la verificación explícita de la implementación en C++: 3 divide a \(R_3\), pero no divide a \(R_{10}\).
La implementación en C++ usa una forma equivalente del mismo criterio: en vez de comprobar \(10^n \bmod 9p\), calcula directamente \(R_n \bmod p\). Las identidades básicas son
$$R_{2m} = R_m(10^m + 1), \qquad R_{2m+1} = 10R_{2m} + 1.$$
Ambas salen de la fórmula general de composición. Al recorrer la expansión binaria de \(n\), el algoritmo mantiene el invariante
$$\text{repunit actual} \equiv R_m \pmod{q}, \qquad \text{potencia actual} \equiv 10^m \pmod{q},$$
donde \(m\) es la longitud ya procesada. Un paso de duplicación lleva de \(m\) a \(2m\); si el siguiente bit vale 1, se añade una cifra 1 adicional y el estado pasa de \(2m\) a \(2m+1\). Así se obtiene un test de costo \(O(\log n)\) sin construir nunca el número de mil millones de cifras.
Las implementaciones recorren los primos en orden creciente y se detienen en cuanto encuentran 40 válidos. Los valores \(2\) y \(5\) se descartan desde el principio. Las versiones dadas en C++, Python y Java generan primos por división de prueba en vez de usar un tamiz, lo cual es suficiente porque los primeros 40 aciertos aparecen bastante pronto.
Python y Java verifican la congruencia
$$10^{10^9} \equiv 1 \pmod{9p}.$$
La evalúan con exponenciación modular por cuadrados repetidos, así que el costo depende solo de la longitud binaria del exponente. La versión en C++ emplea la condición equivalente \(R_{10^9} \equiv 0 \pmod p\) y obtiene ese residuo mediante la recurrencia de duplicación para repunits. Matemáticamente ambas pruebas son la misma idea expresada de dos maneras.
Cada vez que un primo supera la prueba, se añade a la suma acumulada y aumenta el contador de aciertos. La versión en C++ también incluye pequeños puntos de control para validar la lógica antes de la búsqueda grande: los cuatro primeros factores primos de \(R_{10}\) suman \(9414\), los cuatro primeros factores primos de \(R_6\) suman \(34\), y el primo 3 solo divide a los repunits cuya longitud es múltiplo de 3.
Para un primo candidato \(p\), la prueba aritmética cuesta \(O(\log n)\) multiplicaciones modulares con \(n = 10^9\). En la práctica eso significa unas 30 etapas binarias, tanto si se usa exponenciación modular como si se usa la recurrencia de duplicación de \(R_n\).
Si \(M\) es el mayor entero examinado antes de encontrar el 40.º primo válido, el tiempo total queda dominado por la generación de primos y por las pruebas modulares realizadas durante la búsqueda. Como las implementaciones usan división de prueba, un modelo simple da aproximadamente \(O(M\sqrt{M})\) para la fase de exploración, con consumo de memoria muy bajo. La versión en C++ guarda además una pequeña lista de primos ya conocidos; Python y Java, fuera de la aritmética habitual, usan espacio auxiliar prácticamente constante.
设 \(R_n\) 表示十进制下由 \(n\) 个数字 1 组成的 repunit，那么
$$R_n = 11\ldots1 = 1 + 10 + 10^2 + \cdots + 10^{n-1} = \frac{10^n - 1}{9}.$$
题目要求求出所有按从小到大出现的前 40 个素数因子之和，这些素数都必须整除 \(R_{10^9}\)。由于 \(R_{10^9}\) 有十亿位，既不可能真的把它构造出来，也不可能对这个整数做直接分解。可行的方法是只检查素数候选在模意义下是否满足某个条件。
真正有用的转化是：把“素数 \(p\) 是否整除 repunit”改写成“10 的某个幂在模 \(9p\) 下是否等于 1”。这样一来，问题就从大整数分解变成了有针对性的素数筛查。
由定义立刻得到
$$10^n - 1 = 9R_n.$$
当 \(p\) 是不等于 \(2\)、\(5\) 的素数时，可以把整除条件写成
$$p \mid R_n \iff 9p \mid (10^n - 1) \iff 10^n \equiv 1 \pmod{9p}.$$
Python 和 Java 实现正是用这个判定式。至于 \(2\) 和 \(5\)，根本不用测试，因为任何 repunit 的末位都是 1，所以绝不可能被 2 或 5 整除。
对 \(p \neq 2,5\)，定义
$$a_p = \operatorname{ord}_{9p}(10),$$
也就是满足 \(10^{a_p} \equiv 1 \pmod{9p}\) 的最小正整数。于是有完全等价的条件
$$p \mid R_n \iff a_p \mid n.$$
现在代入题目的 \(n = 10^9 = 2^9 \cdot 5^9\)。这说明任何可行的阶 \(a_p\) 都只能含有质因子 2 和 5。很多素数因此立即被排除。例如 \(10^2 \equiv 1 \pmod{99}\)，所以 \(a_{11} = 2\)，从而 11 一定整除 \(R_{10^9}\)。相反，\(10^6 \equiv 1 \pmod{63}\)，而更小的正指数都不成立，所以 \(a_7 = 6\)。因为 \(6 \nmid 10^9\)，7 不可能是目标 repunit 的因子。
repunit 还满足一个非常重要的拼接公式：
$$R_{m+n} = R_m 10^n + R_n.$$
如果 \(n = qm\)，反复使用它可得
$$R_n = R_m\left(1 + 10^m + 10^{2m} + \cdots + 10^{(q-1)m}\right),$$
因此只要 \(m \mid n\)，就有 \(R_m \mid R_n\)。这条性质非常适合构造具体例子。因为 \(10 \mid 10^9\)，所以任何整除 \(R_{10}\) 的素数也一定整除 \(R_{10^9}\)。而
$$R_{10} = 1111111111 = 11 \cdot 41 \cdot 271 \cdot 9091$$
立刻给出了四个明确的目标因子。同样地，小规模检查 \(R_6\) 也很有意义，因为 \(R_6 = 3 \cdot 7 \cdot 11 \cdot 13 \cdot 37\)，所以它的前四个素因子之和确实是 \(34\)。
3 不是像 2、5 那样一开始就排除掉，但它确实值得单独说明，因为 repunit 公式里本身就带有一个 9。这里最简洁的判定是
$$R_n = 1 + 10 + \cdots + 10^{n-1} \equiv 1 + 1 + \cdots + 1 \equiv n \pmod{3}.$$
因此 \(3 \mid R_n\) 当且仅当 \(3 \mid n\)。题目中的 \(10^9 \equiv 1 \pmod{3}\)，所以 3 不是 \(R_{10^9}\) 的因子。这与 C++ 实现中的校验完全一致：3 会整除 \(R_3\)，但不会整除 \(R_{10}\)。
C++ 实现采用了与上面完全等价、但形式略有不同的测试：它不去计算 \(10^n \bmod 9p\)，而是直接求 \(R_n \bmod p\)。核心恒等式是
$$R_{2m} = R_m(10^m + 1), \qquad R_{2m+1} = 10R_{2m} + 1.$$
它们都来自前面的拼接公式。算法按二进制从高位到低位处理 \(n\)，并维护如下不变量：
$$\text{当前 repunit 余数} \equiv R_m \pmod{q}, \qquad \text{当前 10 的幂} \equiv 10^m \pmod{q}.$$
这里的 \(m\) 表示已经处理过的长度。一次“倍增”把长度从 \(m\) 推到 \(2m\)；如果下一位二进制位是 1，就再追加一个数字 1，于是状态从 \(2m\) 进一步变成 \(2m+1\)。这样，即便目标长度是 \(10^9\)，单次判定仍然只需要 \(O(\log n)\) 级别的模运算。
三个实现都会按从小到大的顺序检查素数，并在找到 40 个合格素数后立即停止。\(2\) 和 \(5\) 直接跳过。给出的 C++、Python 和 Java 版本都使用试除法来判断素数，而不是构造复杂的筛法；在这个题目里，这已经足够快了。
Python 和 Java 检查的是
$$10^{10^9} \equiv 1 \pmod{9p}.$$
它们通过重复平方法完成模幂计算，所以十亿这个指数的代价只体现为它的二进制长度。C++ 则检查等价条件 \(R_{10^9} \equiv 0 \pmod p\)，并通过 repunit 的倍增递推直接得到这个余数。两种写法在数学上完全一致，只是实现包装方式不同。
每当某个素数通过判定，它就被加入运行中的总和，同时命中计数增加 1。C++ 版本还附带了几个小型校验点，用来确认推导没有写错：\(R_{10}\) 的前四个素因子之和是 \(9414\)，\(R_6\) 的前四个素因子之和是 \(34\)，而且素数 3 只会整除长度是 3 的倍数的 repunit。
对单个候选素数 \(p\) 而言，核心算术测试的成本是 \(O(\log n)\) 次模乘，其中 \(n = 10^9\)。不论是模幂还是 repunit 倍增递推，实际都只需要大约 30 个二进制步骤。
设 \(M\) 为找到第 40 个合格素数之前检查到的最大整数，那么总体时间主要由素数枚举和沿途进行的模测试组成。由于这里使用的是试除法，给一个简单上界，搜索阶段大约可视为 \(O(M\sqrt{M})\)。空间方面则很轻：C++ 额外保存一个较短的已知素数表，Python 与 Java 除了普通整数运算所需空间外，基本只使用常数级辅助空间。
Обозначим через \(R_n\) десятичный repunit из \(n\) единиц:
$$R_n = 11\ldots1 = 1 + 10 + 10^2 + \cdots + 10^{n-1} = \frac{10^n - 1}{9}.$$
Нужно найти сумму первых 40 простых чисел, которые делят \(R_{10^9}\). Число \(R_{10^9}\) содержит миллиард цифр, поэтому его нельзя ни построить явно, ни факторизовать напрямую. Рабочий путь состоит в том, чтобы проверять простые кандидаты через модульные условия, не касаясь самого гигантского числа.
Ключевой шаг состоит в том, чтобы заменить утверждение «простое \(p\) делит \(R_n\)» эквивалентной конгруэнцией для степеней десятки. После этого задача сводится к перебору простых чисел по возрастанию и суммированию первых 40 подходящих.
Из определения немедленно следует
$$10^n - 1 = 9R_n.$$
Если \(p\) - простое число, отличное от \(2\) и \(5\), то условие делимости принимает вид
$$p \mid R_n \iff 9p \mid (10^n - 1) \iff 10^n \equiv 1 \pmod{9p}.$$
Именно эту проверку используют реализации на Python и Java. Простые \(2\) и \(5\) можно отбросить сразу: любой repunit оканчивается цифрой 1, а значит, не делится ни на 2, ни на 5.
Для \(p \neq 2,5\) определим
$$a_p = \operatorname{ord}_{9p}(10),$$
то есть наименьший положительный показатель, при котором \(10^{a_p} \equiv 1 \pmod{9p}\). Тогда
$$p \mid R_n \iff a_p \mid n.$$
В нашей задаче \(n = 10^9 = 2^9 \cdot 5^9\). Следовательно, допустимый порядок \(a_p\) может содержать только простые множители 2 и 5. Это сразу отбрасывает много кандидатов. Например, \(10^2 \equiv 1 \pmod{99}\), значит \(a_{11} = 2\), и потому 11 делит \(R_{10^9}\). Напротив, \(10^6 \equiv 1 \pmod{63}\), а меньший положительный показатель не подходит, поэтому \(a_7 = 6\). Так как \(6 \nmid 10^9\), число 7 не может быть делителем искомого repunit.
У repunit есть и полезная формула композиции:
$$R_{m+n} = R_m 10^n + R_n.$$
Если \(n = qm\), то повторное применение даёт
$$R_n = R_m\left(1 + 10^m + 10^{2m} + \cdots + 10^{(q-1)m}\right),$$
поэтому из \(m \mid n\) следует \(R_m \mid R_n\). Это удобно для конкретных примеров. Поскольку \(10 \mid 10^9\), любой простой делитель числа \(R_{10}\) автоматически делит и \(R_{10^9}\). А разложение
$$R_{10} = 1111111111 = 11 \cdot 41 \cdot 271 \cdot 9091$$
сразу даёт четыре подходящих простых числа. Та же идея объясняет и маленький контрольный пример \(R_6\): так как \(R_6 = 3 \cdot 7 \cdot 11 \cdot 13 \cdot 37\), сумма первых четырёх простых делителей равна \(34\).
Число 3 не исключается так же, как 2 и 5, но его удобно разобрать отдельно из-за множителя 9 в формуле для repunit. Самая короткая проверка такова:
$$R_n = 1 + 10 + \cdots + 10^{n-1} \equiv 1 + 1 + \cdots + 1 \equiv n \pmod{3}.$$
Следовательно, \(3 \mid R_n\) тогда и только тогда, когда \(3 \mid n\). Для \(n = 10^9\) имеем \(10^9 \equiv 1 \pmod{3}\), значит, 3 не является делителем \(R_{10^9}\). Именно это подтверждает и контроль в реализации на C++: 3 делит \(R_3\), но не делит \(R_{10}\).
Реализация на C++ использует эквивалентную форму критерия: вместо вычисления \(10^n \bmod 9p\) она находит непосредственно \(R_n \bmod p\). Основные тождества здесь такие:
$$R_{2m} = R_m(10^m + 1), \qquad R_{2m+1} = 10R_{2m} + 1.$$
Они следуют из общей формулы композиции. При обходе двоичной записи числа \(n\) алгоритм поддерживает инвариант
$$\text{текущий остаток repunit} \equiv R_m \pmod{q}, \qquad \text{текущий остаток степени} \equiv 10^m \pmod{q},$$
где \(m\) - уже обработанная длина. Шаг удвоения переводит состояние из \(m\) в \(2m\); если следующий бит равен 1, добавляется ещё одна цифра 1, и состояние становится \(2m+1\). Благодаря этому стоимость одной проверки равна \(O(\log n)\), хотя само число имеет длину \(10^9\).
Все три реализации идут по простым числам в возрастающем порядке и останавливаются, как только найдено 40 подходящих значений. Числа \(2\) и \(5\) пропускаются сразу. Данные версии на C++, Python и Java используют проверку простоты делением на пробные делители, а не решето; здесь этого достаточно, потому что нужные 40 делителей находятся довольно рано.
В Python и Java проверяется конгруэнция
$$10^{10^9} \equiv 1 \pmod{9p}.$$
Она вычисляется с помощью модульного возведения в степень методом повторного возведения в квадрат, поэтому цена зависит только от двоичной длины показателя. В C++ используется эквивалентный тест \(R_{10^9} \equiv 0 \pmod p\), а нужный остаток получается через рекуррентные формулы удвоения для repunit. С математической точки зрения это один и тот же критерий, записанный двумя способами.
Каждый раз, когда простой кандидат проходит тест, его значение добавляется к сумме, а счётчик найденных делителей увеличивается. В версии на C++ есть и небольшие контрольные примеры: первые четыре простых делителя \(R_{10}\) дают сумму \(9414\), первые четыре простых делителя \(R_6\) дают \(34\), а простое число 3 делит repunit только тогда, когда длина кратна 3.
Для одного кандидата \(p\) арифметическая проверка требует \(O(\log n)\) модульных умножений при \(n = 10^9\). На практике это около 30 двоичных шагов, независимо от того, используется ли модульное возведение в степень или рекуррентное удвоение для \(R_n\).
Если \(M\) - наибольшее число, просмотренное до нахождения 40-го подходящего простого делителя, то общее время определяется перебором простых и модульными проверками по пути. Поскольку данные реализации используют деление на пробные делители, простой верхний модельный предел для фазы поиска составляет примерно \(O(M\sqrt{M})\), а потребление памяти остаётся очень малым. C++ дополнительно хранит лишь короткий список уже найденных простых; Python и Java сверх обычной арифметики используют почти постоянный объём вспомогательной памяти.
لنرمز بـ \(R_n\) إلى العدد repunit في النظام العشري والمكوَّن من \(n\) مرّات من الرقم 1، أي
$$R_n = 11\ldots1 = 1 + 10 + 10^2 + \cdots + 10^{n-1} = \frac{10^n - 1}{9}.$$
المطلوب هو إيجاد مجموع أول 40 عددًا أوليًا تقسم \(R_{10^9}\). وبما أن \(R_{10^9}\) يتكون من مليار رقم، فلا يمكن بناؤه مباشرة ولا تحليله إلى عوامل بالطريقة التقليدية. لذلك يعتمد الحل على اختبار الأعداد الأولية مرشحًا بعد مرشح باستعمال الحسابيات المعيارية فقط.
الفكرة الحاسمة هي تحويل عبارة «\(p\) عدد أولي يقسم \(R_n\)» إلى شرط تطابقي على قوة للعدد 10. بعد هذا التحويل تصبح المسألة مجرد مسح للأعداد الأولية تصاعديًا وجمع أول 40 عددًا يحقق الشرط.
من التعريف نحصل مباشرة على
$$10^n - 1 = 9R_n.$$
إذا كان \(p\) عددًا أوليًا مختلفًا عن \(2\) و\(5\)، فإن شرط القسمة يصبح
$$p \mid R_n \iff 9p \mid (10^n - 1) \iff 10^n \equiv 1 \pmod{9p}.$$
وهذا بالضبط هو الاختبار المستعمل في تنفيذي Python وJava. أما العددان \(2\) و\(5\) فيُستبعَدان فورًا، لأن كل repunit ينتهي بالرقم 1، وبالتالي لا يقبل القسمة على 2 ولا على 5.
لـ \(p \neq 2,5\) نعرّف
$$a_p = \operatorname{ord}_{9p}(10),$$
أي أصغر أس موجب يحقق \(10^{a_p} \equiv 1 \pmod{9p}\). عندئذ يصبح الشرط المكافئ
$$p \mid R_n \iff a_p \mid n.$$
في مسألتنا \(n = 10^9 = 2^9 \cdot 5^9\). وهذا يعني أن أي رتبة ممكنة \(a_p\) لا بد أن تكون عواملها الأولية محصورة في 2 و5. هذه الملاحظة تستبعد عددًا كبيرًا من المرشحين فورًا. فمثلًا \(10^2 \equiv 1 \pmod{99}\)، إذن \(a_{11} = 2\)، ومن ثم فإن 11 يقسم \(R_{10^9}\). وعلى النقيض من ذلك، لدينا \(10^6 \equiv 1 \pmod{63}\) ولا يوجد أس موجب أصغر يحقق ذلك، أي إن \(a_7 = 6\). وبما أن \(6 \nmid 10^9\)، فالعدد 7 لا يمكن أن يكون عاملًا للعدد المطلوب.
تُحقق أعداد repunit أيضًا هوية تركيبية مهمة:
$$R_{m+n} = R_m 10^n + R_n.$$
وإذا كان \(n = qm\)، فإن تكرار هذه الصيغة يعطي
$$R_n = R_m\left(1 + 10^m + 10^{2m} + \cdots + 10^{(q-1)m}\right),$$
ومن ثم \(R_m \mid R_n\) كلما كان \(m \mid n\). هذه خاصية ممتازة لبناء أمثلة ملموسة. وبما أن \(10 \mid 10^9\)، فإن كل عدد أولي يقسم \(R_{10}\) لا بد أن يقسم \(R_{10^9}\) أيضًا. ولدينا فعلًا
$$R_{10} = 1111111111 = 11 \cdot 41 \cdot 271 \cdot 9091$$
وهذا يعطينا أربعة عوامل أولية صحيحة منذ البداية. والفكرة نفسها تفسر حالة التحقق الصغيرة \(R_6\): بما أن \(R_6 = 3 \cdot 7 \cdot 11 \cdot 13 \cdot 37\)، فإن مجموع أول أربعة عوامل أولية يساوي \(34\).
العدد 3 لا يُستبعد بالطريقة نفسها التي يُستبعد بها 2 و5، لكنه يستحق معالجة منفصلة لأن الصيغة الأصلية تحتوي على العامل 9. أبسط اختبار هو
$$R_n = 1 + 10 + \cdots + 10^{n-1} \equiv 1 + 1 + \cdots + 1 \equiv n \pmod{3}.$$
إذن \(3 \mid R_n\) إذا وفقط إذا كان \(3 \mid n\). وفي حالتنا \(10^9 \equiv 1 \pmod{3}\)، ولذلك فإن 3 ليس عاملًا في \(R_{10^9}\). وهذا يطابق تمامًا نقطة التحقق الموجودة في تنفيذ C++: فالعدد 3 يقسم \(R_3\)، لكنه لا يقسم \(R_{10}\).
يستخدم تنفيذ C++ صيغة مكافئة للاختبار السابق: فبدلًا من فحص \(10^n \bmod 9p\)، يحسب مباشرة \(R_n \bmod p\). وتعتمد الطريقة على الهويتين
$$R_{2m} = R_m(10^m + 1), \qquad R_{2m+1} = 10R_{2m} + 1.$$
وهما ناتجتان مباشرة من صيغة التركيب العامة. أثناء المرور على التمثيل الثنائي للعدد \(n\)، تحافظ الخوارزمية على الثابت
$$u \equiv R_m \pmod{q}, \qquad v \equiv 10^m \pmod{q}.$$
هنا يمثّل \(u\) باقي الـ repunit الحالي، ويمثّل \(v\) باقي القوة الحالية للعدد 10، بينما يمثّل \(m\) الطول الذي تمت معالجته حتى تلك اللحظة. خطوة المضاعفة تنقل الحالة من \(m\) إلى \(2m\)، وإذا كانت البتة التالية تساوي 1، نُلحق رقم 1 إضافيًا فتنتقل الحالة من \(2m\) إلى \(2m+1\). بهذه الطريقة يصبح اختبار القسمة ذا كلفة \(O(\log n)\) رغم أن الطول المطلوب هو \(10^9\).
جميع التنفيذات تسير على الأعداد الأولية بترتيب تصاعدي وتتوقف فور العثور على 40 عددًا مناسبًا. ويُتجاوز العددان \(2\) و\(5\) مباشرة. النسخ المعطاة بلغة C++ وPython وJava تستخدم القسمة التجريبية لاكتشاف الأولية بدلًا من بناء منخل كامل، وهذا كافٍ تمامًا هنا لأن أول 40 عاملًا مناسبًا يظهرون مبكرًا نسبيًا.
في Python وJava يتم فحص التطابق
$$10^{10^9} \equiv 1 \pmod{9p}.$$
ويُحسب ذلك بواسطة الأس المعياري السريع، لذا فإن كلفة الأس الهائل ترتبط فقط بطوله الثنائي. أما تنفيذ C++ فيستخدم الشرط المكافئ \(R_{10^9} \equiv 0 \pmod p\) ويحسب هذا الباقي بواسطة علاقات المضاعفة الخاصة بالـ repunit. من الناحية الرياضية الطريقتان متماثلتان، لكن تغليف الحساب مختلف.
كلما اجتاز عدد أولي الاختبار يُضاف إلى المجموع الجاري ويزداد عداد الأعداد المقبولة بمقدار واحد. ويتضمن تنفيذ C++ أيضًا حالات تحقق صغيرة لتأكيد صحة الاشتقاق: مجموع أول أربعة عوامل أولية لـ \(R_{10}\) هو \(9414\)، ومجموع أول أربعة عوامل أولية لـ \(R_6\) هو \(34\)، والعدد 3 لا يقسم إلا أعداد repunit التي يكون طولها من مضاعفات 3.
لكل عدد أولي مرشح \(p\)، تكلف الاختبارات الحسابية \(O(\log n)\) من الضربات المعيارية حيث \(n = 10^9\). عمليًا يعني ذلك نحو 30 خطوة ثنائية فقط، سواء استُخدمت طريقة الأس المعياري أو طريقة المضاعفة الخاصة بـ \(R_n\).
إذا رمزنا بـ \(M\) إلى أكبر عدد جرى فحصه قبل الوصول إلى العامل الأولي الصحيح رقم 40، فإن الزمن الكلي تهيمن عليه عملية توليد الأعداد الأولية مع الاختبارات المعيارية المصاحبة. وبما أن التنفيذات هنا تعتمد على القسمة التجريبية، فيمكن نمذجة مرحلة البحث بحد علوي بسيط يقارب \(O(M\sqrt{M})\)، مع استهلاك ذاكرة منخفض جدًا. إصدار C++ يحتفظ بقائمة صغيرة من الأعداد الأولية المعروفة، أما Python وJava فلا يحتاجان عمليًا إلا إلى مساحة إضافية شبه ثابتة فوق الحسابات العددية المعتادة.