For the repunit \(R(k)=\underbrace{11\ldots1}_{k}\), let \(A(n)\) be the smallest positive integer \(k\) such that \(R(k)\) is divisible by \(n\). Problem 129 asks for the least \(n>10^6\) for which \(A(n)\) exceeds \(10^6\). The implementations therefore solve the threshold form of the problem: given \(L\), find the smallest \(n>L\) with \(A(n)>L\).
The important restriction is \(\gcd(n,10)=1\). If \(n\) is divisible by 2 or 5, no repunit can be a multiple of \(n\), because every repunit ends in the digit 1. That observation removes many candidates before any serious work starts.
The key idea is to avoid ever constructing the enormous integer \(R(k)\). Instead, the implementations follow only its remainder modulo \(n\), which turns the problem into a simple recurrence on a finite set of states.
The repunits satisfy
$$R(1)=1,\qquad R(k+1)=10R(k)+1.$$
For a fixed candidate \(n\), define
$$r_k \equiv R(k)\pmod n,\qquad 0\le r_k<n.$$
Reducing the repunit recurrence modulo \(n\) gives
$$r_1\equiv 1\pmod n,\qquad r_{k+1}\equiv 10r_k+1\pmod n.$$
By induction, \(r_k\) is always exactly the remainder of \(R(k)\) modulo \(n\). Therefore the quantity we want is
$$A(n)=\min\{k\ge 1:r_k=0\}.$$
This is the invariant used by all three implementations: after \(k\) steps, the stored remainder corresponds to the \(k\)-digit repunit. No big integers are required, because the state never leaves \(\{0,1,\ldots,n-1\}\).
If \(n\) has a factor 2 or 5, divisibility is impossible immediately. The more interesting statement is that when \(\gcd(n,10)=1\), a suitable repunit length is guaranteed to exist. Consider the \(n\) residues \(R(1),R(2),\ldots,R(n)\) modulo \(n\).
If one of them is already 0, then \(A(n)\) exists. Otherwise two residues are equal, say \(R(i)\equiv R(j)\pmod n\) with \(1\le i<j\le n\). Subtracting gives
$$R(j)-R(i)=10^iR(j-i)\equiv 0\pmod n.$$
Because \(\gcd(n,10)=1\), the factor \(10^i\) is invertible modulo \(n\). Hence \(R(j-i)\equiv 0\pmod n\). So for every \(n\) coprime to 10 there is at least one repunit divisible by \(n\), and in fact \(A(n)\le n-1\).
This proof explains why the search can safely ignore every candidate divisible by 2 or 5 and treat every remaining candidate as having a well-defined first zero remainder.
The recurrence is easiest to see on a small example. Start with \(r_1=1\). Then
$$r_2\equiv 10\cdot 1+1\equiv 4\pmod 7,$$
$$r_3\equiv 10\cdot 4+1\equiv 6\pmod 7,$$
$$r_4\equiv 10\cdot 6+1\equiv 5\pmod 7,$$
$$r_5\equiv 10\cdot 5+1\equiv 2\pmod 7,$$
$$r_6\equiv 10\cdot 2+1\equiv 0\pmod 7.$$
So \(A(7)=6\), which matches the identity \(111111=7\cdot 15873\). The example shows exactly what the code is doing for much larger values: it advances one repunit digit at a time and watches when the remainder first reaches zero.
For a threshold \(L\), the search condition is
$$A(n)>L\iff r_k\ne 0\text{ for every }1\le k\le L.$$
This equivalence is what makes the implementation efficient. To decide whether a candidate \(n\) qualifies, there is no need to compute the exact value of \(A(n)\) after it passes the threshold. One simply runs the recurrence for at most \(L\) steps.
If a zero remainder appears during those steps, then \(A(n)\le L\) and the candidate is rejected immediately. If the first \(L\) remainders are all nonzero, then automatically \(A(n)>L\), so the candidate qualifies. Because candidates are examined in increasing order starting from \(L+1\), the first successful one is the required answer.
The C++, Python, and Java implementations all follow the same structure. They begin at \(n=L+1\) with \(L=10^6\), increase \(n\) one by one, and skip every value divisible by 2 or 5 before entering the inner loop. That exactly enforces the necessary condition \(\gcd(n,10)=1\).
For each remaining candidate, the implementation stores only two pieces of information: the current remainder and the current repunit length. Starting from remainder 1, it repeatedly applies the modular update \(r\leftarrow (10r+1)\bmod n\). The loop stops as soon as either the remainder becomes 0 or the length passes the threshold.
If the remainder hits 0 within the first million steps, the candidate is discarded. If the loop survives past the threshold, the current \(n\) is printed and the program terminates. One implementation also includes lightweight sanity checks on smaller cases, such as \(A(7)=6\) and the reduced-threshold result \(L=10\mapsto n=17\), but the mathematical core is identical in all three languages.
Let \(L\) be the threshold and let \(C\) be the number of candidates tested before the first successful one appears. Each candidate is filtered in \(O(1)\) time for divisibility by 2 or 5, and every surviving candidate performs at most \(L\) modular updates. The worst-case running time is therefore \(O(CL)\).
The practical running time is usually smaller than that bound because many candidates reach remainder 0 well before step \(L\), so their inner loops terminate early. Memory usage is \(O(1)\): the algorithm keeps only the current candidate, the current remainder, and a counter.
Für die Repunit-Zahl \(R(k)=\underbrace{11\ldots1}_{k}\) sei \(A(n)\) die kleinste positive Zahl \(k\), für die \(R(k)\) durch \(n\) teilbar ist. Gesucht ist in Problem 129 das kleinste \(n>10^6\), für das \(A(n)\) größer als \(10^6\) ist. Die Implementierungen lösen also die Schwellenwert-Version: Zu gegebenem \(L\) finde das kleinste \(n>L\) mit \(A(n)>L\).
Entscheidend ist die Bedingung \(\gcd(n,10)=1\). Ist \(n\) durch 2 oder 5 teilbar, kann keine Repunit ein Vielfaches von \(n\) sein, weil jede Repunit auf die Ziffer 1 endet. Dadurch werden viele Kandidaten schon vor der eigentlichen Rechnung ausgeschlossen.
Der zentrale Trick besteht darin, die riesige Zahl \(R(k)\) nie direkt zu erzeugen. Stattdessen verfolgen die Implementierungen nur ihren Rest modulo \(n\). Damit wird das Problem zu einer einfachen Rekursion auf endlich vielen Zuständen.
Für Repunits gilt
$$R(1)=1,\qquad R(k+1)=10R(k)+1.$$
Für ein festes \(n\) definieren wir
$$r_k \equiv R(k)\pmod n,\qquad 0\le r_k<n.$$
Die Reduktion der Rekursion modulo \(n\) liefert
$$r_1\equiv 1\pmod n,\qquad r_{k+1}\equiv 10r_k+1\pmod n.$$
Per Induktion ist \(r_k\) immer genau der Rest der \(k\)-stelligen Repunit modulo \(n\). Also gilt
$$A(n)=\min\{k\ge 1:r_k=0\}.$$
Genau dieses Invariante benutzen alle drei Implementierungen: Nach \(k\) Schritten repräsentiert der gespeicherte Rest die \(k\)-stellige Repunit. Große Ganzzahlen tauchen nie auf, weil der Zustand immer in \(\{0,1,\ldots,n-1\}\) bleibt.
Hat \(n\) einen Faktor 2 oder 5, ist Teilbarkeit sofort unmöglich. Interessanter ist die Umkehrung: Wenn \(\gcd(n,10)=1\), dann existiert garantiert eine passende Repunit-Länge. Betrachte die \(n\) Reste \(R(1),R(2),\ldots,R(n)\) modulo \(n\).
Ist einer davon bereits 0, dann existiert \(A(n)\). Andernfalls sind zwei Reste gleich, also \(R(i)\equiv R(j)\pmod n\) mit \(1\le i<j\le n\). Durch Subtraktion erhält man
$$R(j)-R(i)=10^iR(j-i)\equiv 0\pmod n.$$
Da \(\gcd(n,10)=1\) gilt, ist \(10^i\) modulo \(n\) invertierbar. Also folgt \(R(j-i)\equiv 0\pmod n\). Damit besitzt jedes zu 10 teilerfremde \(n\) mindestens eine durch \(n\) teilbare Repunit, sogar mit \(A(n)\le n-1\).
Diese Beobachtung erklärt, warum die Suche alle Vielfachen von 2 und 5 konsequent überspringen darf und bei allen übrigen Kandidaten auf einen ersten Nullrest warten kann.
Bei kleinen Werten wird die Rekursion besonders anschaulich. Man startet mit \(r_1=1\). Dann folgt
$$r_2\equiv 10\cdot 1+1\equiv 4\pmod 7,$$
$$r_3\equiv 10\cdot 4+1\equiv 6\pmod 7,$$
$$r_4\equiv 10\cdot 6+1\equiv 5\pmod 7,$$
$$r_5\equiv 10\cdot 5+1\equiv 2\pmod 7,$$
$$r_6\equiv 10\cdot 2+1\equiv 0\pmod 7.$$
Also ist \(A(7)=6\), was mit \(111111=7\cdot 15873\) übereinstimmt. Genau denselben Mechanismus verwendet der Code für große Kandidaten: Es wird Ziffer für Ziffer weitergebaut, und man beobachtet, wann der Rest erstmals 0 wird.
Für einen Schwellenwert \(L\) lautet die Suchbedingung
$$A(n)>L\iff r_k\ne 0\text{ für alle }1\le k\le L.$$
Gerade diese Äquivalenz macht die Implementierung effizient. Um zu entscheiden, ob ein Kandidat \(n\) genügt, muss der exakte Wert von \(A(n)\) nicht mehr vollständig ausgerechnet werden, sobald die Schwelle überschritten ist. Man führt die Rekursion einfach höchstens \(L\) Schritte lang aus.
Tritt vorher ein Nullrest auf, dann gilt \(A(n)\le L\) und der Kandidat scheidet aus. Bleiben die ersten \(L\) Reste alle ungleich 0, dann folgt sofort \(A(n)>L\). Weil die Kandidaten aufsteigend ab \(L+1\) geprüft werden, ist der erste erfolgreiche Wert automatisch die gesuchte Antwort.
Die C++-, Python- und Java-Implementierungen haben denselben Aufbau. Sie beginnen bei \(n=L+1\) mit \(L=10^6\), erhöhen \(n\) schrittweise und überspringen jeden durch 2 oder 5 teilbaren Wert, noch bevor die innere Schleife startet. Damit wird die notwendige Bedingung \(\gcd(n,10)=1\) direkt umgesetzt.
Für jeden übrigen Kandidaten speichert die Implementierung nur zwei Größen: den aktuellen Rest und die aktuelle Repunit-Länge. Ausgehend vom Rest 1 wird immer wieder das modulare Update \(r\leftarrow (10r+1)\bmod n\) angewandt. Die Schleife endet, sobald entweder der Rest 0 wird oder der Zähler die Schwelle überschreitet.
Wird innerhalb der ersten Million Schritte der Rest 0, wird der Kandidat verworfen. Überlebt die Schleife die gesamte Schwelle, wird das aktuelle \(n\) ausgegeben und das Programm beendet. Eine Implementierung enthält zusätzlich kleine Plausibilitätsprüfungen wie \(A(7)=6\) und beim kleineren Schwellenwert \(L=10\) das Ergebnis \(n=17\), aber der mathematische Kern ist in allen drei Sprachen derselbe.
Sei \(L\) der Schwellenwert und \(C\) die Anzahl getesteter Kandidaten bis zum ersten Erfolg. Jeder Kandidat wird zunächst in \(O(1)\) auf Teilbarkeit durch 2 oder 5 geprüft, und jeder verbleibende Kandidat benötigt höchstens \(L\) modulare Aktualisierungen. Daraus ergibt sich im Worst Case eine Laufzeit von \(O(CL)\).
In der Praxis ist die Laufzeit meist kleiner, weil viele Kandidaten schon deutlich vor Schritt \(L\) den Rest 0 erreichen und deshalb früh abbrechen. Der Speicherbedarf ist \(O(1)\): gehalten werden nur der aktuelle Kandidat, der aktuelle Rest und ein Zähler.
\(R(k)=\underbrace{11\ldots1}_{k}\) repunit sayısı için \(A(n)\), \(R(k)\) sayısını bölen en küçük pozitif \(k\) olsun. Problem 129, \(A(n)\) değeri \(10^6\)'yı aşan en küçük \(n>10^6\) sayısını ister. Dolayısıyla uygulamalar şu eşik biçimini çözer: verilen \(L\) için \(A(n)>L\) koşulunu sağlayan en küçük \(n>L\) değerini bul.
Buradaki temel kısıt \(\gcd(n,10)=1\) şartıdır. \(n\), 2 veya 5 ile bölünüyorsa hiçbir repunit \(n\)'nin katı olamaz; çünkü her repunit son basamakta 1 taşır. Bu gözlem daha en başta pek çok adayı eler.
Ana fikir, devasa büyüklükteki \(R(k)\) sayısını hiç üretmemektir. Onun yerine uygulamalar sadece \(n\) ile bölümünden kalan kısmı takip eder. Böylece problem, sonlu sayıda durum üzerinde işleyen çok basit bir yinelemeye dönüşür.
Repunitler için
$$R(1)=1,\qquad R(k+1)=10R(k)+1$$
bağıntısı vardır. Sabit bir \(n\) için
$$r_k \equiv R(k)\pmod n,\qquad 0\le r_k<n$$
tanımını yapalım. Bu durumda modüler yineleme
$$r_1\equiv 1\pmod n,\qquad r_{k+1}\equiv 10r_k+1\pmod n$$
şeklini alır. İndüksiyonla \(r_k\)'nin her zaman \(R(k)\)'nin \(n\) ile bölümünden kalan olduğu görülür. Demek ki
$$A(n)=\min\{k\ge 1:r_k=0\}.$$
C++, Python ve Java çözümlerinin ortak invarianti tam olarak budur: \(k\) adım sonra elde tutulan kalan, \(k\) basamaklı repuniti temsil eder. Büyük tam sayılarla uğraşmaya gerek yoktur; durum uzayı her zaman \(\{0,1,\ldots,n-1\}\) kümesi içindedir.
\(n\) sayısında 2 veya 5 çarpanı varsa bölünebilme zaten imkansızdır. Daha önemli olan ters yöndür: \(\gcd(n,10)=1\) olduğunda uygun bir repunit uzunluğunun mutlaka var olması. Bunun için \(R(1),R(2),\ldots,R(n)\) değerlerinin \(n\) modundaki kalanlarına bakılır.
Bu kalanlardan biri 0 ise iş biter. Aksi halde iki tanesi eşittir; yani \(1\le i<j\le n\) için \(R(i)\equiv R(j)\pmod n\). Çıkarınca
$$R(j)-R(i)=10^iR(j-i)\equiv 0\pmod n$$
elde edilir. \(\gcd(n,10)=1\) olduğundan \(10^i\) mod \(n\) altında terslenebilir. O hâlde \(R(j-i)\equiv 0\pmod n\) olur. Yani 10 ile aralarında asal olan her \(n\) için en az bir repunit bölünür ve hatta \(A(n)\le n-1\) elde edilir.
Bu ispat, neden 2 ve 5 katlarının tamamen atlanabildiğini ve diğer tüm adaylarda ilk sıfır kalanın anlamlı bir hedef olduğunu açıklar.
Yineleme küçük bir örnekte açıkça görülür. Başlangıçta \(r_1=1\). Sonra
$$r_2\equiv 10\cdot 1+1\equiv 4\pmod 7,$$
$$r_3\equiv 10\cdot 4+1\equiv 6\pmod 7,$$
$$r_4\equiv 10\cdot 6+1\equiv 5\pmod 7,$$
$$r_5\equiv 10\cdot 5+1\equiv 2\pmod 7,$$
$$r_6\equiv 10\cdot 2+1\equiv 0\pmod 7.$$
Böylece \(A(7)=6\) bulunur; gerçekten de \(111111=7\cdot 15873\). Kod çok daha büyük sayılar için de tam olarak bunu yapar: repuniti basamak basamak ilerletir ve kalanın ilk kez ne zaman 0 olduğunu izler.
Eşik \(L\) için aranan koşul
$$A(n)>L\iff r_k\ne 0\text{ her }1\le k\le L\text{ için}$$
şeklindedir. Uygulamaların verimli olmasının nedeni tam olarak bu eşdeğerliktir. Bir adayın uygun olup olmadığını anlamak için \(A(n)\)'yi eşik aşıldıktan sonra tamamen hesaplamak gerekmez; yinelemeyi en fazla \(L\) adım yürütmek yeterlidir.
Bu adımlar içinde kalan 0 olursa \(A(n)\le L\) ve aday elenir. İlk \(L\) adım boyunca hiç 0 görülmezse otomatik olarak \(A(n)>L\) olur. Adaylar \(L+1\)'den başlayarak artan sırayla denendiği için, bu testi geçen ilk değer doğrudan cevaptır.
C++, Python ve Java uygulamaları aynı yapıyı izler. \(L=10^6\) alınarak \(n=L+1\) noktasından başlanır, \(n\) birer birer artırılır ve iç döngüye girmeden önce 2'ye ya da 5'e bölünen her değer atlanır. Böylece gerekli \(\gcd(n,10)=1\) şartı doğrudan uygulanmış olur.
Kalan adaylar için uygulama yalnızca iki şey saklar: güncel kalan ve güncel repunit uzunluğu. Başlangıçta kalan 1'dir; sonra sürekli \(r\leftarrow (10r+1)\bmod n\) güncellemesi yapılır. Döngü, kalan 0 olduğunda ya da sayaç eşiği geçtiğinde biter.
Kalan ilk milyon adım içinde 0 olursa aday reddedilir. Döngü eşik sonrasına taşarsa mevcut \(n\) yazdırılır ve program sonlanır. Uygulamalardan biri ayrıca \(A(7)=6\) ve küçültülmüş eşik \(L=10\) için ilk uygun değerin 17 olması gibi küçük doğrulama örnekleri içerir; fakat üç dilde de matematiksel çekirdek aynıdır.
\(L\) eşik değeri, \(C\) ise ilk başarıya kadar test edilen aday sayısı olsun. Her aday önce 2 ve 5'e bölünebilirlik açısından \(O(1)\) sürede süzülür; geriye kalan her aday en fazla \(L\) modüler güncelleme yapar. Dolayısıyla en kötü durum çalışma süresi \(O(CL)\) olur.
Pratikte süre genellikle bundan daha küçüktür; çünkü birçok aday \(L\) adımına gelmeden önce 0 kalana ulaşır ve erken kesilir. Bellek kullanımı \(O(1)\)'dir: sadece güncel aday, güncel kalan ve bir sayaç tutulur.
Para el repunit \(R(k)=\underbrace{11\ldots1}_{k}\), sea \(A(n)\) el menor entero positivo \(k\) tal que \(R(k)\) es divisible por \(n\). El problema 129 pide el menor \(n>10^6\) para el cual \(A(n)\) supera \(10^6\). Por eso las implementaciones resuelven la versión con umbral: dado \(L\), encontrar el menor \(n>L\) con \(A(n)>L\).
La restricción decisiva es \(\gcd(n,10)=1\). Si \(n\) es divisible por 2 o por 5, ningún repunit puede ser múltiplo de \(n\), porque todo repunit termina en la cifra 1. Esa observación elimina muchos candidatos antes de hacer trabajo modular real.
La idea central es no construir nunca el entero gigantesco \(R(k)\). En su lugar, las implementaciones siguen solo su residuo módulo \(n\). Así, el problema se convierte en una recurrencia muy simple sobre un conjunto finito de estados.
Los repunits cumplen
$$R(1)=1,\qquad R(k+1)=10R(k)+1.$$
Para un candidato fijo \(n\), definimos
$$r_k \equiv R(k)\pmod n,\qquad 0\le r_k<n.$$
Al reducir la recurrencia módulo \(n\) obtenemos
$$r_1\equiv 1\pmod n,\qquad r_{k+1}\equiv 10r_k+1\pmod n.$$
Por inducción, \(r_k\) es siempre exactamente el resto de \(R(k)\) al dividir por \(n\). Por tanto,
$$A(n)=\min\{k\ge 1:r_k=0\}.$$
Ese es el invariante que comparten las tres implementaciones: después de \(k\) pasos, el residuo almacenado corresponde al repunit de longitud \(k\). Nunca hacen falta enteros enormes, porque el estado siempre permanece dentro de \(\{0,1,\ldots,n-1\}\).
Si \(n\) tiene un factor 2 o 5, la divisibilidad es imposible desde el principio. La afirmación interesante es la recíproca: cuando \(\gcd(n,10)=1\), existe con seguridad alguna longitud de repunit válida. Consideremos los \(n\) residuos \(R(1),R(2),\ldots,R(n)\) módulo \(n\).
Si uno de ellos ya es 0, entonces \(A(n)\) existe. Si no, dos de ellos coinciden, es decir, \(R(i)\equiv R(j)\pmod n\) con \(1\le i<j\le n\). Restando se obtiene
$$R(j)-R(i)=10^iR(j-i)\equiv 0\pmod n.$$
Como \(\gcd(n,10)=1\), el factor \(10^i\) es invertible módulo \(n\). Por consiguiente, \(R(j-i)\equiv 0\pmod n\). Así, para todo \(n\) coprimo con 10 existe al menos un repunit divisible por \(n\), y de hecho \(A(n)\le n-1\).
Esta prueba explica por qué la búsqueda puede descartar sistemáticamente los múltiplos de 2 y 5 y esperar, en todos los demás casos, a que aparezca el primer residuo nulo.
La recurrencia se ve con claridad en un ejemplo pequeño. Empezamos con \(r_1=1\). Después,
$$r_2\equiv 10\cdot 1+1\equiv 4\pmod 7,$$
$$r_3\equiv 10\cdot 4+1\equiv 6\pmod 7,$$
$$r_4\equiv 10\cdot 6+1\equiv 5\pmod 7,$$
$$r_5\equiv 10\cdot 5+1\equiv 2\pmod 7,$$
$$r_6\equiv 10\cdot 2+1\equiv 0\pmod 7.$$
Por tanto \(A(7)=6\), en concordancia con \(111111=7\cdot 15873\). Eso es exactamente lo que hace el código para candidatos mucho mayores: avanza un dígito de repunit por iteración y observa cuándo el residuo llega por primera vez a 0.
Para un umbral \(L\), la condición buscada es
$$A(n)>L\iff r_k\ne 0\text{ para todo }1\le k\le L.$$
Esa equivalencia es justamente la razón de la eficiencia. Para decidir si un candidato \(n\) sirve, no hace falta calcular el valor exacto de \(A(n)\) una vez superado el umbral. Basta con ejecutar la recurrencia durante, como mucho, \(L\) pasos.
Si aparece un residuo 0 antes de ese límite, entonces \(A(n)\le L\) y el candidato se rechaza. Si los primeros \(L\) residuos son todos distintos de 0, se concluye automáticamente que \(A(n)>L\). Como los candidatos se prueban en orden creciente a partir de \(L+1\), el primero que supera esta prueba es la respuesta buscada.
Las implementaciones en C++, Python y Java siguen la misma estructura. Empiezan en \(n=L+1\) con \(L=10^6\), incrementan \(n\) de uno en uno y descartan todo valor divisible por 2 o por 5 antes de entrar en el bucle interno. Así se aplica de forma directa la condición necesaria \(\gcd(n,10)=1\).
Para cada candidato restante, la implementación conserva solo dos datos: el residuo actual y la longitud actual del repunit. A partir del residuo 1, repite la actualización modular \(r\leftarrow (10r+1)\bmod n\). El bucle termina tan pronto como el residuo se hace 0 o el contador supera el umbral.
Si el residuo llega a 0 dentro del primer millón de pasos, el candidato se descarta. Si el bucle sobrevive más allá del umbral, se imprime el valor actual de \(n\) y el programa termina. Una de las implementaciones también incluye comprobaciones pequeñas, como \(A(7)=6\) y el resultado reducido \(L=10\mapsto n=17\), pero el núcleo matemático es el mismo en los tres lenguajes.
Sea \(L\) el umbral y \(C\) el número de candidatos probados hasta encontrar el primero válido. Cada candidato se filtra por divisibilidad entre 2 y 5 en tiempo \(O(1)\), y cada candidato que sobrevive realiza como máximo \(L\) actualizaciones modulares. Por tanto, el tiempo de ejecución en el peor caso es \(O(CL)\).
En la práctica suele ser menor, porque muchos candidatos alcanzan residuo 0 bastante antes del paso \(L\) y se abandonan enseguida. El uso de memoria es \(O(1)\): solo se guardan el candidato actual, el residuo actual y un contador.
对 repunit \(R(k)=\underbrace{11\ldots1}_{k}\)，定义 \(A(n)\) 为满足 \(R(k)\) 能被 \(n\) 整除的最小正整数 \(k\)。Problem 129 要求的是最小的 \(n>10^6\)，使得 \(A(n)\) 严格大于 \(10^6\)。因此这些实现实际上在解一个阈值版本的问题：给定 \(L\)，寻找最小的 \(n>L\)，使 \(A(n)>L\)。
最关键的限制条件是 \(\gcd(n,10)=1\)。如果 \(n\) 含有 2 或 5 的因子，那么任何 repunit 都不可能被 \(n\) 整除，因为 repunit 的十进制末位永远是 1。这个观察使得大量候选值在进入主计算之前就可以直接跳过。
核心思想是从头到尾都不去显式构造巨大的整数 \(R(k)\)。实现只追踪它对 \(n\) 的余数。这样一来，问题就被改写成有限状态集合上的一个简单递推过程。
repunit 满足
$$R(1)=1,\qquad R(k+1)=10R(k)+1.$$
对固定候选值 \(n\)，定义
$$r_k \equiv R(k)\pmod n,\qquad 0\le r_k<n.$$
把上式按模 \(n\) 化简，就得到
$$r_1\equiv 1\pmod n,\qquad r_{k+1}\equiv 10r_k+1\pmod n.$$
用归纳法可知，\(r_k\) 始终就是 \(R(k)\) 除以 \(n\) 的余数。因此
$$A(n)=\min\{k\ge 1:r_k=0\}.$$
这正是三种实现共享的不变量：做完第 \(k\) 步之后，程序手里的余数就对应长度为 \(k\) 的 repunit。由于状态永远落在 \(\{0,1,\ldots,n-1\}\) 中，所以完全不需要大整数。
如果 \(n\) 有 2 或 5 作为因子，那么整除性从一开始就是不可能的。更重要的是反过来的结论：当 \(\gcd(n,10)=1\) 时，某个合适的 repunit 长度一定存在。考虑 \(R(1),R(2),\ldots,R(n)\) 在模 \(n\) 下的这 \(n\) 个余数。
如果其中已经有一个等于 0，那么 \(A(n)\) 直接存在。否则，根据抽屉原理，必有两个余数相同，即存在 \(1\le i<j\le n\) 使得 \(R(i)\equiv R(j)\pmod n\)。相减可得
$$R(j)-R(i)=10^iR(j-i)\equiv 0\pmod n.$$
因为 \(\gcd(n,10)=1\)，所以 \(10^i\) 在模 \(n\) 下可逆，于是推出 \(R(j-i)\equiv 0\pmod n\)。也就是说，只要 \(n\) 与 10 互素，就一定存在某个 repunit 被 \(n\) 整除，而且实际上 \(A(n)\le n-1\)。
这个证明说明了两点：为什么 2 和 5 的倍数可以完全跳过，以及为什么对其他候选值来说，“第一次出现零余数的位置”是一个定义良好的对象。
在小例子上，这个递推过程非常直观。先取 \(r_1=1\)。随后有
$$r_2\equiv 10\cdot 1+1\equiv 4\pmod 7,$$
$$r_3\equiv 10\cdot 4+1\equiv 6\pmod 7,$$
$$r_4\equiv 10\cdot 6+1\equiv 5\pmod 7,$$
$$r_5\equiv 10\cdot 5+1\equiv 2\pmod 7,$$
$$r_6\equiv 10\cdot 2+1\equiv 0\pmod 7.$$
所以 \(A(7)=6\)，这与 \(111111=7\cdot 15873\) 完全一致。程序面对更大的候选值时做的也是同一件事：每次增加一个数字 1，并观察余数第一次何时变成 0。
对于阈值 \(L\)，要检查的条件可以写成
$$A(n)>L\iff r_k\ne 0\text{ 对所有 }1\le k\le L.$$
这正是实现能够高效运行的原因。为了判断某个候选值 \(n\) 是否合格，一旦超过阈值，就没有必要再把 \(A(n)\) 的精确数值算到底。只要把递推最多执行 \(L\) 步就够了。
如果在这 \(L\) 步之内出现余数 0，就说明 \(A(n)\le L\)，当前候选值立即淘汰。如果前 \(L\) 个余数全部非零，就自动得到 \(A(n)>L\)。由于候选值从 \(L+1\) 开始按升序检查，第一次通过测试的 \(n\) 就是题目要求的最小值。
C++、Python 和 Java 三个实现的结构完全一致。它们从 \(n=L+1\) 开始，这里 \(L=10^6\)，然后把 \(n\) 逐个递增；凡是能被 2 或 5 整除的值，都在进入内层循环之前直接跳过。这一步正好落实了必要条件 \(\gcd(n,10)=1\)。
对每个剩余候选值，实现只维护两个量：当前余数和当前 repunit 长度。从余数 1 出发，不断执行模更新 \(r\leftarrow (10r+1)\bmod n\)。循环在两种情况下停止：余数变成 0，或者计数器超过阈值。
如果余数在前一百万步内变成 0，当前候选值被丢弃；如果循环在超过阈值后仍未遇到 0，就输出当前 \(n\) 并结束。还有一个实现附带了较小规模的自检，例如 \(A(7)=6\) 以及缩小阈值时 \(L=10\mapsto n=17\)，但三种语言的数学核心完全相同。
设阈值为 \(L\)，在找到第一个成功候选值之前总共测试了 \(C\) 个候选数。每个候选数先用 \(O(1)\) 时间检查是否被 2 或 5 整除，而每个保留下来的候选数最多执行 \(L\) 次模更新。因此最坏情况下的时间复杂度是 \(O(CL)\)。
实际运行通常比这个上界更快，因为很多候选值会在远早于第 \(L\) 步时就遇到余数 0，从而提前退出。空间复杂度是 \(O(1)\)：算法只保存当前候选值、当前余数和一个计数器。
Для репъюнита \(R(k)=\underbrace{11\ldots1}_{k}\) обозначим через \(A(n)\) наименьшее положительное \(k\), при котором \(R(k)\) делится на \(n\). В задаче 129 требуется найти наименьшее \(n>10^6\), для которого \(A(n)\) строго больше \(10^6\). Поэтому реализации фактически решают пороговую формулировку: для данного \(L\) найти наименьшее \(n>L\), такое что \(A(n)>L\).
Ключевое ограничение состоит в условии \(\gcd(n,10)=1\). Если \(n\) делится на 2 или на 5, никакой репъюнит не может быть кратен \(n\), потому что любой репъюнит оканчивается цифрой 1. Это сразу отсеивает много кандидатов.
Главная идея состоит в том, чтобы никогда не строить огромный целый объект \(R(k)\) явно. Реализации отслеживают только его остаток по модулю \(n\). Благодаря этому задача превращается в простую рекурсию на конечном множестве состояний.
Для репъюнитов верно
$$R(1)=1,\qquad R(k+1)=10R(k)+1.$$
Для фиксированного кандидата \(n\) положим
$$r_k \equiv R(k)\pmod n,\qquad 0\le r_k<n.$$
Тогда после перехода к модулю \(n\) получаем рекурсию
$$r_1\equiv 1\pmod n,\qquad r_{k+1}\equiv 10r_k+1\pmod n.$$
По индукции \(r_k\) всегда является точным остатком от \(R(k)\) при делении на \(n\). Следовательно,
$$A(n)=\min\{k\ge 1:r_k=0\}.$$
Именно этот инвариант используют все три реализации: после \(k\) шагов хранимый остаток соответствует репъюниту длины \(k\). Большие целые числа не нужны, потому что состояние никогда не выходит из множества \(\{0,1,\ldots,n-1\}\).
Если у \(n\) есть множитель 2 или 5, делимость невозможна сразу. Более содержательно обратное утверждение: если \(\gcd(n,10)=1\), подходящая длина репъюнита обязательно существует. Рассмотрим \(n\) остатков \(R(1),R(2),\ldots,R(n)\) по модулю \(n\).
Если один из них уже равен 0, то \(A(n)\) существует. Иначе два остатка совпадают: \(R(i)\equiv R(j)\pmod n\) при \(1\le i<j\le n\). Вычитая, получаем
$$R(j)-R(i)=10^iR(j-i)\equiv 0\pmod n.$$
Так как \(\gcd(n,10)=1\), число \(10^i\) обратимо по модулю \(n\). Значит, \(R(j-i)\equiv 0\pmod n\). Итак, для любого \(n\), взаимно простого с 10, найдется хотя бы один репъюнит, кратный \(n\), причём даже \(A(n)\le n-1\).
Это доказательство объясняет, почему можно полностью пропускать кратные 2 и 5 и почему для остальных кандидатов корректно искать первое появление нулевого остатка.
На маленьком примере рекурсия видна особенно ясно. Начинаем с \(r_1=1\). Затем
$$r_2\equiv 10\cdot 1+1\equiv 4\pmod 7,$$
$$r_3\equiv 10\cdot 4+1\equiv 6\pmod 7,$$
$$r_4\equiv 10\cdot 6+1\equiv 5\pmod 7,$$
$$r_5\equiv 10\cdot 5+1\equiv 2\pmod 7,$$
$$r_6\equiv 10\cdot 2+1\equiv 0\pmod 7.$$
Следовательно, \(A(7)=6\), что согласуется с равенством \(111111=7\cdot 15873\). Именно это и делает код для больших кандидатов: добавляет ещё одну цифру 1 и наблюдает, когда остаток впервые станет нулём.
Для порога \(L\) искомое условие можно записать так:
$$A(n)>L\iff r_k\ne 0\text{ для всех }1\le k\le L.$$
Именно эта эквивалентность делает реализацию эффективной. Чтобы понять, подходит ли кандидат \(n\), не нужно вычислять точное значение \(A(n)\) после того, как порог уже пройден. Достаточно выполнить рекурсию не более чем \(L\) шагов.
Если нулевой остаток появляется раньше, то \(A(n)\le L\), и кандидат сразу отвергается. Если первые \(L\) остатков все ненулевые, автоматически получаем \(A(n)>L\). Поскольку кандидаты проверяются по возрастанию, начиная с \(L+1\), первый успешный кандидат и есть ответ.
Реализации на C++, Python и Java устроены одинаково. Они начинают с \(n=L+1\), где \(L=10^6\), увеличивают \(n\) на единицу и пропускают каждое число, делящееся на 2 или 5, ещё до входа во внутренний цикл. Так прямо реализуется необходимое условие \(\gcd(n,10)=1\).
Для каждого оставшегося кандидата хранится только текущий остаток и текущая длина репъюнита. Начиная с остатка 1, программа многократно выполняет обновление \(r\leftarrow (10r+1)\bmod n\). Цикл заканчивается, как только остаток становится равным 0 или счётчик превышает порог.
Если остаток становится 0 в пределах первого миллиона шагов, кандидат отбрасывается. Если цикл переживает порог, текущее \(n\) выводится, и программа завершается. Одна из реализаций также содержит небольшие проверки корректности, например \(A(7)=6\) и результат \(L=10\mapsto n=17\), но математическое ядро во всех трёх языках одинаково.
Пусть \(L\) обозначает порог, а \(C\) — количество кандидатов, проверенных до первого успеха. Каждый кандидат сначала фильтруется по делимости на 2 и 5 за \(O(1)\), а каждый прошедший кандидат делает не более \(L\) модульных обновлений. Следовательно, оценка времени работы в худшем случае равна \(O(CL)\).
На практике программа обычно работает быстрее, потому что у многих кандидатов нулевой остаток возникает задолго до шага \(L\), и внутренний цикл завершается рано. Память равна \(O(1)\): хранятся только текущий кандидат, текущий остаток и счётчик.
لعدد repunit المعطى بالعلاقة \(R(k)=\underbrace{11\ldots1}_{k}\)، نرمز بـ \(A(n)\) إلى أصغر عدد صحيح موجب \(k\) بحيث يكون \(R(k)\) قابلًا للقسمة على \(n\). تطلب المسألة 129 إيجاد أصغر \(n>10^6\) بحيث يكون \(A(n)\) أكبر من \(10^6\) لا مجرد مساويًا له. لذلك فإن التنفيذات الثلاثة تحل الصياغة الحدّية العامة: عند إعطاء حد \(L\)، ابحث عن أصغر \(n>L\) يحقق \(A(n)>L\).
الشرط الحاسم هنا هو \(\gcd(n,10)=1\). فإذا كان \(n\) يقبل القسمة على 2 أو 5، فلا يمكن لأي repunit أن يكون من مضاعفاته، لأن كل repunit ينتهي بالرقم 1. هذه الملاحظة تستبعد عددًا كبيرًا من المرشحين قبل بدء الحساب الحقيقي.
الفكرة الأساسية هي عدم بناء العدد الهائل \(R(k)\) مباشرةً. بدلًا من ذلك، تتابع التنفيذات فقط باقي قسمته على \(n\). وبهذا تتحول المسألة إلى علاقة عودية بسيطة على مجموعة منتهية من الحالات.
أعداد repunit تحقق العلاقة
$$R(1)=1,\qquad R(k+1)=10R(k)+1.$$
ولمرشح ثابت \(n\)، نعرّف
$$r_k \equiv R(k)\pmod n,\qquad 0\le r_k<n.$$
وبأخذ العلاقة السابقة بترديد \(n\) نحصل على
$$r_1\equiv 1\pmod n,\qquad r_{k+1}\equiv 10r_k+1\pmod n.$$
وبالاستقراء يكون \(r_k\) دائمًا هو باقي \(R(k)\) الحقيقي عند القسمة على \(n\). لذلك
$$A(n)=\min\{k\ge 1:r_k=0\}.$$
هذا هو الثابت الرياضي الذي تعتمد عليه حلول C++ وPython وJava جميعًا: بعد \(k\) خطوات، يكون الباقي المخزَّن ممثلًا للـ repunit ذي \(k\) خانات. ولا حاجة إلى أعداد ضخمة، لأن الحالة تبقى دائمًا داخل المجموعة \(\{0,1,\ldots,n-1\}\).
إذا كان لـ \(n\) عامل 2 أو 5 فالقابلية للقسمة مستحيلة من الأصل. والأهم هو العكس: إذا كان \(\gcd(n,10)=1\)، فهناك طول مناسب من repunit ينجح حتمًا. انظر إلى البواقي \(R(1),R(2),\ldots,R(n)\) بترديد \(n\).
إذا كان أحدها صفرًا فالأمر منتهٍ. وإذا لم يحدث ذلك، فلا بد أن يتساوى باقيان، أي توجد قيمتان \(1\le i<j\le n\) تحققان \(R(i)\equiv R(j)\pmod n\). بالطرح نحصل على
$$R(j)-R(i)=10^iR(j-i)\equiv 0\pmod n.$$
وبما أن \(\gcd(n,10)=1\)، فإن \(10^i\) عنصر قابل للعكس بترديد \(n\). إذًا ينتج \(R(j-i)\equiv 0\pmod n\). هذا يثبت أن كل \(n\) أولي نسبيًا مع 10 يقسم أحد أعداد repunit، بل وحتى \(A(n)\le n-1\).
هذه الحجة تفسر لماذا يمكن تجاهل جميع مضاعفات 2 و5 بالكامل، ولماذا يصبح البحث عن أول ظهور للباقي الصفري فكرة صحيحة لكل المرشحين الآخرين.
تتضح العودية بسرعة على مثال صغير. نبدأ بـ \(r_1=1\). بعد ذلك
$$r_2\equiv 10\cdot 1+1\equiv 4\pmod 7,$$
$$r_3\equiv 10\cdot 4+1\equiv 6\pmod 7,$$
$$r_4\equiv 10\cdot 6+1\equiv 5\pmod 7,$$
$$r_5\equiv 10\cdot 5+1\equiv 2\pmod 7,$$
$$r_6\equiv 10\cdot 2+1\equiv 0\pmod 7.$$
إذًا \(A(7)=6\)، وهو ما يطابق العلاقة \(111111=7\cdot 15873\). وهذا بالضبط ما يفعله البرنامج مع القيم الكبيرة أيضًا: يضيف خانة 1 واحدة في كل خطوة ويراقب متى يصبح الباقي صفرًا لأول مرة.
عند حد \(L\)، يمكن كتابة شرط البحث على الصورة
$$A(n)>L\iff r_k\ne 0\text{ لكل }1\le k\le L.$$
هذه المكافأة هي سر الكفاءة. فلكي نقرر هل المرشح \(n\) مناسب، لا نحتاج إلى حساب القيمة الدقيقة لـ \(A(n)\) بعد تجاوز الحد. يكفي أن نشغّل العودية حتى \(L\) خطوة كحد أقصى.
إذا ظهر باقي صفري قبل ذلك، فهذا يعني أن \(A(n)\le L\) ويُرفض المرشح فورًا. وإذا بقيت البواقي غير صفرية خلال أول \(L\) خطوة كلها، فنستنتج مباشرةً أن \(A(n)>L\). وبما أن المرشحين يُفحصون تصاعديًا بدءًا من \(L+1\)، فإن أول قيمة تجتاز هذا الاختبار هي الجواب المطلوب.
تتبع تنفيذات C++ وPython وJava البنية نفسها. فهي تبدأ من \(n=L+1\) حيث \(L=10^6\)، ثم تزيد \(n\) واحدًا واحدًا، وتتجاوز كل قيمة تقبل القسمة على 2 أو 5 قبل دخول الحلقة الداخلية. هكذا يُطبَّق الشرط الضروري \(\gcd(n,10)=1\) مباشرة.
لكل مرشح متبقٍ، يحتفظ التنفيذ بمعلومتين فقط: الباقي الحالي وطول repunit الحالي. انطلاقًا من الباقي 1، يكرر التحديث \(r\leftarrow (10r+1)\bmod n\). وتنتهي الحلقة فور أن يصبح الباقي صفرًا أو أن يتجاوز العداد الحد.
إذا وصل الباقي إلى الصفر خلال أول مليون خطوة، يُرفض المرشح. وإذا تجاوزت الحلقة الحد دون أن ترى صفرًا، تُطبع قيمة \(n\) الحالية ويتوقف البرنامج. كما أن أحد التنفيذات يتضمن فحوصًا صغيرة مثل \(A(7)=6\) والحالة المختزلة \(L=10\mapsto n=17\)، لكن الجوهر الرياضي واحد في اللغات الثلاث.
ليكن \(L\) هو الحد، ولتكن \(C\) هي عدد القيم المرشحة التي تُفحص قبل الوصول إلى أول نجاح. كل مرشح يُرشَّح أولًا في زمن \(O(1)\) باختبار القسمة على 2 و5، وكل مرشح ينجو من هذا الاختبار يحتاج إلى ما لا يزيد على \(L\) تحديثات معيارية. لذلك يكون حد الزمن في أسوأ الأحوال هو \(O(CL)\).
وغالبًا ما يكون الأداء الفعلي أفضل من ذلك، لأن كثيرًا من المرشحين يصلون إلى باقي صفري قبل الخطوة \(L\) بوقت طويل، فتتوقف حلقاتهم الداخلية مبكرًا. أما الذاكرة فهي \(O(1)\): لا يُحفظ إلا المرشح الحالي، والباقي الحالي، وعداد الخطوات.