The Fibonacci generating function is
$$A_F(x)=\sum_{k=1}^{\infty}F_kx^k=\frac{x}{1-x-x^2}.$$
A golden nugget is a positive integer value taken by this series for some rational \(x\). Problem 137 asks for the 15th such integer. The key fact used by the implementations is that the nuggets are exactly
$$N_k=F_{2k}F_{2k+1}\qquad (k\ge 1),$$
so the requested value is
$$N_{15}=F_{30}F_{31}=832040\cdot 1346269=1120149658760.$$
The difficult part is not the final multiplication. The real work is to show that the integer values of the generating function occur in a very rigid Fibonacci pattern, so the 15th nugget can be read off from one indexed product instead of found by trial and error.
Assume that the series takes an integer value \(n\), so \(A_F(x)=n\). Then
$$\frac{x}{1-x-x^2}=n,$$
which rearranges to
$$nx^2+(n+1)x-n=0.$$
The relevant root is the positive one, namely
$$x=\frac{-(n+1)+\sqrt{5n^2+2n+1}}{2n}.$$
Therefore \(x\) can only be rational if the discriminant
$$5n^2+2n+1$$
is a perfect square. That turns the original question into a Diophantine condition on \(n\).
Now introduce the rational numbers
$$x_k=\frac{F_{2k}}{F_{2k+1}}.$$
The Fibonacci identities immediately explain why these values are special. Starting from Cassini's identity and rewriting it, one gets
$$F_{m+1}^2-F_mF_{m+1}-F_m^2=(-1)^m.$$
For an even index \(m=2k\), the right-hand side equals \(1\), so
$$F_{2k+1}^2-F_{2k}F_{2k+1}-F_{2k}^2=1.$$
Divide by \(F_{2k+1}^2\):
$$1-x_k-x_k^2=\frac{1}{F_{2k+1}^2}.$$
Substituting into the generating function gives
$$A_F(x_k)=\frac{F_{2k}/F_{2k+1}}{1/F_{2k+1}^2}=F_{2k}F_{2k+1}.$$
So every product \(F_{2k}F_{2k+1}\) really is a golden nugget, and it comes from the explicit rational input \(x_k=F_{2k}/F_{2k+1}\).
If the discriminant is a square, write
$$m^2=5n^2+2n+1.$$
Multiplying by 5 and completing the square gives the Pell-type equation
$$5m^2-(5n+1)^2=4,$$
or equivalently
$$(5n+1)^2-5m^2=-4.$$
This is exactly the shape of the standard Lucas-Fibonacci identity
$$L_t^2-5F_t^2=4(-1)^t.$$
For odd \(t\), this becomes \(L_t^2-5F_t^2=-4\), so odd-indexed Lucas and Fibonacci numbers solve the same Diophantine equation. Among those odd indices, the requirement that \(5n+1\) be congruent to \(1\) modulo 5 selects \(t=4k+1\). Hence the admissible solutions satisfy
$$m=F_{4k+1},\qquad 5n+1=L_{4k+1}.$$
Using the standard identity
$$L_{4k+1}=5F_{2k}F_{2k+1}+1,$$
we obtain
$$n=F_{2k}F_{2k+1}.$$
So the family produced in the previous subsection is complete: the golden nuggets are precisely the products of consecutive Fibonacci numbers with indices \(2k\) and \(2k+1\).
Take \(k=2\). Then
$$x=\frac{F_4}{F_5}=\frac{3}{5}.$$
From the identity above,
$$1-\frac{3}{5}-\left(\frac{3}{5}\right)^2=\frac{1}{25},$$
so
$$A_F\left(\frac{3}{5}\right)=\frac{3/5}{1/25}=15.$$
That is the second golden nugget. The next one comes from \(k=3\): \(x=8/13\) and
$$A_F\left(\frac{8}{13}\right)=8\cdot 13=104.$$
For the required term we take \(k=15\), which yields \(F_{30}F_{31}=1120149658760\).
The C++, Python, and Java implementations do not search over candidate values of \(x\), and they do not solve the Pell-type equation numerically. They start from the proven closed form
$$N_k=F_{2k}F_{2k+1},$$
so for the 15th nugget they only need \(F_{30}\) and \(F_{31}\).
The implementation keeps two consecutive Fibonacci numbers and repeatedly advances them to the next pair. The loop invariant is straightforward: after finishing step \(i\), the stored pair is \(F_{i-1}\) and \(F_i\). Starting from \(F_0=0\) and \(F_1=1\), iterating up to \(i=31\) leaves exactly the pair \((F_{30},F_{31})\).
Once those two values are available, the answer is their product. One implementation also checks the known small case \(N_3=104\) before printing the requested term, which matches the worked example above. Python and Java use arbitrary-precision integers; the C++ version uses a wide fixed integer type, and the 15th nugget still fits comfortably inside it.
For a general index \(k\), the algorithm computes Fibonacci numbers up to \(F_{2k+1}\), so the running time is \(O(k)\). The auxiliary space is \(O(1)\) beyond the storage needed for the integers themselves, because only a constant number of Fibonacci values are kept at any moment.
For this specific problem \(k=15\), the executed workload is tiny: 30 Fibonacci updates and one multiplication. The mathematics is the hard part; the actual computation is effectively constant-time.
Die Fibonacci-Erzeugungsfunktion lautet
$$A_F(x)=\sum_{k=1}^{\infty}F_kx^k=\frac{x}{1-x-x^2}.$$
Ein Golden Nugget ist ein positiver ganzzahliger Wert dieser Reihe für ein rationales \(x\). In Problem 137 wird nach dem 15. solchen Wert gefragt. Die entscheidende Aussage, auf der die Implementierungen beruhen, ist
$$N_k=F_{2k}F_{2k+1}\qquad (k\ge 1),$$
also ist der gesuchte Wert
$$N_{15}=F_{30}F_{31}=832040\cdot 1346269=1120149658760.$$
Die eigentliche Schwierigkeit ist nicht die Endrechnung, sondern der Nachweis, dass die ganzzahligen Werte der Erzeugungsfunktion genau einem starren Fibonacci-Muster folgen. Sobald diese Struktur klar ist, wird aus einer scheinbaren Suche über rationale \(x\) nur noch ein einzelnes Fibonacci-Produkt.
Nehmen wir an, die Reihe habe den ganzzahligen Wert \(n\), also \(A_F(x)=n\). Dann gilt
$$\frac{x}{1-x-x^2}=n,$$
und damit
$$nx^2+(n+1)x-n=0.$$
Die relevante Lösung ist die positive Wurzel
$$x=\frac{-(n+1)+\sqrt{5n^2+2n+1}}{2n}.$$
Folglich kann \(x\) nur dann rational sein, wenn die Diskriminante
$$5n^2+2n+1$$
ein perfektes Quadrat ist. Damit wird das ursprüngliche Problem zu einer diophantischen Bedingung an \(n\).
Betrachte nun die rationalen Zahlen
$$x_k=\frac{F_{2k}}{F_{2k+1}}.$$
Eine umgeschriebene Form der Cassini-Identität liefert
$$F_{m+1}^2-F_mF_{m+1}-F_m^2=(-1)^m.$$
Für einen geraden Index \(m=2k\) ist die rechte Seite gleich \(1\), also
$$F_{2k+1}^2-F_{2k}F_{2k+1}-F_{2k}^2=1.$$
Nach Division durch \(F_{2k+1}^2\) folgt
$$1-x_k-x_k^2=\frac{1}{F_{2k+1}^2}.$$
Setzt man das in die Erzeugungsfunktion ein, erhält man
$$A_F(x_k)=\frac{F_{2k}/F_{2k+1}}{1/F_{2k+1}^2}=F_{2k}F_{2k+1}.$$
Damit ist jedes Produkt \(F_{2k}F_{2k+1}\) tatsächlich ein Golden Nugget, und zwar mit dem expliziten rationalen Argument \(x_k=F_{2k}/F_{2k+1}\).
Ist die Diskriminante ein Quadrat, so schreiben wir
$$m^2=5n^2+2n+1.$$
Nach Multiplikation mit 5 und Quadratergänzung entsteht die Pell-artige Gleichung
$$5m^2-(5n+1)^2=4,$$
beziehungsweise
$$(5n+1)^2-5m^2=-4.$$
Genau diese Form erscheint in der Standardidentität für Lucas- und Fibonacci-Zahlen,
$$L_t^2-5F_t^2=4(-1)^t.$$
Für ungerade \(t\) wird daraus \(L_t^2-5F_t^2=-4\), also liefern ungerade Indizes Lösungen derselben diophantischen Gleichung. Unter diesen ungeraden Indizes erzwingt die Bedingung \(5n+1\equiv 1\pmod 5\) die Wahl \(t=4k+1\). Somit gilt für die zulässigen Lösungen
$$m=F_{4k+1},\qquad 5n+1=L_{4k+1}.$$
Mit der Standardidentität
$$L_{4k+1}=5F_{2k}F_{2k+1}+1$$
folgt sofort
$$n=F_{2k}F_{2k+1}.$$
Die zuvor konstruierte Familie ist also vollständig: Die Golden Nuggets sind genau die Produkte aufeinanderfolgender Fibonacci-Zahlen mit Indizes \(2k\) und \(2k+1\).
Nimm \(k=2\). Dann ist
$$x=\frac{F_4}{F_5}=\frac{3}{5}.$$
Aus der obigen Identität folgt
$$1-\frac{3}{5}-\left(\frac{3}{5}\right)^2=\frac{1}{25},$$
also
$$A_F\left(\frac{3}{5}\right)=\frac{3/5}{1/25}=15.$$
Das ist das zweite Golden Nugget. Der nächste Fall entsteht bei \(k=3\): \(x=8/13\) und
$$A_F\left(\frac{8}{13}\right)=8\cdot 13=104.$$
Für den gesuchten Term setzt man \(k=15\) und erhält \(F_{30}F_{31}=1120149658760\).
Die C++-, Python- und Java-Implementierungen suchen nicht über rationale Kandidaten \(x\), und sie lösen auch die Pell-artige Gleichung nicht numerisch. Stattdessen benutzen sie direkt die hergeleitete geschlossene Formel
$$N_k=F_{2k}F_{2k+1},$$
sodass für das 15. Nugget nur \(F_{30}\) und \(F_{31}\) benötigt werden.
Die Implementierung speichert zwei aufeinanderfolgende Fibonacci-Zahlen und schiebt dieses Paar in jeder Iteration um eine Position weiter. Die Schleifeninvariante lautet: Nach Abschluss von Schritt \(i\) sind die gespeicherten Werte \(F_{i-1}\) und \(F_i\). Beginnend mit \(F_0=0\) und \(F_1=1\) erhält man nach der Iteration bis \(i=31\) genau das Paar \((F_{30},F_{31})\).
Sobald diese beiden Zahlen vorliegen, ist die Antwort einfach ihr Produkt. Eine Implementierung prüft zusätzlich den bekannten kleinen Fall \(N_3=104\), was mit dem durchgerechneten Beispiel übereinstimmt. Python und Java verwenden Ganzzahlen mit beliebiger Präzision; die C++-Version benutzt einen breiten festen Ganzzahltyp, und das 15. Nugget liegt noch bequem in dessen Wertebereich.
Für einen allgemeinen Index \(k\) werden Fibonacci-Zahlen bis \(F_{2k+1}\) erzeugt, daher beträgt die Laufzeit \(O(k)\). Der zusätzliche Speicherbedarf ist \(O(1)\), abgesehen vom Platz für die Zahlen selbst, weil nur konstant viele Fibonacci-Werte gleichzeitig gehalten werden.
Für dieses konkrete Problem mit \(k=15\) ist der tatsächliche Rechenaufwand winzig: 30 Fibonacci-Updates und eine Multiplikation. Schwer ist die Herleitung, nicht die Ausführung.
Fibonacci üreteç fonksiyonu
$$A_F(x)=\sum_{k=1}^{\infty}F_kx^k=\frac{x}{1-x-x^2}.$$
Altın nugget, bu serinin bir rasyonel \(x\) için aldığı pozitif tam sayı değerdir. Problem 137, bu değerlerin 15'incisini sorar. Uygulamaların dayandığı temel sonuç şudur:
$$N_k=F_{2k}F_{2k+1}\qquad (k\ge 1),$$
dolayısıyla istenen değer
$$N_{15}=F_{30}F_{31}=832040\cdot 1346269=1120149658760.$$
Asıl zorluk son çarpımda değil, üreteç fonksiyonunun tam sayı değerlerinin neden çok katı bir Fibonacci düzeni izlediğini göstermektedir. Bu yapı ortaya çıkarıldığında, rasyonel \(x\) değerleri arasında arama yapmak yerine tek bir indeksli Fibonacci çarpımına ulaşırız.
Serinin tam sayı değeri \(n\) olsun; yani \(A_F(x)=n\). O zaman
$$\frac{x}{1-x-x^2}=n,$$
ve buradan
$$nx^2+(n+1)x-n=0$$
elde edilir. İlgili kök pozitif olanıdır:
$$x=\frac{-(n+1)+\sqrt{5n^2+2n+1}}{2n}.$$
Öyleyse \(x\)'in rasyonel olabilmesi için ayırt edicinin
$$5n^2+2n+1$$
tam kare olması gerekir. Böylece soru, \(n\) üzerinde bir Diofant koşuluna indirgenir.
Şimdi şu rasyonel sayıları tanımlayalım:
$$x_k=\frac{F_{2k}}{F_{2k+1}}.$$
Cassini özdeşliğinin yeniden yazılmış biçimi
$$F_{m+1}^2-F_mF_{m+1}-F_m^2=(-1)^m$$
eşitliğini verir. \(m=2k\) çift olduğunda sağ taraf \(1\) olur; dolayısıyla
$$F_{2k+1}^2-F_{2k}F_{2k+1}-F_{2k}^2=1.$$
Bunu \(F_{2k+1}^2\)'ye bölersek
$$1-x_k-x_k^2=\frac{1}{F_{2k+1}^2}$$
elde edilir. Bunu üreteç fonksiyonuna yerleştirince
$$A_F(x_k)=\frac{F_{2k}/F_{2k+1}}{1/F_{2k+1}^2}=F_{2k}F_{2k+1}$$
olur. Yani her \(F_{2k}F_{2k+1}\) çarpımı gerçekten bir altın nugget'tır ve buna karşılık gelen rasyonel giriş de açıkça \(x_k=F_{2k}/F_{2k+1}\) olur.
Ayırt edici tam kare ise
$$m^2=5n^2+2n+1$$
yazabiliriz. 5 ile çarpıp kare tamamlarsak Pell-tipinde bir denklem elde ederiz:
$$5m^2-(5n+1)^2=4,$$
ya da eşdeğer olarak
$$(5n+1)^2-5m^2=-4.$$
Bu biçim, Lucas ve Fibonacci sayıları için bilinen
$$L_t^2-5F_t^2=4(-1)^t$$
özdeşliğiyle tam olarak aynıdır. \(t\) tek olduğunda \(L_t^2-5F_t^2=-4\) olur; yani tek indeksli Lucas ve Fibonacci sayıları aynı Diofant denkleminin çözümlerini verir. Bu tek indeksler arasında \(5n+1\equiv 1\pmod 5\) koşulu \(t=4k+1\) seçimini zorlar. Böylece geçerli çözümler
$$m=F_{4k+1},\qquad 5n+1=L_{4k+1}$$
şeklindedir. Ayrıca
$$L_{4k+1}=5F_{2k}F_{2k+1}+1$$
özdeşliğini kullanınca
$$n=F_{2k}F_{2k+1}$$
çıkar. Demek ki bir önceki alt bölümde kurulan aile tamdır: altın nugget'lar tam olarak indeksleri \(2k\) ve \(2k+1\) olan ardışık Fibonacci sayılarının çarpımlarıdır.
\(k=2\) alalım. O zaman
$$x=\frac{F_4}{F_5}=\frac{3}{5}.$$
Yukarıdaki özdeşlikten
$$1-\frac{3}{5}-\left(\frac{3}{5}\right)^2=\frac{1}{25}$$
gelir; dolayısıyla
$$A_F\left(\frac{3}{5}\right)=\frac{3/5}{1/25}=15.$$
Bu, ikinci altın nugget'tır. Sonraki örnek \(k=3\) için gelir: \(x=8/13\) ve
$$A_F\left(\frac{8}{13}\right)=8\cdot 13=104.$$
İstenen terim için \(k=15\) alınır ve \(F_{30}F_{31}=1120149658760\) bulunur.
C++, Python ve Java uygulamaları aday \(x\) değerleri üzerinde arama yapmaz; Pell-tipindeki denklemi de sayısal olarak çözmez. Bunun yerine doğrudan kanıtlanmış kapalı formülü kullanır:
$$N_k=F_{2k}F_{2k+1},$$
bu yüzden 15. nugget için yalnızca \(F_{30}\) ve \(F_{31}\) gerekir.
Uygulama her adımda iki ardışık Fibonacci sayısını tutar ve bunları bir sonraki ardışık çifte dönüştürür. Döngü değişmezi şudur: \(i\). adım tamamlandığında elde tutulan çift \(F_{i-1}\) ve \(F_i\) olur. Başlangıçta \(F_0=0\) ve \(F_1=1\) iken, \(i=31\)'e kadar ilerletildiğinde elde tam olarak \((F_{30},F_{31})\) çifti kalır.
Bu iki değer elde edildikten sonra cevap onların çarpımıdır. Uygulamalardan biri, istenen terimi yazdırmadan önce bilinen küçük durum \(N_3=104\)'ü de kontrol eder; bu, yukarıdaki çalışılmış örnekle örtüşür. Python ve Java keyfi hassasiyetli tamsayılar kullanır; C++ sürümü ise geniş bir sabit tamsayı türü kullanır ve 15. nugget bu aralığa rahatça sığar.
Genel bir \(k\) indeksi için algoritma \(F_{2k+1}\)'e kadar Fibonacci sayıları üretir; bu nedenle zaman karmaşıklığı \(O(k)\)'dir. Aynı anda yalnızca sabit sayıda Fibonacci değeri tutulduğu için, sayıların kendi depolama maliyeti dışında ek alan kullanımı \(O(1)\)'dir.
Bu özel problemde \(k=15\) olduğundan gerçek iş yükü çok küçüktür: 30 Fibonacci güncellemesi ve bir çarpma. Zor olan hesaplama değil, bu formüle ulaşan matematiksel türetmedir.
La función generadora de Fibonacci es
$$A_F(x)=\sum_{k=1}^{\infty}F_kx^k=\frac{x}{1-x-x^2}.$$
Una pepita dorada es un valor entero positivo que toma esta serie para algún \(x\) racional. El problema 137 pide la decimoquinta de esas cantidades. El hecho central que usan las implementaciones es
$$N_k=F_{2k}F_{2k+1}\qquad (k\ge 1),$$
de modo que el valor buscado es
$$N_{15}=F_{30}F_{31}=832040\cdot 1346269=1120149658760.$$
La dificultad real no está en la multiplicación final, sino en demostrar que los valores enteros de la función generadora siguen un patrón de Fibonacci muy rígido. Una vez identificada esa estructura, el problema deja de ser una búsqueda sobre muchos racionales \(x\) y pasa a ser un único producto indexado.
Supongamos que la serie vale \(n\), es decir, \(A_F(x)=n\). Entonces
$$\frac{x}{1-x-x^2}=n,$$
y esto se reordena como
$$nx^2+(n+1)x-n=0.$$
La raíz relevante es la positiva,
$$x=\frac{-(n+1)+\sqrt{5n^2+2n+1}}{2n}.$$
Por lo tanto, \(x\) solo puede ser racional si el discriminante
$$5n^2+2n+1$$
es un cuadrado perfecto. Así, la pregunta original se convierte en una condición diofántica sobre \(n\).
Consideremos ahora los racionales
$$x_k=\frac{F_{2k}}{F_{2k+1}}.$$
Al reescribir la identidad de Cassini se obtiene
$$F_{m+1}^2-F_mF_{m+1}-F_m^2=(-1)^m.$$
Si \(m=2k\) es par, el lado derecho vale \(1\), así que
$$F_{2k+1}^2-F_{2k}F_{2k+1}-F_{2k}^2=1.$$
Al dividir entre \(F_{2k+1}^2\) queda
$$1-x_k-x_k^2=\frac{1}{F_{2k+1}^2}.$$
Al sustituir en la función generadora obtenemos
$$A_F(x_k)=\frac{F_{2k}/F_{2k+1}}{1/F_{2k+1}^2}=F_{2k}F_{2k+1}.$$
Por tanto, cada producto \(F_{2k}F_{2k+1}\) es realmente una pepita dorada, y además proviene del valor racional explícito \(x_k=F_{2k}/F_{2k+1}\).
Si el discriminante es un cuadrado, escribimos
$$m^2=5n^2+2n+1.$$
Multiplicar por 5 y completar el cuadrado produce la ecuación de tipo Pell
$$5m^2-(5n+1)^2=4,$$
o, de forma equivalente,
$$(5n+1)^2-5m^2=-4.$$
Esta es exactamente la forma de la identidad clásica entre números de Lucas y Fibonacci,
$$L_t^2-5F_t^2=4(-1)^t.$$
Para \(t\) impar se obtiene \(L_t^2-5F_t^2=-4\), de modo que los índices impares ya generan soluciones de la misma ecuación diofántica. Entre esos índices impares, la condición \(5n+1\equiv 1\pmod 5\) selecciona \(t=4k+1\). Por ello, las soluciones admisibles cumplen
$$m=F_{4k+1},\qquad 5n+1=L_{4k+1}.$$
Usando la identidad
$$L_{4k+1}=5F_{2k}F_{2k+1}+1,$$
se deduce
$$n=F_{2k}F_{2k+1}.$$
En consecuencia, la familia construida en la subsección anterior es completa: las pepitas doradas son exactamente los productos de términos consecutivos de Fibonacci con índices \(2k\) y \(2k+1\).
Tomemos \(k=2\). Entonces
$$x=\frac{F_4}{F_5}=\frac{3}{5}.$$
La identidad anterior da
$$1-\frac{3}{5}-\left(\frac{3}{5}\right)^2=\frac{1}{25},$$
así que
$$A_F\left(\frac{3}{5}\right)=\frac{3/5}{1/25}=15.$$
Esa es la segunda pepita dorada. La siguiente aparece con \(k=3\): \(x=8/13\) y
$$A_F\left(\frac{8}{13}\right)=8\cdot 13=104.$$
Para el término pedido se toma \(k=15\), lo que produce \(F_{30}F_{31}=1120149658760\).
Las implementaciones en C++, Python y Java no prueban muchos valores racionales de \(x\), ni resuelven numéricamente la ecuación de tipo Pell. Empiezan directamente desde la forma cerrada demostrada
$$N_k=F_{2k}F_{2k+1},$$
de modo que para la decimoquinta pepita solo hacen falta \(F_{30}\) y \(F_{31}\).
La implementación mantiene dos números consecutivos de Fibonacci y en cada paso los sustituye por el siguiente par consecutivo. El invariante del bucle es simple: al terminar el paso \(i\), el par almacenado es \(F_{i-1}\) y \(F_i\). Partiendo de \(F_0=0\) y \(F_1=1\), al iterar hasta \(i=31\) se obtiene exactamente \((F_{30},F_{31})\).
Una vez disponibles esos dos valores, la respuesta es su producto. Una implementación también verifica el caso pequeño conocido \(N_3=104\) antes de imprimir el término solicitado, en concordancia con el ejemplo desarrollado. Python y Java usan enteros de precisión arbitraria; la versión en C++ emplea un entero ancho de tamaño fijo, y la decimoquinta pepita sigue entrando sin problema.
Para un índice general \(k\), el algoritmo calcula números de Fibonacci hasta \(F_{2k+1}\), por lo que el tiempo de ejecución es \(O(k)\). El espacio auxiliar es \(O(1)\) aparte del almacenamiento de los propios enteros, ya que solo se conservan simultáneamente una cantidad constante de valores de Fibonacci.
En este problema concreto, con \(k=15\), el trabajo efectivo es mínimo: 30 actualizaciones de Fibonacci y una multiplicación final. Lo difícil es la derivación matemática; la ejecución es prácticamente constante.
斐波那契生成函数为
$$A_F(x)=\sum_{k=1}^{\infty}F_kx^k=\frac{x}{1-x-x^2}.$$
所谓“金块”，是指该级数在某个有理数 \(x\) 处取得的正整数值。第 137 题要求求出第 15 个这样的整数。实现所依赖的核心结论是
$$N_k=F_{2k}F_{2k+1}\qquad (k\ge 1),$$
因此所求答案就是
$$N_{15}=F_{30}F_{31}=832040\cdot 1346269=1120149658760.$$
真正困难的部分不是最后那次乘法，而是说明生成函数的整数取值为什么恰好落在一个非常刚性的斐波那契模式上。一旦这个结构被识别出来，问题就不再是对许多有理数 \(x\) 逐个试探，而是直接定位到一个带下标的斐波那契乘积。
设级数的值为整数 \(n\)，也就是 \(A_F(x)=n\)。那么有
$$\frac{x}{1-x-x^2}=n,$$
整理得到
$$nx^2+(n+1)x-n=0.$$
与题意相关的是它的正根：
$$x=\frac{-(n+1)+\sqrt{5n^2+2n+1}}{2n}.$$
因此，若 \(x\) 是有理数，则判别式
$$5n^2+2n+1$$
必须是完全平方数。原问题于是被转化为关于 \(n\) 的一个丢番图条件。
现在引入一组有理数
$$x_k=\frac{F_{2k}}{F_{2k+1}}.$$
把 Cassini 恒等式改写一下，可得
$$F_{m+1}^2-F_mF_{m+1}-F_m^2=(-1)^m.$$
当 \(m=2k\) 为偶数时，右边等于 \(1\)，于是
$$F_{2k+1}^2-F_{2k}F_{2k+1}-F_{2k}^2=1.$$
再除以 \(F_{2k+1}^2\)，得到
$$1-x_k-x_k^2=\frac{1}{F_{2k+1}^2}.$$
把它代回生成函数：
$$A_F(x_k)=\frac{F_{2k}/F_{2k+1}}{1/F_{2k+1}^2}=F_{2k}F_{2k+1}.$$
这说明每一个乘积 \(F_{2k}F_{2k+1}\) 都确实是金块，而且它对应的有理输入也完全显式：
$$x_k=\frac{F_{2k}}{F_{2k+1}}.$$
如果判别式是平方数，就写成
$$m^2=5n^2+2n+1.$$
乘以 5 并配方后得到 Pell 型方程
$$5m^2-(5n+1)^2=4,$$
等价地也可写成
$$(5n+1)^2-5m^2=-4.$$
这恰好与 Lucas 数和 Fibonacci 数之间的经典恒等式同型：
$$L_t^2-5F_t^2=4(-1)^t.$$
当 \(t\) 为奇数时，上式变成 \(L_t^2-5F_t^2=-4\)，也就是说，奇数下标的 Lucas/Fibonacci 对自然给出了同一丢番图方程的解。再加上 \(5n+1\equiv 1\pmod 5\) 这个整除条件，就会筛选出 \(t=4k+1\)。于是可行解满足
$$m=F_{4k+1},\qquad 5n+1=L_{4k+1}.$$
再利用标准恒等式
$$L_{4k+1}=5F_{2k}F_{2k+1}+1,$$
便得到
$$n=F_{2k}F_{2k+1}.$$
因此，上一小节构造出的那一族并不是一部分解，而是全部解：所有金块恰好就是下标为 \(2k\) 与 \(2k+1\) 的相邻斐波那契数之积。
取 \(k=2\)。这时
$$x=\frac{F_4}{F_5}=\frac{3}{5}.$$
由上面的恒等式可知
$$1-\frac{3}{5}-\left(\frac{3}{5}\right)^2=\frac{1}{25},$$
所以
$$A_F\left(\frac{3}{5}\right)=\frac{3/5}{1/25}=15.$$
这就是第二个金块。下一项对应 \(k=3\)：此时 \(x=8/13\)，并且
$$A_F\left(\frac{8}{13}\right)=8\cdot 13=104.$$
题目要求的是 \(k=15\) 的情况，因此答案为 \(F_{30}F_{31}=1120149658760\)。
C++、Python 和 Java 的实现都不会枚举候选有理数 \(x\)，也不会数值求解 Pell 型方程。它们直接从已经证明的闭式出发：
$$N_k=F_{2k}F_{2k+1},$$
所以第 15 个金块只需要 \(F_{30}\) 和 \(F_{31}\)。
实现中始终维护两个相邻的斐波那契数，并在每一步把它们推进到下一对。循环不变量非常清楚：完成第 \(i\) 步后，保存的两个数恰好是 \(F_{i-1}\) 和 \(F_i\)。从 \(F_0=0\)、\(F_1=1\) 出发，一直迭代到 \(i=31\)，最后得到的正是 \((F_{30},F_{31})\)。
一旦这两个数到手，答案就是它们的乘积。其中一个实现还会在输出目标项之前验证一个已知的小检查点 \(N_3=104\)，这与上面的例子完全一致。Python 和 Java 使用任意精度整数；C++ 使用固定宽度但足够大的整数类型，而第 15 个金块远没有超出它的范围。
对一般的下标 \(k\) 而言，算法需要把斐波那契数推进到 \(F_{2k+1}\)，因此时间复杂度是 \(O(k)\)。除去整数本身所占的存储外，额外空间复杂度为 \(O(1)\)，因为任意时刻只保留常数个斐波那契值。
对本题的固定目标 \(k=15\) 来说，实际执行量非常小：30 次斐波那契更新和 1 次乘法。真正需要思考的是推导过程，而不是运行成本。
Производящая функция Фибоначчи имеет вид
$$A_F(x)=\sum_{k=1}^{\infty}F_kx^k=\frac{x}{1-x-x^2}.$$
Золотой самородок в этой задаче — это положительное целое значение ряда при некотором рациональном \(x\). В задаче 137 нужно найти 15-е такое число. Ключевой факт, на котором основаны реализации, таков:
$$N_k=F_{2k}F_{2k+1}\qquad (k\ge 1),$$
поэтому искомое значение равно
$$N_{15}=F_{30}F_{31}=832040\cdot 1346269=1120149658760.$$
Трудность задачи не в последнем умножении, а в том, чтобы понять, почему целочисленные значения производящей функции образуют очень жесткую фибоначчиеву структуру. После этого задача перестает быть поиском по множеству рациональных \(x\) и сводится к одному индексированному произведению.
Пусть значение ряда равно целому числу \(n\), то есть \(A_F(x)=n\). Тогда
$$\frac{x}{1-x-x^2}=n,$$
и после преобразования получаем
$$nx^2+(n+1)x-n=0.$$
Нужный корень — положительный:
$$x=\frac{-(n+1)+\sqrt{5n^2+2n+1}}{2n}.$$
Следовательно, \(x\) может быть рациональным только в том случае, если дискриминант
$$5n^2+2n+1$$
является точным квадратом. Исходная задача тем самым превращается в диофантово условие на \(n\).
Рассмотрим рациональные числа
$$x_k=\frac{F_{2k}}{F_{2k+1}}.$$
Переписанная тождественная формула Кассини дает
$$F_{m+1}^2-F_mF_{m+1}-F_m^2=(-1)^m.$$
Если \(m=2k\) четно, правая часть равна \(1\), и потому
$$F_{2k+1}^2-F_{2k}F_{2k+1}-F_{2k}^2=1.$$
После деления на \(F_{2k+1}^2\) получаем
$$1-x_k-x_k^2=\frac{1}{F_{2k+1}^2}.$$
Подстановка в производящую функцию приводит к формуле
$$A_F(x_k)=\frac{F_{2k}/F_{2k+1}}{1/F_{2k+1}^2}=F_{2k}F_{2k+1}.$$
Значит, каждое произведение \(F_{2k}F_{2k+1}\) действительно является золотым самородком, причем соответствующее рациональное значение тоже известно явно: \(x_k=F_{2k}/F_{2k+1}\).
Если дискриминант — полный квадрат, запишем
$$m^2=5n^2+2n+1.$$
Умножение на 5 и выделение квадрата дают уравнение типа Пелля
$$5m^2-(5n+1)^2=4,$$
или, что то же самое,
$$(5n+1)^2-5m^2=-4.$$
Это в точности совпадает по форме со стандартным тождеством для чисел Лукаса и Фибоначчи,
$$L_t^2-5F_t^2=4(-1)^t.$$
Для нечетных \(t\) оно превращается в \(L_t^2-5F_t^2=-4\), то есть пары из нечетных индексов уже дают решения того же диофантова уравнения. Среди этих нечетных индексов условие \(5n+1\equiv 1\pmod 5\) выбирает именно \(t=4k+1\). Поэтому допустимые решения имеют вид
$$m=F_{4k+1},\qquad 5n+1=L_{4k+1}.$$
Остается воспользоваться стандартной формулой
$$L_{4k+1}=5F_{2k}F_{2k+1}+1,$$
после чего получаем
$$n=F_{2k}F_{2k+1}.$$
Значит, построенное выше семейство не просто дает бесконечно много самородков, а перечисляет их все: это именно произведения соседних чисел Фибоначчи с индексами \(2k\) и \(2k+1\).
Возьмем \(k=2\). Тогда
$$x=\frac{F_4}{F_5}=\frac{3}{5}.$$
Из приведенной выше формулы следует
$$1-\frac{3}{5}-\left(\frac{3}{5}\right)^2=\frac{1}{25},$$
и потому
$$A_F\left(\frac{3}{5}\right)=\frac{3/5}{1/25}=15.$$
Это второй золотой самородок. Следующий получается при \(k=3\): \(x=8/13\), а
$$A_F\left(\frac{8}{13}\right)=8\cdot 13=104.$$
Для требуемого члена надо взять \(k=15\), что дает \(F_{30}F_{31}=1120149658760\).
Реализации на C++, Python и Java не перебирают рациональные кандидаты \(x\) и не решают уравнение типа Пелля численно. Они сразу используют доказанную замкнутую формулу
$$N_k=F_{2k}F_{2k+1},$$
поэтому для 15-го самородка им нужны только \(F_{30}\) и \(F_{31}\).
В реализации хранятся два соседних числа Фибоначчи, и на каждом шаге эта пара сдвигается к следующей. Инвариант цикла прост: после завершения шага \(i\) в памяти находятся \(F_{i-1}\) и \(F_i\). Если начать с \(F_0=0\) и \(F_1=1\), то после итерации до \(i=31\) получится ровно пара \((F_{30},F_{31})\).
Когда эти два значения уже вычислены, ответом служит их произведение. В одной из реализаций дополнительно проверяется известный малый случай \(N_3=104\), что совпадает с разобранным примером выше. Python и Java используют целые числа произвольной точности; в версии на C++ берется широкий фиксированный целочисленный тип, и 15-й самородок в него уверенно помещается.
Для общего индекса \(k\) алгоритм вычисляет числа Фибоначчи до \(F_{2k+1}\), поэтому время работы равно \(O(k)\). Дополнительная память составляет \(O(1)\), не считая хранения самих чисел, поскольку одновременно поддерживается только постоянное количество значений Фибоначчи.
В данной задаче с \(k=15\) фактическая работа совсем мала: 30 обновлений пары Фибоначчи и одно умножение. Сложность скрыта в выводе формулы, а не в исполнении программы.
دالة التوليد الخاصة بفيبوناتشي هي
$$A_F(x)=\sum_{k=1}^{\infty}F_kx^k=\frac{x}{1-x-x^2}.$$
تسمى القيمة الصحيحة الموجبة التي تأخذها هذه السلسلة عند بعض القيم النسبية \(x\) باسم الشذرة الذهبية. في المسألة 137 نريد الشذرة الخامسة عشرة. الحقيقة الأساسية التي تعتمد عليها جميع التنفيذات هي
$$N_k=F_{2k}F_{2k+1}\qquad (k\ge 1),$$
ولذلك تكون القيمة المطلوبة
$$N_{15}=F_{30}F_{31}=832040\cdot 1346269=1120149658760.$$
الصعوبة الحقيقية ليست في الضرب النهائي، بل في تفسير لماذا تقع جميع القيم الصحيحة للدالة المولدة داخل نمط صارم تحكمه أعداد فيبوناتشي. بعد كشف هذا البناء، تختفي الحاجة إلى تجربة كثير من القيم النسبية لـ \(x\)، ويتحول السؤال إلى حاصل ضرب واحد محدد بالفهرس.
لنفرض أن قيمة السلسلة هي عدد صحيح موجب \(n\)، أي \(A_F(x)=n\). عندئذ
$$\frac{x}{1-x-x^2}=n,$$
ومنها نحصل على
$$nx^2+(n+1)x-n=0.$$
الجذر المهم هو الجذر الموجب:
$$x=\frac{-(n+1)+\sqrt{5n^2+2n+1}}{2n}.$$
إذن لا يمكن أن يكون \(x\) نسبيًا إلا إذا كان المميز
$$5n^2+2n+1$$
مربعًا كاملًا. وهكذا تتحول المسألة الأصلية إلى شرط ديوفانتي يتعلق بالعدد \(n\).
لنأخذ الآن الأعداد النسبية
$$x_k=\frac{F_{2k}}{F_{2k+1}}.$$
من إعادة كتابة متطابقة كاسيني نحصل على
$$F_{m+1}^2-F_mF_{m+1}-F_m^2=(-1)^m.$$
وعندما يكون \(m=2k\) زوجيًا يصبح الطرف الأيمن مساويًا لـ \(1\)، ومن ثم
$$F_{2k+1}^2-F_{2k}F_{2k+1}-F_{2k}^2=1.$$
وبالقسمة على \(F_{2k+1}^2\) نحصل على
$$1-x_k-x_k^2=\frac{1}{F_{2k+1}^2}.$$
وعند التعويض في دالة التوليد نجد أن
$$A_F(x_k)=\frac{F_{2k}/F_{2k+1}}{1/F_{2k+1}^2}=F_{2k}F_{2k+1}.$$
وبذلك يكون كل حاصل ضرب من الشكل \(F_{2k}F_{2k+1}\) شذرة ذهبية فعلًا، كما أن القيمة النسبية المقابلة له معروفة صراحة، وهي \(x_k=F_{2k}/F_{2k+1}\).
إذا كان المميز مربعًا كاملًا، فلنكتب
$$m^2=5n^2+2n+1.$$
وبعد الضرب في 5 وإكمال المربع نحصل على معادلة من نمط بيل:
$$5m^2-(5n+1)^2=4,$$
أو بشكل مكافئ
$$(5n+1)^2-5m^2=-4.$$
وهذا يطابق تمامًا الصورة المعروفة في العلاقة بين أعداد لوكاس وأعداد فيبوناتشي:
$$L_t^2-5F_t^2=4(-1)^t.$$
عندما يكون \(t\) فرديًا تصبح هذه العلاقة \(L_t^2-5F_t^2=-4\)، أي إن الفهارس الفردية تعطي حلولًا للمعادلة الديوفانتية نفسها. ومن بين هذه الفهارس الفردية، يفرض الشرط \(5n+1\equiv 1\pmod 5\) أن يكون \(t=4k+1\). لذلك تحقق الحلول المقبولة
$$m=F_{4k+1},\qquad 5n+1=L_{4k+1}.$$
وباستخدام المتطابقة القياسية
$$L_{4k+1}=5F_{2k}F_{2k+1}+1,$$
نصل إلى
$$n=F_{2k}F_{2k+1}.$$
إذن فالعائلة التي بُنيت في الفقرة السابقة ليست مجرد أمثلة كثيرة، بل هي الوصف الكامل لجميع الشذرات الذهبية: إنها بالضبط حواصل ضرب عددين متتاليين من فيبوناتشي عند الفهرسين \(2k\) و\(2k+1\).
لنأخذ \(k=2\). عندها
$$x=\frac{F_4}{F_5}=\frac{3}{5}.$$
ومن المتطابقة السابقة نحصل على
$$1-\frac{3}{5}-\left(\frac{3}{5}\right)^2=\frac{1}{25},$$
ومن ثم
$$A_F\left(\frac{3}{5}\right)=\frac{3/5}{1/25}=15.$$
وهذه هي الشذرة الذهبية الثانية. أما الحالة التالية فتأتي عند \(k=3\): حيث \(x=8/13\) ويكون
$$A_F\left(\frac{8}{13}\right)=8\cdot 13=104.$$
أما المطلوب في المسألة فينتج من \(k=15\)، وبالتالي تكون القيمة \(F_{30}F_{31}=1120149658760\).
تنفيذات C++ وPython وJava لا تبحث بين قيم نسبية مرشحة لـ \(x\)، ولا تحل معادلة بيل عدديًا. بل تبدأ مباشرة من الصيغة المغلقة المثبتة
$$N_k=F_{2k}F_{2k+1},$$
ولذلك لا تحتاج الشذرة الخامسة عشرة إلا إلى \(F_{30}\) و\(F_{31}\).
تحتفظ الشيفرة دائمًا بعددين متتاليين من فيبوناتشي، ثم تستبدلهما في كل خطوة بالزوج التالي. ثابت الحلقة واضح: بعد إكمال الخطوة \(i\) يكون الزوج المخزن هو \(F_{i-1}\) و\(F_i\). وبالبدء من \(F_0=0\) و\(F_1=1\)، فإن التقدم حتى \(i=31\) يترك الزوج \((F_{30},F_{31})\) بالضبط.
بعد الوصول إلى هذين العددين، تكون الإجابة هي حاصل ضربهما. أحد التنفيذات يضيف أيضًا نقطة تحقق صغيرة هي \(N_3=104\) قبل طباعة القيمة المطلوبة، وهذا يوافق المثال المحسوب أعلاه. في Python وJava تُستخدم أعداد صحيحة ذات دقة غير محدودة، أما في C++ فتُستخدم بنية عددية صحيحة عريضة وثابتة، والقيمة الخامسة عشرة ما زالت ضمن مجالها بسهولة.
للفهرس العام \(k\)، تحسب الخوارزمية أعداد فيبوناتشي حتى \(F_{2k+1}\)، ولذلك يكون الزمن \(O(k)\). أما الذاكرة الإضافية فهي \(O(1)\) باستثناء تخزين الأعداد نفسها، لأن التنفيذ يحتفظ بعدد ثابت فقط من قيم فيبوناتشي في كل لحظة.
وفي هذه المسألة بالذات حيث \(k=15\)، يكون العمل الفعلي صغيرًا جدًا: 30 تحديثًا لزوج فيبوناتشي وعملية ضرب واحدة. الصعوبة كلها في الاشتقاق الرياضي، لا في زمن التنفيذ.