Let \(F_1=F_2=1\) and \(F_{n+2}=F_{n+1}+F_n\). The task is to locate the index \(n\) of the \(N\)-th Fibonacci number that is squarefree, meaning that no prime square divides \(F_n\). After that index is known, the program prints \(F_n\) in a compressed decimal format: the last 16 digits and a scientific-notation leading value with one decimal place. The crucial observation is that the search is carried out on the index line \(n=1,2,3,\dots\), not on the enormous Fibonacci values themselves.
A positive integer is squarefree exactly when it is not divisible by \(p^2\) for any prime \(p\). Therefore
$$\forall p,\ p^2 \nmid F_n.$$
So instead of examining the factorization of \(F_n\) directly, we ask a sharper question: for a fixed prime \(p\), which indices \(n\) force \(p^2\mid F_n\)? Once those forbidden indices are understood, the problem becomes a sieve over the natural numbers.
For a prime \(p\), define the rank of apparition
$$z(p)=\min\{m\ge 1 : p\mid F_m\}.$$
A standard divisibility property of Fibonacci numbers says that
$$p\mid F_n \iff z(p)\mid n.$$
The implementation then uses the Fibonacci valuation law
$$v_p(F_{kz(p)})=v_p(F_{z(p)})+v_p(k),$$
which turns a divisibility question about \(F_n\) into a divisibility question about the index \(n\). In the standard situation used by the sieve, the first index where a second factor of \(p\) appears is \(p\,z(p)\). That leads to the bad period
$$b_p=p\,z(p),$$
and every multiple of \(b_p\) is marked as non-squarefree.
Small examples make this concrete:
$$p=2:\ z(2)=3,\ b_2=6,\qquad F_6=8,$$
$$p=3:\ z(3)=4,\ b_3=12,\qquad F_{12}=144,$$
$$p=5:\ z(5)=5,\ b_5=25,\qquad 25\mid F_{25}.$$
Directly searching for the first Fibonacci number divisible by \(p\) would be too slow. The implementation instead uses the classical theorem
$$z(p)\mid p-\left(\frac{5}{p}\right)\qquad (p\ne 5),$$
where \(\left(\frac{5}{p}\right)\) is the Legendre symbol. Euler's criterion provides that symbol via
$$5^{(p-1)/2}\equiv \left(\frac{5}{p}\right)\pmod p.$$
Thus \(z(p)\) must divide the known candidate \(r=p-\left(\frac{5}{p}\right)\). The algorithm factors \(r\), then tries to remove each prime factor \(q\) as many times as possible. Whenever
$$F_{r/q}\equiv 0 \pmod p,$$
the candidate can be reduced from \(r\) to \(r/q\). After all possible reductions, the remaining value is exactly \(z(p)\). The special primes \(2\) and \(5\) are handled directly with \(z(2)=3\) and \(z(5)=5\).
All Fibonacci evaluations in the implementation are performed with fast doubling. If \((F_m,F_{m+1})\) is known, then
$$F_{2m}=F_m(2F_{m+1}-F_m),$$
$$F_{2m+1}=F_m^2+F_{m+1}^2.$$
These identities reduce the computation of \(F_t\bmod M\) to \(O(\log t)\) modular operations. That is essential both while shrinking the candidate for \(z(p)\) and later when computing the last 16 digits of the final Fibonacci number.
After every bad period \(b_p\le K\) has been generated for a search bound \(K\), the periods are sorted, deduplicated, and reduced. If one period divides another, the larger one is redundant because all its multiples are already covered. For example, \(12\) adds nothing once \(6\) is present.
With the reduced set \(B\), the program marks
$$n\in \bigcup_{b\in B}\{b,2b,3b,\dots\}\qquad (1\le n\le K).$$
The \(N\)-th unmarked index is exactly the index of the \(N\)-th squarefree Fibonacci number.
Only primes \(p\le K/3\) need to be examined. Indeed \(z(p)\ge 3\) for every prime, so \(p\,z(p)\ge 3p\). If \(3p>K\), that bad period cannot affect the search window at all.
Once the desired index \(n\) is known, the last 16 digits come from
$$F_n\bmod 10^{16}.$$
For the leading scientific notation, the implementation uses Binet's formula
$$F_n=\frac{\varphi^n-\psi^n}{\sqrt{5}},\qquad \varphi=\frac{1+\sqrt{5}}{2},\qquad \psi=\frac{1-\sqrt{5}}{2}.$$
Because \(|\psi|<1\), large \(n\) satisfy
$$\log_{10}(F_n)\approx n\log_{10}\varphi-\log_{10}\sqrt{5}.$$
If \(x=\log_{10}(F_n)\), then
$$e=\lfloor x\rfloor,\qquad m=10^{x-e}\in [1,10).$$
Rounding \(m\) to one decimal place gives the displayed mantissa. If that rounding produces \(10.0\), the mantissa is renormalized to \(1.0\) and the exponent is increased by 1.
The C++, Python, and Java implementations follow the same algorithmic pipeline. First they build a smallest-prime-factor sieve up to the prime limit implied by the search bound. Then they compute bad periods \(p\,z(p)\), remove divisibility-redundant periods, and mark every multiple of the remaining periods until the target count of unmarked indices is reached.
The Fibonacci values themselves are never expanded as giant exact decimal strings. Modular fast doubling gives the last 16 digits directly, while high-precision logarithms provide the scientific-notation mantissa and exponent. The C++ implementation additionally parallelizes the prime loop across hardware threads, but the underlying mathematics is the same in all three languages.
A built-in checkpoint validates the workflow on a smaller case: the 200th surviving index produces the formatted output 1608739584170445,9.7e53.
Let \(K\) be the search bound and let \(B\) be the reduced set of bad periods. Building the smallest-prime-factor sieve up to about \(K/3\) is linear or near-linear in practice and uses \(O(K)\) auxiliary space up to constant factors. Computing all ranks of apparition requires modular Fibonacci tests that cost \(O(\log K)\) each, after which the marking phase costs
$$O\!\left(\sum_{b\in B}\frac{K}{b}\right)$$
operations, followed by one linear scan to locate the \(N\)-th unmarked index. The dominant memory usage is the boolean mark array of size \(K+1\) together with the sieve tables and the reduced period list.
Sei \(F_1=F_2=1\) und \(F_{n+2}=F_{n+1}+F_n\). Gesucht ist der Index \(n\) der \(N\)-ten Fibonacci-Zahl, die quadratfrei ist, also von keinem Primquadrat geteilt wird. Sobald dieser Index feststeht, gibt das Programm \(F_n\) in kompakter Dezimalform aus: die letzten 16 Ziffern und eine wissenschaftliche Schreibweise mit einer Nachkommastelle. Entscheidend ist, dass nicht die riesigen Werte \(F_n\) selbst gesiebt werden, sondern die Indizes \(n\).
Eine positive ganze Zahl ist genau dann quadratfrei, wenn sie durch kein \(p^2\) mit \(p\) prim teilbar ist. Daher gilt
$$\forall p,\ p^2 \nmid F_n.$$
Statt also \(F_n\) zu faktorisieren, fragt man für jedes feste \(p\): Für welche Indizes \(n\) erzwingt die Fibonacci-Folge bereits \(p^2\mid F_n\)? Sobald diese verbotenen Indizes bekannt sind, reduziert sich das Problem auf ein Sieb über \(1,2,3,\dots\).
Für eine Primzahl \(p\) definieren wir den Rang des Auftretens durch
$$z(p)=\min\{m\ge 1 : p\mid F_m\}.$$
Eine Standard-Eigenschaft der Fibonacci-Zahlen lautet dann
$$p\mid F_n \iff z(p)\mid n.$$
Die Implementierung benutzt außerdem das Bewertungs-Gesetz
$$v_p(F_{kz(p)})=v_p(F_{z(p)})+v_p(k),$$
das die Teilbarkeitsfrage von \(F_n\) auf den Index \(n\) zurückführt. In der vom Sieb verwendeten Standardsituation ist der erste Index mit einer zweiten Kopie von \(p\) gleich \(p\,z(p)\). Deshalb setzt die Implementierung
$$b_p=p\,z(p)$$
als schlechte Periode an und markiert alle Vielfachen von \(b_p\) als nicht quadratfrei.
Kleine Beispiele zeigen das sofort:
$$p=2:\ z(2)=3,\ b_2=6,\qquad F_6=8,$$
$$p=3:\ z(3)=4,\ b_3=12,\qquad F_{12}=144,$$
$$p=5:\ z(5)=5,\ b_5=25,\qquad 25\mid F_{25}.$$
Ein direktes Suchen nach dem ersten durch \(p\) teilbaren Fibonacci-Glied wäre zu langsam. Stattdessen nutzt die Implementierung den klassischen Satz
$$z(p)\mid p-\left(\frac{5}{p}\right)\qquad (p\ne 5),$$
wobei \(\left(\frac{5}{p}\right)\) das Legendre-Symbol ist. Über das Euler-Kriterium erhält man dieses Symbol durch
$$5^{(p-1)/2}\equiv \left(\frac{5}{p}\right)\pmod p.$$
Also muss \(z(p)\) den bekannten Kandidaten \(r=p-\left(\frac{5}{p}\right)\) teilen. Der Algorithmus faktorisiert \(r\) und versucht dann, jeden Primfaktor \(q\) so oft wie möglich herauszuteilen. Immer wenn
$$F_{r/q}\equiv 0 \pmod p,$$
kann der Kandidat von \(r\) auf \(r/q\) verkleinert werden. Nach allen möglichen Reduktionen bleibt exakt \(z(p)\) übrig. Die Sonderfälle \(2\) und \(5\) werden direkt mit \(z(2)=3\) und \(z(5)=5\) behandelt.
Alle Fibonacci-Auswertungen der Implementierung verwenden Fast Doubling. Kennt man \((F_m,F_{m+1})\), so gilt
$$F_{2m}=F_m(2F_{m+1}-F_m),$$
$$F_{2m+1}=F_m^2+F_{m+1}^2.$$
Damit sinkt die Berechnung von \(F_t\bmod M\) auf \(O(\log t)\) modulare Operationen. Diese Beschleunigung ist sowohl beim Verkleinern des Kandidaten für \(z(p)\) als auch bei der späteren Berechnung der letzten 16 Ziffern unverzichtbar.
Sobald alle schlechten Perioden \(b_p\le K\) bis zu einer Suchgrenze \(K\) erzeugt wurden, werden sie sortiert, dedupliziert und reduziert. Teilt eine kleinere Periode eine größere, dann ist die größere überflüssig, weil ihre Vielfachen bereits erfasst sind. Beispielsweise bringt \(12\) keinen zusätzlichen Effekt mehr, sobald \(6\) vorhanden ist.
Mit der reduzierten Menge \(B\) markiert das Programm
$$n\in \bigcup_{b\in B}\{b,2b,3b,\dots\}\qquad (1\le n\le K).$$
Der \(N\)-te unmarkierte Index ist dann genau der Index der \(N\)-ten quadratfreien Fibonacci-Zahl.
Es genügen Primzahlen \(p\le K/3\). Denn für jede Primzahl gilt \(z(p)\ge 3\), also \(p\,z(p)\ge 3p\). Falls \(3p>K\), kann diese schlechte Periode im Suchfenster nicht mehr auftreten.
Sobald der gesuchte Index \(n\) feststeht, ergeben sich die letzten 16 Ziffern aus
$$F_n\bmod 10^{16}.$$
Für die führende wissenschaftliche Schreibweise verwendet die Implementierung die Binet-Formel
$$F_n=\frac{\varphi^n-\psi^n}{\sqrt{5}},\qquad \varphi=\frac{1+\sqrt{5}}{2},\qquad \psi=\frac{1-\sqrt{5}}{2}.$$
Wegen \(|\psi|<1\) gilt für große \(n\)
$$\log_{10}(F_n)\approx n\log_{10}\varphi-\log_{10}\sqrt{5}.$$
Setzt man \(x=\log_{10}(F_n)\), dann sind
$$e=\lfloor x\rfloor,\qquad m=10^{x-e}\in [1,10).$$
Nach Rundung von \(m\) auf eine Nachkommastelle erhält man die ausgegebene Mantisse. Falls dabei \(10.0\) entsteht, wird auf \(1.0\) normiert und der Exponent um 1 erhöht.
Die C++-, Python- und Java-Implementierungen folgen derselben Pipeline. Zuerst wird ein Sieb für kleinste Primfaktoren bis zur durch die Suchgrenze vorgegebenen Primgrenze aufgebaut. Danach werden die schlechten Perioden \(p\,z(p)\) berechnet, alle durch Teilbarkeit redundanten Perioden entfernt und schließlich alle Vielfachen der verbleibenden Perioden markiert, bis der gewünschte unmarkierte Index erreicht ist.
Die Fibonacci-Werte selbst werden nie als riesige exakte Dezimalzahlen aufgebaut. Modulares Fast Doubling liefert direkt die letzten 16 Ziffern, während hochpräzise Logarithmen Mantisse und Exponent der wissenschaftlichen Schreibweise bestimmen. Die C++-Version verteilt die Primschleife zusätzlich auf mehrere Hardware-Threads; die mathematische Methode bleibt aber in allen drei Sprachen identisch.
Ein eingebauter Kontrolltest prüft die gesamte Kette an einem kleineren Beispiel: Für den 200. überlebenden Index lautet das formatierte Ergebnis 1608739584170445,9.7e53.
Sei \(K\) die Suchgrenze und \(B\) die reduzierte Menge schlechter Perioden. Das Sieb der kleinsten Primfaktoren bis ungefähr \(K/3\) ist in der Praxis linear oder nahezu linear und benötigt bis auf konstante Faktoren \(O(K)\) Hilfsspeicher. Die Berechnung aller Ränge des Auftretens verwendet modulare Fibonacci-Tests mit Kosten \(O(\log K)\) pro Test. Danach kostet die Markierungsphase
$$O\!\left(\sum_{b\in B}\frac{K}{b}\right)$$
Operationen, gefolgt von einer linearen Suche nach dem \(N\)-ten unmarkierten Index. Der dominante Speicherverbrauch besteht aus dem Bool-Array der Größe \(K+1\), den Siebtabellen und der reduzierten Periodenliste.
\(F_1=F_2=1\) ve \(F_{n+2}=F_{n+1}+F_n\) olsun. Amaç, kare-çarpansız olan \(N\). Fibonacci sayısının indeksini bulmaktır; yani aranan \(F_n\) hiçbir asalın karesine bölünmemelidir. Bu indeks bulunduktan sonra program \(F_n\) değerini tam olarak yazmak yerine sıkıştırılmış bir ondalık biçim üretir: son 16 basamak ve bir ondalık basamaklı bilimsel gösterim. Asıl fikir, devasa Fibonacci değerlerini değil, indeksleri elemekten geçer.
Bir pozitif tamsayı ancak ve ancak hiçbir asal karesi tarafından bölünmüyorsa kare-çarpansızdır. Dolayısıyla
$$\forall p,\ p^2 \nmid F_n.$$
Böylece soru şuna dönüşür: sabit bir asal \(p\) için, hangi indeksler \(n\) değeri \(p^2\mid F_n\) koşulunu zorlar? Bu yasak indeksler bulununca geriye doğal sayılar üzerinde bir eleme işlemi kalır.
Bir asal \(p\) için görünme rütbesini
$$z(p)=\min\{m\ge 1 : p\mid F_m\}$$
şeklinde tanımlayalım. Fibonacci dizisinin temel bölünebilirlik özelliklerinden biri
$$p\mid F_n \iff z(p)\mid n$$
eşdeğerliğidir. Uygulama ayrıca şu değerleme özdeşliğini kullanır:
$$v_p(F_{kz(p)})=v_p(F_{z(p)})+v_p(k).$$
Bu formül, \(F_n\) üzerindeki bölünebilirlik sorusunu doğrudan indeks \(n\) üzerindeki bölünebilirliğe çevirir. Elemede kullanılan standart durumda \(p\)'nin ikinci kopyasının ilk kez göründüğü indeks \(p\,z(p)\) olur. Bu yüzden uygulama
$$b_p=p\,z(p)$$
değerini kötü periyot olarak alır ve tüm katlarını kare-çarpansız olmayan indeksler olarak işaretler.
Küçük örnekler bunu açıkça gösterir:
$$p=2:\ z(2)=3,\ b_2=6,\qquad F_6=8,$$
$$p=3:\ z(3)=4,\ b_3=12,\qquad F_{12}=144,$$
$$p=5:\ z(5)=5,\ b_5=25,\qquad 25\mid F_{25}.$$
\(p\)'ye bölünen ilk Fibonacci terimini doğrudan aramak çok pahalı olurdu. Bunun yerine uygulama şu klasik teoremi kullanır:
$$z(p)\mid p-\left(\frac{5}{p}\right)\qquad (p\ne 5),$$
burada \(\left(\frac{5}{p}\right)\) Legendre sembolüdür. Euler ölçütü bu sembolü
$$5^{(p-1)/2}\equiv \left(\frac{5}{p}\right)\pmod p$$
eşitliğiyle verir. O halde \(z(p)\), \(r=p-\left(\frac{5}{p}\right)\) adayını bölmek zorundadır. Algoritma önce \(r\)'yi çarpanlara ayırır, sonra her asal çarpan \(q\)'yu mümkün olduğu kadar dışarı almaya çalışır. Eğer
$$F_{r/q}\equiv 0 \pmod p$$
oluyorsa aday \(r\)'den \(r/q\)'ya indirilebilir. Tüm bu küçültmeler bittiğinde elde kalan değer tam olarak \(z(p)\) olur. \(2\) ve \(5\) için özel durumlar doğrudan \(z(2)=3\) ve \(z(5)=5\) olarak ele alınır.
Uygulamadaki tüm Fibonacci hesapları fast doubling ile yapılır. Eğer \((F_m,F_{m+1})\) biliniyorsa
$$F_{2m}=F_m(2F_{m+1}-F_m),$$
$$F_{2m+1}=F_m^2+F_{m+1}^2$$
özdeşlikleri kullanılır. Böylece \(F_t\bmod M\) hesabı yalnızca \(O(\log t)\) modüler işlem gerektirir. Bu hızlandırma hem \(z(p)\) adayını küçültürken hem de son 16 basamağı hesaplarken kritik rol oynar.
Belirli bir arama sınırı \(K\) için tüm kötü periyotlar \(b_p\le K\) üretildikten sonra sıralanır, tekrarlar silinir ve bölünebilirlik açısından azaltma yapılır. Küçük bir periyot daha büyük bir periyodu bölüyorsa, büyük olan gereksizdir; çünkü onun bütün katları zaten işaretlenmiş olacaktır. Örneğin \(6\) varken \(12\) yeni hiçbir indeks eklemez.
Azaltılmış \(B\) kümesi ile program
$$n\in \bigcup_{b\in B}\{b,2b,3b,\dots\}\qquad (1\le n\le K)$$
şeklindeki tüm indeksleri işaretler. İşaretsiz kalan \(N\). indeks, aranan kare-çarpansız Fibonacci sayısının indeksidir.
Yalnızca \(p\le K/3\) asallarına bakmak yeterlidir. Çünkü her asal için \(z(p)\ge 3\) olduğundan \(p\,z(p)\ge 3p\) elde edilir. Eğer \(3p>K\) ise bu kötü periyot arama penceresinde zaten görünemez.
Aranan indeks \(n\) bulunduktan sonra son 16 basamak
$$F_n\bmod 10^{16}$$
ile hesaplanır. Bilimsel gösterimin baştaki kısmı için ise Binet formülü kullanılır:
$$F_n=\frac{\varphi^n-\psi^n}{\sqrt{5}},\qquad \varphi=\frac{1+\sqrt{5}}{2},\qquad \psi=\frac{1-\sqrt{5}}{2}.$$
\(|\psi|<1\) olduğundan büyük \(n\) için
$$\log_{10}(F_n)\approx n\log_{10}\varphi-\log_{10}\sqrt{5}$$
yaklaşımı geçerlidir. \(x=\log_{10}(F_n)\) denirse
$$e=\lfloor x\rfloor,\qquad m=10^{x-e}\in [1,10)$$
olur. \(m\) değeri bir ondalık basamağa yuvarlanır. Eğer yuvarlama \(10.0\) üretirse mantis \(1.0\)'a çekilir ve üs 1 artırılır.
C++, Python ve Java uygulamaları aynı algoritmik hattı izler. Önce arama sınırının gerektirdiği asal aralığı için en küçük asal bölen süzgeci kurulurlar. Sonra kötü periyotlar \(p\,z(p)\) hesaplanır, bölünebilirlik nedeniyle gereksiz olanlar ayıklanır ve kalan periyotların tüm katları işaretlenerek hedef sayıda işaretsiz indeks bulunur.
Fibonacci değerleri asla dev ondalık dizgiler halinde oluşturulmaz. Modüler fast doubling son 16 basamağı doğrudan üretir; yüksek duyarlıklı logaritmalar da bilimsel gösterimdeki mantis ve üssü verir. C++ uygulaması asal döngüsünü donanım iş parçacıklarına bölerek hız kazandırır, fakat matematiksel içerik üç dilde de aynıdır.
Yerleşik kontrol örneği, daha küçük bir hedef için tüm zinciri doğrular: 200. geçerli indeksin biçimlendirilmiş çıktısı 1608739584170445,9.7e53 olur.
\(K\) arama sınırı ve \(B\) azaltılmış kötü periyotlar kümesi olsun. Yaklaşık \(K/3\)'e kadar en küçük asal bölen süzgeci pratikte lineer ya da lineere çok yakın zamanda kurulur ve sabit katsayılar dışında \(O(K)\) bellek kullanır. Görünme rütbelerinin hesaplanmasında kullanılan modüler Fibonacci testlerinin her biri \(O(\log K)\) maliyetlidir. Ardından işaretleme aşaması
$$O\!\left(\sum_{b\in B}\frac{K}{b}\right)$$
işlem gerektirir; sonrasında da \(N\). işaretsiz indeksi bulmak için bir doğrusal tarama yapılır. Baskın bellek maliyeti \(K+1\) uzunluklu işaret dizisi, süzgeç tabloları ve azaltılmış periyot listesidir.
Sea \(F_1=F_2=1\) y \(F_{n+2}=F_{n+1}+F_n\). Debemos encontrar el índice \(n\) del \(N\)-ésimo número de Fibonacci que sea libre de cuadrados, es decir, tal que ningún cuadrado primo divida a \(F_n\). Una vez hallado ese índice, el programa no imprime el entero completo, sino una representación decimal compacta: las últimas 16 cifras y una notación científica con una sola cifra decimal. La idea central es trabajar sobre los índices, no sobre valores gigantes de Fibonacci.
Un entero positivo es libre de cuadrados si y solo si no es divisible por \(p^2\) para ningún primo \(p\). Por tanto,
$$\forall p,\ p^2 \nmid F_n.$$
En vez de factorizar directamente \(F_n\), conviene preguntar: para un primo fijo \(p\), ¿qué índices \(n\) obligan a que \(p^2\mid F_n\)? Cuando se conocen esos índices prohibidos, el problema se convierte en un cribado sobre \(1,2,3,\dots\).
Para un primo \(p\), definimos el rango de aparición por
$$z(p)=\min\{m\ge 1 : p\mid F_m\}.$$
Una propiedad clásica de divisibilidad de Fibonacci afirma que
$$p\mid F_n \iff z(p)\mid n.$$
La implementación usa además la ley de valuación
$$v_p(F_{kz(p)})=v_p(F_{z(p)})+v_p(k),$$
que transforma la pregunta sobre \(F_n\) en una pregunta sobre el propio índice \(n\). En la situación estándar utilizada por el cribado, el primer índice donde aparece una segunda potencia de \(p\) es \(p\,z(p)\). Por eso la implementación define
$$b_p=p\,z(p)$$
como período malo y marca todos sus múltiplos como índices no squarefree.
Los primeros ejemplos son ilustrativos:
$$p=2:\ z(2)=3,\ b_2=6,\qquad F_6=8,$$
$$p=3:\ z(3)=4,\ b_3=12,\qquad F_{12}=144,$$
$$p=5:\ z(5)=5,\ b_5=25,\qquad 25\mid F_{25}.$$
Buscar \(z(p)\) por fuerza bruta sería demasiado lento. La implementación utiliza en cambio el teorema clásico
$$z(p)\mid p-\left(\frac{5}{p}\right)\qquad (p\ne 5),$$
donde \(\left(\frac{5}{p}\right)\) es el símbolo de Legendre. El criterio de Euler permite obtener ese símbolo mediante
$$5^{(p-1)/2}\equiv \left(\frac{5}{p}\right)\pmod p.$$
Así, \(z(p)\) debe dividir al candidato conocido \(r=p-\left(\frac{5}{p}\right)\). El algoritmo factoriza \(r\) y trata de eliminar cada factor primo \(q\) tantas veces como sea posible. Cuando
$$F_{r/q}\equiv 0 \pmod p,$$
el candidato puede reducirse de \(r\) a \(r/q\). Después de todas las reducciones, el valor restante es exactamente \(z(p)\). Los casos especiales \(2\) y \(5\) se resuelven directamente con \(z(2)=3\) y \(z(5)=5\).
Todas las evaluaciones de Fibonacci en la implementación usan fast doubling. Si conocemos \((F_m,F_{m+1})\), entonces
$$F_{2m}=F_m(2F_{m+1}-F_m),$$
$$F_{2m+1}=F_m^2+F_{m+1}^2.$$
Estas identidades reducen el cálculo de \(F_t\bmod M\) a solo \(O(\log t)\) operaciones modulares. Esa aceleración es esencial tanto al reducir el candidato de \(z(p)\) como al calcular luego las últimas 16 cifras del Fibonacci final.
Una vez generados todos los períodos malos \(b_p\le K\) hasta un límite de búsqueda \(K\), se ordenan, se eliminan duplicados y se reduce el conjunto. Si un período divide a otro mayor, el mayor es redundante porque todos sus múltiplos ya estaban cubiertos. Por ejemplo, \(12\) deja de aportar información nueva cuando \(6\) ya está presente.
Con el conjunto reducido \(B\), el programa marca
$$n\in \bigcup_{b\in B}\{b,2b,3b,\dots\}\qquad (1\le n\le K).$$
El \(N\)-ésimo índice no marcado es exactamente el índice del \(N\)-ésimo Fibonacci libre de cuadrados.
Solo es necesario considerar primos \(p\le K/3\). En efecto, siempre se cumple \(z(p)\ge 3\), luego \(p\,z(p)\ge 3p\). Si \(3p>K\), ese período malo no puede influir en la ventana de búsqueda.
Con el índice final \(n\), las últimas 16 cifras se obtienen mediante
$$F_n\bmod 10^{16}.$$
Para la notación científica inicial, la implementación usa la fórmula de Binet
$$F_n=\frac{\varphi^n-\psi^n}{\sqrt{5}},\qquad \varphi=\frac{1+\sqrt{5}}{2},\qquad \psi=\frac{1-\sqrt{5}}{2}.$$
Como \(|\psi|<1\), para \(n\) grande vale la aproximación
$$\log_{10}(F_n)\approx n\log_{10}\varphi-\log_{10}\sqrt{5}.$$
Si \(x=\log_{10}(F_n)\), entonces
$$e=\lfloor x\rfloor,\qquad m=10^{x-e}\in [1,10).$$
Al redondear \(m\) a una cifra decimal se obtiene la mantisa mostrada. Si el redondeo produce \(10.0\), se renormaliza a \(1.0\) y se incrementa el exponente en 1.
Las implementaciones en C++, Python y Java siguen la misma secuencia matemática. Primero construyen un cribado de menor factor primo hasta el límite necesario. Después calculan los períodos malos \(p\,z(p)\), eliminan los redundantes por divisibilidad y marcan todos los múltiplos de los períodos restantes hasta encontrar la cantidad buscada de índices no marcados.
Los valores de Fibonacci nunca se expanden como enteros decimales gigantes. El fast doubling modular entrega directamente las últimas 16 cifras, mientras que logaritmos de alta precisión producen la mantisa y el exponente de la notación científica. La versión en C++ además reparte el recorrido de primos entre varios hilos, pero el contenido matemático es el mismo en los tres lenguajes.
La implementación incluye una comprobación interna con un caso menor: el índice superviviente número 200 produce la salida formateada 1608739584170445,9.7e53.
Sea \(K\) el límite de búsqueda y \(B\) el conjunto reducido de períodos malos. Construir el cribado de menor factor primo hasta aproximadamente \(K/3\) es lineal o casi lineal en la práctica y requiere \(O(K)\) memoria auxiliar salvo constantes. El cálculo de todos los rangos de aparición usa pruebas modulares de Fibonacci con coste \(O(\log K)\) por prueba. Después, la fase de marcado cuesta
$$O\!\left(\sum_{b\in B}\frac{K}{b}\right)$$
operaciones, seguida de un barrido lineal para localizar el \(N\)-ésimo índice no marcado. El principal consumo de memoria es el arreglo booleano de tamaño \(K+1\), junto con las tablas del cribado y la lista reducida de períodos.
设 \(F_1=F_2=1\)，并且 \(F_{n+2}=F_{n+1}+F_n\)。题目要求找出第 \(N\) 个平方因子自由的 Fibonacci 数对应的下标 \(n\)，也就是说该项 \(F_n\) 不被任何素数平方整除。得到这个下标以后，程序并不输出完整的巨大整数，而是给出一种压缩十进制表示：最后 16 位数字，以及保留一位小数的科学计数法前导值。真正的技巧在于把问题放到下标轴上处理，而不是直接分解巨大的 Fibonacci 值。
一个正整数当且仅当不被任何 \(p^2\) 整除时才是平方因子自由的，因此
$$\forall p,\ p^2 \nmid F_n.$$
于是关键问题变成：对固定素数 \(p\)，哪些下标 \(n\) 会强制满足 \(p^2\mid F_n\)？一旦这些“坏下标”能够描述出来，整个任务就从“大整数分解”变成了对自然数下标的筛法。
对素数 \(p\)，定义它在 Fibonacci 序列中的出现秩
$$z(p)=\min\{m\ge 1 : p\mid F_m\}.$$
Fibonacci 数有一个标准整除性质：
$$p\mid F_n \iff z(p)\mid n.$$
实现还利用了 \(p\)-进赋值公式
$$v_p(F_{kz(p)})=v_p(F_{z(p)})+v_p(k),$$
它把关于 \(F_n\) 的整除问题转成了关于下标 \(n\) 的整除问题。在筛法采用的标准情形里，\(p\) 的第二个因子第一次出现的下标就是 \(p\,z(p)\)。因此实现把
$$b_p=p\,z(p)$$
视为对应素数的坏周期，并把它的所有倍数都标成“非平方因子自由”。
前几个例子非常直观：
$$p=2:\ z(2)=3,\ b_2=6,\qquad F_6=8,$$
$$p=3:\ z(3)=4,\ b_3=12,\qquad F_{12}=144,$$
$$p=5:\ z(5)=5,\ b_5=25,\qquad 25\mid F_{25}.$$
如果直接逐项搜索第一个被 \(p\) 整除的 Fibonacci 数，代价会很高。实现采用经典定理
$$z(p)\mid p-\left(\frac{5}{p}\right)\qquad (p\ne 5),$$
其中 \(\left(\frac{5}{p}\right)\) 是 Legendre 符号。借助 Euler 判别法可以通过
$$5^{(p-1)/2}\equiv \left(\frac{5}{p}\right)\pmod p$$
得到该符号。这样一来，\(z(p)\) 一定整除已知候选量 \(r=p-\left(\frac{5}{p}\right)\)。算法先分解 \(r\)，再尝试把每个素因子 \(q\) 尽可能多地除掉。只要
$$F_{r/q}\equiv 0 \pmod p,$$
就可以把候选值从 \(r\) 缩小到 \(r/q\)。经过所有可能的缩减后，留下的正是 \(z(p)\)。特殊素数 \(2\) 和 \(5\) 则直接使用 \(z(2)=3\) 与 \(z(5)=5\)。
实现中的所有 Fibonacci 取模计算都使用 fast doubling。若已知 \((F_m,F_{m+1})\)，则有
$$F_{2m}=F_m(2F_{m+1}-F_m),$$
$$F_{2m+1}=F_m^2+F_{m+1}^2.$$
因此计算 \(F_t\bmod M\) 只需 \(O(\log t)\) 次模运算。这一点在缩减 \(z(p)\) 的候选值时非常关键，在最后计算目标 Fibonacci 数的末 16 位时也同样重要。
当某个搜索上界 \(K\) 内的所有坏周期 \(b_p\le K\) 都生成之后，程序会先排序、去重，再做约简。如果较小周期能整除较大周期，那么较大者是冗余的，因为它的每个倍数早已被较小周期覆盖。例如一旦保留了 \(6\)，周期 \(12\) 就不再提供新的坏下标。
对约简后的集合 \(B\)，程序标记
$$n\in \bigcup_{b\in B}\{b,2b,3b,\dots\}\qquad (1\le n\le K).$$
第 \(N\) 个未被标记的下标，就是第 \(N\) 个平方因子自由 Fibonacci 数的下标。
只需要考虑 \(p\le K/3\) 的素数。原因是任意素数都满足 \(z(p)\ge 3\)，于是 \(p\,z(p)\ge 3p\)。如果 \(3p>K\)，对应的坏周期就不可能落入搜索窗口。
在目标下标 \(n\) 已知之后，末 16 位由
$$F_n\bmod 10^{16}$$
直接给出。科学计数法的前导部分则来自 Binet 公式
$$F_n=\frac{\varphi^n-\psi^n}{\sqrt{5}},\qquad \varphi=\frac{1+\sqrt{5}}{2},\qquad \psi=\frac{1-\sqrt{5}}{2}.$$
由于 \(|\psi|<1\)，当 \(n\) 很大时有
$$\log_{10}(F_n)\approx n\log_{10}\varphi-\log_{10}\sqrt{5}.$$
令 \(x=\log_{10}(F_n)\)，则
$$e=\lfloor x\rfloor,\qquad m=10^{x-e}\in [1,10).$$
把 \(m\) 四舍五入到一位小数即可得到显示用的尾数；如果舍入后变成 \(10.0\)，就把它重新规范化为 \(1.0\)，同时指数加 1。
C++、Python 和 Java 三个实现遵循完全相同的算法流程。首先建立与搜索上界对应的最小素因子筛表，然后计算所有坏周期 \(p\,z(p)\)，删除在整除关系下冗余的周期，并对剩余周期的全部倍数做标记，直到找到目标数量的未标记下标为止。
Fibonacci 数本身不会被展开成完整的超大十进制整数。模 fast doubling 直接给出末 16 位，而高精度对数负责产生科学计数法中的尾数和指数。C++ 实现还会把素数循环分发到多个硬件线程上以提升速度，但数学步骤在三种语言中完全一致。
实现内置了一个较小规模的检查点：第 200 个保留下来的下标会得到格式化结果 1608739584170445,9.7e53。
设搜索上界为 \(K\)，约简后的坏周期集合为 \(B\)。构建到大约 \(K/3\) 的最小素因子筛，在实践中是线性或接近线性的，并且辅助空间在常数因子下为 \(O(K)\)。所有出现秩的计算都依赖模 Fibonacci 测试，而每次测试的代价是 \(O(\log K)\)。接下来，标记阶段的总工作量为
$$O\!\left(\sum_{b\in B}\frac{K}{b}\right),$$
之后还要进行一次线性扫描，以找出第 \(N\) 个未标记下标。主要内存消耗来自长度为 \(K+1\) 的布尔标记数组、筛表以及约简后的周期列表。
Пусть \(F_1=F_2=1\) и \(F_{n+2}=F_{n+1}+F_n\). Требуется найти индекс \(n\) у \(N\)-го числа Фибоначчи, которое является квадратсвободным, то есть не делится ни на один квадрат простого числа. После нахождения этого индекса программа выводит не весь огромный \(F_n\), а компактное десятичное представление: последние 16 цифр и научную запись с одной цифрой после запятой. Главная идея состоит в том, чтобы работать не с самими значениями \(F_n\), а с множеством индексов \(n\).
Положительное число квадратсвободно тогда и только тогда, когда ни для одного простого \(p\) не выполняется делимость на \(p^2\). Следовательно,
$$\forall p,\ p^2 \nmid F_n.$$
Поэтому вместо прямой факторизации \(F_n\) полезнее задать вопрос: для фиксированного простого \(p\) какие индексы \(n\) обязательно приводят к \(p^2\mid F_n\)? Когда такие запрещенные индексы описаны, задача превращается в решето на натуральных числах.
Для простого \(p\) определим ранг появления
$$z(p)=\min\{m\ge 1 : p\mid F_m\}.$$
Стандартное свойство делимости чисел Фибоначчи утверждает, что
$$p\mid F_n \iff z(p)\mid n.$$
Далее реализация использует формулу для \(p\)-адической оценки
$$v_p(F_{kz(p)})=v_p(F_{z(p)})+v_p(k),$$
которая переносит вопрос о делимости самого \(F_n\) на вопрос о делимости индекса \(n\). В стандартной ситуации, используемой решетом, первый индекс, на котором возникает второй множитель \(p\), равен \(p\,z(p)\). Поэтому реализация вводит плохой период
$$b_p=p\,z(p)$$
и помечает все его кратные как индексы, дающие неквадратсвободное число Фибоначчи.
Первые примеры хорошо это показывают:
$$p=2:\ z(2)=3,\ b_2=6,\qquad F_6=8,$$
$$p=3:\ z(3)=4,\ b_3=12,\qquad F_{12}=144,$$
$$p=5:\ z(5)=5,\ b_5=25,\qquad 25\mid F_{25}.$$
Искать первый делящийся на \(p\) член напрямую было бы слишком дорого. Вместо этого реализация использует классическую теорему
$$z(p)\mid p-\left(\frac{5}{p}\right)\qquad (p\ne 5),$$
где \(\left(\frac{5}{p}\right)\) обозначает символ Лежандра. По критерию Эйлера этот символ можно получить из соотношения
$$5^{(p-1)/2}\equiv \left(\frac{5}{p}\right)\pmod p.$$
Следовательно, \(z(p)\) обязательно делит известный кандидат \(r=p-\left(\frac{5}{p}\right)\). Алгоритм факторизует \(r\), а затем пытается делить его на каждый простой множитель \(q\) столько раз, сколько допускает проверка. Если
$$F_{r/q}\equiv 0 \pmod p,$$
то кандидат можно уменьшить с \(r\) до \(r/q\). После всех возможных сокращений остаток и есть точное значение \(z(p)\). Для простых \(2\) и \(5\) используются прямые значения \(z(2)=3\) и \(z(5)=5\).
Все вычисления Fibonacci по модулю выполняются методом fast doubling. Если известна пара \((F_m,F_{m+1})\), то
$$F_{2m}=F_m(2F_{m+1}-F_m),$$
$$F_{2m+1}=F_m^2+F_{m+1}^2.$$
Тем самым вычисление \(F_t\bmod M\) требует лишь \(O(\log t)\) модульных операций. Это критично и при уменьшении кандидата для \(z(p)\), и при последующем вычислении последних 16 цифр искомого числа Фибоначчи.
Когда все плохие периоды \(b_p\le K\) построены для заданной границы поиска \(K\), они сортируются, очищаются от повторов и дополнительно сокращаются. Если меньший период делит больший, то больший избыточен: все его кратные уже покрыты меньшим периодом. Например, период \(12\) не нужен, если период \(6\) уже сохранен.
Для сокращенного множества \(B\) программа помечает
$$n\in \bigcup_{b\in B}\{b,2b,3b,\dots\}\qquad (1\le n\le K).$$
\(N\)-й непомеченный индекс и есть индекс \(N\)-го квадратсвободного числа Фибоначчи.
Достаточно рассматривать только простые \(p\le K/3\). Действительно, для любого простого выполняется \(z(p)\ge 3\), а значит \(p\,z(p)\ge 3p\). Если \(3p>K\), такой плохой период просто не может попасть в окно поиска.
После нахождения нужного индекса \(n\) последние 16 цифр получаются как
$$F_n\bmod 10^{16}.$$
Для ведущей части в научной записи реализация использует формулу Бине
$$F_n=\frac{\varphi^n-\psi^n}{\sqrt{5}},\qquad \varphi=\frac{1+\sqrt{5}}{2},\qquad \psi=\frac{1-\sqrt{5}}{2}.$$
Поскольку \(|\psi|<1\), при больших \(n\) справедливо приближение
$$\log_{10}(F_n)\approx n\log_{10}\varphi-\log_{10}\sqrt{5}.$$
Если положить \(x=\log_{10}(F_n)\), то
$$e=\lfloor x\rfloor,\qquad m=10^{x-e}\in [1,10).$$
После округления \(m\) до одной цифры после запятой получаем выводимую мантиссу. Если округление дает \(10.0\), мантисса нормализуется к \(1.0\), а показатель увеличивается на 1.
Реализации на C++, Python и Java следуют одной и той же вычислительной схеме. Сначала строится решето наименьшего простого делителя до границы, определяемой окном поиска. Затем вычисляются плохие периоды \(p\,z(p)\), удаляются периоды, избыточные по делимости, и помечаются все кратные оставшихся периодов, пока не будет найдено нужное число непомеченных индексов.
Сами числа Фибоначчи не разворачиваются в полные гигантские десятичные строки. Модульный fast doubling напрямую дает последние 16 цифр, а высокоточные логарифмы дают мантиссу и показатель для научной записи. В версии на C++ цикл по простым дополнительно распараллелен по аппаратным потокам, но математическая основа одинакова во всех трех языках.
Встроенная контрольная проверка подтверждает корректность всей цепочки на меньшем примере: для 200-го выжившего индекса форматированный результат равен 1608739584170445,9.7e53.
Пусть \(K\) обозначает границу поиска, а \(B\) — сокращенное множество плохих периодов. Построение решета наименьшего простого делителя до примерно \(K/3\) на практике линейно или почти линейно и требует \(O(K)\) дополнительной памяти с точностью до констант. Вычисление всех рангов появления использует модульные проверки Fibonacci стоимостью \(O(\log K)\) каждая. После этого этап пометок требует
$$O\!\left(\sum_{b\in B}\frac{K}{b}\right)$$
операций, а затем выполняется один линейный проход для поиска \(N\)-го непомеченного индекса. Основное потребление памяти дают булев массив длины \(K+1\), таблицы решета и список сокращенных периодов.
لتكن \(F_1=F_2=1\) و \(F_{n+2}=F_{n+1}+F_n\). المطلوب هو إيجاد الفهرس \(n\) للحد رقم \(N\) من متتالية فيبوناتشي الذي يكون خاليًا من مربعات العوامل الأولية، أي إن \(F_n\) لا يقبل القسمة على \(p^2\) لأي عدد أولي \(p\). بعد تحديد هذا الفهرس لا يطبع البرنامج العدد الكامل الهائل، بل يخرج تمثيلًا عشريًا مضغوطًا: آخر 16 رقمًا، ثم صيغة علمية ذات منزلة عشرية واحدة. الفكرة الحاسمة هي أن المعالجة تتم على فضاء الفهارس \(n\)، لا على قيم فيبوناتشي الضخمة نفسها.
العدد الموجب يكون خاليًا من المربعات إذا وفقط إذا لم يقبل القسمة على \(p^2\) لأي عدد أولي \(p\). لذلك
$$\forall p,\ p^2 \nmid F_n.$$
وعليه فالسؤال الحقيقي ليس تفكيك \(F_n\) مباشرة، بل تحديد الفهارس \(n\) التي تجعل \(p^2\mid F_n\) حتميًا لكل عدد أولي ثابت \(p\). متى عُرفت هذه الفهارس الممنوعة تحولت المسألة إلى غربال على الأعداد الطبيعية.
لعدد أولي \(p\) نعرّف رتبة الظهور بـ
$$z(p)=\min\{m\ge 1 : p\mid F_m\}.$$
ومن خصائص القسمة القياسية في متتالية فيبوناتشي أن
$$p\mid F_n \iff z(p)\mid n.$$
وتستخدم الخوارزمية أيضًا علاقة التقييم \(p\)-الأدي
$$v_p(F_{kz(p)})=v_p(F_{z(p)})+v_p(k),$$
وهي التي تنقل مسألة القسمة من \(F_n\) نفسه إلى الفهرس \(n\). في الحالة القياسية التي يعتمدها الغربال، يكون أول فهرس تظهر عنده نسخة ثانية من العامل \(p\) هو \(p\,z(p)\). لذلك تعتبر الخوارزمية أن
$$b_p=p\,z(p)$$
هو الدورة السيئة المقابلة للعدد الأولي \(p\)، ثم تُعلَّم جميع مضاعفات هذه الدورة على أنها فهارس غير صالحة.
وتوضح الأمثلة الأولى الفكرة مباشرة:
$$p=2:\ z(2)=3,\ b_2=6,\qquad F_6=8,$$
$$p=3:\ z(3)=4,\ b_3=12,\qquad F_{12}=144,$$
$$p=5:\ z(5)=5,\ b_5=25,\qquad 25\mid F_{25}.$$
البحث المباشر عن أول حد من فيبوناتشي يقبل القسمة على \(p\) سيكون بطيئًا جدًا. لذلك تستخدم الخوارزمية النظرية الكلاسيكية
$$z(p)\mid p-\left(\frac{5}{p}\right)\qquad (p\ne 5),$$
حيث \(\left(\frac{5}{p}\right)\) هو رمز ليجاندر. ويمكن الحصول على هذا الرمز من معيار أويلر
$$5^{(p-1)/2}\equiv \left(\frac{5}{p}\right)\pmod p.$$
إذن لا بد أن يقسم \(z(p)\) المرشح المعروف \(r=p-\left(\frac{5}{p}\right)\). تقوم الخوارزمية بتحليل \(r\) إلى عوامله الأولية، ثم تحاول حذف كل عامل أولي \(q\) أكبر عدد ممكن من المرات. فإذا تحقق
$$F_{r/q}\equiv 0 \pmod p,$$
فيمكن تخفيض المرشح من \(r\) إلى \(r/q\). وبعد تنفيذ جميع التخفيضات الممكنة يبقى العدد الصحيح \(z(p)\). أما الحالتان الخاصتان \(2\) و\(5\) فتُعالجان مباشرة بالقيمتين \(z(2)=3\) و\(z(5)=5\).
جميع حسابات فيبوناتشي في التنفيذ تتم بطريقة fast doubling. فإذا كانت الزوجية \((F_m,F_{m+1})\) معلومة، فإن
$$F_{2m}=F_m(2F_{m+1}-F_m),$$
$$F_{2m+1}=F_m^2+F_{m+1}^2.$$
وبذلك يصبح حساب \(F_t\bmod M\) ممكنًا في \(O(\log t)\) عملية معيارية فقط. هذه السرعة ضرورية عند تقليص مرشح \(z(p)\)، وضرورية أيضًا لاحقًا عند استخراج آخر 16 رقمًا من عدد فيبوناتشي النهائي.
بعد توليد جميع الدورات السيئة \(b_p\le K\) حتى حد البحث \(K\)، تُرتَّب هذه الدورات، وتُزال التكرارات، ثم تُختزل. فإذا كانت دورة أصغر تقسم دورة أكبر، فالدورة الأكبر زائدة لأن كل مضاعفاتها كانت مغطاة مسبقًا. على سبيل المثال، تصبح \(12\) غير مفيدة ما إن تكون \(6\) موجودة.
وباستخدام المجموعة المختزلة \(B\)، يعلِّم البرنامج كل فهرس يحقق
$$n\in \bigcup_{b\in B}\{b,2b,3b,\dots\}\qquad (1\le n\le K).$$
وعندئذ يكون الفهرس غير المعلَّم رقم \(N\) هو بالضبط فهرس الحد \(N\) من أعداد فيبوناتشي الخالية من المربعات.
ولا حاجة إلى فحص إلا الأعداد الأولية \(p\le K/3\). فالرتبة \(z(p)\) لا تقل عن \(3\) لأي عدد أولي، ومن ثم \(p\,z(p)\ge 3p\). فإذا كان \(3p>K\)، فلن تؤثر تلك الدورة السيئة داخل نافذة البحث.
بعد معرفة الفهرس النهائي \(n\)، تُحسب آخر 16 خانة من خلال
$$F_n\bmod 10^{16}.$$
أما الجزء الأول في الصيغة العلمية فيأتي من صيغة بينيه
$$F_n=\frac{\varphi^n-\psi^n}{\sqrt{5}},\qquad \varphi=\frac{1+\sqrt{5}}{2},\qquad \psi=\frac{1-\sqrt{5}}{2}.$$
وبما أن \(|\psi|<1\)، نحصل للأعداد الكبيرة على التقريب
$$\log_{10}(F_n)\approx n\log_{10}\varphi-\log_{10}\sqrt{5}.$$
إذا وضعنا \(x=\log_{10}(F_n)\)، فإن
$$e=\lfloor x\rfloor,\qquad m=10^{x-e}\in [1,10).$$
ثم تُقرَّب \(m\) إلى منزلة عشرية واحدة لإنتاج القيمة المعروضة. وإذا أدى التقريب إلى \(10.0\)، تُعاد المعيارية إلى \(1.0\) ويزاد الأس بمقدار 1.
تتبع تطبيقات C++ وPython وJava السلسلة الحسابية نفسها. فهي تبدأ ببناء غربال لأصغر عامل أولي حتى الحد المناسب للبحث، ثم تحسب الدورات السيئة \(p\,z(p)\)، وتحذف الدورات الزائدة بحسب القسمة، وبعد ذلك تعلِّم جميع مضاعفات الدورات المتبقية إلى أن تصل إلى العدد المطلوب من الفهارس غير المعلَّمة.
ولا تُبنى قيم فيبوناتشي على هيئة سلاسل عشرية كاملة ضخمة. فطريقة fast doubling المعيارية تعطي آخر 16 رقمًا مباشرة، بينما توفر اللوغاريتمات عالية الدقة المانتيسا والأس للصيغة العلمية. وتضيف نسخة C++ تسريعًا إضافيًا بتوزيع حلقة الأعداد الأولية على عدة خيوط عتادية، لكن الجوهر الرياضي يبقى نفسه في اللغات الثلاث.
كما يوجد اختبار تحقق داخلي على مثال أصغر: الفهرس الناجي رقم 200 يعطي الخرج المنسق 1608739584170445,9.7e53.
لنفرض أن \(K\) هو حد البحث وأن \(B\) هي المجموعة المختزلة من الدورات السيئة. بناء غربال أصغر عامل أولي حتى ما يقارب \(K/3\) يكون خطيًا أو قريبًا من الخطي عمليًا، ويستهلك \(O(K)\) ذاكرة مساعدة حتى الثوابت. أما حساب جميع رتب الظهور فيعتمد على اختبارات Fibonacci معيارية كلفة كل منها \(O(\log K)\). بعد ذلك تصبح كلفة مرحلة التعليم
$$O\!\left(\sum_{b\in B}\frac{K}{b}\right)$$
عملية، ثم يتبعها مسح خطي واحد لإيجاد الفهرس غير المعلَّم رقم \(N\). والاستهلاك الأكبر للذاكرة يأتي من مصفوفة التعليم المنطقية بطول \(K+1\)، ومن جداول الغربال، ومن قائمة الدورات المختزلة.