For a positive integer \(k\), let \(R(k)\) be the base-10 repunit with \(k\) ones: $$R(k)=\underbrace{11\ldots1}_{k}=\frac{10^k-1}{9}.$$ For every \(n\) with \(\gcd(n,10)=1\), define \(A(n)\) as the least \(k\ge 1\) such that \(R(k)\equiv 0 \pmod{n}\). The problem asks for the sum of the first 25 composite integers \(n\) for which \(A(n)\mid(n-1)\).
The reason this is interesting is that primes already behave this way: every prime \(p>5\) satisfies \(A(p)\mid(p-1)\). Problem 130 asks for composite numbers that imitate that prime-style repunit divisibility property.
The implementations do not factor numbers, build giant repunits, or use heavy algebraic machinery. They rely on the definition of \(A(n)\), a simple remainder recurrence, and a direct search over composite candidates.
The quantity \(A(n)\) is the first length for which a repunit becomes divisible by \(n\). The condition \(\gcd(n,10)=1\) is essential: if \(n\) shared a factor with 2 or 5, no number ending in digit 1 could be divisible by \(n\).
Existence of \(A(n)\) follows from a pigeonhole argument. Consider the residues of \(R(1),R(2),\ldots,R(n)\) modulo \(n\). If one of them is already 0, we are done. Otherwise two of them are equal, say \(R(i)\equiv R(j)\pmod n\) with \(i>j\). Then
$$R(i)-R(j)=10^jR(i-j)\equiv 0 \pmod n.$$
Because \(\gcd(10,n)=1\), the factor \(10^j\) is invertible modulo \(n\), so \(R(i-j)\equiv 0\pmod n\). Thus \(A(n)\) always exists, and in fact \(A(n)\le n\).
When \(3\nmid n\), this is equivalent to saying that \(A(n)\) is the multiplicative order of 10 modulo \(n\). The implementations do not need that reformulation; they work directly with repunit remainders, which also handles multiples of 3 uniformly.
For a prime \(p>5\), Fermat's little theorem gives
$$10^{p-1}\equiv 1 \pmod p.$$
Since \(p\neq 3\), the number 9 is invertible modulo \(p\), so
$$R(p-1)=\frac{10^{p-1}-1}{9}\equiv 0 \pmod p.$$
By definition, \(A(p)\) is the smallest repunit length divisible by \(p\), so \(A(p)\mid(p-1)\). The target numbers in this problem are composites for which the same divisibility pattern still happens.
Suppose \(A(n)=a\). Then \(n\mid R(a)\), and the desired condition is \(a\mid(n-1)\). If we write \(n-1=qa\), then the standard factorization of repunits gives
$$R(qa)=R(a)\left(1+10^a+10^{2a}+\cdots+10^{(q-1)a}\right).$$
Therefore \(n\mid R(a)\) immediately implies \(n\mid R(n-1)\) whenever \(A(n)\mid(n-1)\). Conversely, if \(n\mid R(n-1)\), then the minimality of \(A(n)\) forces \(A(n)\mid(n-1)\). So the problem is exactly about composite \(n\) for which the repunit \(R(n-1)\) is divisible by \(n\).
The core invariant in the code is the remainder of the current repunit modulo \(n\). If we define
$$r_k\equiv R(k)\pmod n,$$
then appending one more digit 1 turns \(R(k)\) into \(10R(k)+1\), so the remainders satisfy
$$r_1\equiv 1\pmod n,\qquad r_{k+1}\equiv 10r_k+1\pmod n.$$
That gives a tiny loop: start from the remainder of 1, keep appending another 1 in modular arithmetic, and stop when the remainder becomes 0. The first index where this happens is exactly \(A(n)\). No repunit is ever stored as a large integer; only one remainder and one length counter are maintained.
The composite number 91 is coprime to 10, so \(A(91)\) exists. Using the recurrence:
$$\begin{aligned} r_1&=1,\\ r_2&\equiv 11,\\ r_3&\equiv 111\equiv 20\pmod{91},\\ r_4&\equiv 10\cdot 20+1=201\equiv 19\pmod{91},\\ r_5&\equiv 10\cdot 19+1=191\equiv 9\pmod{91},\\ r_6&\equiv 10\cdot 9+1=91\equiv 0\pmod{91}. \end{aligned}$$
So \(A(91)=6\). Since \(6\mid 90=91-1\), the number 91 is one of the composites counted by the problem.
The C++, Python, and Java implementations scan odd integers \(n=3,5,7,\ldots\) upward. Multiples of 5 are skipped immediately, primes are rejected, and an explicit \(\gcd(n,10)=1\) check keeps the search aligned with the definition of \(A(n)\).
For each remaining composite candidate, the implementation runs the recurrence for repunit remainders. Each loop iteration corresponds to appending one more digit 1, reducing modulo \(n\), and increasing the current length by 1. The moment the remainder becomes 0, that length is \(A(n)\).
Once \(A(n)\) has been found, the acceptance test is just
$$ (n-1)\bmod A(n)=0. $$
If the divisibility holds, the implementation counts \(n\), adds it to the running sum, and continues until 25 such composites have been found.
For one candidate \(n\), the hand-written primality tests in the C++ and Java versions take \(O(\sqrt n)\) time in the worst case, while the repunit loop takes \(O(A(n))\) steps and \(O(1)\) extra memory. Because \(A(n)\le n\), a coarse upper bound for scanning all candidates up to some limit \(N\) is \(O(N^2)\) time and \(O(1)\) auxiliary space.
That bound is deliberately conservative. In practice the search is much faster because only odd numbers not divisible by 5 are examined, and the computation stops as soon as 25 valid composites have been accumulated.
Für eine positive ganze Zahl \(k\) sei \(R(k)\) die dezimale Repunit mit \(k\) Einsen: $$R(k)=\underbrace{11\ldots1}_{k}=\frac{10^k-1}{9}.$$ Für jedes \(n\) mit \(\gcd(n,10)=1\) bezeichnet \(A(n)\) die kleinste Zahl \(k\ge 1\), für die \(R(k)\equiv 0 \pmod n\) gilt. Gesucht ist die Summe der ersten 25 zusammengesetzten Zahlen \(n\), für die \(A(n)\mid(n-1)\) erfüllt ist.
Das ist deshalb interessant, weil Primzahlen dieses Verhalten bereits besitzen: Für jede Primzahl \(p>5\) gilt automatisch \(A(p)\mid(p-1)\). Aufgabe 130 sucht also zusammengesetzte Zahlen, die dieselbe Repunit-Eigenschaft wie Primzahlen nachahmen.
Die Implementierungen faktorisieren die Zahlen nicht, konstruieren keine riesigen Repunits und benutzen keine komplizierte Theorie. Sie stützen sich direkt auf die Definition von \(A(n)\), auf eine einfache Restrekursion und auf eine lineare Suche über geeignete zusammengesetzte Kandidaten.
Die Größe \(A(n)\) ist genau die erste Länge, bei der eine Repunit durch \(n\) teilbar wird. Die Bedingung \(\gcd(n,10)=1\) ist unverzichtbar: Hat \(n\) einen gemeinsamen Faktor mit 2 oder 5, kann keine Zahl, die auf 1 endet, durch \(n\) teilbar sein.
Die Existenz von \(A(n)\) folgt aus einem Schubfachargument. Betrachte die Reste von \(R(1),R(2),\ldots,R(n)\) modulo \(n\). Ist einer davon 0, sind wir fertig. Andernfalls müssen zwei gleich sein, etwa \(R(i)\equiv R(j)\pmod n\) mit \(i>j\). Dann gilt
$$R(i)-R(j)=10^jR(i-j)\equiv 0 \pmod n.$$
Da \(\gcd(10,n)=1\), ist \(10^j\) modulo \(n\) invertierbar, also folgt \(R(i-j)\equiv 0\pmod n\). Damit existiert \(A(n)\) immer, und sogar \(A(n)\le n\).
Falls \(3\nmid n\), kann man \(A(n)\) auch als multiplikative Ordnung von 10 modulo \(n\) auffassen. Die Implementierungen brauchen diese Umformulierung aber nicht; die Restrekursion arbeitet auch für Vielfache von 3 ohne Sonderfallbehandlung.
Für eine Primzahl \(p>5\) liefert der kleine Satz von Fermat
$$10^{p-1}\equiv 1 \pmod p.$$
Wegen \(p\neq 3\) ist 9 modulo \(p\) invertierbar, also
$$R(p-1)=\frac{10^{p-1}-1}{9}\equiv 0 \pmod p.$$
Da \(A(p)\) per Definition die kleinste passende Repunit-Länge ist, muss \(A(p)\mid(p-1)\) gelten. Die gesuchten Zahlen sind also Komposita, die dieses primzahlartige Teilbarkeitsmuster ebenfalls besitzen.
Sei \(A(n)=a\). Dann gilt \(n\mid R(a)\), und gesucht ist \(a\mid(n-1)\). Schreiben wir \(n-1=qa\), dann liefert die Standardfaktorisierung von Repunits
$$R(qa)=R(a)\left(1+10^a+10^{2a}+\cdots+10^{(q-1)a}\right).$$
Also folgt aus \(n\mid R(a)\) sofort \(n\mid R(n-1)\), sobald \(A(n)\mid(n-1)\) gilt. Umgekehrt erzwingt \(n\mid R(n-1)\) wegen der Minimalität von \(A(n)\), dass \(A(n)\mid(n-1)\) ist. Die Aufgabe sucht daher genau zusammengesetzte Zahlen \(n\), die \(R(n-1)\) teilen.
Die zentrale Invariante im Code ist der Rest der aktuellen Repunit modulo \(n\). Definiert man
$$r_k\equiv R(k)\pmod n,$$
dann entsteht durch Anhängen einer weiteren Ziffer 1 die Rekursion
$$r_1\equiv 1\pmod n,\qquad r_{k+1}\equiv 10r_k+1\pmod n.$$
Damit erhält man eine sehr kleine Schleife: mit dem Rest von 1 starten, modulo \(n\) jeweils eine weitere 1 anhängen und stoppen, sobald der Rest 0 wird. Der erste Index mit Rest 0 ist genau \(A(n)\). Große Repunits werden nie explizit gespeichert.
Die Zahl 91 ist zusammengesetzt und teilerfremd zu 10, also existiert \(A(91)\). Mit der Rekursion erhält man
$$\begin{aligned} r_1&=1,\\ r_2&\equiv 11,\\ r_3&\equiv 111\equiv 20\pmod{91},\\ r_4&\equiv 10\cdot 20+1=201\equiv 19\pmod{91},\\ r_5&\equiv 10\cdot 19+1=191\equiv 9\pmod{91},\\ r_6&\equiv 10\cdot 9+1=91\equiv 0\pmod{91}. \end{aligned}$$
Damit ist \(A(91)=6\). Weil \(6\mid 90=91-1\) gilt, ist 91 eine der gesuchten zusammengesetzten Zahlen.
Die Implementierungen in C++, Python und Java durchlaufen die ungeraden Zahlen \(n=3,5,7,\ldots\). Vielfache von 5 werden sofort übersprungen, Primzahlen verworfen, und eine explizite Prüfung \(\gcd(n,10)=1\) hält die Suche exakt auf dem Definitionsbereich von \(A(n)\).
Für jeden verbleibenden zusammengesetzten Kandidaten wird die Restrekursion für die Repunits ausgeführt. Jeder Schleifendurchlauf entspricht dem Anhängen einer weiteren Ziffer 1, der Reduktion modulo \(n\) und einer Erhöhung der aktuellen Länge um 1. Sobald der Rest 0 ist, ist diese Länge gleich \(A(n)\).
Nachdem \(A(n)\) berechnet wurde, ist die Annahmebedingung einfach
$$ (n-1)\bmod A(n)=0. $$
Wenn die Teilbarkeit stimmt, zählt die Implementierung \(n\), addiert es zur laufenden Summe und fährt fort, bis 25 passende Komposita gefunden wurden.
Für einen einzelnen Kandidaten \(n\) benötigen die von Hand geschriebenen Primzahltests in C++ und Java im schlechtesten Fall \(O(\sqrt n)\) Zeit, während die Repunit-Schleife \(O(A(n))\) Schritte und \(O(1)\) Zusatzspeicher braucht. Weil \(A(n)\le n\) gilt, erhält man für die Suche bis zu einer Schranke \(N\) die grobe obere Schranke \(O(N^2)\) Zeit und \(O(1)\) Hilfsspeicher.
Diese Schranke ist bewusst grob. In der Praxis läuft die Suche deutlich schneller, weil nur ungerade Zahlen, die nicht durch 5 teilbar sind, untersucht werden und der Prozess endet, sobald 25 gültige Komposita gefunden sind.
Pozitif bir \(k\) için \(R(k)\), \(k\) tane 1'den oluşan onluk repunit olsun: $$R(k)=\underbrace{11\ldots1}_{k}=\frac{10^k-1}{9}.$$ \(\gcd(n,10)=1\) olan her \(n\) için \(A(n)\), \(R(k)\equiv 0 \pmod n\) yapan en küçük \(k\ge 1\) değeridir. İstenen, \(A(n)\mid(n-1)\) koşulunu sağlayan ilk 25 bileşik sayının toplamıdır.
Bu koşul ilginçtir çünkü asallar zaten böyle davranır: her \(p>5\) asalı için \(A(p)\mid(p-1)\) doğrudur. Problem 130, aynı repunit bölünebilirlik özelliğini taklit eden bileşikleri arıyor.
Uygulamalar sayı çarpanlarına ayırma yapmaz, dev repunitler kurmaz ve ağır bir teoriye yaslanmaz. Çözüm, doğrudan \(A(n)\) tanımına, basit bir kalan yinelemesine ve uygun adaylar üzerinde yapılan doğrudan aramaya dayanır.
\(A(n)\), bir repunitin \(n\)'e ilk kez bölündüğü uzunluktur. \(\gcd(n,10)=1\) şartı zorunludur; çünkü \(n\), 2 veya 5 ile ortak bölen taşıyorsa sonu 1 ile biten hiçbir sayı \(n\)'e bölünemez.
\(A(n)\)'in varlığı bir güvercin yuvası argümanıyla gelir. \(R(1),R(2),\ldots,R(n)\) değerlerinin \(n\)'e göre kalanlarına bakın. İçlerinden biri 0 ise iş biter. Aksi halde iki tanesi eşittir; diyelim \(R(i)\equiv R(j)\pmod n\) ve \(i>j\). O zaman
$$R(i)-R(j)=10^jR(i-j)\equiv 0 \pmod n.$$
\(\gcd(10,n)=1\) olduğu için \(10^j\), mod \(n\) altında terslenebilir; dolayısıyla \(R(i-j)\equiv 0\pmod n\) çıkar. Böylece \(A(n)\) her zaman vardır ve hatta \(A(n)\le n\) olur.
Eğer \(3\nmid n\) ise bu, \(A(n)\)'in 10'un mod \(n\) altındaki çarpımsal mertebesi olduğu anlamına gelir. Fakat uygulamalar bu yeniden yazıma ihtiyaç duymaz; doğrudan repunit kalanlarını izlemek 3'ün katlarını da düzgün biçimde kapsar.
\(p>5\) bir asal için Fermat'nın küçük teoremi
$$10^{p-1}\equiv 1 \pmod p$$
verir. \(p\neq 3\) olduğundan 9 sayısı mod \(p\) altında terslenebilir ve
$$R(p-1)=\frac{10^{p-1}-1}{9}\equiv 0 \pmod p$$
elde edilir. \(A(p)\), bu özelliği sağlayan en küçük uzunluk olduğundan \(A(p)\mid(p-1)\) zorunludur. Sorunun hedefi, aynı deseni asallar olmadan sergileyen sayıları bulmaktır.
\(A(n)=a\) olsun. O zaman \(n\mid R(a)\) ve istediğimiz koşul \(a\mid(n-1)\)'dir. \(n-1=qa\) yazarsak repunitlerin standart çarpanlaşması
$$R(qa)=R(a)\left(1+10^a+10^{2a}+\cdots+10^{(q-1)a}\right)$$
şeklindedir. Bu yüzden \(A(n)\mid(n-1)\) olduğunda \(n\mid R(a)\) doğrudan \(n\mid R(n-1)\) sonucunu verir. Tersi yönde de, \(n\mid R(n-1)\) ise \(A(n)\)'in en küçük tanımı nedeniyle \(A(n)\mid(n-1)\) olmak zorundadır. Yani problem tam olarak \(R(n-1)\)'i bölen bileşik \(n\)'leri arar.
Koddaki temel değişmez, mevcut repunitin mod \(n\) altındaki kalanı olur. Eğer
$$r_k\equiv R(k)\pmod n$$
diye tanımlarsak, sona bir tane daha 1 eklemek
$$r_1\equiv 1\pmod n,\qquad r_{k+1}\equiv 10r_k+1\pmod n$$
yinelemesini verir. Böylece çok küçük bir döngü yeterlidir: 1'in kalanı ile başla, mod \(n\) altında bir 1 daha ekleyerek ilerle ve kalan 0 olduğunda dur. İlk sıfırın görüldüğü adım tam olarak \(A(n)\)'dir. Hiçbir noktada dev repunitler oluşturulmaz.
91 sayısı bileşiktir ve 10 ile aralarında asal olduğundan \(A(91)\) vardır. Yineleme ile
$$\begin{aligned} r_1&=1,\\ r_2&\equiv 11,\\ r_3&\equiv 111\equiv 20\pmod{91},\\ r_4&\equiv 10\cdot 20+1=201\equiv 19\pmod{91},\\ r_5&\equiv 10\cdot 19+1=191\equiv 9\pmod{91},\\ r_6&\equiv 10\cdot 9+1=91\equiv 0\pmod{91}. \end{aligned}$$
elde edilir. Demek ki \(A(91)=6\). Ayrıca \(6\mid 90=91-1\) olduğu için 91, aranan bileşiklerden biridir.
C++, Python ve Java uygulamaları \(n=3,5,7,\ldots\) biçiminde tek sayıları yukarı doğru tarar. 5'in katları hemen atlanır, asallar elenir ve açık bir \(\gcd(n,10)=1\) kontrolü aramayı \(A(n)\)'in tanımlı olduğu bölgeye sabitler.
Kalan her bileşik aday için repunit kalan yinelemesi çalıştırılır. Her döngü adımı bir tane daha 1 eklemeye, sonucu mod \(n\) altında küçültmeye ve mevcut uzunluğu 1 artırmaya karşılık gelir. Kalan 0 olur olmaz o anki uzunluk \(A(n)\) olur.
\(A(n)\) bulunduğunda kabul testi sadece
$$ (n-1)\bmod A(n)=0 $$
şeklindedir. Bölünebilirlik sağlanıyorsa uygulama \(n\)'i sayar, toplama ekler ve 25 uygun bileşik bulunana kadar devam eder.
Tek bir aday \(n\) için C++ ve Java sürümlerindeki elle yazılmış asallık testleri en kötü durumda \(O(\sqrt n)\) zaman alır. Repunit döngüsü ise \(O(A(n))\) adım ve \(O(1)\) ek bellek kullanır. \(A(n)\le n\) olduğu için, \(N\)'e kadar tarama için kaba bir üst sınır \(O(N^2)\) zaman ve \(O(1)\) yardımcı bellektir.
Bu sınır bilinçli olarak kabadır. Pratikte işlem çok daha hızlıdır; çünkü yalnızca 5'e bölünmeyen tek sayılar incelenir ve 25 geçerli bileşik bulunduğu anda arama durur.
Para un entero positivo \(k\), sea \(R(k)\) el repunit decimal formado por \(k\) unos: $$R(k)=\underbrace{11\ldots1}_{k}=\frac{10^k-1}{9}.$$ Para cada \(n\) con \(\gcd(n,10)=1\), definimos \(A(n)\) como el menor \(k\ge 1\) tal que \(R(k)\equiv 0 \pmod n\). El problema pide la suma de los primeros 25 enteros compuestos \(n\) para los cuales \(A(n)\mid(n-1)\).
La condición llama la atención porque los primos ya la satisfacen: todo primo \(p>5\) cumple \(A(p)\mid(p-1)\). La tarea consiste en encontrar compuestos que imitan exactamente ese comportamiento de divisibilidad asociado a los repunits.
Las implementaciones no factorizan números, no construyen repunits gigantes y no dependen de una teoría pesada. Todo se apoya en la definición de \(A(n)\), en una recurrencia muy corta para los residuos y en una búsqueda directa sobre candidatos compuestos.
La cantidad \(A(n)\) es la primera longitud para la que un repunit resulta divisible por \(n\). La condición \(\gcd(n,10)=1\) es indispensable: si \(n\) comparte un factor con 2 o con 5, ningún número terminado en 1 puede ser múltiplo de \(n\).
La existencia de \(A(n)\) sale de un argumento de palomar. Consideramos los residuos de \(R(1),R(2),\ldots,R(n)\) módulo \(n\). Si alguno ya vale 0, terminamos. Si no, dos de ellos deben coincidir, digamos \(R(i)\equiv R(j)\pmod n\) con \(i>j\). Entonces
$$R(i)-R(j)=10^jR(i-j)\equiv 0 \pmod n.$$
Como \(\gcd(10,n)=1\), el factor \(10^j\) es invertible módulo \(n\), de modo que \(R(i-j)\equiv 0\pmod n\). Por lo tanto \(A(n)\) siempre existe y, además, \(A(n)\le n\).
Cuando \(3\nmid n\), esto equivale a decir que \(A(n)\) es el orden multiplicativo de 10 módulo \(n\). Las implementaciones no necesitan esa formulación: trabajar directamente con residuos de repunits evita cualquier caso especial relacionado con el factor 3.
Para un primo \(p>5\), el pequeño teorema de Fermat afirma que
$$10^{p-1}\equiv 1 \pmod p.$$
Como \(p\neq 3\), el 9 es invertible módulo \(p\), y por ello
$$R(p-1)=\frac{10^{p-1}-1}{9}\equiv 0 \pmod p.$$
Dado que \(A(p)\) es, por definición, la menor longitud válida, necesariamente \(A(p)\mid(p-1)\). El interés del problema está en los compuestos que siguen mostrando ese mismo patrón.
Supongamos que \(A(n)=a\). Entonces \(n\mid R(a)\), y la condición buscada es \(a\mid(n-1)\). Si escribimos \(n-1=qa\), la factorización estándar de repunits da
$$R(qa)=R(a)\left(1+10^a+10^{2a}+\cdots+10^{(q-1)a}\right).$$
Así, \(n\mid R(a)\) implica inmediatamente \(n\mid R(n-1)\) cuando \(A(n)\mid(n-1)\). En sentido inverso, si \(n\mid R(n-1)\), la minimalidad de \(A(n)\) obliga a que \(A(n)\mid(n-1)\). En otras palabras, el problema busca precisamente los compuestos \(n\) que dividen al repunit \(R(n-1)\).
El invariante central del código es el residuo del repunit actual módulo \(n\). Si definimos
$$r_k\equiv R(k)\pmod n,$$
entonces añadir un nuevo dígito 1 transforma \(R(k)\) en \(10R(k)+1\), y por tanto
$$r_1\equiv 1\pmod n,\qquad r_{k+1}\equiv 10r_k+1\pmod n.$$
Eso produce un bucle muy pequeño: se empieza con el residuo de 1, se añade otro 1 en aritmética modular y se detiene el proceso cuando el residuo se vuelve 0. El primer índice donde ocurre eso es exactamente \(A(n)\). En ningún momento se construye explícitamente el repunit completo.
El número 91 es compuesto y coprimo con 10, así que \(A(91)\) existe. Aplicando la recurrencia:
$$\begin{aligned} r_1&=1,\\ r_2&\equiv 11,\\ r_3&\equiv 111\equiv 20\pmod{91},\\ r_4&\equiv 10\cdot 20+1=201\equiv 19\pmod{91},\\ r_5&\equiv 10\cdot 19+1=191\equiv 9\pmod{91},\\ r_6&\equiv 10\cdot 9+1=91\equiv 0\pmod{91}. \end{aligned}$$
Por tanto \(A(91)=6\). Como \(6\mid 90=91-1\), el 91 es uno de los compuestos aceptados por el problema.
Las implementaciones en C++, Python y Java recorren los enteros impares \(n=3,5,7,\ldots\). Se descartan enseguida los múltiplos de 5, se rechazan los primos y se mantiene una comprobación explícita de \(\gcd(n,10)=1\) para respetar exactamente la definición de \(A(n)\).
Para cada candidato compuesto que sobrevive al filtrado, la implementación ejecuta la recurrencia de residuos de repunits. Cada iteración añade un nuevo dígito 1, reduce módulo \(n\) y aumenta en 1 la longitud actual. En cuanto el residuo se vuelve 0, esa longitud es \(A(n)\).
Una vez conocido \(A(n)\), la condición de aceptación es simplemente
$$ (n-1)\bmod A(n)=0. $$
Si se cumple, la implementación cuenta ese \(n\), lo suma al acumulador y continúa hasta reunir 25 compuestos válidos.
Para un candidato \(n\), las pruebas de primalidad escritas a mano en C++ y Java cuestan \(O(\sqrt n)\) en el peor caso, mientras que el bucle del repunit necesita \(O(A(n))\) pasos y \(O(1)\) memoria adicional. Como \(A(n)\le n\), una cota superior gruesa para explorar todos los candidatos hasta un límite \(N\) es \(O(N^2)\) tiempo y \(O(1)\) espacio auxiliar.
Esa cota es conservadora. En la práctica el proceso es bastante más rápido, porque solo se examinan impares no divisibles por 5 y la búsqueda termina en cuanto aparecen los 25 compuestos requeridos.
对正整数 \(k\)，记 \(R(k)\) 为由 \(k\) 个数字 1 组成的十进制 repunit： $$R(k)=\underbrace{11\ldots1}_{k}=\frac{10^k-1}{9}.$$ 对每个满足 \(\gcd(n,10)=1\) 的整数 \(n\)，定义 \(A(n)\) 为使 \(R(k)\equiv 0 \pmod n\) 的最小正整数 \(k\)。题目要求把前 25 个满足 \(A(n)\mid(n-1)\) 的合数 \(n\) 相加。
这个条件之所以值得研究，是因为素数本来就具有类似性质：每个 \(p>5\) 的素数都满足 \(A(p)\mid(p-1)\)。因此本题寻找的是那些在 repunit 整除行为上“看起来像素数”的合数。
三个实现都没有做复杂因式分解，也没有真的去构造超长 repunit，更没有依赖沉重的高阶数论工具。整个方法完全建立在 \(A(n)\) 的定义、一个很短的模递推以及对候选合数的直接扫描上。
\(A(n)\) 表示“长度最短的、能够被 \(n\) 整除的 repunit 的位数”。条件 \(\gcd(n,10)=1\) 是必要的：如果 \(n\) 含有 2 或 5 的因子，那么任何末位是 1 的十进制整数都不可能被 \(n\) 整除。
\(A(n)\) 一定存在，这一点可以用抽屉原理证明。考虑 \(R(1),R(2),\ldots,R(n)\) 模 \(n\) 的余数。如果其中某个余数已经是 0，那么定义直接成立。否则，这 \(n\) 个值全都落在非零余数里，而非零余数最多只有 \(n-1\) 种，所以必有两个相等。设 \(R(i)\equiv R(j)\pmod n\) 且 \(i>j\)，则
$$R(i)-R(j)=10^jR(i-j)\equiv 0 \pmod n.$$
由于 \(\gcd(10,n)=1\)，\(10^j\) 在模 \(n\) 下可逆，于是得到 \(R(i-j)\equiv 0\pmod n\)。这说明 \(A(n)\) 不但存在，而且满足 \(A(n)\le n\)。
当 \(3\nmid n\) 时，也可以把 \(A(n)\) 看成 10 在模 \(n\) 下的乘法阶。不过实现并不需要把问题改写成那个形式；直接跟踪 repunit 余数可以统一处理所有与 10 互素的 \(n\)，包括含有因子 3 的情况。
若 \(p>5\) 是素数，由费马小定理可知
$$10^{p-1}\equiv 1 \pmod p.$$
因为 \(p\neq 3\)，所以 9 在模 \(p\) 下可逆，从而
$$R(p-1)=\frac{10^{p-1}-1}{9}\equiv 0 \pmod p.$$
而 \(A(p)\) 按定义是满足这一整除关系的最小长度，因此必定有 \(A(p)\mid(p-1)\)。本题真正关心的是：哪些合数也会表现出同样的 repunit 整除规律。
设 \(A(n)=a\)。那么 \(n\mid R(a)\)，而题目要求 \(a\mid(n-1)\)。若写成 \(n-1=qa\)，利用 repunit 的标准分解可得
$$R(qa)=R(a)\left(1+10^a+10^{2a}+\cdots+10^{(q-1)a}\right).$$
所以只要 \(A(n)\mid(n-1)\)，由 \(n\mid R(a)\) 就立刻推出 \(n\mid R(n-1)\)。反过来，如果 \(n\mid R(n-1)\)，由于 \(A(n)\) 是最小可行长度，也必然有 \(A(n)\mid(n-1)\)。也就是说，本题等价于寻找满足 \(n\mid R(n-1)\) 的合数 \(n\)。
代码里最重要的不变量是“当前 repunit 对 \(n\) 取模后的余数”。记
$$r_k\equiv R(k)\pmod n,$$
那么在末尾再补一个数字 1，相当于把 \(R(k)\) 变成 \(10R(k)+1\)，所以有递推式
$$r_1\equiv 1\pmod n,\qquad r_{k+1}\equiv 10r_k+1\pmod n.$$
这就把问题化成了一个极小的循环：从余数 1 开始，每一步都在模 \(n\) 意义下“再拼接一个 1”，一旦余数变成 0，就说明当前长度正好是 \(A(n)\)。整个过程中不会显式构造大整数 \(111\ldots1\)，始终只维护一个余数和一个长度计数器。
91 是合数，并且与 10 互素，因此 \(A(91)\) 存在。按上面的递推计算：
$$\begin{aligned} r_1&=1,\\ r_2&\equiv 11,\\ r_3&\equiv 111\equiv 20\pmod{91},\\ r_4&\equiv 10\cdot 20+1=201\equiv 19\pmod{91},\\ r_5&\equiv 10\cdot 19+1=191\equiv 9\pmod{91},\\ r_6&\equiv 10\cdot 9+1=91\equiv 0\pmod{91}. \end{aligned}$$
因此 \(A(91)=6\)。而 \(6\mid 90=91-1\)，所以 91 就是题目要求统计的合数之一。这个例子完整展示了“余数递推 + 整除检验”的核心机制。
C++、Python 和 Java 实现都从 \(n=3\) 开始按奇数向上扫描。能被 5 整除的值会立刻跳过，素数会先被排除，同时还保留显式的 \(\gcd(n,10)=1\) 检查，以保证后续计算始终处在 \(A(n)\) 有定义的范围里。
对每个保留下来的合数候选，实现都会运行上面的 repunit 余数递推。每一次循环都对应“再加一个数字 1，再对 \(n\) 取模，再把长度加 1”。一旦余数归零，当前长度就是 \(A(n)\)。这个过程只做常数空间的整数运算。
求出 \(A(n)\) 后，判断条件只有一行：
$$ (n-1)\bmod A(n)=0. $$
若成立，就把这个 \(n\) 计入答案并加入总和；否则直接继续扫描下一个候选值。整个搜索在找到 25 个满足条件的合数后停止。
对单个候选 \(n\) 来说，C++ 与 Java 中手写的素性判断在最坏情况下需要 \(O(\sqrt n)\) 时间；repunit 余数循环需要 \(O(A(n))\) 步、\(O(1)\) 额外空间。由于 \(A(n)\le n\)，如果把搜索上界记作 \(N\)，那么一个宽松但正确的总时间上界是 \(O(N^2)\)，辅助空间为 \(O(1)\)。
这个界非常保守。实际运行时要快得多，因为程序只检查奇数、跳过 5 的倍数，而且一旦收集满 25 个合格合数就立即终止，不会继续无意义地向后搜索。
Для положительного целого \(k\) обозначим через \(R(k)\) десятичный репьюнит из \(k\) единиц: $$R(k)=\underbrace{11\ldots1}_{k}=\frac{10^k-1}{9}.$$ Для каждого \(n\), взаимно простого с 10, величина \(A(n)\) определяется как наименьшее \(k\ge 1\), для которого \(R(k)\equiv 0 \pmod n\). Требуется найти сумму первых 25 составных чисел \(n\), удовлетворяющих условию \(A(n)\mid(n-1)\).
Эта задача интересна тем, что простые числа уже ведут себя так же: для любого простого \(p>5\) выполняется \(A(p)\mid(p-1)\). Значит, здесь нужно найти составные числа, которые копируют характерное для простых repunit-свойство делимости.
Реализации не раскладывают числа на множители, не строят огромные репьюниты и не используют тяжелую теорию. Все основано на определении \(A(n)\), на короткой рекуррентной формуле для остатков и на прямом переборе подходящих составных кандидатов.
Величина \(A(n)\) показывает минимальную длину репьюнита, который делится на \(n\). Условие \(\gcd(n,10)=1\) обязательно: если у \(n\) есть общий множитель с 2 или 5, то никакое число, оканчивающееся на 1, не сможет делиться на \(n\).
Существование \(A(n)\) следует из принципа Дирихле. Рассмотрим остатки чисел \(R(1),R(2),\ldots,R(n)\) по модулю \(n\). Если один из них равен 0, вопрос решен. Иначе два остатка совпадут; пусть \(R(i)\equiv R(j)\pmod n\) и \(i>j\). Тогда
$$R(i)-R(j)=10^jR(i-j)\equiv 0 \pmod n.$$
Так как \(\gcd(10,n)=1\), число \(10^j\) обратимо по модулю \(n\), поэтому \(R(i-j)\equiv 0\pmod n\). Следовательно, \(A(n)\) существует всегда и даже удовлетворяет оценке \(A(n)\le n\).
Если \(3\nmid n\), то \(A(n)\) можно интерпретировать как мультипликативный порядок числа 10 по модулю \(n\). Однако реализациям эта переформулировка не нужна: работа напрямую с остатками репьюнитов одинаково хорошо покрывает и числа, делящиеся на 3.
Для простого \(p>5\) малая теорема Ферма дает
$$10^{p-1}\equiv 1 \pmod p.$$
Поскольку \(p\neq 3\), число 9 обратимо по модулю \(p\), и потому
$$R(p-1)=\frac{10^{p-1}-1}{9}\equiv 0 \pmod p.$$
Но \(A(p)\) по определению является минимальной допустимой длиной, значит \(A(p)\mid(p-1)\). Задача ищет именно составные числа, для которых сохраняется тот же рисунок делимости.
Пусть \(A(n)=a\). Тогда \(n\mid R(a)\), а требуемое условие есть \(a\mid(n-1)\). Если записать \(n-1=qa\), стандартное разложение репьюнитов имеет вид
$$R(qa)=R(a)\left(1+10^a+10^{2a}+\cdots+10^{(q-1)a}\right).$$
Поэтому из \(n\mid R(a)\) сразу следует \(n\mid R(n-1)\), как только выполнено \(A(n)\mid(n-1)\). Обратное тоже верно: если \(n\mid R(n-1)\), то минимальность \(A(n)\) заставляет \(A(n)\) делить \(n-1\). Значит, задача эквивалентна поиску составных \(n\), которые делят репьюнит \(R(n-1)\).
Главный инвариант в коде - остаток текущего репьюнита по модулю \(n\). Если обозначить
$$r_k\equiv R(k)\pmod n,$$
то при приписывании еще одной единицы получаем рекурсию
$$r_1\equiv 1\pmod n,\qquad r_{k+1}\equiv 10r_k+1\pmod n.$$
Это превращает вычисление \(A(n)\) в очень короткий цикл: начать с остатка числа 1, затем на каждом шаге приписывать еще одну единицу в модульной арифметике и остановиться, когда остаток станет нулем. Первый индекс с нулевым остатком и есть \(A(n)\). Никаких длинных чисел вида \(111\ldots1\) программа не хранит.
Число 91 составное и взаимно просто с 10, следовательно, \(A(91)\) существует. По рекурсии получаем
$$\begin{aligned} r_1&=1,\\ r_2&\equiv 11,\\ r_3&\equiv 111\equiv 20\pmod{91},\\ r_4&\equiv 10\cdot 20+1=201\equiv 19\pmod{91},\\ r_5&\equiv 10\cdot 19+1=191\equiv 9\pmod{91},\\ r_6&\equiv 10\cdot 9+1=91\equiv 0\pmod{91}. \end{aligned}$$
Следовательно, \(A(91)=6\). Так как \(6\mid 90=91-1\), число 91 является одним из составных чисел, которые учитываются в ответе.
Реализации на C++, Python и Java просматривают нечетные числа \(n=3,5,7,\ldots\) по возрастанию. Кратные 5 пропускаются сразу, простые числа отбрасываются, а явная проверка \(\gcd(n,10)=1\) удерживает поиск ровно в той области, где \(A(n)\) определена.
Для каждого оставшегося составного кандидата запускается рекурсия по остаткам репьюнитов. Каждый проход цикла соответствует приписыванию очередной цифры 1, взятию результата по модулю \(n\) и увеличению текущей длины на 1. Как только остаток становится нулем, эта длина и есть \(A(n)\).
Когда \(A(n)\) найдено, условие принятия сводится к одной проверке:
$$ (n-1)\bmod A(n)=0. $$
Если делимость выполнена, число \(n\) добавляется в счетчик и в сумму. Поиск завершается, когда найдено 25 подходящих составных чисел.
Для одного кандидата \(n\) самописные проверки на простоту в версиях C++ и Java занимают \(O(\sqrt n)\) времени в худшем случае, а цикл по репьюнитам требует \(O(A(n))\) шагов и \(O(1)\) дополнительной памяти. Поскольку \(A(n)\le n\), грубая верхняя оценка для поиска до границы \(N\) имеет вид \(O(N^2)\) по времени и \(O(1)\) по вспомогательной памяти.
Эта оценка заведомо завышена. На практике работа идет быстрее, потому что рассматриваются только нечетные числа, не кратные 5, а алгоритм останавливается сразу после нахождения первых 25 подходящих составных значений.
لأي عدد صحيح موجب \(k\)، لنرمز بـ \(R(k)\) إلى repunit العشري المؤلف من \(k\) آحاد: $$R(k)=\underbrace{11\ldots1}_{k}=\frac{10^k-1}{9}.$$ ولكل \(n\) يحقق \(\gcd(n,10)=1\)، نعرّف \(A(n)\) على أنه أصغر \(k\ge 1\) بحيث \(R(k)\equiv 0 \pmod n\). المطلوب هو إيجاد مجموع أول 25 عددًا مركبًا \(n\) يحقق الشرط \(A(n)\mid(n-1)\).
تكمن أهمية هذا الشرط في أن الأعداد الأولية تمتلكه أصلًا: فكل عدد أولي \(p>5\) يحقق \(A(p)\mid(p-1)\). إذن المسألة تبحث عن أعداد مركبة تتصرف تجاه repunit كما لو كانت أولية.
التطبيقات لا تقوم بتحليل عددي ثقيل، ولا تبني repunitات هائلة الطول، ولا تعتمد على أدوات نظرية عميقة. كل ما تحتاجه هو تعريف \(A(n)\)، وعلاقة تراجعية قصيرة للبواقي، وتمشيط مباشر للأعداد المركبة المرشحة.
\(A(n)\) هو أول طول يجعل repunit قابلًا للقسمة على \(n\). والشرط \(\gcd(n,10)=1\) أساسي؛ فإذا كان لـ \(n\) عامل مشترك مع 2 أو 5 فلن يكون أي عدد ينتهي بالرقم 1 قابلًا للقسمة على \(n\).
وجود \(A(n)\) ينتج من حجة حمام زاجل بسيطة. ننظر إلى بواقي \(R(1),R(2),\ldots,R(n)\) بترديد \(n\). إذا كان أحدها يساوي 0 فقد انتهينا. وإن لم يكن كذلك، فلا بد أن يتساوى باقيان، لنقل \(R(i)\equiv R(j)\pmod n\) مع \(i>j\). عندها
$$R(i)-R(j)=10^jR(i-j)\equiv 0 \pmod n.$$
وبما أن \(\gcd(10,n)=1\)، فإن \(10^j\) قابل للعكس بترديد \(n\)، وبالتالي نستنتج \(R(i-j)\equiv 0\pmod n\). هذا يثبت أن \(A(n)\) موجود دائمًا، بل ويحقق \(A(n)\le n\).
عندما لا يكون 3 قاسمًا لـ \(n\)، يمكن أيضًا تفسير \(A(n)\) على أنه الرتبة الضربية للعدد 10 بترديد \(n\). لكن الشيفرات لا تحتاج إلى هذا الوصف؛ فهي تعمل مباشرة مع بواقي repunit، وبذلك تعالج حتى القيم التي يدخل فيها العامل 3 من دون أي حالات خاصة.
إذا كان \(p>5\) عددًا أوليًا، فإن مبرهنة فيرما الصغرى تعطي
$$10^{p-1}\equiv 1 \pmod p.$$
ولأن \(p\neq 3\)، فإن العدد 9 قابل للعكس بترديد \(p\)، ومن ثم
$$R(p-1)=\frac{10^{p-1}-1}{9}\equiv 0 \pmod p.$$
وبما أن \(A(p)\) هو أصغر طول يحقق هذه القابلية للقسمة، فلا بد أن \(A(p)\mid(p-1)\). المسألة تهتم بالأعداد المركبة التي تحتفظ بالنمط نفسه رغم أنها ليست أولية.
لنفرض أن \(A(n)=a\). عندئذٍ \(n\mid R(a)\)، أما الشرط المطلوب فهو \(a\mid(n-1)\). إذا كتبنا \(n-1=qa\)، فإن التحليل القياسي للـ repunit يعطي
$$R(qa)=R(a)\left(1+10^a+10^{2a}+\cdots+10^{(q-1)a}\right).$$
إذن متى تحقق \(A(n)\mid(n-1)\)، فإن القسمة \(n\mid R(a)\) تؤدي فورًا إلى \(n\mid R(n-1)\). وبالعكس، إذا كان \(n\mid R(n-1)\)، فإن أصغرية \(A(n)\) تفرض أن \(A(n)\mid(n-1)\). لذا يمكن فهم المسألة على أنها بحث عن الأعداد المركبة \(n\) التي تقسم repunit ذي الطول \(n-1\).
الثابت الأساسي في الشيفرة هو باقي الـ repunit الحالي بترديد \(n\). إذا عرفنا
$$r_k\equiv R(k)\pmod n,$$
فإن إضافة رقم 1 جديد في النهاية تحول \(R(k)\) إلى \(10R(k)+1\)، وبالتالي نحصل على
$$r_1\equiv 1\pmod n,\qquad r_{k+1}\equiv 10r_k+1\pmod n.$$
وهذا يولد حلقة صغيرة جدًا: نبدأ من باقي العدد 1، ثم نضيف 1 أخرى في الحساب المعياري، ونتوقف حين يصبح الباقي صفرًا. أول فهرس يصل فيه الباقي إلى الصفر هو بالضبط \(A(n)\). لا يتم أبدًا إنشاء العدد الكامل \(111\ldots1\) صراحة.
العدد 91 مركب ومشتركه الأكبر مع 10 يساوي 1، لذا فإن \(A(91)\) موجود. باستخدام العلاقة التراجعية نحصل على
$$\begin{aligned} r_1&=1,\\ r_2&\equiv 11,\\ r_3&\equiv 111\equiv 20\pmod{91},\\ r_4&\equiv 10\cdot 20+1=201\equiv 19\pmod{91},\\ r_5&\equiv 10\cdot 19+1=191\equiv 9\pmod{91},\\ r_6&\equiv 10\cdot 9+1=91\equiv 0\pmod{91}. \end{aligned}$$
إذن \(A(91)=6\). وبما أن \(6\mid 90=91-1\)، فإن 91 أحد الأعداد المركبة التي تدخل في الجواب.
تقوم تطبيقات C++ وPython وJava بتمرير الأعداد الفردية \(n=3,5,7,\ldots\) تصاعديًا. تُستبعد مضاعفات 5 فورًا، وتُرفض الأعداد الأولية، كما يبقى شرط \(\gcd(n,10)=1\) حاضرًا صراحةً حتى تظل جميع القيم المختبرة ضمن المجال الذي تكون فيه \(A(n)\) معرفة.
لكل عدد مركب يمر من التصفية، تنفذ الشيفرة تراجع بواقي repunit. كل دورة من الحلقة تعني إلحاق رقم 1 جديد، ثم أخذ النتيجة بترديد \(n\)، ثم زيادة الطول الحالي بمقدار 1. وما إن يصبح الباقي صفرًا، يكون ذلك الطول هو \(A(n)\).
بعد إيجاد \(A(n)\)، يصبح شرط القبول مجرد فحص واحد:
$$ (n-1)\bmod A(n)=0. $$
إذا تحقق الشرط، يُزاد عداد القيم المقبولة ويُضاف \(n\) إلى المجموع الجاري. وتتوقف العملية كلها عند الوصول إلى 25 عددًا مركبًا صالحًا.
لكل مرشح \(n\)، فإن اختبارات الأولية المكتوبة يدويًا في نسختي C++ وJava تكلف \(O(\sqrt n)\) زمنًا في أسوأ حالة، بينما تحتاج حلقة repunit إلى \(O(A(n))\) خطوة وذاكرة إضافية مقدارها \(O(1)\). وبما أن \(A(n)\le n\)، فإن حدًا علويًا خشنًا لكنه صحيح للمسح حتى قيمة عظمى \(N\) هو \(O(N^2)\) زمنًا و\(O(1)\) مساحةً مساعدة.
هذا الحد العلوي متحفظ عمدًا. عمليًا يكون التنفيذ أسرع كثيرًا، لأن البرنامج لا يفحص إلا الأعداد الفردية غير القابلة للقسمة على 5، ويتوقف فورًا بمجرد العثور على أول 25 عددًا مركبًا تحقق الشرط.