The Fibonacci sequence is defined by \(F_1=1\), \(F_2=1\), and \(F_n=F_{n-1}+F_{n-2}\) for \(n \ge 3\). The problem asks for the first index \(n\) such that \(F_n\) has 1000 decimal digits.
A direct search would keep generating larger and larger Fibonacci numbers until the digit count reaches 1000. The implementations take a lighter route: they still advance the Fibonacci recurrence, but they rescale the stored pair whenever a new power of ten is crossed. This keeps only mantissa-sized values in memory while still tracking exactly when the digit count increases.
Two complementary viewpoints are useful here. Analytically, Binet's formula and logarithms explain why the answer is 4782. Computationally, the implemented code uses the same growth law in iterative form by normalizing consecutive Fibonacci terms.
Because each term is the sum of the previous two, the Fibonacci numbers grow exponentially. The exact closed form is
\[ F_n=\frac{\varphi^n-\psi^n}{\sqrt5}, \qquad \varphi=\frac{1+\sqrt5}{2}, \qquad \psi=\frac{1-\sqrt5}{2}. \]
Here \(\varphi\) is the golden ratio and \(|\psi| \lt 1\). That second fact matters: the term \(\psi^n\) shrinks rapidly, so the size of \(F_n\) is controlled by \(\varphi^n/\sqrt5\). This is why the problem can be solved from growth alone without constructing a 1000-digit integer.
For any positive integer \(N\), the number of decimal digits is
\[ \operatorname{digits}(N)=\lfloor \log_{10} N \rfloor + 1. \]
So the first Fibonacci number with at least \(D\) digits is the first one satisfying
\[ F_n \ge 10^{D-1}. \]
Because the Fibonacci sequence is strictly increasing for \(n \ge 2\), this threshold is crossed only once. That means the problem really is "find the smallest index where the inequality becomes true."
For \(n \ge 2\), the standard Fibonacci digit formula is
\[ \operatorname{digits}(F_n)=\left\lfloor n\log_{10}\varphi-\log_{10}\sqrt5 \right\rfloor+1. \]
Therefore we want the smallest integer \(n\) such that
\[ \left\lfloor n\log_{10}\varphi-\log_{10}\sqrt5 \right\rfloor+1 \ge D. \]
That is equivalent to
\[ n\log_{10}\varphi-\log_{10}\sqrt5 \ge D-1, \]
hence
\[ n \ge \frac{D-1+\log_{10}\sqrt5}{\log_{10}\varphi}. \]
Since \(n\) must be an integer, the first valid index is
\[ \boxed{n=\left\lceil\frac{D-1+\log_{10}\sqrt5}{\log_{10}\varphi}\right\rceil.} \]
The special case \(D=1\) is handled separately, because \(F_1=1\) already has one digit.
Take \(D=3\). Then
\[ n=\left\lceil\frac{2+\log_{10}\sqrt5}{\log_{10}\varphi}\right\rceil =\left\lceil 11.00\ldots \right\rceil =12. \]
That matches the sequence itself: \(F_{11}=89\) has only 2 digits, while \(F_{12}=144\) has 3 digits. The same reasoning scales immediately to the Project Euler target \(D=1000\):
\[ n=\left\lceil\frac{999+\log_{10}\sqrt5}{\log_{10}\varphi}\right\rceil =\left\lceil 4781.859\ldots \right\rceil =4782. \]
An equivalent computational view keeps a scaled pair proportional to \((F_n,F_{n+1})\) and divides both values by \(10\) whenever the current term grows past \(10\). Because the Fibonacci recurrence is linear and homogeneous, this common rescaling does not change which index first reaches a given digit threshold. The ratio of consecutive terms still approaches \(1/\varphi\), so the normalized loop is the iterative counterpart of the same growth law.
The C++, Python, and Java implementations keep two consecutive Fibonacci terms in scaled form, together with a decimal-exponent counter and the current index. They start from \(F_1=F_2=1\), advance by the usual recurrence, and inspect the newly current term after each step.
If that stored term has grown past \(10\), both stored values are divided by \(10\) and the exponent counter is incremented. Applying the same factor to both terms preserves the recurrence up to a common scale, so the next update remains proportional to the true Fibonacci sequence.
The loop stops when the exponent counter first reaches \(D\). At that moment the current index is exactly the first index whose Fibonacci number has \(D\) digits. The implementations verify this on the checkpoints \(D=2 \mapsto 7\), \(D=3 \mapsto 12\), and \(D=1000 \mapsto 4782\).
Let \(t\) be the answer index. The normalized loop performs one constant-cost update per Fibonacci step, so the running time is \(O(t)\). Because Fibonacci digit counts grow linearly with the index, this is also \(O(D)\) for a requested digit threshold \(D\).
Memory usage is \(O(1)\): only two scaled terms, one exponent counter, and one index are stored. For the Project Euler target the total work is just 4782 iterations, so the method remains effectively instantaneous while avoiding both big integers and a direct logarithmic formula.
Die Fibonacci-Folge ist durch \(F_1=1\), \(F_2=1\) und \(F_n=F_{n-1}+F_{n-2}\) fur \(n \ge 3\) definiert. Gesucht ist der erste Index \(n\), fur den \(F_n\) genau genommen mindestens 1000 Dezimalstellen besitzt.
Man konnte die Folge naiv so lange erzeugen, bis die Stellenzahl 1000 erreicht wird. Die Implementierungen gehen aber leichter vor: Sie setzen die Fibonacci-Rekurrenz weiter fort, skalieren das gespeicherte Zahlenpaar jedoch jedes Mal gemeinsam herunter, wenn eine neue Zehnerpotenz ueberschritten wird. So bleiben nur mantissenartige Werte im Speicher, waehrend trotzdem exakt verfolgt wird, wann die Stellenzahl anwaechst.
Hier sind zwei Blickwinkel hilfreich. Analytisch erklaeren Binets Formel und Logarithmen, warum die Antwort 4782 lautet. Rechnerisch benutzt der implementierte Code dieselbe Wachstumsidee in iterativer Form, indem er aufeinanderfolgende Fibonacci-Zahlen fortlaufend normiert.
Die lineare Rekurrenz besitzt die exakte Darstellung
\[ F_n=\frac{\varphi^n-\psi^n}{\sqrt5}, \qquad \varphi=\frac{1+\sqrt5}{2}, \qquad \psi=\frac{1-\sqrt5}{2}. \]
\(\varphi\) ist der goldene Schnitt. Weil \(|\psi| \lt 1\) gilt, wird der Term \(\psi^n\) mit wachsendem \(n\) schnell klein. Das exponentielle Wachstum von \(F_n\) wird also praktisch von \(\varphi^n/\sqrt5\) gesteuert. Genau deshalb muss man die 1000-stellige Zahl nicht selbst konstruieren, wenn nur ihr erster Index gefragt ist.
Fur jede positive ganze Zahl \(N\) ist die Anzahl ihrer Dezimalstellen
\[ \operatorname{digits}(N)=\lfloor \log_{10} N \rfloor + 1. \]
Damit ist "mindestens \(D\) Stellen" gleichbedeutend mit
\[ F_n \ge 10^{D-1}. \]
Da die Fibonacci-Folge fur \(n \ge 2\) streng wachst, kann diese Schwelle nur ein einziges Mal erstmals uberschritten werden. Genau deshalb suchen wir wirklich nur das kleinste \(n\), fur das die Bedingung gilt.
Fur \(n \ge 2\) verwendet man die exakte Standardformel
\[ \operatorname{digits}(F_n)=\left\lfloor n\log_{10}\varphi-\log_{10}\sqrt5 \right\rfloor+1. \]
Gesucht ist also das kleinste \(n\) mit
\[ \left\lfloor n\log_{10}\varphi-\log_{10}\sqrt5 \right\rfloor+1 \ge D. \]
Das ist aquivalent zu
\[ n\log_{10}\varphi-\log_{10}\sqrt5 \ge D-1, \]
und damit zu
\[ n \ge \frac{D-1+\log_{10}\sqrt5}{\log_{10}\varphi}. \]
Da \(n\) ganzzahlig sein muss, folgt unmittelbar
\[ \boxed{n=\left\lceil\frac{D-1+\log_{10}\sqrt5}{\log_{10}\varphi}\right\rceil.} \]
Der Fall \(D=1\) ist ein Sonderfall, denn bereits \(F_1=1\) besitzt eine Stelle.
Setzen wir \(D=3\). Dann ergibt sich
\[ n=\left\lceil\frac{2+\log_{10}\sqrt5}{\log_{10}\varphi}\right\rceil =\left\lceil 11.00\ldots \right\rceil =12. \]
Das passt exakt zur Folge: \(F_{11}=89\) hat noch 2 Stellen, aber \(F_{12}=144\) hat 3. Fur die eigentliche Aufgabe mit \(D=1000\) erhalt man
\[ n=\left\lceil\frac{999+\log_{10}\sqrt5}{\log_{10}\varphi}\right\rceil =\left\lceil 4781.859\ldots \right\rceil =4782. \]
Eine gleichwertige numerische Sicht haelt ein skaliertes Paar proportional zu \((F_n,F_{n+1})\) fest und teilt beide Werte durch \(10\), sobald der aktuelle Term ueber \(10\) waechst. Weil die Fibonacci-Rekurrenz linear und homogen ist, aendert diese gemeinsame Reskalierung nicht, bei welchem Index erstmals eine vorgegebene Stellenzahl erreicht wird. Das Verhaeltnis aufeinanderfolgender Terme konvergiert weiterhin gegen \(1/\varphi\); damit ist die normierte Schleife das iterative Gegenstueck zum selben Wachstumsgesetz.
Die C++-, Python- und Java-Implementierungen halten zwei aufeinanderfolgende Fibonacci-Zahlen in skalierter Form, dazu einen Dezimalexponenten-Zaehler und den aktuellen Index. Sie starten bei \(F_1=F_2=1\), gehen die Rekurrenz Schritt fuer Schritt weiter und betrachten nach jedem Schritt den nun aktuellen Term.
Sobald dieser gespeicherte Term ueber \(10\) waechst, werden beide gespeicherten Werte durch \(10\) geteilt und der Exponenten-Zaehler wird erhoeht. Weil derselbe Faktor auf beide Zahlen angewendet wird, bleibt die Rekurrenz bis auf eine gemeinsame Skalierung erhalten; der naechste Schritt ist also weiterhin proportional zur echten Fibonacci-Folge.
Die Schleife endet genau dann, wenn der Exponenten-Zaehler erstmals \(D\) erreicht. In diesem Moment ist der aktuelle Index genau der erste Index, dessen Fibonacci-Zahl \(D\) Stellen besitzt. Geprueft wird das mit den Kontrollpunkten \(D=2 \mapsto 7\), \(D=3 \mapsto 12\) und \(D=1000 \mapsto 4782\).
Sei \(t\) der gesuchte Index. Die normierte Schleife fuehrt pro Fibonacci-Schritt genau ein Update mit konstantem Aufwand aus, also betraegt die Laufzeit \(O(t)\). Da die Stellenzahl der Fibonacci-Zahlen linear mit dem Index waechst, ist das in Abhaengigkeit von der geforderten Stellenzahl \(D\) ebenso \(O(D)\).
Der Speicherverbrauch bleibt \(O(1)\): gespeichert werden nur zwei skalierte Terme, ein Exponenten-Zaehler und ein Index. Fuer das Project-Euler-Ziel sind das lediglich 4782 Iterationen; damit ist die Methode praktisch sofort fertig, ohne grosse Ganzzahlen oder eine direkte Logarithmenformel zu benoetigen.
Fibonacci dizisi \(F_1=1\), \(F_2=1\) ve \(n \ge 3\) icin \(F_n=F_{n-1}+F_{n-2}\) seklinde tanimlanir. Soruda istenen sey, ondalik yaziminda en az 1000 basamak bulunan ilk Fibonacci sayisinin indisidir.
Naif yaklasim, Fibonacci sayilarini sirayla uretip basamak sayisi 1000 olana kadar devam etmektir. Uygulamalar ise daha hafif bir yol izler: Fibonacci yinelemesini surdururler, fakat saklanan cifti her yeni 10 kuvveti asildiginda birlikte yeniden olceklendirirler. Boylece bellekte yalnizca mantissa buyuklugunde degerler tutulurken basamak sayisinin ne zaman arttigi da tam olarak izlenir.
Burada iki tamamlayici bakis acisi yararlidir. Analitik tarafta Binet formulu ve logaritmalar cevabin neden 4782 oldugunu aciklar. Hesaplamali tarafta ise uygulanan kod, ardisik Fibonacci terimlerini normalize ederek ayni buyume kanununu yinelemeli bicimde kullanir.
Fibonacci rekurrensinin tam cozumu
\[ F_n=\frac{\varphi^n-\psi^n}{\sqrt5}, \qquad \varphi=\frac{1+\sqrt5}{2}, \qquad \psi=\frac{1-\sqrt5}{2}. \]
Burada \(\varphi\) altin orandir. \(|\psi| \lt 1\) oldugu icin \(\psi^n\) terimi hizla kuculur; dolayisiyla \(F_n\)'in buyuklugu esas olarak \(\varphi^n/\sqrt5\) ile belirlenir. Problem sadece ilk uygun indisi sordugu icin, devasa Fibonacci sayisinin kendisini yazmaya ihtiyac kalmaz.
Her pozitif tam sayi \(N\) icin ondalik basamak sayisi
\[ \operatorname{digits}(N)=\lfloor \log_{10} N \rfloor + 1 \]
seklindedir. O halde \(F_n\)'in en az \(D\) basamakli olmasi
\[ F_n \ge 10^{D-1} \]
demektir. Fibonacci sayilari \(n \ge 2\) icin kesinlikle artan oldugundan, bu esik ilk kez yalnizca tek bir indiste asilabilir. Bu nedenle aradigimiz sey, esitsizligi saglayan en kucuk indisin kendisidir.
Fibonacci sayilari icin \(n \ge 2\) durumunda kullanilan standart tam formul ise
\[ \operatorname{digits}(F_n)=\left\lfloor n\log_{10}\varphi-\log_{10}\sqrt5 \right\rfloor+1. \]
Bu nedenle asgari \(n\) su kosulu saglamalidir:
\[ \left\lfloor n\log_{10}\varphi-\log_{10}\sqrt5 \right\rfloor+1 \ge D. \]
Bu da
\[ n\log_{10}\varphi-\log_{10}\sqrt5 \ge D-1 \]
ve dolayisiyla
\[ n \ge \frac{D-1+\log_{10}\sqrt5}{\log_{10}\varphi} \]
anlamina gelir. \(n\) tam sayi olmak zorunda oldugu icin ilk uygun indis
\[ \boxed{n=\left\lceil\frac{D-1+\log_{10}\sqrt5}{\log_{10}\varphi}\right\rceil} \]
olur. \(D=1\) durumu ayrica ele alinmalidir; cunku \(F_1=1\) zaten tek basamaklidir.
Ornek olarak \(D=3\) alalim. Formul
\[ n=\left\lceil\frac{2+\log_{10}\sqrt5}{\log_{10}\varphi}\right\rceil =\left\lceil 11.00\ldots \right\rceil =12 \]
sonucunu verir. Gercekten de \(F_{11}=89\) iki basamaklidir, \(F_{12}=144\) ise uc basamaklidir. Asil hedef olan \(D=1000\) icin ayni hesap
\[ n=\left\lceil\frac{999+\log_{10}\sqrt5}{\log_{10}\varphi}\right\rceil =\left\lceil 4781.859\ldots \right\rceil =4782 \]
degerini verir.
Buna esit bir sayisal bakis da vardir: \((F_n,F_{n+1})\) ciftiyle orantili olceklenmis bir cift tutulur ve guncel terim \(10\)'u astiginda iki deger de birlikte \(10\)'a bolunur. Fibonacci yinelemesi dogrusal ve homojen oldugu icin bu ortak yeniden olcekleme, verilen bir basamak esigine ilk hangi indiste ulasildigini degistirmez. Ardisik terimlerin orani yine \(1/\varphi\)'ye yaklastigindan, normalize dongu ayni buyume kanununun yinelemeli karsiligidir.
C++, Python ve Java uygulamalari iki ardisik Fibonacci terimini olceklenmis bicimde, bir ondalik us sayaci ve guncel indis ile birlikte tutar. \(F_1=F_2=1\) durumundan baslar, alisilmis yinelemeyi adim adim ilerletir ve her adimdan sonra artik guncel olan terime bakar.
Bu saklanan terim \(10\)'u astiginda iki deger de \(10\)'a bolunur ve us sayaci bir arttirilir. Ayni ortak carpanin iki terime birden uygulanmasi, yinelemeyi ortak bir olcek haricinde korudugu icin siradaki adim gercek Fibonacci dizisiyle orantili kalir.
Dongu, us sayaci ilk kez \(D\)'ye ulastiginda durur. O anda eldeki indis, Fibonacci sayisi \(D\) basamakli olan ilk indisle tam olarak aynidir. Uygulamalar bunu \(D=2 \mapsto 7\), \(D=3 \mapsto 12\) ve \(D=1000 \mapsto 4782\) kontrol noktalarinda dogrular.
Aranan cevap indisina \(t\) diyelim. Normalize dongu her Fibonacci adiminda sabit maliyetli tek bir guncelleme yaptigi icin calisma suresi \(O(t)\)'dir. Fibonacci basamak sayisi indisle dogrusal buyudugunden, istenen basamak esigi \(D\) cinsinden de bu \(O(D)\) olur.
Bellek kullanimi \(O(1)\) olarak kalir; yalnizca iki olceklenmis terim, bir us sayaci ve bir indis tutulur. Project Euler hedefinde toplam is sadece 4782 iterasyondur; dolayisiyla bu yontem buyuk tamsayilardan ve dogrudan logaritma formulunden kacinarak yine de fiilen anlik calisir.
La sucesion de Fibonacci esta definida por \(F_1=1\), \(F_2=1\) y \(F_n=F_{n-1}+F_{n-2}\) para \(n \ge 3\). El objetivo es encontrar el primer indice \(n\) para el cual \(F_n\) tiene al menos 1000 cifras decimales.
Una solucion directa generaria terminos de Fibonacci hasta que la longitud decimal alcance 1000. Las implementaciones siguen una via mas ligera: avanzan la recurrencia de Fibonacci, pero reescalan el par almacenado cada vez que se cruza una nueva potencia de \(10\). Asi solo quedan en memoria valores del tamano de una mantisa, y aun asi se registra con exactitud el momento en que aumenta el numero de cifras.
Aqui conviene separar dos miradas complementarias. En la parte analitica, la formula de Binet y los logaritmos explican por que la respuesta es 4782. En la parte computacional, el codigo implementado usa esa misma ley de crecimiento en forma iterativa, normalizando terminos consecutivos de Fibonacci.
La solucion exacta de la recurrencia es
\[ F_n=\frac{\varphi^n-\psi^n}{\sqrt5}, \qquad \varphi=\frac{1+\sqrt5}{2}, \qquad \psi=\frac{1-\sqrt5}{2}. \]
\(\varphi\) es la razon aurea. Como \(|\psi| \lt 1\), el termino \(\psi^n\) se vuelve rapidamente insignificante cuando \(n\) crece. Por eso el tamano de \(F_n\) esta gobernado por \(\varphi^n/\sqrt5\), y eso basta para localizar el primer indice que cruza un umbral de cifras.
Para cualquier entero positivo \(N\), el numero de cifras decimales es
\[ \operatorname{digits}(N)=\lfloor \log_{10} N \rfloor + 1. \]
Asi, pedir que \(F_n\) tenga al menos \(D\) cifras equivale a exigir
\[ F_n \ge 10^{D-1}. \]
Como la sucesion de Fibonacci es estrictamente creciente para \(n \ge 2\), ese umbral se cruza por primera vez en un unico indice. Por tanto basta con localizar el menor \(n\) que satisface la condicion.
En el caso de Fibonacci, para \(n \ge 2\) se usa la formula exacta
\[ \operatorname{digits}(F_n)=\left\lfloor n\log_{10}\varphi-\log_{10}\sqrt5 \right\rfloor+1. \]
Por tanto buscamos el menor entero \(n\) tal que
\[ \left\lfloor n\log_{10}\varphi-\log_{10}\sqrt5 \right\rfloor+1 \ge D. \]
Esto se simplifica a
\[ n\log_{10}\varphi-\log_{10}\sqrt5 \ge D-1, \]
y luego a
\[ n \ge \frac{D-1+\log_{10}\sqrt5}{\log_{10}\varphi}. \]
Como \(n\) debe ser entero, el primer indice valido es
\[ \boxed{n=\left\lceil\frac{D-1+\log_{10}\sqrt5}{\log_{10}\varphi}\right\rceil.} \]
El caso \(D=1\) se trata aparte, porque \(F_1=1\) ya tiene una cifra.
Si tomamos \(D=3\), obtenemos
\[ n=\left\lceil\frac{2+\log_{10}\sqrt5}{\log_{10}\varphi}\right\rceil =\left\lceil 11.00\ldots \right\rceil =12. \]
La comprobacion directa coincide: \(F_{11}=89\) todavia tiene 2 cifras, mientras que \(F_{12}=144\) ya tiene 3. Para el objetivo del problema, \(D=1000\), la misma formula produce
\[ n=\left\lceil\frac{999+\log_{10}\sqrt5}{\log_{10}\varphi}\right\rceil =\left\lceil 4781.859\ldots \right\rceil =4782. \]
Existe una lectura numerica equivalente: mantener un par escalado proporcional a \((F_n,F_{n+1})\) y dividir ambos valores entre \(10\) cuando el termino actual supera \(10\). Como la recurrencia de Fibonacci es lineal y homogenea, ese reescalado comun no altera el indice en el que se alcanza por primera vez un cierto umbral de cifras. La razon entre terminos consecutivos sigue acercandose a \(1/\varphi\), de modo que el bucle normalizado es la version iterativa de la misma ley de crecimiento.
Las implementaciones en C++, Python y Java guardan dos terminos consecutivos de Fibonacci en forma escalada, junto con un contador de exponente decimal y el indice actual. Empiezan en \(F_1=F_2=1\), avanzan con la recurrencia habitual y, tras cada paso, inspeccionan el termino que acaba de quedar como actual.
Si ese termino almacenado ya ha superado \(10\), ambos valores se dividen entre \(10\) y el contador de exponente aumenta en una unidad. Como el mismo factor se aplica a los dos terminos, la recurrencia se conserva salvo por una escala comun, y el siguiente paso sigue siendo proporcional a la sucesion real de Fibonacci.
El bucle termina cuando el contador de exponente alcanza por primera vez \(D\). En ese instante, el indice actual es exactamente el primero cuyo numero de Fibonacci tiene \(D\) cifras. Las implementaciones lo verifican con los puntos de control \(D=2 \mapsto 7\), \(D=3 \mapsto 12\) y \(D=1000 \mapsto 4782\).
Sea \(t\) el indice buscado. El bucle normalizado realiza una actualizacion de coste constante por cada paso de Fibonacci, de modo que el tiempo de ejecucion es \(O(t)\). Como el numero de cifras de Fibonacci crece linealmente con el indice, eso equivale tambien a \(O(D)\) respecto al umbral de cifras pedido.
El consumo de memoria sigue siendo \(O(1)\): solo se almacenan dos terminos escalados, un contador de exponente y un indice. Para el objetivo de Project Euler el trabajo total es de apenas 4782 iteraciones, asi que el metodo sigue siendo practicamente instantaneo sin recurrir ni a enteros gigantes ni a una formula logaritmica directa.
斐波那契数列满足 \(F_1=1\)、\(F_2=1\)，并且对 \(n \ge 3\) 有 \(F_n=F_{n-1}+F_{n-2}\)。本题要求找出第一个使 \(F_n\) 拥有至少 1000 位十进制数字的下标。
如果直接做，可以从头生成斐波那契数并不断检查位数，直到第一次达到 1000 位为止。这里的实现采用了更轻量的做法：它仍然沿着斐波那契递推前进，但每当当前项跨过一个新的 \(10\) 的幂，就把保存的相邻两项同时缩放。这样内存里始终只保留尾数量级的数值，却仍能精确记录位数何时增加。
这个问题有两个互补的视角。分析上，Binet 公式与对数直接解释了答案为什么是 4782；计算上，实际代码把同样的增长规律写成了对相邻斐波那契项持续归一化的迭代过程。
斐波那契递推的精确闭式是
\[ F_n=\frac{\varphi^n-\psi^n}{\sqrt5}, \qquad \varphi=\frac{1+\sqrt5}{2}, \qquad \psi=\frac{1-\sqrt5}{2}. \]
其中 \(\varphi\) 是黄金比例，\(\psi\) 是另一个特征根。关键点在于 \(|\psi| \lt 1\)，所以当 \(n\) 增大时，\(\psi^n\) 会非常快地衰减。也就是说，\(F_n\) 的数量级由 \(\varphi^n/\sqrt5\) 主导。这正是本题可以不去构造 1000 位整数、而只通过增长率就锁定答案的原因。
对任意正整数 \(N\)，其十进制位数满足
\[ \operatorname{digits}(N)=\lfloor \log_{10} N \rfloor + 1. \]
因此，\(F_n\) 至少有 \(D\) 位，当且仅当
\[ F_n \ge 10^{D-1}. \]
由于斐波那契数列在 \(n \ge 2\) 时严格递增，所以这个阈值只会第一次被跨过一次。题目于是变成了一个更精确的问题：求使这条不等式成立的最小下标。
对斐波那契数来说，在 \(n \ge 2\) 时可直接使用标准的精确位数公式
\[ \operatorname{digits}(F_n)=\left\lfloor n\log_{10}\varphi-\log_{10}\sqrt5 \right\rfloor+1. \]
于是我们要找最小的整数 \(n\)，使得
\[ \left\lfloor n\log_{10}\varphi-\log_{10}\sqrt5 \right\rfloor+1 \ge D. \]
这等价于
\[ n\log_{10}\varphi-\log_{10}\sqrt5 \ge D-1, \]
再整理得到
\[ n \ge \frac{D-1+\log_{10}\sqrt5}{\log_{10}\varphi}. \]
由于 \(n\) 必须是整数，第一个满足条件的下标就是
\[ \boxed{n=\left\lceil\frac{D-1+\log_{10}\sqrt5}{\log_{10}\varphi}\right\rceil.} \]
需要单独说明的是 \(D=1\) 的情况，因为 \(F_1=1\) 本身已经是一位数；实现中也专门把这个边界条件单独处理。
先看一个较小的例子：如果要求第一个 3 位的斐波那契数，那么 \(D=3\)，公式给出
\[ n=\left\lceil\frac{2+\log_{10}\sqrt5}{\log_{10}\varphi}\right\rceil =\left\lceil 11.00\ldots \right\rceil =12. \]
这和实际序列完全一致，因为 \(F_{11}=89\) 仍然只有 2 位，而 \(F_{12}=144\) 已经达到 3 位。把同样的推导应用到题目的目标 \(D=1000\)，就得到
\[ n=\left\lceil\frac{999+\log_{10}\sqrt5}{\log_{10}\varphi}\right\rceil =\left\lceil 4781.859\ldots \right\rceil =4782. \]
所以答案并不是通过生成第 4782 个斐波那契数之后再数位数得到的，而是先从增长规律上证明“第一个达到 1000 位的下标必须是 4782”。
与上面的闭式推导等价，还有一种数值视角：始终维护一个与 \((F_n,F_{n+1})\) 成比例的缩放二元组，并在当前项超过 \(10\) 时把两者同时除以 \(10\)。由于斐波那契递推是线性齐次的，这种共同缩放不会改变“第一次达到某个位数阈值”的下标。相邻两项的比值仍会趋向 \(1/\varphi\)，所以这个归一化循环正是同一增长规律的迭代版本。
C++、Python 和 Java 三个实现都保存两个缩放后的相邻斐波那契项，再配上一个十进制指数计数器和当前下标。它们从 \(F_1=F_2=1\) 出发，按普通递推前进，并在每一步之后检查刚成为“当前项”的那个值。
如果这个保存的当前项已经超过 \(10\)，就把两个值同时除以 \(10\)，并把指数计数器加一。因为两个项被施加了同一个公共因子，递推关系除了整体尺度外并没有改变，所以下一步仍然与真实的斐波那契序列成比例。
当指数计数器第一次达到 \(D\) 时，循环就停止。此时的下标恰好就是第一个拥有 \(D\) 位的斐波那契数下标。实现用 \(D=2 \mapsto 7\)、\(D=3 \mapsto 12\) 和 \(D=1000 \mapsto 4782\) 这些检查点来验证结果。
设答案下标为 \(t\)。归一化循环对每一个斐波那契步只做一次常数成本更新，因此时间复杂度是 \(O(t)\)。由于斐波那契数的位数随下标线性增长，所以相对于目标位数阈值 \(D\)，这也可以写成 \(O(D)\)。
空间复杂度仍是 \(O(1)\)：程序只保存两个缩放项、一个指数计数器和一个下标。对 Project Euler 这里的目标而言，总工作量不过 4782 次迭代，因此它依然几乎是瞬时完成，同时还避开了大整数和直接套用对数公式。
Последовательность Фибоначчи задается условиями \(F_1=1\), \(F_2=1\) и \(F_n=F_{n-1}+F_{n-2}\) при \(n \ge 3\). Требуется найти наименьший индекс \(n\), для которого число \(F_n\) содержит не менее 1000 десятичных цифр.
Можно было бы просто порождать числа Фибоначчи по порядку и на каждом шаге проверять длину записи. Но реализации выбирают более легкий путь: они продолжают обычную рекурсию, но каждый раз совместно масштабируют хранимую соседнюю пару, когда текущий член переходит к новой степени десяти. Так в памяти остаются только значения масштаба мантиссы, а момент увеличения числа цифр все равно отслеживается точно.
Здесь полезно держать в уме два дополняющих друг друга взгляда. Аналитически формула Бине и логарифмы объясняют, почему ответ равен 4782. Вычислительно же реализованный код использует тот же закон роста в виде нормализованной итерации по соседним членам Фибоначчи.
Точное выражение для \(F_n\) имеет вид
\[ F_n=\frac{\varphi^n-\psi^n}{\sqrt5}, \qquad \varphi=\frac{1+\sqrt5}{2}, \qquad \psi=\frac{1-\sqrt5}{2}. \]
\(\varphi\) - это золотое сечение. Важное наблюдение состоит в том, что \(|\psi| \lt 1\), поэтому член \(\psi^n\) очень быстро убывает по модулю. Значит, величина \(F_n\) фактически определяется главным ростовым членом \(\varphi^n/\sqrt5\). Поэтому, если нужен только индекс первого подходящего числа, строить само 1000-значное число не требуется.
Для любого положительного целого \(N\) количество десятичных цифр равно
\[ \operatorname{digits}(N)=\lfloor \log_{10} N \rfloor + 1. \]
Следовательно, условие "у \(F_n\) не меньше \(D\) цифр" эквивалентно неравенству
\[ F_n \ge 10^{D-1}. \]
Так как последовательность Фибоначчи строго возрастает при \(n \ge 2\), этот порог впервые пересекается ровно в одном месте. Значит, нужно просто найти наименьший индекс, для которого неравенство уже верно.
Для чисел Фибоначчи при \(n \ge 2\) используется стандартная точная формула
\[ \operatorname{digits}(F_n)=\left\lfloor n\log_{10}\varphi-\log_{10}\sqrt5 \right\rfloor+1. \]
Значит, нужно найти минимальное целое \(n\), удовлетворяющее
\[ \left\lfloor n\log_{10}\varphi-\log_{10}\sqrt5 \right\rfloor+1 \ge D. \]
Это равносильно условию
\[ n\log_{10}\varphi-\log_{10}\sqrt5 \ge D-1, \]
то есть
\[ n \ge \frac{D-1+\log_{10}\sqrt5}{\log_{10}\varphi}. \]
Поскольку индекс должен быть целым, получаем точную формулу
\[ \boxed{n=\left\lceil\frac{D-1+\log_{10}\sqrt5}{\log_{10}\varphi}\right\rceil.} \]
Случай \(D=1\) рассматривается отдельно: уже \(F_1=1\) имеет одну цифру.
Пусть \(D=3\). Тогда
\[ n=\left\lceil\frac{2+\log_{10}\sqrt5}{\log_{10}\varphi}\right\rceil =\left\lceil 11.00\ldots \right\rceil =12. \]
Проверка по самой последовательности дает то же самое: \(F_{11}=89\) еще двузначно, а \(F_{12}=144\) уже трехзначно. Для исходной задачи с \(D=1000\) формула дает
\[ n=\left\lceil\frac{999+\log_{10}\sqrt5}{\log_{10}\varphi}\right\rceil =\left\lceil 4781.859\ldots \right\rceil =4782. \]
Есть и эквивалентный численный взгляд: хранить масштабированную пару, пропорциональную \((F_n,F_{n+1})\), и делить оба значения на \(10\), когда текущий член становится больше \(10\). Так как рекуррентное соотношение Фибоначчи линейно и однородно, такое общее масштабирование не меняет индекс, на котором впервые достигается заданный порог по числу цифр. Отношение соседних членов по-прежнему стремится к \(1/\varphi\), поэтому нормализованный цикл является итерационным двойником того же закона роста.
Реализации на C++, Python и Java хранят два соседних числа Фибоначчи в масштабированном виде, а также счетчик десятичного показателя и текущий индекс. Они стартуют из \(F_1=F_2=1\), двигаются по обычной рекурсии и после каждого шага смотрят на тот член, который только что стал текущим.
Если этот сохраненный член уже превысил \(10\), оба значения делятся на \(10\), а счетчик показателя увеличивается на единицу. Поскольку один и тот же общий множитель применяется к обоим членам, рекуррентное соотношение сохраняется с точностью до общего масштаба, и следующий шаг остается пропорционален истинной последовательности Фибоначчи.
Цикл завершается, когда счетчик показателя впервые достигает \(D\). В этот момент текущий индекс в точности является первым индексом, у которого число Фибоначчи имеет \(D\) цифр. Реализации проверяют это на контрольных точках \(D=2 \mapsto 7\), \(D=3 \mapsto 12\) и \(D=1000 \mapsto 4782\).
Пусть \(t\) - искомый индекс. Нормализованный цикл делает одно обновление постоянной стоимости на каждый шаг Фибоначчи, поэтому время работы равно \(O(t)\). Поскольку число цифр у чисел Фибоначчи растет линейно вместе с индексом, по отношению к требуемому порогу \(D\) это то же самое \(O(D)\).
Память остается \(O(1)\): хранятся только два масштабированных члена, счетчик показателя и индекс. Для цели Project Euler это всего 4782 итерации, так что метод практически мгновенен, хотя и не использует ни большие целые числа, ни прямую логарифмическую формулу.
متتالية فيبوناتشي معرفة بالعلاقات \(F_1=1\) و\(F_2=1\) و\(F_n=F_{n-1}+F_{n-2}\) عندما \(n \ge 3\). المطلوب هو إيجاد أول فهرس \(n\) يكون فيه العدد \(F_n\) ذا 1000 رقم عشري على الأقل.
يمكن حل المسألة بطريقة مباشرة عبر توليد اعداد فيبوناتشي واحدا بعد واحد ثم فحص عدد الارقام في كل مرة. لكن التطبيقات تختار طريقا اخف: فهي تتابع علاقة فيبوناتشي نفسها، لكنها تعيد تحجيم الزوج المخزن معا كلما تجاوز الحد الحالي قوة جديدة للعدد \(10\). وبهذا تبقى في الذاكرة قيم بحجم المانتيسا فقط، مع استمرار تتبع لحظة ازدياد عدد الارقام بدقة تامة.
من المفيد هنا الجمع بين منظورين متكاملين. تحليليا تشرح صيغة بينيه واللوغاريتمات لماذا تكون الاجابة 4782. وحسابيا تستعمل الشيفرة المنفذة قانون النمو نفسه بصيغة تكرارية عبر تطبيع حدود فيبوناتشي المتجاورة.
الحل الدقيق لعلاقة فيبوناتشي هو
\[ F_n=\frac{\varphi^n-\psi^n}{\sqrt5}, \qquad \varphi=\frac{1+\sqrt5}{2}, \qquad \psi=\frac{1-\sqrt5}{2}. \]
\(\varphi\) هو العدد الذهبي. والنقطة الحاسمة هي ان \(|\psi| \lt 1\)، ولذلك فان \(\psi^n\) يتضاءل بسرعة كبيرة مع ازدياد \(n\). هذا يعني ان حجم \(F_n\) تحكمه عمليا الكمية \(\varphi^n/\sqrt5\)، ومن ثم لا حاجة الى بناء عدد فيبوناتشي المكون من 1000 رقم حتى نعرف اين يظهر لاول مرة.
لاي عدد صحيح موجب \(N\)، يكون عدد ارقامه العشرية مساويا لـ
\[ \operatorname{digits}(N)=\lfloor \log_{10} N \rfloor + 1. \]
لذلك فان امتلاك \(F_n\) لما لا يقل عن \(D\) رقما يكافئ الشرط
\[ F_n \ge 10^{D-1}. \]
وبما ان متتالية فيبوناتشي تزداد بشكل صارم عندما \(n \ge 2\)، فان هذه العتبة لا يتم تجاوزها لاول مرة الا عند فهرس واحد محدد. لذلك يكفي ان نعزل اصغر \(n\) يحقق هذا الشرط.
وبالنسبة لاعداد فيبوناتشي، فعند \(n \ge 2\) نستعمل الصيغة الدقيقة القياسية
\[ \operatorname{digits}(F_n)=\left\lfloor n\log_{10}\varphi-\log_{10}\sqrt5 \right\rfloor+1. \]
اذن نبحث عن اصغر عدد صحيح \(n\) يحقق
\[ \left\lfloor n\log_{10}\varphi-\log_{10}\sqrt5 \right\rfloor+1 \ge D. \]
وهذا يكافئ
\[ n\log_{10}\varphi-\log_{10}\sqrt5 \ge D-1, \]
ومن ثم
\[ n \ge \frac{D-1+\log_{10}\sqrt5}{\log_{10}\varphi}. \]
وبما ان \(n\) يجب ان يكون عددا صحيحا، فان اول فهرس مناسب هو
\[ \boxed{n=\left\lceil\frac{D-1+\log_{10}\sqrt5}{\log_{10}\varphi}\right\rceil.} \]
اما الحالة \(D=1\) فتعالج منفصلة، لان \(F_1=1\) هو بالفعل عدد مكون من رقم واحد.
اذا اخذنا \(D=3\)، نحصل على
\[ n=\left\lceil\frac{2+\log_{10}\sqrt5}{\log_{10}\varphi}\right\rceil =\left\lceil 11.00\ldots \right\rceil =12. \]
وهذا يطابق المتتالية نفسها: \(F_{11}=89\) ما زال ذا رقمين، بينما \(F_{12}=144\) هو اول حد ذي ثلاثة ارقام. وعند تطبيق الصيغة على هدف المسألة \(D=1000\) نجد
\[ n=\left\lceil\frac{999+\log_{10}\sqrt5}{\log_{10}\varphi}\right\rceil =\left\lceil 4781.859\ldots \right\rceil =4782. \]
وهناك قراءة عددية مكافئة ايضا: نحتفظ بزوج مقياس متناسب مع \((F_n,F_{n+1})\)، ثم نقسم القيمتين معا على \(10\) كلما تجاوز الحد الحالي القيمة \(10\). ولان علاقة فيبوناتشي خطية ومتجانسة، فان اعادة التحجيم المشتركة هذه لا تغير الفهرس الذي يبلغ عنده الشرط العددي عددا معينا من الارقام لاول مرة. كما ان نسبة حدين متتاليين تظل متجهة نحو \(1/\varphi\)، ولذلك فالحلقة المطبعة هي النظير التكراري لقانون النمو نفسه.
تحتفظ تطبيقات C++ وPython وJava بحدين متتاليين من فيبوناتشي في صورة مقياسة، مع عداد لاس عشري وفهرس حالي. وهي تبدأ من \(F_1=F_2=1\)، ثم تتحرك بعلاقة التراجع المعتادة، وبعد كل خطوة تفحص الحد الذي صار حاليا بعد التحديث.
اذا تجاوز هذا الحد المخزن القيمة \(10\)، تقسم القيمتان معا على \(10\) ويزاد عداد الاس بمقدار واحد. وبما ان العامل نفسه يطبق على الحدين معا، تبقى علاقة التراجع محفوظة حتى مع وجود مقياس مشترك، ولذلك يظل التحديث التالي متناسبا مع متتالية فيبوناتشي الحقيقية.
تتوقف الحلقة عندما يبلغ عداد الاس القيمة \(D\) لاول مرة. وعندها يكون الفهرس الحالي هو بالضبط اول فهرس يملك فيه عدد فيبوناتشي \(D\) رقما. وتتحقق التطبيقات من ذلك عند نقاط الفحص \(D=2 \mapsto 7\) و\(D=3 \mapsto 12\) و\(D=1000 \mapsto 4782\).
لنفترض ان \(t\) هو الفهرس المطلوب. تنفذ الحلقة المطبعة تحديثا واحدا ذا كلفة ثابتة في كل خطوة من خطوات فيبوناتشي، ولذلك يكون زمن التنفيذ \(O(t)\). وبما ان عدد ارقام اعداد فيبوناتشي ينمو خطيا مع الفهرس، فهذا يكافئ ايضا \(O(D)\) بالنسبة الى عتبة الارقام المطلوبة.
اما استهلاك الذاكرة فيبقى \(O(1)\)، لان المخزن هو حدان مقياسان فقط مع عداد اس وفهرس. وفي هدف Project Euler هنا لا يتجاوز العمل 4782 تكرارا، ولذا تبقى الطريقة عملية وفورية تقريبا من غير حاجة الى اعداد صحيحة ضخمة ولا الى صيغة لوغاريتمية مباشرة.