The implementation searches for the smallest integer \(n>42\) such that a derived quantity \(t(n)\) is divisible by \(10^6\). Instead of building enormous exact integers, it works with a seventh-order linear recurrence and tracks only residues modulo \(10^6\).
The recurrence starts from
$$a_0=1,\quad a_1=1,\quad a_2=1,\quad a_3=2,\quad a_4=2,\quad a_5=3,\quad a_6=4,$$
and the tested quantity is
$$t(n)=2^{\lfloor n/2\rfloor}-a_n.$$
So the task is to find the first \(n>42\) with
$$t(n)\equiv 0 \pmod{10^6}.$$
The key observation is that the problem is entirely about divisibility by \(10^6\), so both the recurrence and the power term can be evolved in modular arithmetic from the very beginning.
For \(n\ge 7\), the sequence satisfies
$$a_n=a_{n-1}+2a_{n-2}-2a_{n-3}-a_{n-4}+a_{n-5}+a_{n-6}-a_{n-7}.$$
The target expression is the difference between a parity-driven power of two and the recurrence value:
$$t(n)=2^{\lfloor n/2\rfloor}-a_n.$$
Nothing else is needed for the search: once \(a_n\) and \(2^{\lfloor n/2\rfloor}\) are known, the divisibility test is immediate.
Let
$$M=10^6.$$
Because divisibility by \(M\) depends only on residues modulo \(M\), we may replace every exact value by its residue:
$$a_n \equiv \overline{a}_n \pmod{M},\qquad 2^{\lfloor n/2\rfloor}\equiv \overline{p}_n \pmod{M}.$$
Then
$$t(n)\equiv \overline{p}_n-\overline{a}_n \pmod{M},$$
so the search condition becomes
$$\overline{p}_n-\overline{a}_n\equiv 0\pmod{M}.$$
This means the exact integers are unnecessary. The implementation can run forever using bounded integers in the interval \([0,M)\).
Define
$$p_n=2^{\lfloor n/2\rfloor}.$$
Since \(\lfloor n/2\rfloor\) increases only when \(n\) changes from odd to even, the sequence \(p_n\) obeys a very simple rule:
$$p_n=\begin{cases} p_{n-1}, & n\text{ odd},\\ 2p_{n-1}, & n\text{ even}. \end{cases}$$
Therefore the modular power residue needs only one multiplication by \(2\) on even steps, and no change on odd steps.
The recurrence for \(a_n\) depends only on the previous seven values. Consequently, the full history is irrelevant once the latest seven residues are known.
If we keep the block
$$\left(\overline{a}_{n-1},\overline{a}_{n-2},\dots,\overline{a}_{n-7}\right),$$
then the next residue follows from the same linear combination, interpreted modulo \(M\):
$$\overline{a}_n\equiv \overline{a}_{n-1}+2\overline{a}_{n-2}-2\overline{a}_{n-3}-\overline{a}_{n-4}+\overline{a}_{n-5}+\overline{a}_{n-6}-\overline{a}_{n-7}\pmod{M}.$$
That is why a circular buffer of length \(7\) is enough. The search is linear in the answer but constant in memory.
The recurrence contains negative coefficients, so intermediate sums may be negative before reduction. Mathematically, the correct residue is always the unique value in \([0,M)\) congruent to that sum.
In formula form, one may write
$$\operatorname{norm}(x)=((x\bmod M)+M)\bmod M.$$
This keeps every stored recurrence value and every tested difference inside the canonical residue range.
The first few recurrence steps are small enough to compute exactly. Using the initial values, we obtain
$$\begin{aligned} a_7&=4+2\cdot 3-2\cdot 2-2+1+1-1=5,\\ a_8&=5+2\cdot 4-2\cdot 3-2+2+1-1=7,\\ a_9&=7+2\cdot 5-2\cdot 4-3+2+2-1=9,\\ a_{10}&=9+2\cdot 7-2\cdot 5-4+3+2-2=12. \end{aligned}$$
The power term is
$$p_7=2^3=8,\qquad p_8=2^4=16,\qquad p_9=2^4=16,\qquad p_{10}=2^5=32.$$
Hence
$$t(7)=8-5=3,\qquad t(8)=16-7=9,\qquad t(9)=16-9=7,\qquad t(10)=32-12=20.$$
Two larger checkpoints that agree with the exact recurrence are
$$t(20)=824,\qquad t(42)=1{,}999{,}923.$$
Those values confirm that the recurrence and the power-tracking rule are synchronized correctly before the final modular scan continues beyond \(42\).
The C++, Python, and Java implementations all follow the same structure. They initialize the seven starting values of the recurrence and a running residue for \(2^{\lfloor n/2\rfloor}\). The main loop advances \(n\) one step at a time. On even \(n\), the power residue is doubled modulo \(10^6\). Once \(n\ge 7\), the next recurrence value is computed from the previous seven stored residues and written back into the recycled slot of a circular buffer.
After that update, the implementation compares the power residue and the recurrence residue modulo \(10^6\). If their difference is congruent to \(0\), then \(t(n)\) is divisible by \(10^6\). The loop returns the first such \(n\) with \(n>42\). Because only seven recurrence entries and one power residue are retained, the code stays compact and memory-efficient.
Let \(N_*\) be the first index greater than \(42\) satisfying \(t(N_*)\equiv 0\pmod{10^6}\). Each loop iteration performs a constant amount of arithmetic: one parity check, at most one multiplication by \(2\), one recurrence update using seven cached residues, and one modular comparison. Therefore the running time is \(O(N_*)\), while the memory usage is \(O(1)\).
Die Implementierung sucht das kleinste \(n>42\), für das eine abgeleitete Größe \(t(n)\) durch \(10^6\) teilbar ist. Statt riesige exakte Zahlen aufzubauen, arbeitet sie mit einer linearen Rekurrenz siebter Ordnung und verfolgt nur Restklassen modulo \(10^6\).
Die Rekurrenz startet mit
$$a_0=1,\quad a_1=1,\quad a_2=1,\quad a_3=2,\quad a_4=2,\quad a_5=3,\quad a_6=4,$$
und die getestete Größe ist
$$t(n)=2^{\lfloor n/2\rfloor}-a_n.$$
Gesucht ist also das erste \(n>42\) mit
$$t(n)\equiv 0 \pmod{10^6}.$$
Der entscheidende Punkt ist, dass nur die Teilbarkeit durch \(10^6\) interessiert. Deshalb können sowohl die Rekurrenz als auch der Zweierpotenz-Term von Anfang an vollständig modular entwickelt werden.
Für \(n\ge 7\) gilt
$$a_n=a_{n-1}+2a_{n-2}-2a_{n-3}-a_{n-4}+a_{n-5}+a_{n-6}-a_{n-7}.$$
Die Zielgröße ist die Differenz zwischen einer paritätsgesteuerten Zweierpotenz und dem Rekurrenzwert:
$$t(n)=2^{\lfloor n/2\rfloor}-a_n.$$
Mehr ist für die Suche nicht nötig: Sind \(a_n\) und \(2^{\lfloor n/2\rfloor}\) bekannt, ist der Teilbarkeitstest unmittelbar.
Setze
$$M=10^6.$$
Da Teilbarkeit durch \(M\) nur von Restklassen modulo \(M\) abhängt, dürfen alle exakten Werte durch ihre Reste ersetzt werden:
$$a_n \equiv \overline{a}_n \pmod{M},\qquad 2^{\lfloor n/2\rfloor}\equiv \overline{p}_n \pmod{M}.$$
Dann folgt
$$t(n)\equiv \overline{p}_n-\overline{a}_n \pmod{M},$$
und die Bedingung wird zu
$$\overline{p}_n-\overline{a}_n\equiv 0\pmod{M}.$$
Exakte Großzahlen sind also überflüssig; die Implementierung kann ausschließlich mit Resten im Bereich \([0,M)\) arbeiten.
Definiere
$$p_n=2^{\lfloor n/2\rfloor}.$$
Weil \(\lfloor n/2\rfloor\) nur beim Übergang von ungerade zu gerade wächst, gilt
$$p_n=\begin{cases} p_{n-1}, & n\text{ ungerade},\\ 2p_{n-1}, & n\text{ gerade}. \end{cases}$$
Modular bedeutet das: Nur in geraden Schritten ist eine Multiplikation mit \(2\) nötig; in ungeraden Schritten bleibt der Rest unverändert.
Die Rekurrenz für \(a_n\) verwendet ausschließlich die letzten sieben Werte. Damit ist die ältere Historie irrelevant, sobald diese sieben Reste bekannt sind.
Speichert man
$$\left(\overline{a}_{n-1},\overline{a}_{n-2},\dots,\overline{a}_{n-7}\right),$$
dann ergibt sich der nächste Rest durch dieselbe lineare Kombination, nur modulo \(M\):
$$\overline{a}_n\equiv \overline{a}_{n-1}+2\overline{a}_{n-2}-2\overline{a}_{n-3}-\overline{a}_{n-4}+\overline{a}_{n-5}+\overline{a}_{n-6}-\overline{a}_{n-7}\pmod{M}.$$
Genau deshalb genügt ein Ringpuffer der Länge \(7\). Die Suche ist linear in der gefundenen Antwort, aber konstant im Speicher.
Wegen der negativen Koeffizienten können Zwischensummen vor der Reduktion negativ werden. Mathematisch korrekt ist stets der eindeutige Rest in \([0,M)\).
Formelhaft kann man schreiben
$$\operatorname{norm}(x)=((x\bmod M)+M)\bmod M.$$
Damit bleiben sowohl die gespeicherten Rekurrenzwerte als auch die getesteten Differenzen im kanonischen Restklassenbereich.
Die ersten Rekurrenzschritte lassen sich noch exakt ausrechnen. Aus den Startwerten folgt
$$\begin{aligned} a_7&=4+2\cdot 3-2\cdot 2-2+1+1-1=5,\\ a_8&=5+2\cdot 4-2\cdot 3-2+2+1-1=7,\\ a_9&=7+2\cdot 5-2\cdot 4-3+2+2-1=9,\\ a_{10}&=9+2\cdot 7-2\cdot 5-4+3+2-2=12. \end{aligned}$$
Für den Potenzterm gilt
$$p_7=2^3=8,\qquad p_8=2^4=16,\qquad p_9=2^4=16,\qquad p_{10}=2^5=32.$$
Also
$$t(7)=8-5=3,\qquad t(8)=16-7=9,\qquad t(9)=16-9=7,\qquad t(10)=32-12=20.$$
Zwei größere Kontrollwerte, die mit der exakten Rekurrenz übereinstimmen, sind
$$t(20)=824,\qquad t(42)=1{,}999{,}923.$$
Diese Werte bestätigen, dass Rekurrenz und Potenzverfolgung korrekt zusammenspielen, bevor die eigentliche Modulsuche hinter \(42\) weiterläuft.
Die C++-, Python- und Java-Implementierungen verwenden dieselbe Grundstruktur. Sie initialisieren die sieben Startwerte der Rekurrenz und einen laufenden Rest für \(2^{\lfloor n/2\rfloor}\). Die Hauptschleife erhöht \(n\) schrittweise. Bei geradem \(n\) wird der Potenzrest modulo \(10^6\) verdoppelt. Sobald \(n\ge 7\) ist, wird der nächste Rekurrenzwert aus den letzten sieben gespeicherten Resten berechnet und in den wiederverwendeten Slot eines Ringpuffers zurückgeschrieben.
Danach vergleicht die Implementierung den Potenzrest und den Rekurrenzrest modulo \(10^6\). Ist ihre Differenz kongruent zu \(0\), dann ist \(t(n)\) durch \(10^6\) teilbar. Zurückgegeben wird das erste solche \(n\) mit \(n>42\). Weil nur sieben Rekurrenzwerte und ein Potenzrest gespeichert werden, bleibt der Code kompakt und speichersparend.
Sei \(N_*\) der erste Index größer als \(42\) mit \(t(N_*)\equiv 0\pmod{10^6}\). Jede Schleifeniteration benötigt nur konstant viel Arbeit: eine Paritätsprüfung, höchstens eine Multiplikation mit \(2\), eine Rekurrenzaktualisierung aus sieben zwischengespeicherten Resten und einen modularen Vergleich. Damit beträgt die Laufzeit \(O(N_*)\), während der Speicherverbrauch \(O(1)\) ist.
Uygulama, \(t(n)\) değerinin \(10^6\)'ya bölündüğü ilk \(n>42\) değerini arar. Çok büyük tam sayılar üretmek yerine, yedinci dereceden lineer bir yineleme ile \(10^6\) modundaki kalıntıları izler.
Yineleme şu başlangıç değerleriyle başlar:
$$a_0=1,\quad a_1=1,\quad a_2=1,\quad a_3=2,\quad a_4=2,\quad a_5=3,\quad a_6=4,$$
ve test edilen büyüklük
$$t(n)=2^{\lfloor n/2\rfloor}-a_n$$
şeklindedir. Dolayısıyla aranan koşul
$$t(n)\equiv 0 \pmod{10^6}$$
olur.
Temel fikir şudur: problem yalnızca \(10^6\)'ya bölünebilirlikle ilgilidir. Bu yüzden hem yineleme hem de iki kuvveti terimi en baştan itibaren tamamen modüler aritmetikte yürütülebilir.
\(n\ge 7\) için
$$a_n=a_{n-1}+2a_{n-2}-2a_{n-3}-a_{n-4}+a_{n-5}+a_{n-6}-a_{n-7}$$
olur. Aranan ifade ise yineleme değeri ile pariteye bağlı bir iki kuvvetinin farkıdır:
$$t(n)=2^{\lfloor n/2\rfloor}-a_n.$$
Arama için gereken her şey bunun içindedir: \(a_n\) ve \(2^{\lfloor n/2\rfloor}\) bilindiğinde bölünebilirlik testi doğrudan yapılır.
Şunu yazalım:
$$M=10^6.$$
\(M\)'ye bölünebilirlik yalnızca mod \(M\) kalıntılarına bağlı olduğundan bütün tam değerler kalıntılarıyla değiştirilebilir:
$$a_n \equiv \overline{a}_n \pmod{M},\qquad 2^{\lfloor n/2\rfloor}\equiv \overline{p}_n \pmod{M}.$$
Böylece
$$t(n)\equiv \overline{p}_n-\overline{a}_n \pmod{M}$$
ve test koşulu
$$\overline{p}_n-\overline{a}_n\equiv 0\pmod{M}$$
haline gelir. Yani devasa kesin sayılara hiç ihtiyaç yoktur; uygulama yalnızca \([0,M)\) aralığındaki kalıntılarla ilerleyebilir.
Şimdi
$$p_n=2^{\lfloor n/2\rfloor}$$
tanımını kullanalım. \(\lfloor n/2\rfloor\) yalnızca \(n\) tekten çifte geçerken arttığı için
$$p_n=\begin{cases} p_{n-1}, & n\text{ tek},\\ 2p_{n-1}, & n\text{ çift}. \end{cases}$$
Dolayısıyla modüler kuvvet kalıntısı sadece çift adımlarda \(2\) ile çarpılır; tek adımlarda aynen korunur.
\(a_n\) yinelemesi yalnızca son yedi değere bağlıdır. Bu nedenle son yedi kalıntı bilindiğinde daha eski geçmişin hiçbir önemi kalmaz.
Şu bloğu tuttuğumuzu düşünelim:
$$\left(\overline{a}_{n-1},\overline{a}_{n-2},\dots,\overline{a}_{n-7}\right).$$
Bir sonraki kalıntı, aynı lineer birleşimin mod \(M\) altında yorumlanmasıyla bulunur:
$$\overline{a}_n\equiv \overline{a}_{n-1}+2\overline{a}_{n-2}-2\overline{a}_{n-3}-\overline{a}_{n-4}+\overline{a}_{n-5}+\overline{a}_{n-6}-\overline{a}_{n-7}\pmod{M}.$$
Bu yüzden uzunluğu \(7\) olan halkasal bir tampon yeterlidir. Arama cevabın büyüklüğüne göre lineerdir ama bellekte sabittir.
Katsayıların bir kısmı negatif olduğu için indirgeme öncesi toplamlar negatif olabilir. Matematiksel olarak doğru kalıntı, her zaman \([0,M)\) aralığındaki eşdeğer değerdir.
Bunu formül olarak
$$\operatorname{norm}(x)=((x\bmod M)+M)\bmod M$$
şeklinde yazabiliriz. Böylece hem saklanan yineleme değerleri hem de kontrol edilen farklar standart kalıntı aralığında tutulur.
İlk birkaç yineleme adımı tam olarak hesaplanabilir. Başlangıç değerlerinden
$$\begin{aligned} a_7&=4+2\cdot 3-2\cdot 2-2+1+1-1=5,\\ a_8&=5+2\cdot 4-2\cdot 3-2+2+1-1=7,\\ a_9&=7+2\cdot 5-2\cdot 4-3+2+2-1=9,\\ a_{10}&=9+2\cdot 7-2\cdot 5-4+3+2-2=12 \end{aligned}$$
elde edilir. Kuvvet terimi ise
$$p_7=2^3=8,\qquad p_8=2^4=16,\qquad p_9=2^4=16,\qquad p_{10}=2^5=32$$
olur. Bu yüzden
$$t(7)=8-5=3,\qquad t(8)=16-7=9,\qquad t(9)=16-9=7,\qquad t(10)=32-12=20.$$
Daha büyük iki kontrol değeri de
$$t(20)=824,\qquad t(42)=1{,}999{,}923$$
şeklindedir. Bunlar, son modüler taramaya geçmeden önce yineleme ile kuvvet güncellemesinin doğru eşlendiğini gösterir.
C++, Python ve Java uygulamaları aynı iskeleti izler. Önce yinelemenin yedi başlangıç değeri ve \(2^{\lfloor n/2\rfloor}\) için çalışan bir kalıntı başlatılır. Ana döngü \(n\)'i birer birer artırır. \(n\) çift olduğunda kuvvet kalıntısı \(10^6\) modunda ikiyle çarpılır. \(n\ge 7\) olduğunda ise sıradaki yineleme değeri, saklanan son yedi kalıntıdan üretilir ve halkasal tampondaki en eski yerin üzerine yazılır.
Bundan sonra uygulama kuvvet kalıntısı ile yineleme kalıntısını \(10^6\) modunda karşılaştırır. Aralarındaki fark \(0\) ile denkse, \(t(n)\) değeri \(10^6\)'ya bölünür. Döngü, \(n>42\) koşulunu sağlayan ilk böyle değeri döndürür. Yalnızca yedi yineleme girdisi ve bir kuvvet kalıntısı saklandığı için kod hem kısa hem de bellek açısından verimlidir.
\(N_*\), \(42\)'den büyük olup \(t(N_*)\equiv 0\pmod{10^6}\) koşulunu sağlayan ilk indis olsun. Her döngü adımında sabit miktarda işlem yapılır: bir parite kontrolü, en fazla bir tane \(2\) ile çarpma, yedi önbellekli kalıntıdan bir yineleme güncellemesi ve bir modüler karşılaştırma. Bu nedenle çalışma süresi \(O(N_*)\), bellek kullanımı ise \(O(1)\)'dir.
La implementación busca el menor \(n>42\) para el cual una cantidad derivada \(t(n)\) es divisible por \(10^6\). En lugar de construir enteros exactos gigantes, trabaja con una recurrencia lineal de orden \(7\) y conserva solo residuos módulo \(10^6\).
La recurrencia parte de
$$a_0=1,\quad a_1=1,\quad a_2=1,\quad a_3=2,\quad a_4=2,\quad a_5=3,\quad a_6=4,$$
y la magnitud comprobada es
$$t(n)=2^{\lfloor n/2\rfloor}-a_n.$$
Por tanto, el objetivo es hallar el primer \(n>42\) con
$$t(n)\equiv 0 \pmod{10^6}.$$
La idea central es que el problema solo pregunta por divisibilidad entre \(10^6\). Por eso tanto la recurrencia como el término de potencia pueden evolucionarse íntegramente en aritmética modular desde el principio.
Para \(n\ge 7\), la sucesión cumple
$$a_n=a_{n-1}+2a_{n-2}-2a_{n-3}-a_{n-4}+a_{n-5}+a_{n-6}-a_{n-7}.$$
La expresión que interesa es la diferencia entre una potencia de \(2\) gobernada por la paridad y el valor de la recurrencia:
$$t(n)=2^{\lfloor n/2\rfloor}-a_n.$$
No hace falta nada más para la búsqueda: una vez conocidos \(a_n\) y \(2^{\lfloor n/2\rfloor}\), la prueba de divisibilidad es inmediata.
Sea
$$M=10^6.$$
Como la divisibilidad por \(M\) depende solo del residuo módulo \(M\), podemos sustituir cada valor exacto por su clase residual:
$$a_n \equiv \overline{a}_n \pmod{M},\qquad 2^{\lfloor n/2\rfloor}\equiv \overline{p}_n \pmod{M}.$$
Entonces
$$t(n)\equiv \overline{p}_n-\overline{a}_n \pmod{M},$$
y la condición buscada se convierte en
$$\overline{p}_n-\overline{a}_n\equiv 0\pmod{M}.$$
Eso elimina la necesidad de enteros enormes: la implementación puede trabajar siempre con valores dentro de \([0,M)\).
Definamos
$$p_n=2^{\lfloor n/2\rfloor}.$$
Dado que \(\lfloor n/2\rfloor\) solo aumenta cuando \(n\) pasa de impar a par, la evolución de \(p_n\) es
$$p_n=\begin{cases} p_{n-1}, & n\text{ impar},\\ 2p_{n-1}, & n\text{ par}. \end{cases}$$
En consecuencia, el residuo modular de la potencia necesita una sola multiplicación por \(2\) en los pasos pares y ningún cambio en los pasos impares.
La fórmula de \(a_n\) solo usa los siete términos anteriores. Por ello, todo el historial más antiguo deja de importar una vez que se conservan esos siete residuos.
Si almacenamos
$$\left(\overline{a}_{n-1},\overline{a}_{n-2},\dots,\overline{a}_{n-7}\right),$$
el siguiente residuo se obtiene con la misma combinación lineal, interpretada módulo \(M\):
$$\overline{a}_n\equiv \overline{a}_{n-1}+2\overline{a}_{n-2}-2\overline{a}_{n-3}-\overline{a}_{n-4}+\overline{a}_{n-5}+\overline{a}_{n-6}-\overline{a}_{n-7}\pmod{M}.$$
Por eso basta un búfer circular de longitud \(7\). La búsqueda es lineal en la respuesta, pero constante en memoria.
La recurrencia contiene coeficientes negativos, así que algunas sumas parciales pueden ser negativas antes de reducirlas. Matemáticamente, el residuo correcto es siempre el representante único en \([0,M)\).
Eso puede escribirse como
$$\operatorname{norm}(x)=((x\bmod M)+M)\bmod M.$$
Así, tanto los valores almacenados de la recurrencia como la diferencia comprobada permanecen en el rango canónico de residuos.
Las primeras iteraciones todavía pueden calcularse de forma exacta. A partir de los valores iniciales se obtiene
$$\begin{aligned} a_7&=4+2\cdot 3-2\cdot 2-2+1+1-1=5,\\ a_8&=5+2\cdot 4-2\cdot 3-2+2+1-1=7,\\ a_9&=7+2\cdot 5-2\cdot 4-3+2+2-1=9,\\ a_{10}&=9+2\cdot 7-2\cdot 5-4+3+2-2=12. \end{aligned}$$
El término de potencia vale
$$p_7=2^3=8,\qquad p_8=2^4=16,\qquad p_9=2^4=16,\qquad p_{10}=2^5=32.$$
Por tanto
$$t(7)=8-5=3,\qquad t(8)=16-7=9,\qquad t(9)=16-9=7,\qquad t(10)=32-12=20.$$
Dos puntos de control más grandes, coherentes con la recurrencia exacta, son
$$t(20)=824,\qquad t(42)=1{,}999{,}923.$$
Esos valores verifican que la recurrencia y la regla de actualización de la potencia están sincronizadas correctamente antes de continuar la exploración modular más allá de \(42\).
Las implementaciones en C++, Python y Java siguen la misma estructura. Inicializan los siete valores base de la recurrencia y un residuo acumulado para \(2^{\lfloor n/2\rfloor}\). El bucle principal avanza \(n\) de uno en uno. Cuando \(n\) es par, el residuo de la potencia se duplica módulo \(10^6\). Una vez que \(n\ge 7\), el siguiente valor de la recurrencia se calcula a partir de los siete residuos almacenados y se escribe en la posición reciclada del búfer circular.
Después de esa actualización, la implementación compara módulo \(10^6\) el residuo de la potencia y el residuo de la recurrencia. Si su diferencia es congruente con \(0\), entonces \(t(n)\) es divisible por \(10^6\). El proceso devuelve el primer \(n\) que cumple eso con \(n>42\). Como solo se guardan siete entradas de la recurrencia y un residuo de potencia, el código mantiene memoria constante.
Sea \(N_*\) el primer índice mayor que \(42\) que satisface \(t(N_*)\equiv 0\pmod{10^6}\). Cada iteración del bucle realiza una cantidad constante de trabajo: una comprobación de paridad, como mucho una multiplicación por \(2\), una actualización de la recurrencia usando siete residuos en caché y una comparación modular. Por ello el tiempo total es \(O(N_*)\) y la memoria utilizada es \(O(1)\).
这里要求的是找到最小的 \(n>42\)，使得某个导出量 \(t(n)\) 能被 \(10^6\) 整除。实现并不去维护巨大的精确整数，而是把问题转化为一个七阶线性递推，再把所有计算都限制在模 \(10^6\) 的剩余类里进行。
递推的初值为
$$a_0=1,\quad a_1=1,\quad a_2=1,\quad a_3=2,\quad a_4=2,\quad a_5=3,\quad a_6=4,$$
被检测的量定义为
$$t(n)=2^{\lfloor n/2\rfloor}-a_n.$$
因此真正要做的是找出第一个满足
$$t(n)\equiv 0 \pmod{10^6}$$
的 \(n>42\)。
整个方法的出发点很直接：题目最终只关心是否被 \(10^6\) 整除，所以无论是递推序列还是幂项，都没有必要先算出精确值再取模，完全可以从第一步开始就在模运算体系内推进。
当 \(n\ge 7\) 时，序列满足
$$a_n=a_{n-1}+2a_{n-2}-2a_{n-3}-a_{n-4}+a_{n-5}+a_{n-6}-a_{n-7}.$$
而要测试的对象是
$$t(n)=2^{\lfloor n/2\rfloor}-a_n.$$
也就是说，只要同时知道递推值 \(a_n\) 和幂项 \(2^{\lfloor n/2\rfloor}\)，就可以立刻判断这一项是否对 \(10^6\) 同余于零。
记
$$M=10^6.$$
因为一个整数是否被 \(M\) 整除，只取决于它模 \(M\) 的余数，所以我们可以把所有精确值都替换成它们的模 \(M\) 表示：
$$a_n \equiv \overline{a}_n \pmod{M},\qquad 2^{\lfloor n/2\rfloor}\equiv \overline{p}_n \pmod{M}.$$
于是有
$$t(n)\equiv \overline{p}_n-\overline{a}_n \pmod{M},$$
所以搜索条件等价于
$$\overline{p}_n-\overline{a}_n\equiv 0\pmod{M}.$$
这一点非常关键，因为它说明根本不需要保存精确整数的完整大小。实现中只要维护 \([0,M)\) 范围内的余数，就已经保留了与整除性有关的全部信息。
令
$$p_n=2^{\lfloor n/2\rfloor}.$$
注意 \(\lfloor n/2\rfloor\) 只有在 \(n\) 从奇数变为偶数时才会增加 \(1\)。因此 \(p_n\) 的演化规律非常简单：
$$p_n=\begin{cases} p_{n-1}, & n\text{ 为奇数},\\ 2p_{n-1}, & n\text{ 为偶数}. \end{cases}$$
这意味着程序根本不需要每一步重新计算幂。它只需维护当前的模 \(M\) 余数，在偶数步乘一次 \(2\)，在奇数步保持不变即可。这正是代码能够用常数代价推进幂项的原因。
上面的递推式只依赖于前七项，所以更早的历史一旦超出这个窗口，就再也不会被访问。换句话说，只要当前保存了
$$\left(\overline{a}_{n-1},\overline{a}_{n-2},\dots,\overline{a}_{n-7}\right),$$
下一项的余数就能由同一线性组合直接得到：
$$\overline{a}_n\equiv \overline{a}_{n-1}+2\overline{a}_{n-2}-2\overline{a}_{n-3}-\overline{a}_{n-4}+\overline{a}_{n-5}+\overline{a}_{n-6}-\overline{a}_{n-7}\pmod{M}.$$
因此完全没必要开一个随着 \(n\) 增长而扩大的数组。一个长度为 \(7\) 的循环缓冲区就足够了：每产生一个新值，就覆盖掉最旧的那个槽位。这就是空间复杂度能保持为常数的根本原因。
递推中含有 \(-2\) 和 \(-1\) 这样的负系数，所以线性组合在取模之前可能暂时落到负数区间。例如，即使最终余数应该是某个正数，中间和式也可能先变成负值再回到正确的同余类。
数学上，我们总是希望把结果标准化为 \([0,M)\) 中唯一的代表元。可写为
$$\operatorname{norm}(x)=((x\bmod M)+M)\bmod M.$$
这样不管中间表达式原本是正是负，最后保存下来的都是标准余数。对于不同语言来说，这一步同样重要，因为各语言对负数取模的具体行为不完全相同，而标准化之后逻辑就统一了。
前几项可以完全手算出来，因此非常适合作为递推与幂项更新规则的校验。
先由初值计算递推：
$$\begin{aligned} a_7&=4+2\cdot 3-2\cdot 2-2+1+1-1=5,\\ a_8&=5+2\cdot 4-2\cdot 3-2+2+1-1=7,\\ a_9&=7+2\cdot 5-2\cdot 4-3+2+2-1=9,\\ a_{10}&=9+2\cdot 7-2\cdot 5-4+3+2-2=12. \end{aligned}$$
再看幂项：
$$p_7=2^3=8,\qquad p_8=2^4=16,\qquad p_9=2^4=16,\qquad p_{10}=2^5=32.$$
于是得到
$$t(7)=8-5=3,\qquad t(8)=16-7=9,\qquad t(9)=16-9=7,\qquad t(10)=32-12=20.$$
这组小例子清楚展示了两件事。第一，递推值确实只依赖最近七项。第二，幂项在奇数步保持不变、在偶数步翻倍的规律与 \(\lfloor n/2\rfloor\) 完全一致。
再往后看，两个更大的校验点是
$$t(20)=824,\qquad t(42)=1{,}999{,}923.$$
这些值说明在进入最终搜索区间之前，递推本身与幂项的维护已经对齐无误。
C++、Python 和 Java 的实现结构是一致的。它们先装入七个初始递推值，再维护一个当前的 \(2^{\lfloor n/2\rfloor}\) 模 \(10^6\) 余数。主循环每次把 \(n\) 增加 \(1\)。如果当前 \(n\) 是偶数，就把幂项余数乘 \(2\) 并对 \(10^6\) 取模。如果 \(n\ge 7\)，就根据最近七个递推余数计算出新的递推值，并把它写回循环缓冲区中最旧的位置。
完成更新后，实现会比较幂项余数与递推余数在模 \(10^6\) 下的差。如果这个差同余于 \(0\)，就说明 \(t(n)\) 被 \(10^6\) 整除。循环返回第一个满足这个条件且 \(n>42\) 的位置。由于始终只保留七个递推槽位和一个幂项余数，所以整个程序的空间占用保持常数级。
设 \(N_*\) 是第一个大于 \(42\) 且满足 \(t(N_*)\equiv 0\pmod{10^6}\) 的下标。每一步循环都只做常数数量的工作：一次奇偶判断、至多一次乘 \(2\)、一次基于七个缓存值的递推更新，以及一次模比较。因此总时间复杂度是 \(O(N_*)\)，空间复杂度是 \(O(1)\)。
Реализация ищет наименьшее \(n>42\), для которого некоторая производная величина \(t(n)\) делится на \(10^6\). Вместо работы с огромными точными числами она использует линейную рекуррентную последовательность седьмого порядка и хранит только остатки по модулю \(10^6\).
Начальные значения таковы:
$$a_0=1,\quad a_1=1,\quad a_2=1,\quad a_3=2,\quad a_4=2,\quad a_5=3,\quad a_6=4,$$
а проверяемая величина определяется формулой
$$t(n)=2^{\lfloor n/2\rfloor}-a_n.$$
Следовательно, нужно найти первое \(n>42\), удовлетворяющее
$$t(n)\equiv 0 \pmod{10^6}.$$
Основное наблюдение состоит в том, что задача спрашивает только о делимости на \(10^6\). Значит, и рекурсию, и степень двойки можно с самого начала разворачивать исключительно в модульной арифметике.
Для \(n\ge 7\) выполняется соотношение
$$a_n=a_{n-1}+2a_{n-2}-2a_{n-3}-a_{n-4}+a_{n-5}+a_{n-6}-a_{n-7}.$$
Интересующая нас величина есть разность между степенью двойки, зависящей от четности, и очередным членом рекурсии:
$$t(n)=2^{\lfloor n/2\rfloor}-a_n.$$
На этом математическая постановка поиска фактически заканчивается: когда известны \(a_n\) и \(2^{\lfloor n/2\rfloor}\), проверка делимости выполняется сразу.
Обозначим
$$M=10^6.$$
Так как делимость на \(M\) зависит только от остатка по модулю \(M\), можно заменить все точные значения их остатками:
$$a_n \equiv \overline{a}_n \pmod{M},\qquad 2^{\lfloor n/2\rfloor}\equiv \overline{p}_n \pmod{M}.$$
Тогда
$$t(n)\equiv \overline{p}_n-\overline{a}_n \pmod{M},$$
а условие поиска принимает вид
$$\overline{p}_n-\overline{a}_n\equiv 0\pmod{M}.$$
Отсюда следует, что точные большие числа нам не нужны вовсе. Вся информация, важная для задачи, сохраняется в остатках из диапазона \([0,M)\).
Положим
$$p_n=2^{\lfloor n/2\rfloor}.$$
Поскольку \(\lfloor n/2\rfloor\) увеличивается лишь тогда, когда \(n\) меняется с нечетного на четное, имеем простое правило:
$$p_n=\begin{cases} p_{n-1}, & n\text{ нечетно},\\ 2p_{n-1}, & n\text{ четно}. \end{cases}$$
Поэтому в программе остаток степени обновляется особенно дешево: на четных шагах он удваивается, на нечетных просто переносится дальше без изменений.
Формула для \(a_n\) использует только предыдущие семь членов. Значит, более ранняя история уже не влияет на вычисления, если известны последние семь остатков.
Если хранить блок
$$\left(\overline{a}_{n-1},\overline{a}_{n-2},\dots,\overline{a}_{n-7}\right),$$
то следующий остаток определяется той же линейной комбинацией, но по модулю \(M\):
$$\overline{a}_n\equiv \overline{a}_{n-1}+2\overline{a}_{n-2}-2\overline{a}_{n-3}-\overline{a}_{n-4}+\overline{a}_{n-5}+\overline{a}_{n-6}-\overline{a}_{n-7}\pmod{M}.$$
Именно поэтому достаточно кольцевого буфера длины \(7\). Время растет линейно по ответу, а память остается постоянной.
Из-за отрицательных коэффициентов промежуточная сумма до взятия по модулю может оказаться отрицательной. Математически правильным остатком всегда является единственное число из \([0,M)\), сравнимое с этой суммой по модулю \(M\).
Это можно записать как
$$\operatorname{norm}(x)=((x\bmod M)+M)\bmod M.$$
Такое приведение гарантирует, что и значения рекурсии, и тестируемая разность всегда хранятся в каноническом диапазоне остатков.
Первые несколько шагов удобно посчитать точно вручную. Из начальных значений получаем
$$\begin{aligned} a_7&=4+2\cdot 3-2\cdot 2-2+1+1-1=5,\\ a_8&=5+2\cdot 4-2\cdot 3-2+2+1-1=7,\\ a_9&=7+2\cdot 5-2\cdot 4-3+2+2-1=9,\\ a_{10}&=9+2\cdot 7-2\cdot 5-4+3+2-2=12. \end{aligned}$$
Для степени двойки имеем
$$p_7=2^3=8,\qquad p_8=2^4=16,\qquad p_9=2^4=16,\qquad p_{10}=2^5=32.$$
Следовательно,
$$t(7)=8-5=3,\qquad t(8)=16-7=9,\qquad t(9)=16-9=7,\qquad t(10)=32-12=20.$$
Два более крупных контрольных значения, согласующихся с точной рекурсией, таковы:
$$t(20)=824,\qquad t(42)=1{,}999{,}923.$$
Они подтверждают, что правило обновления степени и сама рекурсия согласованы корректно еще до того, как поиск продолжается за пределами \(42\).
Реализации на C++, Python и Java устроены одинаково. Сначала они инициализируют семь стартовых значений рекурсии и текущий остаток для \(2^{\lfloor n/2\rfloor}\). Основной цикл увеличивает \(n\) по одному. На четных шагах остаток степени удваивается по модулю \(10^6\). Как только \(n\ge 7\), следующий член рекурсии вычисляется по семи сохраненным остаткам и записывается в переиспользуемую ячейку кольцевого буфера.
После этого реализация сравнивает остаток степени и остаток рекурсии по модулю \(10^6\). Если их разность сравнима с нулем, то \(t(n)\) делится на \(10^6\). Цикл возвращает первое такое \(n\), удовлетворяющее \(n>42\). Поскольку хранятся только семь членов рекурсии и один остаток степени, память остается постоянной.
Пусть \(N_*\) обозначает первый индекс больше \(42\), для которого \(t(N_*)\equiv 0\pmod{10^6}\). Каждая итерация цикла выполняет лишь константное число операций: проверку четности, не более одного умножения на \(2\), одно обновление рекурсии из семи кэшированных остатков и одно модульное сравнение. Поэтому время работы равно \(O(N_*)\), а память равна \(O(1)\).
تبحث الخوارزمية عن أصغر \(n>42\) بحيث تكون الكمية المشتقة \(t(n)\) قابلة للقسمة على \(10^6\). وبدلاً من التعامل مع أعداد صحيحة ضخمة بدقة كاملة، تعتمد على علاقة عودية خطية من الرتبة السابعة وتحتفظ فقط بالبواقي modulo \(10^6\).
تبدأ المتتالية بالقيم
$$a_0=1,\quad a_1=1,\quad a_2=1,\quad a_3=2,\quad a_4=2,\quad a_5=3,\quad a_6=4,$$
أما الكمية التي يتم فحصها فهي
$$t(n)=2^{\lfloor n/2\rfloor}-a_n.$$
إذن المطلوب هو إيجاد أول \(n>42\) يحقق
$$t(n)\equiv 0 \pmod{10^6}.$$
الفكرة الأساسية بسيطة: بما أن السؤال النهائي يتعلق فقط بالقابلية للقسمة على \(10^6\)، فلا حاجة لحساب القيم الدقيقة كاملة. يمكن تطوير كل من المتتالية والحد الأسي مباشرة داخل الحساب المعياري.
لـ \(n\ge 7\) تتحقق العلاقة
$$a_n=a_{n-1}+2a_{n-2}-2a_{n-3}-a_{n-4}+a_{n-5}+a_{n-6}-a_{n-7}.$$
والكمية المراد اختبارها هي الفرق بين قوة للعدد \(2\) تتحكم فيها parity وبين قيمة المتتالية:
$$t(n)=2^{\lfloor n/2\rfloor}-a_n.$$
وبذلك يصبح البحث محدداً بالكامل: إذا عُرفت \(a_n\) وعُرفت \(2^{\lfloor n/2\rfloor}\)، فإن اختبار القابلية للقسمة يصبح مباشراً.
لنكتب
$$M=10^6.$$
بما أن القابلية للقسمة على \(M\) تعتمد فقط على الباقي modulo \(M\)، يمكن استبدال كل قيمة دقيقة بممثلها المعياري:
$$a_n \equiv \overline{a}_n \pmod{M},\qquad 2^{\lfloor n/2\rfloor}\equiv \overline{p}_n \pmod{M}.$$
وعندئذٍ
$$t(n)\equiv \overline{p}_n-\overline{a}_n \pmod{M},$$
فتصبح شرطية البحث
$$\overline{p}_n-\overline{a}_n\equiv 0\pmod{M}.$$
هذا يعني أن الأعداد الدقيقة الضخمة ليست ضرورية إطلاقاً؛ فكل ما يلزم هو تخزين بواقي ضمن المجال \([0,M)\).
عرّف
$$p_n=2^{\lfloor n/2\rfloor}.$$
بما أن \(\lfloor n/2\rfloor\) يزيد فقط عندما ينتقل \(n\) من فردي إلى زوجي، فإن
$$p_n=\begin{cases} p_{n-1}, & n\text{ odd},\\ 2p_{n-1}, & n\text{ even}. \end{cases}$$
إذن لا حاجة لإعادة حساب القوة من الصفر في كل خطوة. يكفي أن نحافظ على باقيها الحالي، فنضربه في \(2\) عند الخطوات الزوجية ونتركه كما هو عند الخطوات الفردية.
العلاقة العودية الخاصة بـ \(a_n\) تعتمد فقط على القيم السبع السابقة. لذلك لا توجد فائدة من الاحتفاظ بتاريخ أطول من ذلك.
إذا احتفظنا بالكتلة
$$\left(\overline{a}_{n-1},\overline{a}_{n-2},\dots,\overline{a}_{n-7}\right),$$
فإن الحد التالي يُحسب من نفس التركيبة الخطية ولكن modulo \(M\):
$$\overline{a}_n\equiv \overline{a}_{n-1}+2\overline{a}_{n-2}-2\overline{a}_{n-3}-\overline{a}_{n-4}+\overline{a}_{n-5}+\overline{a}_{n-6}-\overline{a}_{n-7}\pmod{M}.$$
ولهذا يكفي مخزن دائري بطول \(7\). فالزمن ينمو خطياً مع موضع الجواب، أما الذاكرة فتبقى ثابتة.
لأن بعض معاملات العلاقة العودية سالبة، قد تصبح المجاميع الوسيطة سالبة قبل أخذ modulo. رياضياً، الباقي الصحيح هو دائماً الممثل الوحيد داخل \([0,M)\) الموافق لتلك القيمة.
ويمكن كتابة ذلك على الصورة
$$\operatorname{norm}(x)=((x\bmod M)+M)\bmod M.$$
بهذا التطبيع تبقى كل القيم المخزنة، وكذلك الفرق الذي يتم اختباره، ضمن المجال القياسي للبواقي.
الخطوات الأولى يمكن حسابها يدوياً بدقة، وهي مناسبة جداً لفهم تزامن العودية مع حد القوة.
من القيم الابتدائية نحصل على
$$\begin{aligned} a_7&=4+2\cdot 3-2\cdot 2-2+1+1-1=5,\\ a_8&=5+2\cdot 4-2\cdot 3-2+2+1-1=7,\\ a_9&=7+2\cdot 5-2\cdot 4-3+2+2-1=9,\\ a_{10}&=9+2\cdot 7-2\cdot 5-4+3+2-2=12. \end{aligned}$$
أما حد القوة فيكون
$$p_7=2^3=8,\qquad p_8=2^4=16,\qquad p_9=2^4=16,\qquad p_{10}=2^5=32.$$
ومن ثم
$$t(7)=8-5=3,\qquad t(8)=16-7=9,\qquad t(9)=16-9=7,\qquad t(10)=32-12=20.$$
ويوجد أيضاً نقطتا تحقق أكبر حجماً هما
$$t(20)=824,\qquad t(42)=1{,}999{,}923.$$
وهاتان القيمتان تؤكدان أن قاعدة تحديث القوة والعلاقة العودية تسيران معاً بالشكل الصحيح قبل أن يستمر الفحص المعياري إلى ما بعد \(42\).
تتبع تطبيقات C++ وPython وJava البنية نفسها. فهي تبدأ بتهيئة القيم السبع الابتدائية للمتتالية، وباقٍ جارٍ للكمية \(2^{\lfloor n/2\rfloor}\). ثم تزيد الحلقة الرئيسية قيمة \(n\) خطوة خطوة. عندما تكون \(n\) زوجية، يُضاعف باقي القوة modulo \(10^6\). وعندما يصبح \(n\ge 7\)، يُحسب الحد العودي التالي من البواقي السبع المخزنة ويُكتب فوق أقدم موضع داخل مخزن دائري.
بعد ذلك تقارن الخوارزمية بين باقي القوة وباقي المتتالية modulo \(10^6\). إذا كان الفرق بينهما مكافئاً للصفر، فهذا يعني أن \(t(n)\) تقبل القسمة على \(10^6\). وتُرجع الحلقة أول قيمة تحقق ذلك مع الشرط \(n>42\). وبما أن التخزين يقتصر على سبعة حدود عودية وباقٍ واحد للقوة، فإن استهلاك الذاكرة يبقى ثابتاً.
ليكن \(N_*\) أول فهرس أكبر من \(42\) يحقق \(t(N_*)\equiv 0\pmod{10^6}\). كل دورة من الحلقة تنفذ عدداً ثابتاً من العمليات: اختبار زوجية، وعلى الأكثر عملية ضرب واحدة في \(2\)، وتحديثاً واحداً للعلاقة العودية باستخدام سبعة بواقي مخزنة، ثم مقارنة معيارية واحدة. لذلك يكون الزمن الكلي \(O(N_*)\)، بينما تكون الذاكرة \(O(1)\).