The problem asks for the first Fibonacci index \(k\) such that the first nine digits of \(F_k\) and the last nine digits of \(F_k\) are both 1-9 pandigital. In other words, each of those 9-digit blocks must contain every digit from 1 through 9 exactly once, with no zero and no repetition.
The obstacle is scale. By the time the answer appears, the Fibonacci number itself has tens of thousands of digits, so constructing it exactly at every step would be wasteful. The implementations therefore split the question into two smaller numerical views of the same sequence: the tail is handled exactly with modular arithmetic, while the head is reconstructed from logarithms.
Let the Fibonacci sequence be defined by \(F_1=1\), \(F_2=1\), and \(F_n=F_{n-1}+F_{n-2}\) for \(n \ge 3\). The search condition is naturally the conjunction of two tests on the same index \(n\): one test on \(F_n \bmod 10^9\), and one test on the leading decimal digits of \(F_n\).
If the last nine digits are all that matter, then the entire problem lives modulo \(10^9\). If the first nine digits are all that matter, then only the decimal order of magnitude and mantissa matter. Those two facts let us avoid big integers in the main loop.
The key point is that the Fibonacci recurrence survives reduction modulo any integer:
$$F_n \equiv F_{n-1}+F_{n-2} \pmod{10^9}.$$
At the same time, the size of \(F_n\) is controlled by Binet's formula, which makes the leading digits accessible through logarithms.
Maintain two consecutive residues modulo \(10^9\). If at some moment they represent \(F_{n-2} \bmod 10^9\) and \(F_{n-1} \bmod 10^9\), then one update produces \(F_n \bmod 10^9\). This invariant stays true for the entire scan, so the last nine digits are always known exactly, even though the full integer is enormous.
A 9-digit block is 1-9 pandigital precisely when its digits are the set \(\{1,2,\dots,9\}\). The C++, Python, and Java implementations all enforce the same condition, either by extracting digits and marking them or by checking a 9-character decimal string. A useful checkpoint is
$$F_{541}\equiv 839725641 \pmod{10^9},$$
and the block \(839725641\) is indeed pandigital. This shows that the trailing test can succeed much earlier than the full two-sided condition.
For the front of the number, the implementations use
$$F_n=\frac{\varphi^n-\psi^n}{\sqrt5},\qquad \varphi=\frac{1+\sqrt5}{2},\qquad \psi=\frac{1-\sqrt5}{2}.$$
Because \(|\psi| \lt 1\), the term \(\psi^n\) decays exponentially. For the indices relevant here, it is far too small to affect the first nine digits, so \(F_n\) is governed by \(\varphi^n/\sqrt5\).
Take base-10 logarithms and define
$$x=n\log_{10}\varphi-\log_{10}\sqrt5.$$
Write \(x=m+f\) with integer part \(m=\lfloor x \rfloor\) and fractional part \(0 \le f \lt 1\). Then
$$F_n \approx 10^x = 10^{m+f}=10^m\cdot 10^f.$$
The factor \(10^m\) determines the number of digits, while \(10^f\) determines the leading significand. Therefore the first nine digits are
$$\left\lfloor 10^{f+8}\right\rfloor.$$
This is the central formula used by all three implementations for the head of \(F_n\).
A concrete checkpoint from the implementations is \(n=2749\). For this index,
$$x=2749\log_{10}\varphi-\log_{10}\sqrt5 \approx 574.157538045.$$
So \(f \approx 0.157538045\), and
$$\left\lfloor 10^{f+8}\right\rfloor=\left\lfloor 10^{8.157538045}\right\rfloor=143726895.$$
The block \(143726895\) is 1-9 pandigital, so \(F_{2749}\) passes the leading-digit test. It does not yet solve the full problem because the trailing block at the same index is not pandigital. The final answer is the first index where both checks succeed simultaneously.
The tail test is exact and very cheap: one modular addition plus a 9-digit scan. The head test is also \(O(1)\), but it uses floating-point logarithms, so it is sensible to apply it only after the tail has already passed. In practice, trailing-pandigital Fibonacci residues are rare, so most indices are rejected before any logarithmic work is needed.
The numerical approximation is stable here because the first nine digits depend only on the fractional part of \(x\), and double or long-double precision is more than sufficient for indices in the few-hundred-thousand range. One implementation adds a tiny safeguard before converting \(10^{f+8}\) to an integer, protecting against boundary effects when floating-point rounding lands extremely close to \(10^9\).
The C++, Python, and Java implementations perform a forward scan through Fibonacci indices starting at \(n=3\). At each iteration they update two consecutive Fibonacci values modulo \(10^9\), so the running state always represents adjacent terms of the recurrence reduced to their last nine digits.
Next comes the pandigital filter on the trailing block. The string-based implementations format the residue as a 9-digit decimal block so that leading zeros are preserved before checking the digit set. The integer-based implementation extracts digits numerically and accepts only values with exactly nine digits, no zero, and no repetition. Those are two representations of the same mathematical test.
Whenever the trailing block passes, the implementation computes the leading block from the logarithmic formula. It then applies the same pandigital condition to that 9-digit prefix. As soon as both tests succeed for the same index, the scan terminates and returns the first valid index, which is \(k=329468\).
If the first successful index is \(k\), the algorithm performs \(k-2\) Fibonacci updates. Every iteration uses constant time: one modular addition, one 9-digit pandigital check, and only occasionally one logarithm-based leading-digit computation. Hence the total running time is \(O(k)\).
For this problem the search stops at \(k=329468\), so the real workload is only a few hundred thousand iterations. The memory usage is \(O(1)\), since the scan stores only two current Fibonacci residues, a handful of floating-point constants, and small temporary digit-tracking state.
Gesucht ist der erste Fibonacci-Index \(k\), für den sowohl die ersten neun Ziffern von \(F_k\) als auch die letzten neun Ziffern von \(F_k\) 1-9-pandigital sind. Jeder dieser 9-stelligen Blöcke muss also jede Ziffer von 1 bis 9 genau einmal enthalten; Nullen und Wiederholungen sind verboten.
Die Schwierigkeit liegt in der Größe der Zahlen. Wenn die Lösung erreicht wird, hat \(F_k\) bereits zehntausende Stellen. Deshalb bauen die Implementierungen nicht jedes Fibonacci-Zahl exakt auf, sondern zerlegen die Aufgabe in zwei numerisch viel kleinere Teilprobleme: den Endblock modulo \(10^9\) und den Anfangsblock über Logarithmen.
Die Fibonacci-Folge sei durch \(F_1=1\), \(F_2=1\) und \(F_n=F_{n-1}+F_{n-2}\) für \(n \ge 3\) definiert. Die Suchbedingung besteht dann aus zwei unabhängigen Prüfungen für denselben Index \(n\): einer exakten Prüfung der letzten neun Stellen und einer rekonstruierten Prüfung der ersten neun Stellen.
Für die letzten neun Ziffern genügt die Folge modulo \(10^9\). Für die ersten neun Ziffern genügt es, die Größenordnung und die führende Dezimalmantisse von \(F_n\) zu kennen. Genau diese Trennung macht den Algorithmus so leichtgewichtig.
Die Rekurrenz bleibt nämlich unter Modulo-Ersetzung erhalten:
$$F_n \equiv F_{n-1}+F_{n-2} \pmod{10^9}.$$
Außerdem beschreibt die geschlossene Form der Fibonacci-Zahlen das Wachstum von \(F_n\) so präzise, dass die führenden Stellen aus einem Logarithmus gewonnen werden können.
Man speichert stets zwei aufeinanderfolgende Reste modulo \(10^9\). Wenn diese gerade \(F_{n-2} \bmod 10^9\) und \(F_{n-1} \bmod 10^9\) darstellen, liefert ein einziger Update-Schritt sofort \(F_n \bmod 10^9\). Diese Invariante bleibt während des gesamten Durchlaufs gültig, sodass der Endblock immer exakt bekannt ist.
Ein 9-stelliger Block ist genau dann 1-9-pandigital, wenn seine Ziffernmenge \(\{1,2,\dots,9\}\) ist. Die C++-, Python- und Java-Implementierungen testen dieselbe Bedingung nur in unterschiedlicher Darstellung, entweder über Ziffernextraktion oder über einen 9-stelligen String. Ein nützlicher Kontrollpunkt ist
$$F_{541}\equiv 839725641 \pmod{10^9},$$
und der Block \(839725641\) ist tatsächlich pandigital. Damit sieht man sofort, dass die Endbedingung deutlich früher eintreten kann als die vollständige doppelte Bedingung.
Für den Anfang der Zahl verwenden die Implementierungen die Formel
$$F_n=\frac{\varphi^n-\psi^n}{\sqrt5},\qquad \varphi=\frac{1+\sqrt5}{2},\qquad \psi=\frac{1-\sqrt5}{2}.$$
Da \(|\psi| \lt 1\), verschwindet der Beitrag \(\psi^n\) exponentiell schnell. Für die hier relevanten Indizes ist er viel zu klein, um die ersten neun Ziffern zu beeinflussen, also wird \(F_n\) effektiv von \(\varphi^n/\sqrt5\) bestimmt.
Mit dem Zehnerlogarithmus definiert man
$$x=n\log_{10}\varphi-\log_{10}\sqrt5.$$
Schreibt man \(x=m+f\) mit \(m=\lfloor x \rfloor\) und \(0 \le f \lt 1\), dann gilt näherungsweise
$$F_n \approx 10^x = 10^{m+f}=10^m\cdot 10^f.$$
Der Faktor \(10^m\) legt die Stellenzahl fest; \(10^f\) bestimmt die führende Mantisse. Deshalb erhält man die ersten neun Ziffern aus
$$\left\lfloor 10^{f+8}\right\rfloor.$$
Ein konkreter Kontrollpunkt der Implementierungen ist \(n=2749\). Für diesen Index gilt
$$x=2749\log_{10}\varphi-\log_{10}\sqrt5 \approx 574.157538045.$$
Also ist \(f \approx 0.157538045\), und damit
$$\left\lfloor 10^{f+8}\right\rfloor=\left\lfloor 10^{8.157538045}\right\rfloor=143726895.$$
Der Block \(143726895\) ist 1-9-pandigital. Damit besteht \(F_{2749}\) die Prüfung der führenden Stellen. Zur endgültigen Lösung reicht das aber noch nicht, weil die letzten neun Stellen an diesem Index nicht pandigital sind.
Die Endprüfung ist exakt und extrem billig: eine modulare Addition und ein kurzer Zifferntest. Die Anfangsprüfung ist ebenfalls \(O(1)\), benutzt aber Fließkomma-Logarithmen. Deshalb ist es sinnvoll, sie nur dann auszuführen, wenn der Endblock bereits bestanden hat. In der Praxis fallen fast alle Indizes schon an der letzten-neun-Ziffern-Prüfung heraus.
Numerisch ist das Verfahren stabil, weil nur der Bruchteil von \(x\) gebraucht wird und die erforderliche Genauigkeit für Indizes im Bereich einiger hunderttausend locker innerhalb von Double- oder Long-Double-Präzision liegt. Eine Implementierung ergänzt vor der Umwandlung von \(10^{f+8}\) in eine ganze Zahl sogar noch eine winzige Schutzkorrektur gegen Grenzfälle direkt an der Schwelle zu \(10^9\).
Die C++-, Python- und Java-Implementierungen laufen die Fibonacci-Indizes ab \(n=3\) vorwärts durch. In jeder Iteration aktualisieren sie zwei aufeinanderfolgende Fibonacci-Werte modulo \(10^9\). Die Schleifeninvariante lautet also: Der aktuelle Zustand repräsentiert immer zwei benachbarte Folgenglieder in ihren letzten neun Stellen.
Danach folgt der Pandigital-Filter für den Endblock. Die stringbasierten Versionen formatieren den Rest als 9-stelligen Dezimalblock, damit auch führende Nullen im Endblock korrekt berücksichtigt werden. Die integerbasierte Version extrahiert die Ziffern direkt und akzeptiert nur Werte mit genau neun Stellen, ohne Null und ohne Wiederholung. Mathematisch sind diese Tests äquivalent.
Nur wenn die letzten neun Ziffern bestehen, berechnet die Implementierung den Anfangsblock mit der Logarithmusformel und testet dort dieselbe Pandigital-Bedingung. Sobald beide Prüfungen am selben Index erfolgreich sind, endet der Durchlauf und liefert den ersten gültigen Index \(k=329468\).
Ist \(k\) der erste erfolgreiche Index, dann führt der Algorithmus \(k-2\) Fibonacci-Updates aus. Jede Iteration benötigt konstante Zeit: eine modulare Addition, einen Test auf neun Ziffern und nur gelegentlich eine logarithmische Berechnung für den Anfangsblock. Insgesamt ergibt das \(O(k)\) Laufzeit.
In diesem Problem stoppt die Suche bei \(k=329468\), also nach nur einigen hunderttausend Schritten. Der Speicherverbrauch ist \(O(1)\), weil nur zwei aktuelle Fibonacci-Reste, einige Fließkomma-Konstanten und sehr kleine Hilfsstrukturen für Ziffernmarkierungen gehalten werden.
Aranan şey, \(F_k\) Fibonacci sayısının hem ilk dokuz basamağı hem de son dokuz basamağı 1-9 pandigital olan ilk indeks \(k\)'dır. Yani bu iki 9 basamaklı blokta da 1'den 9'a kadar her rakam tam bir kez görünmeli; sıfır olmamalı ve tekrar bulunmamalıdır.
Zorluk sayıların çok hızlı büyümesidir. Çözüm indeksine gelindiğinde \(F_k\) on binlerce basamaklıdır. Bu yüzden uygulamalar her adımda tam Fibonacci sayısını üretmek yerine problemi iki ayrı sayısal görünüme ayırır: son dokuz basamak modüler aritmetikle tam olarak izlenir, ilk dokuz basamak ise logaritmalarla çıkarılır.
Fibonacci dizisini \(F_1=1\), \(F_2=1\) ve \(n \ge 3\) için \(F_n=F_{n-1}+F_{n-2}\) ile tanımlayalım. O zaman aranan koşul, aynı \(n\) için iki ayrı testten oluşur: \(F_n \bmod 10^9\) üzerinden son dokuz basamak testi ve \(F_n\)'nin başındaki dokuz basamağı veren logaritmik test.
Yalnızca son dokuz basamak önemliyse bütün problem \(10^9\) modunda yaşar. Yalnızca ilk dokuz basamak önemliyse, sayının tam değerine değil sadece ondalık büyüklüğüne ve öndeki mantissasına ihtiyaç vardır. Büyük tamsayıları ana döngüden çıkarmamızı sağlayan ayrım budur.
Fibonacci bağıntısı mod alma altında korunur:
$$F_n \equiv F_{n-1}+F_{n-2} \pmod{10^9}.$$
Aynı anda Binet formülü de \(F_n\)'nin büyümesini öyle iyi açıklar ki, öndeki basamaklar logaritmadan elde edilebilir.
Her an için \(10^9\) modunda ardışık iki Fibonacci kalanı tutulur. Eğer bunlar o anda \(F_{n-2} \bmod 10^9\) ve \(F_{n-1} \bmod 10^9\) ise, tek bir güncelleme ile \(F_n \bmod 10^9\) elde edilir. Bu değişmez tüm tarama boyunca korunduğu için, tam sayı devasa boyutlara ulaşsa bile son dokuz basamak eksiksiz olarak bilinir.
Bir 9 basamaklı blok ancak ve ancak rakam kümesi \(\{1,2,\dots,9\}\) ise 1-9 pandigitaldir. C++, Python ve Java uygulamaları aynı matematiksel testi farklı gösterimlerle yapar; biri rakamları sayısal olarak ayırır, diğerleri 9 karakterlik ondalık blok üzerinde çalışır. Faydalı bir ara kontrol noktası şudur:
$$F_{541}\equiv 839725641 \pmod{10^9}.$$
\(839725641\) bloğu pandigitaldir. Bu da son basamak koşulunun, çift taraflı tam koşuldan çok daha erken sağlanabildiğini gösterir.
Sayının baş tarafı için uygulamalar
$$F_n=\frac{\varphi^n-\psi^n}{\sqrt5},\qquad \varphi=\frac{1+\sqrt5}{2},\qquad \psi=\frac{1-\sqrt5}{2}$$
formülünü kullanır. \(|\psi| \lt 1\) olduğundan \(\psi^n\) terimi üssel olarak küçülür. Buradaki indeksler için bu terim ilk dokuz basamağı etkilemeyecek kadar küçüktür; dolayısıyla \(F_n\)'nin ön kısmını fiilen \(\varphi^n/\sqrt5\) belirler.
Taban 10 logaritması alınır ve
$$x=n\log_{10}\varphi-\log_{10}\sqrt5$$
tanımlanır. \(x=m+f\) olacak şekilde \(m=\lfloor x \rfloor\) ve \(0 \le f \lt 1\) yazılırsa
$$F_n \approx 10^x = 10^{m+f}=10^m\cdot 10^f$$
elde edilir. \(10^m\) terimi basamak sayısını, \(10^f\) ise öndeki anlamlı kısmı belirler. Bu yüzden ilk dokuz basamak
$$\left\lfloor 10^{f+8}\right\rfloor$$
formülüyle bulunur. Üç uygulamanın da baş basamaklar için kullandığı esas ifade budur.
Uygulamalardaki somut bir kontrol noktası \(n=2749\)'dur. Bu indeks için
$$x=2749\log_{10}\varphi-\log_{10}\sqrt5 \approx 574.157538045$$
olur. Dolayısıyla \(f \approx 0.157538045\) ve
$$\left\lfloor 10^{f+8}\right\rfloor=\left\lfloor 10^{8.157538045}\right\rfloor=143726895.$$
\(143726895\) bloğu 1-9 pandigitaldir; yani \(F_{2749}\) öndeki basamak testini geçer. Ancak aynı indeksteki son blok pandigital olmadığı için nihai cevap bu değildir. Asıl çözüm, iki testin de aynı anda geçtiği ilk indekstir.
Son basamak testi tam ve ucuzdur: bir modüler toplama ve kısa bir 9 rakam taraması yeterlidir. İlk basamak testi de \(O(1)\)'dir fakat kayan noktalı logaritmalara dayanır. Bu yüzden onu yalnızca son blok testi geçildiğinde uygulamak en doğru stratejidir. Pratikte son dokuz basamağı pandigital olan kalıntılar çok seyrek çıktığı için çoğu indeks logaritma hesabına hiç ulaşmaz.
Sayısal yaklaşım burada kararlıdır; çünkü gereken tek şey \(x\)'in kesirli kısmıdır ve birkaç yüz bin mertebesindeki indeksler için double ya da long double hassasiyeti rahatça yeterlidir. Bir uygulama ayrıca \(10^{f+8}\) değerini tam sayıya dönüştürmeden önce çok küçük bir güvenlik düzeltmesi ekleyerek, hesap sonucu \(10^9\) sınırına aşırı yakın olduğunda oluşabilecek yuvarlama etkilerini bastırır.
C++, Python ve Java uygulamaları \(n=3\)'ten başlayarak Fibonacci indekslerini ileri doğru tarar. Her adımda \(10^9\) modunda ardışık iki Fibonacci değeri güncellenir; böylece döngü durumu her zaman bağıntının komşu iki terimini son dokuz basamak seviyesinde temsil eder.
Ardından son blok için pandigital filtre uygulanır. String tabanlı sürümler, kalanı 9 karakterlik bir ondalık blok olarak biçimlendirip öndeki sıfırları korur. Sayısal sürüm ise rakamları tek tek çıkarır ve yalnızca tam 9 basamaklı, sıfırsız ve tekrarsız değerleri kabul eder. İki yaklaşımın yaptığı matematik aynıdır.
Son dokuz basamak testi geçerse bu kez logaritma formülüyle ilk dokuz basamak hesaplanır ve aynı pandigital koşulu ona uygulanır. Aynı indeks için iki test de başarılı olduğunda tarama durur ve ilk geçerli indeks olan \(k=329468\) döndürülür.
İlk başarılı indeks \(k\) ise algoritma toplam \(k-2\) adet Fibonacci güncellemesi yapar. Her iterasyon sabit zamanda çalışır: bir modüler toplama, 9 rakamlık bir test ve yalnızca nadiren bir logaritma tabanlı ilk-basamak hesabı vardır. Bu yüzden toplam süre \(O(k)\)'dır.
Bu problemde arama \(k=329468\)'de biter; yani gerçek iş yükü sadece birkaç yüz bin adımdır. Bellek kullanımı \(O(1)\)'dir; çünkü yalnızca iki güncel Fibonacci kalanı, birkaç kayan nokta sabiti ve çok küçük rakam izleme yardımcıları tutulur.
Hay que encontrar el primer índice \(k\) de Fibonacci tal que los primeros nueve dígitos de \(F_k\) y los últimos nueve dígitos de \(F_k\) sean ambos pandigitales del 1 al 9. Eso significa que cada uno de esos bloques de 9 dígitos debe contener exactamente una vez cada cifra entre 1 y 9, sin ceros ni repeticiones.
La dificultad real es el tamaño de los números. Cuando aparece la solución, \(F_k\) ya tiene decenas de miles de dígitos. Por eso las implementaciones no construyen el entero completo en cada paso, sino que separan el problema en dos observaciones numéricas mucho más baratas: la cola se sigue exactamente módulo \(10^9\), y la cabecera se reconstruye mediante logaritmos.
La sucesión de Fibonacci queda definida por \(F_1=1\), \(F_2=1\) y \(F_n=F_{n-1}+F_{n-2}\) para \(n \ge 3\). La condición buscada se descompone entonces en dos pruebas sobre el mismo índice \(n\): una prueba exacta para los últimos nueve dígitos y otra prueba aproximada pero fiable para los primeros nueve.
Si solo importan los últimos nueve dígitos, toda la información relevante vive en \(F_n \bmod 10^9\). Si solo importan los primeros nueve, basta conocer el orden de magnitud decimal y la mantisa inicial. Esa separación es lo que evita trabajar con enteros gigantes durante el bucle principal.
La recurrencia de Fibonacci sigue siendo válida después de reducir módulo \(10^9\):
$$F_n \equiv F_{n-1}+F_{n-2} \pmod{10^9}.$$
Por otro lado, la fórmula cerrada de Fibonacci describe el crecimiento de \(F_n\) con suficiente precisión como para recuperar sus primeros dígitos a partir de logaritmos decimales.
Se mantienen dos residuos consecutivos módulo \(10^9\). Si en un momento dado representan \(F_{n-2} \bmod 10^9\) y \(F_{n-1} \bmod 10^9\), una sola actualización produce \(F_n \bmod 10^9\). Esta invariante se conserva durante todo el recorrido, de modo que la cola de nueve dígitos siempre se conoce exactamente aunque el valor completo de \(F_n\) sea inmenso.
Un bloque de 9 dígitos es pandigital del 1 al 9 exactamente cuando su conjunto de cifras es \(\{1,2,\dots,9\}\). Las implementaciones en C++, Python y Java verifican esa misma propiedad, ya sea extrayendo cifras numéricamente o comprobando un bloque decimal de longitud 9. Un punto de control útil es
$$F_{541}\equiv 839725641 \pmod{10^9},$$
y el bloque \(839725641\) sí es pandigital. Eso muestra que la condición sobre la cola puede cumplirse bastante antes que la condición completa en ambos extremos.
Para la parte inicial del número, las implementaciones usan
$$F_n=\frac{\varphi^n-\psi^n}{\sqrt5},\qquad \varphi=\frac{1+\sqrt5}{2},\qquad \psi=\frac{1-\sqrt5}{2}.$$
Como \(|\psi| \lt 1\), el término \(\psi^n\) decrece exponencialmente. En los índices que nos interesan es demasiado pequeño para alterar los primeros nueve dígitos, así que el tamaño de \(F_n\) viene dominado por \(\varphi^n/\sqrt5\).
Tomando logaritmos en base 10 definimos
$$x=n\log_{10}\varphi-\log_{10}\sqrt5.$$
Si escribimos \(x=m+f\), con \(m=\lfloor x \rfloor\) y \(0 \le f \lt 1\), entonces
$$F_n \approx 10^x = 10^{m+f}=10^m\cdot 10^f.$$
El factor \(10^m\) fija la cantidad de dígitos, mientras que \(10^f\) determina la mantisa inicial. Por eso los primeros nueve dígitos se obtienen con
$$\left\lfloor 10^{f+8}\right\rfloor.$$
Esa es la fórmula central que usan las tres implementaciones para la cabecera de \(F_n\).
Un punto de control concreto de las implementaciones es \(n=2749\). Para ese índice,
$$x=2749\log_{10}\varphi-\log_{10}\sqrt5 \approx 574.157538045.$$
Así, \(f \approx 0.157538045\), y por tanto
$$\left\lfloor 10^{f+8}\right\rfloor=\left\lfloor 10^{8.157538045}\right\rfloor=143726895.$$
El bloque \(143726895\) es pandigital del 1 al 9, de modo que \(F_{2749}\) supera la prueba de los primeros nueve dígitos. Aun así no resuelve el problema completo, porque en ese mismo índice la cola no es pandigital. La respuesta final es el primer índice donde ambas pruebas coinciden.
La comprobación de la cola es exacta y muy barata: una suma modular y una inspección de nueve cifras. La comprobación de la cabecera también es \(O(1)\), pero depende de logaritmos en coma flotante. Por eso conviene ejecutarla solo después de que la cola haya pasado. En la práctica, los residuos pandigitales en la cola son raros, así que casi todos los índices se descartan antes de llegar al cálculo logarítmico.
La aproximación numérica es estable porque solo depende de la parte fraccionaria de \(x\), y la precisión de double o long double basta de sobra para índices del orden de unos cientos de miles. Una de las implementaciones añade además una corrección diminuta antes de convertir \(10^{f+8}\) a entero, para evitar efectos de redondeo cuando el valor cae extremadamente cerca del umbral \(10^9\).
Las implementaciones en C++, Python y Java recorren los índices de Fibonacci hacia adelante a partir de \(n=3\). En cada iteración actualizan dos valores consecutivos de Fibonacci módulo \(10^9\), de modo que el estado del bucle siempre representa dos términos adyacentes de la recurrencia vistos a través de sus últimos nueve dígitos.
Después aplican el filtro pandigital sobre la cola. Las versiones basadas en cadenas formatean el residuo como un bloque decimal de 9 caracteres para conservar ceros a la izquierda cuando sean necesarios. La versión basada en enteros extrae las cifras numéricamente y solo acepta valores con exactamente nueve dígitos, sin cero y sin repetición. Son dos maneras de implementar la misma condición matemática.
Cuando la cola supera el filtro, la implementación calcula la cabecera mediante la fórmula logarítmica y vuelve a aplicar la condición pandigital. En cuanto ambas pruebas tienen éxito para el mismo índice, el proceso termina y devuelve el primer índice válido, \(k=329468\).
Si \(k\) es el primer índice exitoso, el algoritmo realiza \(k-2\) actualizaciones de Fibonacci. Cada iteración cuesta tiempo constante: una suma modular, una comprobación pandigital sobre nueve cifras y, solo de vez en cuando, un cálculo logarítmico para la cabecera. Por tanto, el tiempo total es \(O(k)\).
En este problema la búsqueda termina en \(k=329468\), así que el trabajo real es solo de unos pocos cientos de miles de iteraciones. El uso de memoria es \(O(1)\), porque únicamente se guardan dos residuos actuales de Fibonacci, unas pocas constantes en coma flotante y estructuras diminutas para marcar cifras.
题目要求找到最小的 Fibonacci 下标 \(k\)，使得 \(F_k\) 的前九位和后九位都恰好由 1 到 9 这九个数字各出现一次组成。也就是说，这两个 9 位数字块都不能出现 0，也不能出现重复数字。
真正的难点不在递推本身，而在数字规模。到答案出现时，\(F_k\) 已经有数万位，若每一步都把整个整数精确算出来，成本完全没有必要。因此实现采用两个互补的数值视角：末尾九位通过模 \(10^9\) 精确维护，开头九位则通过对数恢复出来。
设 Fibonacci 数列满足 \(F_1=1\)、\(F_2=1\)，并且对 \(n \ge 3\) 有 \(F_n=F_{n-1}+F_{n-2}\)。那么题目的判定条件可以自然分成同一个下标 \(n\) 上的两部分：一部分检查 \(F_n\) 的最后九位，另一部分检查 \(F_n\) 的最前九位。
如果只关心最后九位，那么全部信息都包含在 \(F_n \bmod 10^9\) 中；如果只关心最前九位，那么只需要知道 \(F_n\) 的十进制数量级和前导有效数字。这种拆分使主循环完全不需要维护大整数。
首先，Fibonacci 递推在模运算下仍然成立：
$$F_n \equiv F_{n-1}+F_{n-2} \pmod{10^9}.$$
其次，Fibonacci 数的闭式公式可以非常准确地刻画它的增长速度，因此首部数字可以从对数中直接提取。
实现始终维护两个相邻的模 \(10^9\) 余数。如果当前它们分别代表 \(F_{n-2} \bmod 10^9\) 和 \(F_{n-1} \bmod 10^9\)，那么一次更新就能得到 \(F_n \bmod 10^9\)。这个不变量在整个扫描过程中始终成立，所以即使 \(F_n\) 本身已经极其巨大，末尾九位仍然是完全精确的。
一个 9 位数字块当且仅当其数字集合正好是 \(\{1,2,\dots,9\}\) 时，才是 1-9 pandigital。C++、Python 和 Java 实现都在做这件事，只是表现形式不同：有的直接逐位提取并标记，有的把结果视为长度为 9 的十进制字符串。一个很有用的检查点是
$$F_{541}\equiv 839725641 \pmod{10^9},$$
而 \(839725641\) 确实是 pandigital 的。这说明“尾部通过”会比“首尾同时通过”更早出现。
对首部数字，实现使用的是
$$F_n=\frac{\varphi^n-\psi^n}{\sqrt5},\qquad \varphi=\frac{1+\sqrt5}{2},\qquad \psi=\frac{1-\sqrt5}{2}.$$
由于 \(|\psi| \lt 1\)，项 \(\psi^n\) 会指数级衰减。对于本题涉及的下标范围，它小到不足以影响前九位，因此 \(F_n\) 的数量级和前导数字基本完全由 \(\varphi^n/\sqrt5\) 决定。
取以 10 为底的对数，定义
$$x=n\log_{10}\varphi-\log_{10}\sqrt5.$$
把它写成 \(x=m+f\)，其中 \(m=\lfloor x \rfloor\)，并且 \(0 \le f \lt 1\)。于是有近似关系
$$F_n \approx 10^x = 10^{m+f}=10^m\cdot 10^f.$$
\(10^m\) 决定了总位数，而 \(10^f\) 决定了最前面的有效数字。于是前九位可以由下式直接给出：
$$\left\lfloor 10^{f+8}\right\rfloor.$$
这正是三份实现求首部九位时共同使用的核心公式。
实现里有一个非常好的首部检查点：\(n=2749\)。这时
$$x=2749\log_{10}\varphi-\log_{10}\sqrt5 \approx 574.157538045.$$
因此 \(f \approx 0.157538045\)，从而
$$\left\lfloor 10^{f+8}\right\rfloor=\left\lfloor 10^{8.157538045}\right\rfloor=143726895.$$
\(143726895\) 也是一个 1-9 pandigital 的 9 位块，所以 \(F_{2749}\) 通过了前九位测试。但它并不是最终答案，因为同一下标的后九位并不满足 pandigital 条件。真正的答案必须是首尾两项测试同时通过的最小下标。
尾部测试是完全精确的，而且代价极低，只需要一次模加法和一次 9 位检查。首部测试虽然同样是 \(O(1)\)，但它依赖浮点对数，因此最合理的做法是先做尾部过滤，只有尾部通过时才去计算首部。在实际搜索中，尾部九位恰好 pandigital 的下标非常稀少，所以绝大多数 \(n\) 在这一步就被筛掉了。
这种浮点方法在本题中是稳定的，因为真正需要的是 \(x\) 的小数部分，而对几十万量级的下标来说，double 或 long double 的精度绰绰有余。还有一份实现会在把 \(10^{f+8}\) 转成整数之前加入一个极小的保护量，以防止结果恰好落在接近 \(10^9\) 的边界附近时出现舍入扰动。
C++、Python 和 Java 实现都从 \(n=3\) 开始顺序扫描 Fibonacci 下标。每轮迭代先更新两个相邻的 Fibonacci 模 \(10^9\) 余数，因此循环状态始终表示递推式中相邻两项的“后九位视图”。
随后程序对尾部 9 位做 pandigital 过滤。基于字符串的实现会把余数格式化为长度恰好为 9 的十进制块，这样尾部中的前导零不会丢失；基于整数的实现则直接逐位提取，并要求必须恰好有九位、不能含 0、不能重复。这只是实现方式不同，数学判定完全一样。
如果尾部通过，程序就用上面的对数公式计算前九位，再对这一块重复同样的 pandigital 检查。一旦某个下标同时通过两项测试，扫描立即停止，并返回最小有效下标 \(k=329468\)。
如果第一个成功的下标是 \(k\)，那么算法总共进行了 \(k-2\) 次 Fibonacci 更新。每一轮都是常数时间：一次模加法、一次 9 位判定，外加极少数情况下的一次对数计算，因此总时间复杂度是 \(O(k)\)。
在本题中搜索停在 \(k=329468\)，所以真实工作量只是几十万轮。空间复杂度为 \(O(1)\)，因为程序只保存两个当前余数、少量浮点常数以及很小的数字标记结构。
Нужно найти наименьший индекс \(k\), для которого число Фибоначчи \(F_k\) имеет и первые девять цифр, и последние девять цифр пандигитальными по цифрам 1-9. Это означает, что в каждом из двух 9-значных блоков каждая цифра от 1 до 9 встречается ровно один раз, а нуля и повторов нет.
Главная трудность связана не с самой рекурсией, а с размером чисел. К моменту появления ответа \(F_k\) уже содержит десятки тысяч цифр, поэтому строить полное значение на каждом шаге бессмысленно. Реализации делят задачу на две существенно более дешевые части: хвост отслеживается точно по модулю \(10^9\), а голова восстанавливается через логарифмы.
Пусть последовательность Фибоначчи задана условиями \(F_1=1\), \(F_2=1\) и \(F_n=F_{n-1}+F_{n-2}\) при \(n \ge 3\). Тогда искомое условие естественно распадается на две проверки для одного и того же индекса \(n\): точную проверку последних девяти цифр и надежную проверку первых девяти цифр.
Если нас интересуют только последние девять цифр, вся нужная информация содержится в \(F_n \bmod 10^9\). Если важны только первые девять цифр, достаточно знать десятичный порядок величины и ведущую мантиссу числа. Именно это разделение позволяет полностью убрать большие целые из основного цикла.
Рекуррентное соотношение Фибоначчи сохраняется после взятия по модулю:
$$F_n \equiv F_{n-1}+F_{n-2} \pmod{10^9}.$$
С другой стороны, замкнутая формула для \(F_n\) настолько хорошо описывает рост последовательности, что первые цифры можно извлечь из десятичного логарифма.
В процессе поиска хранятся два соседних остатка по модулю \(10^9\). Если в некоторый момент они равны \(F_{n-2} \bmod 10^9\) и \(F_{n-1} \bmod 10^9\), то одно обновление сразу дает \(F_n \bmod 10^9\). Этот инвариант сохраняется на всем протяжении прохода, поэтому хвост из девяти цифр известен точно, хотя само число \(F_n\) уже огромно.
9-значный блок является пандигитальным по цифрам 1-9 тогда и только тогда, когда множество его цифр равно \(\{1,2,\dots,9\}\). Реализации на C++, Python и Java проверяют ровно это свойство, только в разных представлениях: либо через поразрядное извлечение, либо через строку длины 9. Полезная контрольная точка:
$$F_{541}\equiv 839725641 \pmod{10^9},$$
и блок \(839725641\) действительно пандигитален. Это показывает, что условие на хвост может выполниться намного раньше, чем полное двустороннее условие.
Для начала числа реализации используют формулу
$$F_n=\frac{\varphi^n-\psi^n}{\sqrt5},\qquad \varphi=\frac{1+\sqrt5}{2},\qquad \psi=\frac{1-\sqrt5}{2}.$$
Так как \(|\psi| \lt 1\), член \(\psi^n\) убывает экспоненциально. В диапазоне индексов этой задачи он слишком мал, чтобы повлиять на первые девять цифр, поэтому начальные цифры фактически определяются величиной \(\varphi^n/\sqrt5\).
Возьмем десятичный логарифм и обозначим
$$x=n\log_{10}\varphi-\log_{10}\sqrt5.$$
Пусть \(x=m+f\), где \(m=\lfloor x \rfloor\), а \(0 \le f \lt 1\). Тогда
$$F_n \approx 10^x = 10^{m+f}=10^m\cdot 10^f.$$
Множитель \(10^m\) задает число цифр, а \(10^f\) определяет ведущую значащую часть. Следовательно, первые девять цифр равны
$$\left\lfloor 10^{f+8}\right\rfloor.$$
Именно этой формулой все три реализации пользуются для вычисления начального 9-значного блока.
У реализаций есть очень удобная контрольная точка \(n=2749\). Для нее
$$x=2749\log_{10}\varphi-\log_{10}\sqrt5 \approx 574.157538045.$$
Значит, \(f \approx 0.157538045\), и потому
$$\left\lfloor 10^{f+8}\right\rfloor=\left\lfloor 10^{8.157538045}\right\rfloor=143726895.$$
Блок \(143726895\) является пандигитальным, так что \(F_{2749}\) проходит проверку по первым девяти цифрам. Но это еще не решение всей задачи, потому что последние девять цифр при том же индексе не пандигитальны. Нужен первый индекс, на котором выполняются обе проверки сразу.
Проверка хвоста точна и очень дешева: одна сумма по модулю и просмотр девяти цифр. Проверка головы тоже имеет стоимость \(O(1)\), но использует логарифмы с плавающей точкой. Поэтому разумно выполнять ее только после того, как хвост уже прошел фильтр. На практике пандигитальные хвосты встречаются редко, так что почти все индексы отсеиваются раньше.
Численная схема здесь устойчива, потому что нужны лишь дробная часть \(x\) и девять ведущих цифр, а точности double или long double вполне хватает для индексов порядка нескольких сотен тысяч. Одна из реализаций дополнительно вводит крошечную защитную поправку перед преобразованием \(10^{f+8}\) в целое, чтобы исключить граничные эффекты, если вычисление попало слишком близко к порогу \(10^9\).
Реализации на C++, Python и Java последовательно перебирают индексы Фибоначчи, начиная с \(n=3\). На каждом шаге обновляются два соседних значения Фибоначчи по модулю \(10^9\), так что состояние цикла всегда представляет два смежных члена рекуррентной последовательности в виде их последних девяти цифр.
Затем применяется пандигитальный фильтр к хвостовому блоку. Версии, работающие со строками, форматируют остаток как десятичный блок длины 9, чтобы не потерять ведущие нули внутри хвоста. Версия, работающая с целым числом, извлекает цифры напрямую и принимает только значения с ровно девятью цифрами, без нулей и повторов. Математически это один и тот же критерий.
Если хвост прошел проверку, код вычисляет головной блок по логарифмической формуле и проверяет его тем же пандигитальным условием. Как только обе проверки выполнены для одного индекса, перебор останавливается и возвращается первый подходящий индекс \(k=329468\).
Если первый успешный индекс равен \(k\), то алгоритм выполняет \(k-2\) обновлений Fibonacci. Каждая итерация работает за константное время: одна модульная сумма, одна проверка девяти цифр и лишь изредка одно логарифмическое вычисление для начала числа. Следовательно, общая временная сложность равна \(O(k)\).
В данной задаче поиск заканчивается на \(k=329468\), поэтому реальный объем работы составляет всего несколько сотен тысяч итераций. Память расходуется как \(O(1)\), потому что хранятся только два текущих остатка, несколько вещественных констант и очень маленькие структуры для отметки цифр.
المطلوب هو إيجاد أصغر فهرس \(k\) في متتالية فيبوناتشي بحيث تكون أول تسعة أرقام من \(F_k\) وآخر تسعة أرقام من \(F_k\) كلاهما شاملاً للأرقام من 1 إلى 9 مرة واحدة لكل رقم. أي إن كل كتلة من هاتين الكتلتين ذات الطول 9 يجب أن تحتوي الأرقام \(1,2,\dots,9\) بلا أصفار وبلا تكرار.
الصعوبة الحقيقية ليست في علاقة فيبوناتشي نفسها، بل في حجم الأعداد. عند الوصول إلى الجواب يكون \(F_k\) قد صار عددًا ذا عشرات الآلاف من الخانات، ولذلك لا جدوى من بناء العدد كاملًا في كل خطوة. لهذا تفصل التطبيقات المسألة إلى منظورين عدديين أبسط بكثير: الذيل يُتابَع بدقة modulo \(10^9\)، بينما المقدمة تُستخرج من اللوغاريتمات.
لنعرّف متتالية فيبوناتشي بالعلاقات \(F_1=1\)، \(F_2=1\)، و\(F_n=F_{n-1}+F_{n-2}\) عندما \(n \ge 3\). عندها يصبح الشرط المطلوب اختبارين مختلفين على الفهرس نفسه \(n\): اختبار دقيق لآخر تسعة أرقام، واختبار موثوق لأول تسعة أرقام.
إذا كانت آخر تسعة أرقام فقط هي المهمة، فكل المعلومات اللازمة موجودة في \(F_n \bmod 10^9\). وإذا كانت أول تسعة أرقام فقط هي المهمة، فنحن لا نحتاج القيمة الكاملة، بل نحتاج فقط رتبة العدد العشرية والجزء القيادي من تمثيله العشري. هذا الفصل هو ما يسمح بالتخلّص من الأعداد الصحيحة الضخمة داخل الحلقة الرئيسية.
علاقة فيبوناتشي تبقى صحيحة بعد أخذ باقي القسمة:
$$F_n \equiv F_{n-1}+F_{n-2} \pmod{10^9}.$$
وفي الوقت نفسه تصف الصيغة المغلقة لنمو \(F_n\) الحجم بدقة كافية بحيث يمكن استرجاع الأرقام الأولى من اللوغاريتم.
يتم الاحتفاظ دائمًا بباقيين متتاليين modulo \(10^9\). فإذا كانا في لحظة ما يمثلان \(F_{n-2} \bmod 10^9\) و\(F_{n-1} \bmod 10^9\)، فإن تحديثًا واحدًا ينتج \(F_n \bmod 10^9\). هذه invariant تبقى صحيحة طوال المسح، ولذلك تكون آخر تسعة أرقام معروفة بدقة تامة مهما بلغ حجم \(F_n\).
الكتلة ذات 9 خانات تكون pandigital من 1 إلى 9 إذا وفقط إذا كان مجموع أرقامها هو بالضبط \(\{1,2,\dots,9\}\). تطبّق نسخ C++ وPython وJava هذا الاختبار نفسه، إمّا باستخراج الأرقام عدديًا أو بفحص سلسلة عشرية طولها 9. ومن نقاط التحقق المفيدة:
$$F_{541}\equiv 839725641 \pmod{10^9},$$
والكتلة \(839725641\) فعلًا pandigital. هذا يوضح أن شرط الذيل يمكن أن يتحقق قبل الشرط الكامل على البداية والنهاية معًا.
من أجل مقدمة العدد تستخدم التطبيقات الصيغة
$$F_n=\frac{\varphi^n-\psi^n}{\sqrt5},\qquad \varphi=\frac{1+\sqrt5}{2},\qquad \psi=\frac{1-\sqrt5}{2}.$$
بما أن \(|\psi| \lt 1\)، فإن الحد \(\psi^n\) يتضاءل أسيًا. وفي المجال الذي نهتم به في هذه المسألة يكون صغيرًا جدًا إلى حد لا يمكنه تغيير أول تسعة أرقام، ولذلك تتحدد المقدمة فعليًا بواسطة \(\varphi^n/\sqrt5\).
نأخذ اللوغاريتم العشري ونعرّف
$$x=n\log_{10}\varphi-\log_{10}\sqrt5.$$
اكتب \(x=m+f\) حيث \(m=\lfloor x \rfloor\) و\(0 \le f \lt 1\). عندئذٍ
$$F_n \approx 10^x = 10^{m+f}=10^m\cdot 10^f.$$
العامل \(10^m\) يحدد عدد الخانات، بينما \(10^f\) يحدد المانتيسا القيادية. لذلك فإن أول تسعة أرقام تُستخرج من
$$\left\lfloor 10^{f+8}\right\rfloor.$$
وهذه هي الصيغة الأساسية التي تعتمدها التطبيقات الثلاثة لحساب مقدمة \(F_n\).
هناك نقطة تحقق واضحة في التطبيقات عند \(n=2749\). في هذه الحالة
$$x=2749\log_{10}\varphi-\log_{10}\sqrt5 \approx 574.157538045.$$
إذن \(f \approx 0.157538045\)، ومن ثم
$$\left\lfloor 10^{f+8}\right\rfloor=\left\lfloor 10^{8.157538045}\right\rfloor=143726895.$$
والكتلة \(143726895\) pandigital من 1 إلى 9، لذلك ينجح \(F_{2749}\) في اختبار البداية. لكنه ليس الجواب النهائي، لأن آخر تسعة أرقام عند الفهرس نفسه ليست pandigital. المطلوب هو أول فهرس ينجح فيه الاختباران معًا.
اختبار الذيل دقيق ورخيص جدًا: جمع واحد modulo \(10^9\) ثم فحص تسع خانات. أما اختبار المقدمة فهو أيضًا \(O(1)\)، لكنه يعتمد على لوغاريتمات عددية عائمة. لذلك من الطبيعي أن يُستخدم فقط بعد نجاح اختبار الذيل. عمليًا، الحالات التي تكون فيها آخر تسعة أرقام pandigital نادرة، ولهذا تُرفض أغلب الفهارس قبل أي حساب لوغاريتمي.
الطريقة العددية مستقرة هنا لأن المطلوب في النهاية هو الجزء الكسري من \(x\)، ودقة double أو long double كافية تمامًا لفهارس من رتبة مئات الآلاف. كما أن إحدى التطبيقات تضيف تصحيحًا صغيرًا جدًا قبل تحويل \(10^{f+8}\) إلى عدد صحيح، حمايةً من حالات الحافة عندما تقع النتيجة قريبًا جدًا من \(10^9\).
تنفّذ تطبيقات C++ وPython وJava مسحًا تصاعديًا لفهارس فيبوناتشي بدءًا من \(n=3\). في كل دورة يتم تحديث قيمتين متتاليتين من المتتالية modulo \(10^9\)، وبذلك تمثل حالة الحلقة دائمًا حدين متجاورين من علاقة فيبوناتشي من منظور آخر تسعة أرقام.
بعد ذلك يُطبَّق فلتر pandigital على كتلة الذيل. النسخ المعتمدة على السلاسل النصية تهيئ الباقي في صورة كتلة عشرية طولها 9 حتى لا تضيع الأصفار القيادية داخل الذيل. أما النسخة العددية فتستخرج الأرقام مباشرة وتقبل فقط القيم ذات التسع خانات تمامًا، من دون صفر ومن دون تكرار. هذا اختلاف في التمثيل فقط، لا في المعيار الرياضي.
إذا نجح الذيل، تحسب الشيفرة كتلة البداية من الصيغة اللوغاريتمية ثم تطبق عليها الشرط نفسه. وبمجرد أن ينجح الاختباران عند الفهرس نفسه تتوقف عملية البحث وتعيد أول فهرس صالح، وهو \(k=329468\).
إذا كان \(k\) هو أول فهرس ناجح، فإن الخوارزمية تنفذ \(k-2\) تحديثات لفibonacci. كل دورة تعمل بزمن ثابت: جمع modulo \(10^9\)، وفحص pandigital على تسع خانات، وفقط أحيانًا حساب لوغاريتمي لمقدمة العدد. لذلك يكون التعقيد الزمني الكلي \(O(k)\).
في هذه المسألة يتوقف البحث عند \(k=329468\)، أي بعد بضع مئات آلاف من الدورات فقط. أما التعقيد المكاني فهو \(O(1)\)، لأن البرنامج يحتفظ فقط بباقيين حاليين، وعدد صغير من الثوابت العائمة، وبنية صغيرة جدًا لتتبع الأرقام.