For a modulus \(n\), the Fibonacci sequence reduced modulo \(n\) eventually becomes periodic, and \(\pi(n)\) denotes the length of its first full cycle. Problem 853 asks for
$$\sum_{\substack{2 \le n \lt 10^9 \\ \pi(n)=120}} n.$$
Testing every integer below \(10^9\) would be hopeless. The successful idea is to turn the period condition into a precise return-to-state test and then use divisibility of Fibonacci numbers to shrink the search space to a small divisor set.
Write
$$S_k(n)=\bigl(F_k \bmod n,\; F_{k+1} \bmod n\bigr).$$
Because the Fibonacci recurrence is determined completely by two consecutive values, the Pisano period is the smallest positive integer \(T\) with \(S_T(n)=S_0(n)=(0,1)\).
The pair \((F_k,F_{k+1})\) determines the entire future sequence, so the sequence modulo \(n\) restarts exactly when the pair \((0,1)\) reappears. Therefore \(T\) is a period modulo \(n\) if and only if
$$F_T \equiv 0 \pmod n,\qquad F_{T+1} \equiv 1 \pmod n.$$
To make \(T\) the exact Pisano period, not merely a multiple of it, no proper divisor \(d \mid T\) may satisfy the same pair of congruences.
If \(\pi(n)=120\), then the first congruence immediately gives
$$n \mid F_{120}.$$
The implementations use the explicit factorization
$$F_{120}=2^5 \cdot 3^2 \cdot 5 \cdot 7 \cdot 11 \cdot 23 \cdot 31 \cdot 41 \cdot 61 \cdot 241 \cdot 2161 \cdot 2521 \cdot 20641.$$
This is only a necessary condition, because we still must enforce \(F_{121}\equiv 1 \pmod n\) and minimality. But it is already powerful: every valid modulus must be a divisor of this single number, so no other prime factor can ever appear.
From the factorization above, the number of divisors of \(F_{120}\) is
$$\tau(F_{120})=(5+1)(2+1)2^{11}=36864.$$
So before applying the bound \(n \lt 10^9\), there are only tens of thousands of structurally possible candidates instead of one billion integers. The implementations build these divisors multiplicatively, prime by prime, and retain only those below the problem limit.
Dividing \(F_{120}\) is not enough. A candidate modulus can satisfy \(F_{120}\equiv 0 \pmod n\) even when its true Pisano period is \(10\), \(20\), \(30\), \(40\), \(60\), or another proper divisor of \(120\). Exactness is recovered by requiring
$$S_{120}(n)=(0,1),$$
but also
$$S_d(n)\ne(0,1)\qquad(d \mid 120,\ d \lt 120).$$
That second condition is precisely the minimality test.
The C++, Python, and Java implementations evaluate Fibonacci pairs modulo \(n\) using fast doubling. If \(m\ge 0\), then
$$F_{2m}=F_m\bigl(2F_{m+1}-F_m\bigr),\qquad F_{2m+1}=F_m^2+F_{m+1}^2.$$
These identities allow the index to be halved at each recursive step, so the pair \((F_k,F_{k+1})\bmod n\) is obtained in \(O(\log k)\) time. Since every check here uses \(k=120\) or a divisor of \(120\), the period test is extremely cheap.
The divisor \(11\) shows why the minimality test matters. Because \(11\mid F_{120}\), it survives candidate generation, and indeed
$$S_{120}(11)=(0,1).$$
However, the same reset already occurs at \(d=10\), so the true Pisano period modulo \(11\) is \(10\), not \(120\). Therefore \(11\) must be rejected.
By contrast, \(2521\) also divides \(F_{120}\) and satisfies \(S_{120}(2521)=(0,1)\), but none of the proper divisors of \(120\) returns to \((0,1)\) modulo \(2521\). Hence \(\pi(2521)=120\), so \(2521\) contributes to the final sum.
The small checkpoint built into the overall method works the same way: if the target period is changed to \(18\) and the search range is restricted to \(2 \le n \lt 50\), the only valid moduli are \(19\) and \(38\), and their sum is \(57\).
The implementation first lists all proper divisors of \(120\), because those are exactly the indices needed for the exact-period rejection step. It then stores the prime factorization of \(F_{120}\) and generates all divisors below \(10^9\) by multiplying allowed prime powers cumulatively.
For each candidate modulus, the implementation computes the Fibonacci state at index \(120\). If the state is not \((0,1)\), the candidate is discarded immediately. If the state does return to \((0,1)\), the implementation repeats the same check for every proper divisor of \(120\). A candidate is accepted only when every smaller check fails.
This mirrors the mathematics exactly: divisor generation enforces the necessary condition \(n\mid F_{120}\), while the state tests upgrade that necessary condition to the exact statement \(\pi(n)=120\).
Let \(C\) be the number of generated divisors below \(10^9\). The implementations never scan the full interval \([2,10^9)\); they inspect only this divisor list. From the factorization of \(F_{120}\), the theoretical upper bound before the cutoff is \(36864\) candidates.
Each candidate requires one Fibonacci-pair evaluation at \(120\) and one more for each proper divisor of \(120\). There are \(15\) proper divisors, and each evaluation costs \(O(\log 120)\). Therefore the total running time is \(O(C\log 120)\), which is effectively linear in the candidate count, and the memory usage is \(O(C)\).
Für ein Modul \(n\) wird die Fibonacci-Folge modulo \(n\) periodisch, und \(\pi(n)\) bezeichnet die Länge ihres ersten vollständigen Zyklus. In Problem 853 ist zu berechnen
$$\sum_{\substack{2 \le n \lt 10^9 \\ \pi(n)=120}} n.$$
Eine Prüfung aller Zahlen unter \(10^9\) wäre aussichtslos. Der entscheidende Gedanke besteht darin, die Periodenbedingung als exakten Zustandsrücksprung zu formulieren und dann mit Teilbarkeitseigenschaften der Fibonacci-Zahlen die Kandidatenmenge auf wenige Teiler zu reduzieren.
Wir schreiben
$$S_k(n)=\bigl(F_k \bmod n,\; F_{k+1} \bmod n\bigr).$$
Da die Fibonacci-Rekurrenz vollständig durch zwei aufeinanderfolgende Werte bestimmt ist, ist die Pisano-Periode die kleinste positive Zahl \(T\) mit \(S_T(n)=S_0(n)=(0,1)\).
Das Paar \((F_k,F_{k+1})\) bestimmt die gesamte weitere Folge. Daher beginnt die Folge modulo \(n\) genau dann von vorn, wenn das Paar \((0,1)\) wieder erscheint. Somit ist \(T\) genau dann eine Periode modulo \(n\), wenn
$$F_T \equiv 0 \pmod n,\qquad F_{T+1} \equiv 1 \pmod n.$$
Damit \(T\) die exakte Pisano-Periode und nicht nur ein Vielfaches davon ist, darf kein echter Teiler \(d \mid T\) dieselben Kongruenzen erfüllen.
Falls \(\pi(n)=120\), liefert bereits die erste Kongruenz
$$n \mid F_{120}.$$
Die Implementierungen verwenden die explizite Zerlegung
$$F_{120}=2^5 \cdot 3^2 \cdot 5 \cdot 7 \cdot 11 \cdot 23 \cdot 31 \cdot 41 \cdot 61 \cdot 241 \cdot 2161 \cdot 2521 \cdot 20641.$$
Das ist nur eine notwendige Bedingung, denn \(F_{121}\equiv 1 \pmod n\) und die Minimalität müssen später noch geprüft werden. Trotzdem ist sie sehr stark: Jeder gültige Modulus ist ein Teiler dieser einen Zahl, und keine andere Primzahl kann auftreten.
Aus der Zerlegung oben folgt für die Anzahl der Teiler von \(F_{120}\)
$$\tau(F_{120})=(5+1)(2+1)2^{11}=36864.$$
Schon vor der Schranke \(n \lt 10^9\) bleiben also nur einige zehntausend strukturell mögliche Kandidaten übrig statt einer Milliarde Zahlen. Die Implementierungen erzeugen diese Teiler multiplikativ, Primfaktor für Primfaktor, und behalten nur die Werte unterhalb der Problemschranke.
Die Bedingung \(n \mid F_{120}\) genügt nicht. Ein Kandidat kann \(F_{120}\equiv 0 \pmod n\) erfüllen, obwohl seine wahre Pisano-Periode \(10\), \(20\), \(30\), \(40\), \(60\) oder ein anderer echter Teiler von \(120\) ist. Exaktheit erhält man durch
$$S_{120}(n)=(0,1),$$
zusammen mit
$$S_d(n)\ne(0,1)\qquad(d \mid 120,\ d \lt 120).$$
Genau diese zweite Bedingung ist der Minimalitätstest.
Die C++-, Python- und Java-Implementierungen berechnen Fibonacci-Paare modulo \(n\) mit Fast Doubling. Für \(m\ge 0\) gilt
$$F_{2m}=F_m\bigl(2F_{m+1}-F_m\bigr),\qquad F_{2m+1}=F_m^2+F_{m+1}^2.$$
Damit halbiert sich der Index in jedem rekursiven Schritt, sodass \((F_k,F_{k+1})\bmod n\) in \(O(\log k)\) Zeit berechnet wird. Da hier immer nur \(k=120\) oder ein Teiler von \(120\) geprüft wird, ist der Test sehr billig.
Der Teiler \(11\) zeigt gut, warum der Minimalitätstest nötig ist. Weil \(11\mid F_{120}\), überlebt er die Kandidatenerzeugung, und außerdem gilt
$$S_{120}(11)=(0,1).$$
Allerdings tritt derselbe Rücksprung bereits bei \(d=10\) auf. Die wahre Pisano-Periode modulo \(11\) ist also \(10\) und nicht \(120\). Daher muss \(11\) verworfen werden.
Dagegen teilt \(2521\) ebenfalls \(F_{120}\) und erfüllt \(S_{120}(2521)=(0,1)\), aber keiner der echten Teiler von \(120\) liefert modulo \(2521\) den Zustand \((0,1)\). Also ist \(\pi(2521)=120\), und \(2521\) geht in die Endsumme ein.
Eine kleine Kontrollrechnung im selben Stil lautet: Ersetzt man die Zielperiode durch \(18\) und beschränkt die Suche auf \(2 \le n \lt 50\), dann sind \(19\) und \(38\) die einzigen gültigen Moduli, und ihre Summe ist \(57\).
Die Implementierung listet zuerst alle echten Teiler von \(120\) auf, denn genau diese Indizes werden für den Ablehnungstest der exakten Periode benötigt. Danach wird die Primfaktorzerlegung von \(F_{120}\) festgehalten, und alle Teiler unter \(10^9\) werden durch sukzessives Multiplizieren der zulässigen Primzahlpotenzen erzeugt.
Für jeden Kandidaten berechnet die Implementierung den Fibonacci-Zustand bei Index \(120\). Ist der Zustand nicht \((0,1)\), wird der Kandidat sofort verworfen. Andernfalls wird derselbe Test für jeden echten Teiler von \(120\) wiederholt. Ein Kandidat wird nur dann akzeptiert, wenn alle kleineren Prüfungen scheitern.
Das spiegelt die Mathematik exakt wider: Die Teilererzeugung erzwingt die notwendige Bedingung \(n\mid F_{120}\), und die Zustandstests verschärfen sie zur exakten Aussage \(\pi(n)=120\).
Sei \(C\) die Anzahl der erzeugten Teiler unter \(10^9\). Die Implementierungen durchsuchen nie das volle Intervall \([2,10^9)\), sondern nur diese Teilerliste. Aus der Zerlegung von \(F_{120}\) ergibt sich vor dem Grenzwert eine theoretische Obergrenze von \(36864\) Kandidaten.
Jeder Kandidat benötigt eine Fibonacci-Paar-Berechnung bei \(120\) und eine weitere für jeden echten Teiler von \(120\). Es gibt \(15\) echte Teiler, und jede Berechnung kostet \(O(\log 120)\). Damit ist die Gesamtlaufzeit \(O(C\log 120)\), also praktisch linear in der Kandidatenzahl, und der Speicherbedarf beträgt \(O(C)\).
Bir \(n\) modülü için Fibonacci dizisi modulo \(n\) sonunda periyodik olur ve \(\pi(n)\) bu ilk tam döngünün uzunluğunu gösterir. Problem 853 şu toplamı ister:
$$\sum_{\substack{2 \le n \lt 10^9 \\ \pi(n)=120}} n.$$
\(10^9\)'dan küçük bütün sayıları tek tek sınamak pratik değildir. Esas fikir, periyot koşulunu kesin bir durum-dönüş testine çevirmek ve ardından Fibonacci sayılarının bölünebilirlik yapısını kullanarak aday uzayını küçük bir bölen kümesine indirmektir.
Şunu yazalım:
$$S_k(n)=\bigl(F_k \bmod n,\; F_{k+1} \bmod n\bigr).$$
Fibonacci bağıntısı iki ardışık terim tarafından tamamen belirlendiği için, Pisano periyodu \(S_T(n)=S_0(n)=(0,1)\) eşitliğini sağlayan en küçük pozitif \(T\) değeridir.
\((F_k,F_{k+1})\) çifti dizinin bütün geleceğini belirler. Bu yüzden modulo \(n\) altında dizi ancak \((0,1)\) çifti yeniden göründüğünde başa dönmüş olur. Dolayısıyla \(T\), modulo \(n\) için ancak ve ancak
$$F_T \equiv 0 \pmod n,\qquad F_{T+1} \equiv 1 \pmod n$$
ise bir periyottur. \(T\)'nin yalnızca bir kat değil de tam Pisano periyodu olabilmesi için, \(T\)'nin hiçbir uygun böleni \(d \mid T\) aynı koşulu sağlamamalıdır.
Eğer \(\pi(n)=120\) ise ilk kongruens hemen şunu verir:
$$n \mid F_{120}.$$
Uygulamalar şu açık çarpanlara ayrılışı kullanır:
$$F_{120}=2^5 \cdot 3^2 \cdot 5 \cdot 7 \cdot 11 \cdot 23 \cdot 31 \cdot 41 \cdot 61 \cdot 241 \cdot 2161 \cdot 2521 \cdot 20641.$$
Bu yalnızca gerekli bir koşuldur; çünkü daha sonra hem \(F_{121}\equiv 1 \pmod n\) şartını hem de minimaliteyi doğrulamak gerekir. Yine de çok güçlüdür: geçerli her modül bu tek sayının bir böleni olmalıdır ve bunun dışındaki hiçbir asal çarpan ortaya çıkamaz.
Yukarıdaki çarpanlara ayrılıştan \(F_{120}\)'nin bölen sayısı
$$\tau(F_{120})=(5+1)(2+1)2^{11}=36864$$
olur. Yani \(n \lt 10^9\) sınırını bile uygulamadan, yapısal olarak mümkün aday sayısı bir milyardan birkaç on bine düşer. Uygulamalar bu bölenleri asal çarpanları sırayla çoğaltarak üretir ve problem sınırının altındaki değerleri korur.
\(n \mid F_{120}\) olması tek başına yetmez. Bir aday modül \(F_{120}\equiv 0 \pmod n\) koşulunu sağlayabilir, ama gerçek Pisano periyodu \(10\), \(20\), \(30\), \(40\), \(60\) ya da \(120\)'nin başka bir uygun böleni olabilir. Kesinlik şu iki koşulla elde edilir:
$$S_{120}(n)=(0,1),$$
ve aynı zamanda
$$S_d(n)\ne(0,1)\qquad(d \mid 120,\ d \lt 120).$$
İkinci koşul tam olarak minimalite testidir.
C++, Python ve Java uygulamaları Fibonacci çiftlerini modulo \(n\) altında fast doubling yöntemiyle hesaplar. \(m\ge 0\) için
$$F_{2m}=F_m\bigl(2F_{m+1}-F_m\bigr),\qquad F_{2m+1}=F_m^2+F_{m+1}^2$$
özdeşlikleri geçerlidir. Böylece her özyinelemeli adımda indis yarıya iner ve \((F_k,F_{k+1})\bmod n\) çifti \(O(\log k)\) zamanda bulunur. Burada kontrol edilen tüm indisler \(120\) ya da \(120\)'nin bölenleri olduğu için maliyet çok küçüktür.
\(11\) sayısı, minimalite testinin neden gerekli olduğunu açıkça gösterir. Çünkü \(11\mid F_{120}\), dolayısıyla aday üretiminden geçer ve ayrıca
$$S_{120}(11)=(0,1)$$
eşitliği de sağlanır. Fakat aynı dönüş daha önce \(d=10\) için zaten gerçekleşir. Demek ki modulo \(11\) altında gerçek Pisano periyodu \(120\) değil \(10\)'dur. Bu nedenle \(11\) elenmelidir.
Buna karşılık \(2521\) de \(F_{120}\)'yi böler ve \(S_{120}(2521)=(0,1)\) koşulunu sağlar; ancak \(120\)'nin hiçbir uygun böleni modulo \(2521\) altında \((0,1)\) durumuna geri dönmez. Bu yüzden \(\pi(2521)=120\) olur ve \(2521\) son toplama girer.
Yöntemin küçük doğrulama örneği de aynı mantığı izler: hedef periyot \(18\) yapılır ve aralık \(2 \le n \lt 50\) ile sınırlandırılırsa, geçerli tek modüller \(19\) ve \(38\) olur; toplam da \(57\)'dir.
Uygulama önce \(120\)'nin tüm uygun bölenlerini çıkarır; çünkü tam periyot denetiminde gereken küçük indisler yalnızca bunlardır. Daha sonra \(F_{120}\)'nin asal çarpanlara ayrılışı sabit olarak tutulur ve izin verilen asal kuvvetler kademeli biçimde çarpılarak \(10^9\)'dan küçük tüm bölenler üretilir.
Her aday modül için uygulama, Fibonacci durumunu \(120\). adımda hesaplar. Eğer durum \((0,1)\) değilse aday hemen reddedilir. Eğer durum \((0,1)\)'e dönüyorsa, aynı test \(120\)'nin her uygun böleni için tekrar yapılır. Aday ancak tüm küçük testler başarısız olduğunda kabul edilir.
Böylece kod matematiği bire bir izler: bölen üretimi \(n\mid F_{120}\) zorunlu koşulunu uygular, durum testleri ise bunu \(\pi(n)=120\) biçimindeki kesin sonuca yükseltir.
\(C\), \(10^9\)'dan küçük üretilen bölen sayısı olsun. Uygulamalar asla \([2,10^9)\) aralığının tamamını taramaz; sadece bu bölen listesini inceler. \(F_{120}\)'nin çarpanlarına ayrılışından, üst sınır uygulanmadan önce teorik aday üst sınırı \(36864\)'tür.
Her aday için \(120\) noktasında bir Fibonacci-çifti hesabı ve \(120\)'nin her uygun böleni için birer ek hesap gerekir. \(120\)'nin \(15\) uygun böleni vardır ve her hesap \(O(\log 120)\) sürer. Dolayısıyla toplam çalışma süresi \(O(C\log 120)\) olur; bu pratikte aday sayısına göre neredeyse doğrusaldır. Bellek kullanımı da \(O(C)\)'dir.
Para un módulo \(n\), la sucesión de Fibonacci reducida módulo \(n\) termina siendo periódica, y \(\pi(n)\) denota la longitud de su primer ciclo completo. El problema 853 pide calcular
$$\sum_{\substack{2 \le n \lt 10^9 \\ \pi(n)=120}} n.$$
Probar todos los enteros menores que \(10^9\) sería inviable. La idea correcta es convertir la condición sobre el período en una prueba exacta de regreso al estado inicial y luego usar propiedades de divisibilidad de los números de Fibonacci para reducir el espacio de búsqueda a un conjunto pequeño de divisores.
Escribimos
$$S_k(n)=\bigl(F_k \bmod n,\; F_{k+1} \bmod n\bigr).$$
Como la recurrencia de Fibonacci queda determinada por dos valores consecutivos, el período de Pisano es el menor entero positivo \(T\) tal que \(S_T(n)=S_0(n)=(0,1)\).
El par \((F_k,F_{k+1})\) determina toda la evolución futura de la sucesión. Por eso, la sucesión módulo \(n\) recomienza exactamente cuando reaparece el par \((0,1)\). En consecuencia, \(T\) es un período módulo \(n\) si y solo si
$$F_T \equiv 0 \pmod n,\qquad F_{T+1} \equiv 1 \pmod n.$$
Para que \(T\) sea el período de Pisano exacto, y no solo un múltiplo suyo, ningún divisor propio \(d \mid T\) puede satisfacer esas mismas congruencias.
Si \(\pi(n)=120\), entonces la primera congruencia implica de inmediato
$$n \mid F_{120}.$$
Las implementaciones usan la factorización explícita
$$F_{120}=2^5 \cdot 3^2 \cdot 5 \cdot 7 \cdot 11 \cdot 23 \cdot 31 \cdot 41 \cdot 61 \cdot 241 \cdot 2161 \cdot 2521 \cdot 20641.$$
Esto es solo una condición necesaria, porque todavía hay que imponer \(F_{121}\equiv 1 \pmod n\) y la minimalidad. Aun así, el recorte es enorme: todo módulo válido debe ser divisor de ese único número, así que ningún otro primo puede intervenir.
La cantidad de divisores de \(F_{120}\) es
$$\tau(F_{120})=(5+1)(2+1)2^{11}=36864.$$
Así, incluso antes de aplicar la cota \(n \lt 10^9\), ya solo quedan unas decenas de miles de candidatos estructuralmente posibles en lugar de mil millones de enteros. Las implementaciones generan esos divisores multiplicando las potencias primas permitidas y conservando únicamente los valores menores que el límite del problema.
Ser divisor de \(F_{120}\) no basta. Un candidato puede cumplir \(F_{120}\equiv 0 \pmod n\) aunque su verdadero período de Pisano sea \(10\), \(20\), \(30\), \(40\), \(60\) u otro divisor propio de \(120\). La exactitud se recupera exigiendo
$$S_{120}(n)=(0,1),$$
pero también
$$S_d(n)\ne(0,1)\qquad(d \mid 120,\ d \lt 120).$$
Esa segunda condición es exactamente la prueba de minimalidad.
Las implementaciones en C++, Python y Java evalúan pares de Fibonacci módulo \(n\) usando fast doubling. Para \(m\ge 0\),
$$F_{2m}=F_m\bigl(2F_{m+1}-F_m\bigr),\qquad F_{2m+1}=F_m^2+F_{m+1}^2.$$
Estas identidades permiten dividir el índice entre dos en cada paso recursivo, así que \((F_k,F_{k+1})\bmod n\) se obtiene en tiempo \(O(\log k)\). Como aquí solo se usan \(k=120\) o divisores de \(120\), el filtro resulta muy barato.
El divisor \(11\) muestra por qué la prueba de minimalidad es indispensable. Como \(11\mid F_{120}\), sobrevive a la generación de candidatos, y además
$$S_{120}(11)=(0,1).$$
Sin embargo, el mismo reinicio ya ocurre en \(d=10\), así que el verdadero período de Pisano módulo \(11\) es \(10\), no \(120\). Por eso \(11\) debe rechazarse.
En cambio, \(2521\) también divide a \(F_{120}\) y satisface \(S_{120}(2521)=(0,1)\), pero ningún divisor propio de \(120\) devuelve el estado \((0,1)\) módulo \(2521\). Por tanto, \(\pi(2521)=120\) y \(2521\) sí contribuye a la suma final.
La pequeña comprobación del método funciona igual: si el período objetivo se cambia a \(18\) y la búsqueda se limita a \(2 \le n \lt 50\), los únicos módulos válidos son \(19\) y \(38\), y la suma de control es \(57\).
La implementación comienza listando todos los divisores propios de \(120\), porque son exactamente los índices necesarios para rechazar candidatos cuyo período real sea más pequeño. Después fija la factorización prima de \(F_{120}\) y genera todos los divisores menores que \(10^9\) multiplicando acumulativamente las potencias primas permitidas.
Para cada módulo candidato, la implementación calcula el estado de Fibonacci en el índice \(120\). Si el estado no es \((0,1)\), el candidato se descarta de inmediato. Si sí vuelve a \((0,1)\), la implementación repite la misma prueba en cada divisor propio de \(120\). Un candidato se acepta solo cuando todas esas comprobaciones menores fallan.
La traducción entre matemáticas y programa es directa: la generación de divisores impone la condición necesaria \(n\mid F_{120}\), y las pruebas de estado la convierten en la afirmación exacta \(\pi(n)=120\).
Sea \(C\) el número de divisores generados por debajo de \(10^9\). Las implementaciones nunca recorren el intervalo completo \([2,10^9)\); solo inspeccionan esa lista de divisores. A partir de la factorización de \(F_{120}\), el máximo teórico antes del corte es \(36864\) candidatos.
Cada candidato requiere una evaluación del par de Fibonacci en \(120\) y otra adicional para cada divisor propio de \(120\). Hay \(15\) divisores propios, y cada evaluación cuesta \(O(\log 120)\). En consecuencia, el tiempo total es \(O(C\log 120)\), que en la práctica es casi lineal en el número de candidatos, y la memoria utilizada es \(O(C)\).
对于模数 \(n\)，Fibonacci 数列在模 \(n\) 意义下最终会进入循环，\(\pi(n)\) 表示它第一次完整循环的长度。第 853 题要求计算
$$\sum_{\substack{2 \le n \lt 10^9 \\ \pi(n)=120}} n.$$
如果把 \(10^9\) 以下的每个整数都逐个检验，代价会大得无法接受。有效做法是先把“周期等于 120”改写成一个严格的状态回归条件，再利用 Fibonacci 数的整除性质，把候选集合压缩到一个很小的约数集合中。
记
$$S_k(n)=\bigl(F_k \bmod n,\; F_{k+1} \bmod n\bigr).$$
因为 Fibonacci 递推只由两个相邻项决定，所以 Pisano 周期就是满足 \(S_T(n)=S_0(n)=(0,1)\) 的最小正整数 \(T\)。
\((F_k,F_{k+1})\) 这个有序对决定了后续整个数列，因此模 \(n\) 下的 Fibonacci 数列只有在 \((0,1)\) 重新出现时才真正“从头开始”。于是 \(T\) 是模 \(n\) 的一个周期，当且仅当
$$F_T \equiv 0 \pmod n,\qquad F_{T+1} \equiv 1 \pmod n.$$
但这还不够。若要让 \(T\) 是精确的 Pisano 周期，而不是某个更小周期的倍数，就必须要求 \(T\) 的任何真因子 \(d \mid T\) 都不能满足同样的状态回归条件。
如果 \(\pi(n)=120\)，那么第一条同余立刻说明
$$n \mid F_{120}.$$
实现所依赖的关键事实是
$$F_{120}=2^5 \cdot 3^2 \cdot 5 \cdot 7 \cdot 11 \cdot 23 \cdot 31 \cdot 41 \cdot 61 \cdot 241 \cdot 2161 \cdot 2521 \cdot 20641.$$
这只是必要条件，因为后面仍需检查 \(F_{121}\equiv 1 \pmod n\) 以及周期最小性。不过它已经极大地缩小了范围：任何合法的 \(n\) 都必须是这一个整数的约数，因此除此之外的素因子完全不可能出现。
由上面的分解式可知，\(F_{120}\) 的约数个数为
$$\tau(F_{120})=(5+1)(2+1)2^{11}=36864.$$
也就是说，在施加 \(n \lt 10^9\) 这个限制之前，结构上可能的候选数就已经从十亿个整数缩减到几万个。实现按素因子逐步相乘来构造这些约数，并且只保留小于题目上界的那些值。
仅仅满足 \(n \mid F_{120}\) 远远不够。某个候选模数也许让 \(F_{120}\equiv 0 \pmod n\) 成立，但它真正的 Pisano 周期可能是 \(10\)、\(20\)、\(30\)、\(40\)、\(60\) 或者 \(120\) 的其他真因子。要得到精确结论，必须同时满足
$$S_{120}(n)=(0,1),$$
并且
$$S_d(n)\ne(0,1)\qquad(d \mid 120,\ d \lt 120).$$
第二条恰好就是“最小周期”检查。
C++、Python 和 Java 实现都用快速倍增来计算模 \(n\) 下的 Fibonacci 相邻项。对任意 \(m\ge 0\)，有
$$F_{2m}=F_m\bigl(2F_{m+1}-F_m\bigr),\qquad F_{2m+1}=F_m^2+F_{m+1}^2.$$
这两个恒等式使得每次递归都能把下标减半，因此 \((F_k,F_{k+1})\bmod n\) 可以在 \(O(\log k)\) 时间内求出。由于本题中 \(k\) 只会取 \(120\) 或 \(120\) 的约数，所以单次检查的常数因子非常小。
\(11\) 是一个很能说明问题的例子。因为 \(11\mid F_{120}\)，它会出现在候选列表中，而且
$$S_{120}(11)=(0,1).$$
但是同样的状态回归在 \(d=10\) 时就已经发生了，所以模 \(11\) 的真实 Pisano 周期是 \(10\)，不是 \(120\)。因此 \(11\) 必须被排除。
相反，\(2521\) 同样整除 \(F_{120}\)，并且满足 \(S_{120}(2521)=(0,1)\)。更重要的是，\(120\) 的任何真因子在模 \(2521\) 下都不会把状态带回 \((0,1)\)。所以 \(\pi(2521)=120\)，它应当被计入最终总和。
实现中使用的小型校验也遵循同样思路：如果把目标周期改成 \(18\)，并把搜索区间限制为 \(2 \le n \lt 50\)，那么唯一符合条件的模数是 \(19\) 和 \(38\)，它们的和为 \(57\)。
实现首先列出 \(120\) 的所有真因子，因为这些正是判定“是否已经在更小步数回到起点”所需的检查点。然后把 \(F_{120}\) 的素因子分解作为固定输入，通过逐步乘入允许的素数幂，生成所有小于 \(10^9\) 的约数。
对每个候选模数，实现先计算第 \(120\) 项对应的 Fibonacci 状态。如果结果不是 \((0,1)\)，这个候选立刻被丢弃。如果确实回到了 \((0,1)\)，实现再对 \(120\) 的每个真因子做同样的状态检查。只有当这些更小的检查全部失败时，该候选才会被接受。
因此，代码与数学推导是一一对应的：约数生成阶段负责施加必要条件 \(n\mid F_{120}\)，状态检查阶段则把它提升为精确结论 \(\pi(n)=120\)。
设 \(C\) 为所有小于 \(10^9\) 的候选约数个数。实现从不扫描整个 \([2,10^9)\) 区间，而只处理这份约数列表。由 \(F_{120}\) 的分解可知，在上界筛选之前，理论上的候选总数上限是 \(36864\)。
每个候选需要在 \(120\) 处做一次 Fibonacci 状态计算，并对 \(120\) 的每个真因子各做一次。\(120\) 一共有 \(15\) 个真因子，而每次状态计算都只需 \(O(\log 120)\) 时间。因此总时间复杂度为 \(O(C\log 120)\)，在实际中几乎就是按候选数量线性增长；空间复杂度为 \(O(C)\)。
Для модуля \(n\) последовательность Fibonacci по модулю \(n\) в итоге становится периодической, а \(\pi(n)\) обозначает длину её первого полного цикла. В задаче 853 требуется вычислить
$$\sum_{\substack{2 \le n \lt 10^9 \\ \pi(n)=120}} n.$$
Проверять все числа меньше \(10^9\) напрямую бессмысленно. Рабочая идея состоит в том, чтобы переписать условие о периоде как точный возврат в начальное состояние, а затем с помощью свойств делимости чисел Fibonacci сократить пространство поиска до небольшого множества делителей.
Обозначим
$$S_k(n)=\bigl(F_k \bmod n,\; F_{k+1} \bmod n\bigr).$$
Так как рекуррентное соотношение Fibonacci полностью задаётся двумя соседними значениями, период Пизано есть наименьшее положительное \(T\), для которого \(S_T(n)=S_0(n)=(0,1)\).
Пара \((F_k,F_{k+1})\) определяет всё дальнейшее развитие последовательности. Поэтому последовательность по модулю \(n\) начинается заново ровно тогда, когда вновь появляется пара \((0,1)\). Следовательно, \(T\) является периодом по модулю \(n\) тогда и только тогда, когда
$$F_T \equiv 0 \pmod n,\qquad F_{T+1} \equiv 1 \pmod n.$$
Чтобы \(T\) был именно точным периодом Пизано, а не просто его кратным, ни один собственный делитель \(d \mid T\) не должен удовлетворять тем же сравнениям.
Если \(\pi(n)=120\), то первое сравнение сразу даёт
$$n \mid F_{120}.$$
Реализации используют явное разложение
$$F_{120}=2^5 \cdot 3^2 \cdot 5 \cdot 7 \cdot 11 \cdot 23 \cdot 31 \cdot 41 \cdot 61 \cdot 241 \cdot 2161 \cdot 2521 \cdot 20641.$$
Это только необходимое условие, потому что далее ещё нужно проверить \(F_{121}\equiv 1 \pmod n\) и минимальность периода. Но даже оно очень сильное: любой допустимый модуль обязан быть делителем именно этого числа, а значит, никакие другие простые множители появиться не могут.
Из разложения выше следует, что число делителей \(F_{120}\) равно
$$\tau(F_{120})=(5+1)(2+1)2^{11}=36864.$$
То есть ещё до применения ограничения \(n \lt 10^9\) мы сокращаем миллиард возможных чисел до нескольких десятков тысяч структурно допустимых кандидатов. Реализации строят эти делители мультипликативно, по простым множителям, и сохраняют только значения ниже заданного предела.
Того, что \(n\mid F_{120}\), недостаточно. Кандидат может удовлетворять сравнению \(F_{120}\equiv 0 \pmod n\), хотя его настоящий период Пизано равен \(10\), \(20\), \(30\), \(40\), \(60\) или другому собственному делителю \(120\). Точность восстанавливается требованиями
$$S_{120}(n)=(0,1),$$
и одновременно
$$S_d(n)\ne(0,1)\qquad(d \mid 120,\ d \lt 120).$$
Именно второе условие и есть проверка минимальности.
Реализации на C++, Python и Java вычисляют пары Fibonacci по модулю \(n\) методом fast doubling. Для \(m\ge 0\) выполняются тождества
$$F_{2m}=F_m\bigl(2F_{m+1}-F_m\bigr),\qquad F_{2m+1}=F_m^2+F_{m+1}^2.$$
Они позволяют уменьшать индекс вдвое на каждом рекурсивном шаге, поэтому \((F_k,F_{k+1})\bmod n\) находится за \(O(\log k)\). Здесь \(k\) всегда равно \(120\) или одному из делителей \(120\), так что стоимость проверки очень мала.
Число \(11\) хорошо показывает, зачем нужна проверка минимальности. Так как \(11\mid F_{120}\), оно попадает в список кандидатов, и кроме того
$$S_{120}(11)=(0,1).$$
Но тот же возврат происходит уже при \(d=10\), значит, истинный период Пизано по модулю \(11\) равен \(10\), а не \(120\). Поэтому \(11\) нужно отбросить.
Напротив, \(2521\) тоже делит \(F_{120}\) и удовлетворяет условию \(S_{120}(2521)=(0,1)\), но ни один собственный делитель \(120\) не возвращает состояние \((0,1)\) по модулю \(2521\). Следовательно, \(\pi(2521)=120\), и это число входит в итоговую сумму.
Небольшая контрольная проверка метода устроена так же: если заменить целевой период на \(18\) и ограничить поиск диапазоном \(2 \le n \lt 50\), единственными подходящими модулями окажутся \(19\) и \(38\), а контрольная сумма будет равна \(57\).
Сначала реализация выписывает все собственные делители числа \(120\), потому что именно они нужны для отсечения кандидатов с меньшим настоящим периодом. Затем фиксируется разложение \(F_{120}\) на простые множители, и все делители меньше \(10^9\) генерируются путём последовательного умножения допустимых простых степеней.
Для каждого кандидатного модуля реализация вычисляет состояние Fibonacci на шаге \(120\). Если это не \((0,1)\), кандидат немедленно отбрасывается. Если возврат к \((0,1)\) произошёл, тот же тест выполняется для каждого собственного делителя \(120\). Кандидат принимается только тогда, когда все меньшие проверки дают отрицательный результат.
Тем самым программа точно повторяет математическую схему: генерация делителей реализует необходимое условие \(n\mid F_{120}\), а проверки состояния превращают его в точное равенство \(\pi(n)=120\).
Пусть \(C\) обозначает число сгенерированных делителей, меньших \(10^9\). Реализации никогда не перебирают весь интервал \([2,10^9)\), а работают только с этим списком делителей. Из разложения \(F_{120}\) следует, что теоретическая верхняя граница до отсечения по лимиту равна \(36864\).
Для каждого кандидата нужна одна оценка пары Fibonacci в точке \(120\) и ещё по одной для каждого собственного делителя \(120\). У числа \(120\) ровно \(15\) собственных делителей, а каждая оценка стоит \(O(\log 120)\). Значит, суммарная сложность равна \(O(C\log 120)\), то есть практически линейна по числу кандидатов, а потребление памяти составляет \(O(C)\).
عند العمل بترديد \(n\)، تصبح متتالية Fibonacci دورية في النهاية، ونرمز بـ \(\pi(n)\) إلى طول أول دورة كاملة لها. تطلب المسألة 853 حساب
$$\sum_{\substack{2 \le n \lt 10^9 \\ \pi(n)=120}} n.$$
فحص جميع الأعداد الأصغر من \(10^9\) مباشرة غير عملي تمامًا. الفكرة الصحيحة هي تحويل شرط الفترة إلى اختبار دقيق لعودة الحالة الابتدائية، ثم استخدام خواص قابلية القسمة لأعداد Fibonacci من أجل تقليص فضاء البحث إلى مجموعة صغيرة من القواسم.
لنكتب
$$S_k(n)=\bigl(F_k \bmod n,\; F_{k+1} \bmod n\bigr).$$
ولأن علاقة Fibonacci التكرارية تتحدد بالكامل بحدين متتاليين، فإن فترة Pisano هي أصغر عدد موجب \(T\) يحقق \(S_T(n)=S_0(n)=(0,1)\).
الزوج \((F_k,F_{k+1})\) يحدد كل ما يأتي بعده في المتتالية. لذلك فإن المتتالية modulo \(n\) لا تبدأ من جديد إلا عندما يظهر الزوج \((0,1)\) مرة أخرى. ومن ثم يكون \(T\) فترة modulo \(n\) إذا وفقط إذا تحقق
$$F_T \equiv 0 \pmod n,\qquad F_{T+1} \equiv 1 \pmod n.$$
لكن حتى تكون \(T\) هي فترة Pisano الدنيا بالضبط، وليس مجرد مضاعف لها، فلا بد أن يفشل كل قاسم حقيقي \(d \mid T\) في تحقيق الشرط نفسه.
إذا كان \(\pi(n)=120\)، فإن أول علاقة توافق تعطينا مباشرة
$$n \mid F_{120}.$$
وتعتمد التطبيقات على التحليل الصريح التالي:
$$F_{120}=2^5 \cdot 3^2 \cdot 5 \cdot 7 \cdot 11 \cdot 23 \cdot 31 \cdot 41 \cdot 61 \cdot 241 \cdot 2161 \cdot 2521 \cdot 20641.$$
هذا شرط لازم فقط، لأننا ما زلنا بحاجة إلى التحقق من \(F_{121}\equiv 1 \pmod n\) ومن أصغرية الفترة. ومع ذلك فهو شديد القوة: أي \(n\) صالح لا بد أن يكون قاسمًا لهذا العدد الواحد، وبالتالي لا يمكن أن يظهر أي عامل أولي خارج هذه القائمة.
من التحليل السابق يكون عدد قواسم \(F_{120}\) مساويًا لـ
$$\tau(F_{120})=(5+1)(2+1)2^{11}=36864.$$
إذن حتى قبل تطبيق القيد \(n \lt 10^9\)، ينخفض عدد المرشحين الممكنين بنيويًا من مليار عدد إلى بضعة عشرات الآلاف فقط. وتقوم التطبيقات بتوليد هذه القواسم بصورة ضربّية، عاملًا أوليًا بعد عامل أولي، ثم تحتفظ فقط بالقيم الأصغر من حد المسألة.
كون \(n \mid F_{120}\) ليس كافيًا. فقد يحقق مرشح ما الشرط \(F_{120}\equiv 0 \pmod n\) رغم أن فترة Pisano الحقيقية له هي \(10\) أو \(20\) أو \(30\) أو \(40\) أو \(60\) أو أي قاسم حقيقي آخر للعدد \(120\). للحصول على المساواة الدقيقة، يجب أن يتحقق
$$S_{120}(n)=(0,1),$$
وكذلك
$$S_d(n)\ne(0,1)\qquad(d \mid 120,\ d \lt 120).$$
وهذا الشرط الثاني هو بالضبط اختبار الأصغرية.
تقوم تطبيقات C++ وPython وJava بحساب أزواج Fibonacci modulo \(n\) باستخدام طريقة fast doubling. فعندما \(m\ge 0\) نحصل على
$$F_{2m}=F_m\bigl(2F_{m+1}-F_m\bigr),\qquad F_{2m+1}=F_m^2+F_{m+1}^2.$$
تسمح هذه العلاقات بخفض الفهرس إلى النصف في كل خطوة تكرارية، ولذلك يمكن إيجاد \((F_k,F_{k+1})\bmod n\) في زمن \(O(\log k)\). وبما أن جميع القيم المستخدمة هنا هي \(120\) أو أحد قواسمه، فإن كلفة الاختبار صغيرة جدًا.
يُظهر العدد \(11\) بوضوح لماذا نحتاج إلى اختبار الأصغرية. بما أن \(11\mid F_{120}\)، فإنه ينجو من مرحلة توليد المرشحين، كما أن
$$S_{120}(11)=(0,1).$$
لكن العودة نفسها تحدث مسبقًا عند \(d=10\)، ولذلك فإن فترة Pisano الحقيقية modulo \(11\) هي \(10\) وليست \(120\). ولهذا يجب رفض \(11\).
أما \(2521\) فهو أيضًا يقسم \(F_{120}\) ويحقق \(S_{120}(2521)=(0,1)\)، لكن لا يوجد أي قاسم حقيقي للعدد \(120\) يعيد الحالة إلى \((0,1)\) modulo \(2521\). ومن ثم فإن \(\pi(2521)=120\)، ولذلك يدخل \(2521\) في المجموع النهائي.
وتعمل نقطة التحقق الصغيرة في المنهج بالطريقة نفسها: إذا غُيِّرت الفترة المستهدفة إلى \(18\) وقُيِّد البحث بالمجال \(2 \le n \lt 50\)، فإن القيمتين الوحيدتين الصالحتين هما \(19\) و\(38\)، ويكون مجموع الاختبار \(57\).
تبدأ الشيفرة بحصر جميع القواسم الحقيقية للعدد \(120\)، لأن هذه هي الفهارس الوحيدة المطلوبة لاكتشاف ما إذا كانت الفترة الحقيقية أصغر من \(120\). بعد ذلك تُثبَّت عوامل \(F_{120}\) الأولية، ثم تُولَّد جميع القواسم الأصغر من \(10^9\) عبر ضرب قوى العوامل الأولية المسموح بها بصورة تراكمية.
لكل modulus مرشح، تحسب الشيفرة حالة Fibonacci عند الفهرس \(120\). فإذا لم تكن النتيجة هي \((0,1)\)، يُرفض المرشح فورًا. وإذا عادت الحالة إلى \((0,1)\)، تعيد الشيفرة الاختبار نفسه عند كل قاسم حقيقي للعدد \(120\). ولا يُقبل المرشح إلا إذا فشلت جميع الاختبارات الأصغر.
وبذلك تطابق الشيفرة البرهان الرياضي مباشرة: توليد القواسم يفرض الشرط اللازم \(n\mid F_{120}\)، واختبارات الحالة ترفعه إلى العبارة الدقيقة \(\pi(n)=120\).
لنفرض أن \(C\) هو عدد القواسم المولدة تحت الحد \(10^9\). لا تقوم التطبيقات بمسح المجال الكامل \([2,10^9)\)، بل تعمل فقط على هذه القائمة من القواسم. ومن تحليل \(F_{120}\) نحصل على حد نظري أعلى يساوي \(36864\) مرشحًا قبل تطبيق شرط الحد الأعلى.
يحتاج كل مرشح إلى حساب واحد لزوج Fibonacci عند \(120\)، وحساب إضافي لكل قاسم حقيقي من قواسم \(120\). يوجد \(15\) قاسمًا حقيقيًا، وكل حساب يكلف \(O(\log 120)\). لذلك يكون الزمن الكلي \(O(C\log 120)\)، وهو عمليًا شبه خطي في عدد المرشحين، بينما يكون استهلاك الذاكرة \(O(C)\).