Let \(G_1=1\), \(G_2=4\), and \(G_k=G_{k-1}+G_{k-2}\) for \(k\ge 3\). The generating function is
$$A_G(x)=\sum_{k=1}^{\infty} G_k x^k.$$
A "golden nugget" is a positive integer \(n\) for which the equation \(A_G(x)=n\) has a positive rational solution \(x\). The task is to add the first 30 such integers.
The crucial point is that this is not a search over rational numbers. After simplifying the generating function, the nugget condition becomes a Pell-type Diophantine equation, and the implementations generate all relevant solutions from a small set of seed pairs.
The sequence begins \(1,4,5,9,14,23,\dots\), so the same Fibonacci recurrence is present, but the initial values are different. That changes the numerator of the generating function and, later, the constant term in the Pell equation.
Write \(A_G(x)=x+4x^2+\sum_{k=3}^{\infty} G_k x^k\). Using \(G_k=G_{k-1}+G_{k-2}\),
$$A_G(x)=x+4x^2+\sum_{k=3}^{\infty}(G_{k-1}+G_{k-2})x^k.$$
Reindex the two sums:
$$A_G(x)=x+4x^2+x\sum_{j=2}^{\infty}G_j x^j+x^2\sum_{j=1}^{\infty}G_j x^j=x+4x^2+x(A_G(x)-x)+x^2A_G(x).$$
Therefore
$$A_G(x)(1-x-x^2)=x+3x^2,$$
so the generating function is
$$\boxed{A_G(x)=\frac{x+3x^2}{1-x-x^2}.}$$
Set \(A_G(x)=n\) with \(n\in \mathbb Z_{>0}\). Then
$$n(1-x-x^2)=x+3x^2,$$
which rearranges to
$$\boxed{(n+3)x^2+(n+1)x-n=0.}$$
This quadratic has a rational root exactly when its discriminant is a perfect square:
$$\Delta=(n+1)^2+4n(n+3)=5n^2+14n+1=m^2.$$
Conversely, if \(m^2=5n^2+14n+1\), then
$$x=\frac{-\,(n+1)+m}{2(n+3)}$$
is rational, and it is positive because \(m^2-(n+1)^2=4n(n+3)>0\).
Multiply the discriminant identity by 5:
$$25n^2+70n+5=5m^2.$$
Now complete the square:
$$25n^2+70n+49-44=5m^2,$$
so
$$\boxed{(5n+7)^2-5m^2=44.}$$
If we define
$$U=5n+7,\qquad V=m,$$
then every nugget gives a positive solution of
$$\boxed{U^2-5V^2=44,}$$
and every solution with \(U>7\) and \(U-7\) divisible by 5 gives back a nugget through
$$\boxed{n=\frac{U-7}{5}.}$$
The unit \(9+4\sqrt5\) has norm 1, because \(9^2-5\cdot4^2=1\). Multiplying \(U+V\sqrt5\) by this unit sends one solution of \(U^2-5V^2=44\) to another:
$$U'=(9U+20V),\qquad V'=(4U+9V).$$
A direct expansion shows the invariant is preserved:
$$U'^2-5V'^2=U^2-5V^2.$$
For the positive solution set relevant here, the branches can be represented by the six minimal positive seeds
$$(7,1),\ (8,2),\ (13,5),\ (17,7),\ (32,14),\ (43,19).$$
Not every iterate is a nugget. The recurrence preserves the Pell norm, but it does not force \(U\equiv 7 \pmod 5\). That is why the implementations generate each branch and keep only those states with \(U>7\) and \(U-7\) divisible by 5. The first accepted nuggets are
$$2,\ 5,\ 21,\ 42,\ 152,\ 296,\ 1050,\ 2037,\dots$$
The seed \((7,1)\) itself corresponds to \(n=0\), so it is not a golden nugget, but its later iterates still belong to a valid branch and eventually produce positive nuggets.
Take \((U,V)=(17,7)\). It satisfies
$$17^2-5\cdot 7^2=289-245=44,$$
and because \(17-7\) is divisible by 5, it yields
$$n=\frac{17-7}{5}=2.$$
Then the quadratic becomes
$$5x^2+3x-2=0,$$
whose positive rational root is
$$x=\frac{-3+7}{10}=\frac25.$$
So \(A_G(2/5)=2\), and 2 is indeed a golden nugget. If we apply the Pell recurrence once, we get \((293,131)\); the invariant \(U^2-5V^2=44\) still holds, but \(293-7\) is not divisible by 5, so that iterate is not accepted. This is exactly why the code keeps the recurrence and the divisibility test separate.
The C++, Python, and Java implementations hard-code the six seed pairs above and iterate the recurrence
$$U' = 9U+20V,\qquad V' = 4U+9V.$$
Each family is advanced a fixed number of times. Whenever an iterate satisfies \(U>7\) and \(U-7\) divisible by 5, the implementation converts it to a nugget with \(n=(U-7)/5\) and inserts it into an ordered collection. Using a set is a simple way to deduplicate values and keep them sorted for the final sum.
After all branches have been generated, the implementations read the nuggets in increasing order and add the first 30 of them. One implementation also allows a different requested count and includes a small checkpoint that the first five nuggets sum to 222, but the underlying mathematics is the same in all three languages.
The fixed iteration depth is more than enough because the branch growth factor is \(9+4\sqrt5\approx 17.944\), so the values explode exponentially. A few dozen steps per seed already produce far more than 30 valid nuggets.
As written, the algorithm is essentially constant-time. There are 6 seed families and 50 recurrence steps per family, so fewer than 300 Pell updates are performed, followed by insertion into a small ordered set and extraction of the first 30 values.
If one abstracts away from the hard-coded bounds, the cost is linear in the number of generated Pell iterates, with an additional logarithmic factor if an ordered set is used for deduplication and sorting. For the actual problem instance, both time and memory usage are negligible.
Es sei \(G_1=1\), \(G_2=4\) und \(G_k=G_{k-1}+G_{k-2}\) für \(k\ge 3\). Die erzeugende Funktion lautet
$$A_G(x)=\sum_{k=1}^{\infty} G_k x^k.$$
Ein "golden nugget" ist eine positive ganze Zahl \(n\), für die die Gleichung \(A_G(x)=n\) eine positive rationale Lösung \(x\) besitzt. Gesucht ist die Summe der ersten 30 solcher Zahlen.
Der Kern der Aufgabe ist keine Suche über rationale Zahlen. Nach der Umformung der erzeugenden Funktion bleibt eine Pell-artige diophantische Gleichung übrig, und die Implementierungen erzeugen alle relevanten Lösungen aus wenigen Startpaaren.
Die Folge beginnt mit \(1,4,5,9,14,23,\dots\). Die Rekursion ist also dieselbe wie bei Fibonacci, aber die Anfangswerte sind verändert. Genau das ändert den Zähler der erzeugenden Funktion und später die Konstante in der Pell-Gleichung.
Schreibe \(A_G(x)=x+4x^2+\sum_{k=3}^{\infty} G_k x^k\). Mit \(G_k=G_{k-1}+G_{k-2}\) folgt
$$A_G(x)=x+4x^2+\sum_{k=3}^{\infty}(G_{k-1}+G_{k-2})x^k.$$
Nach Umindizierung erhält man
$$A_G(x)=x+4x^2+x\sum_{j=2}^{\infty}G_j x^j+x^2\sum_{j=1}^{\infty}G_j x^j=x+4x^2+x(A_G(x)-x)+x^2A_G(x).$$
Daraus folgt
$$A_G(x)(1-x-x^2)=x+3x^2,$$
also
$$\boxed{A_G(x)=\frac{x+3x^2}{1-x-x^2}.}$$
Setzt man \(A_G(x)=n\) mit \(n\in \mathbb Z_{>0}\), so erhält man
$$n(1-x-x^2)=x+3x^2,$$
also
$$\boxed{(n+3)x^2+(n+1)x-n=0.}$$
Eine rationale Wurzel existiert genau dann, wenn die Diskriminante ein Quadrat ist:
$$\Delta=(n+1)^2+4n(n+3)=5n^2+14n+1=m^2.$$
Umgekehrt liefert jedes \(m\) mit \(m^2=5n^2+14n+1\) die rationale Lösung
$$x=\frac{-\,(n+1)+m}{2(n+3)},$$
und diese ist positiv, weil \(m^2-(n+1)^2=4n(n+3)>0\).
Multipliziert man die Diskriminantenbedingung mit 5, so ergibt sich
$$25n^2+70n+5=5m^2.$$
Durch Quadratergänzung folgt
$$25n^2+70n+49-44=5m^2,$$
also
$$\boxed{(5n+7)^2-5m^2=44.}$$
Mit
$$U=5n+7,\qquad V=m$$
wird daraus
$$\boxed{U^2-5V^2=44.}$$
Jedes Nugget liefert also eine positive Lösung dieser Normgleichung, und jede Lösung mit \(U>7\) und \(U-7\) als Vielfachem von 5 gibt über
$$\boxed{n=\frac{U-7}{5}}$$
wieder ein Nugget zurück.
Die Einheit \(9+4\sqrt5\) hat Norm 1, denn \(9^2-5\cdot4^2=1\). Multipliziert man \(U+V\sqrt5\) mit dieser Einheit, erhält man wieder eine Lösung von \(U^2-5V^2=44\):
$$U'=(9U+20V),\qquad V'=(4U+9V).$$
Direktes Ausmultiplizieren zeigt
$$U'^2-5V'^2=U^2-5V^2.$$
Für die hier relevanten positiven Lösungen genügen sechs minimale Repräsentanten:
$$(7,1),\ (8,2),\ (13,5),\ (17,7),\ (32,14),\ (43,19).$$
Nicht jeder Iterationsschritt erzeugt ein Nugget. Die Rekurrenz erhält zwar die Pell-Norm, erzwingt aber nicht die Teilbarkeitsbedingung \(U-7\equiv 0 \pmod 5\). Deshalb erzeugen die Implementierungen jede Bahn vollständig und akzeptieren nur Zustände mit \(U>7\) und \(U-7\) als Vielfachem von 5. Die ersten akzeptierten Nuggets sind
$$2,\ 5,\ 21,\ 42,\ 152,\ 296,\ 1050,\ 2037,\dots$$
Das Startpaar \((7,1)\) liefert selbst \(n=0\) und ist daher noch kein golden nugget, gehört aber zu einem echten Lösungszweig, der später positive Nuggets erzeugt.
Nimm \((U,V)=(17,7)\). Dann gilt
$$17^2-5\cdot 7^2=289-245=44,$$
und weil \(17-7\) durch 5 teilbar ist, folgt
$$n=\frac{17-7}{5}=2.$$
Die zugehörige quadratische Gleichung lautet
$$5x^2+3x-2=0,$$
mit positiver rationaler Lösung
$$x=\frac{-3+7}{10}=\frac25.$$
Also ist \(A_G(2/5)=2\). Wendet man die Pell-Rekurrenz einmal an, so entsteht \((293,131)\). Die Invariante \(U^2-5V^2=44\) bleibt erhalten, aber \(293-7\) ist nicht durch 5 teilbar; genau deshalb trennt der Code die Rekurrenz von der Filterbedingung.
Die C++-, Python- und Java-Implementierungen hinterlegen die sechs Startpaare und iterieren die Rekurrenz
$$U' = 9U+20V,\qquad V' = 4U+9V.$$
Jede Bahn wird eine feste Anzahl von Schritten weitergeführt. Immer wenn \(U>7\) und \(U-7\) durch 5 teilbar ist, wird \(n=(U-7)/5\) gebildet und in eine geordnete Sammlung eingefügt. Eine Menge ist hier praktisch, weil sie Duplikate entfernt und die Werte zugleich sortiert hält.
Nach der Erzeugung aller Bahnen lesen die Implementierungen die Nuggets in aufsteigender Reihenfolge aus und addieren die ersten 30. Eine der drei Fassungen erlaubt zusätzlich eine andere gewünschte Anzahl und enthält einen kleinen Kontrolltest, dass die ersten fünf Nuggets zusammen 222 ergeben; die zugrunde liegende Mathematik ist jedoch in allen drei Sprachen identisch.
Die feste Iterationstiefe genügt locker, weil der Wachstumsfaktor \(9+4\sqrt5\approx 17{,}944\) ist. Schon wenige Dutzend Schritte pro Startpaar erzeugen deutlich mehr als 30 gültige Nuggets.
In der gegebenen Form ist der Algorithmus praktisch konstant schnell. Es gibt 6 Startzweige und 50 Rekurrenzschritte pro Zweig, also weniger als 300 Pell-Updates, gefolgt von Einfügungen in eine kleine geordnete Menge und der Entnahme der ersten 30 Werte.
Abstrahiert man von den fest eingebauten Grenzen, so ist der Aufwand linear in der Zahl der erzeugten Pell-Iterationen, mit einem zusätzlichen logarithmischen Faktor bei Verwendung einer geordneten Menge für Deduplizierung und Sortierung. Für die konkrete Aufgabe sind Laufzeit und Speicherbedarf vernachlässigbar.
\(G_1=1\), \(G_2=4\) ve \(k\ge 3\) için \(G_k=G_{k-1}+G_{k-2}\) olsun. Üretici fonksiyon
$$A_G(x)=\sum_{k=1}^{\infty} G_k x^k$$
şeklindedir. "Golden nugget" denilen şey, \(A_G(x)=n\) denkleminin pozitif rasyonel bir \(x\) çözümü olduğu pozitif tam sayı \(n\)'dir. İstenen, ilk 30 böyle sayının toplamıdır.
Esas fikir rasyonel sayılar üzerinde kör arama yapmak değildir. Üretici fonksiyon sadeleştirildiğinde koşul bir Pell tipi Diofant denkleme dönüşür; uygulamalar da ilgili bütün çözümleri birkaç başlangıç çiftinden üretir.
Dizi \(1,4,5,9,14,23,\dots\) diye başlar. Yani Fibonacci tipi yineleme aynıdır, fakat başlangıç değerleri farklıdır. Problem 140'ın karakteri tam burada ortaya çıkar: üreteç fonksiyonunun payı değişir, bunun sonucu olarak Pell denklemindeki sabit de değişir.
\(A_G(x)=x+4x^2+\sum_{k=3}^{\infty} G_k x^k\) yazalım. \(G_k=G_{k-1}+G_{k-2}\) olduğundan
$$A_G(x)=x+4x^2+\sum_{k=3}^{\infty}(G_{k-1}+G_{k-2})x^k.$$
İki toplamı yeniden indekslersek
$$A_G(x)=x+4x^2+x\sum_{j=2}^{\infty}G_j x^j+x^2\sum_{j=1}^{\infty}G_j x^j=x+4x^2+x(A_G(x)-x)+x^2A_G(x).$$
Buradan
$$A_G(x)(1-x-x^2)=x+3x^2$$
ve dolayısıyla
$$\boxed{A_G(x)=\frac{x+3x^2}{1-x-x^2}}$$
elde edilir.
\(A_G(x)=n\) yazarsak
$$n(1-x-x^2)=x+3x^2,$$
yani
$$\boxed{(n+3)x^2+(n+1)x-n=0.}$$
Bu ikinci dereceden denklemin rasyonel kökü olması için ayırtanın tam kare olması gerekir:
$$\Delta=(n+1)^2+4n(n+3)=5n^2+14n+1=m^2.$$
Tersine, \(m^2=5n^2+14n+1\) ise
$$x=\frac{-\,(n+1)+m}{2(n+3)}$$
rasyoneldir; ayrıca \(m^2-(n+1)^2=4n(n+3)>0\) olduğu için bu kök pozitiftir.
Ayırtan eşitliğini 5 ile çarpalım:
$$25n^2+70n+5=5m^2.$$
Kare tamamlarsak
$$25n^2+70n+49-44=5m^2,$$
yani
$$\boxed{(5n+7)^2-5m^2=44.}$$
\(U=5n+7\) ve \(V=m\) tanımlarıyla
$$\boxed{U^2-5V^2=44}$$
elde edilir. Böylece her golden nugget, normu 44 olan bu Pell tipi denklemde bir çözüme karşılık gelir. Ters yönde ise \(U>7\) ve \(U-7\) sayısı 5'e bölünebiliyorsa
$$\boxed{n=\frac{U-7}{5}}$$
ile tekrar nugget'a döneriz.
\(9+4\sqrt5\) sayısının normu 1'dir; çünkü \(9^2-5\cdot 4^2=1\). Bu yüzden \(U+V\sqrt5\) ile çarpıldığında \(U^2-5V^2=44\) normu korunur:
$$U'=(9U+20V),\qquad V'=(4U+9V).$$
Doğrudan açarsak
$$U'^2-5V'^2=U^2-5V^2$$
olduğunu görürüz. İlgili pozitif çözüm dalları şu altı en küçük başlangıç çiftiyle temsil edilebilir:
$$(7,1),\ (8,2),\ (13,5),\ (17,7),\ (32,14),\ (43,19).$$
Her yineleme adımı bir nugget vermez. Bu dönüşüm Pell normunu korur ama \(U-7\)'nin 5'e bölünebilir olmasını garanti etmez. Bu yüzden uygulamalar her dalı üretir, sonra yalnızca \(U>7\) ve \(U-7\equiv 0 \pmod 5\) olan durumları kabul eder. İlk kabul edilen nugget'lar şunlardır:
$$2,\ 5,\ 21,\ 42,\ 152,\ 296,\ 1050,\ 2037,\dots$$
\((7,1)\) çifti kendi başına \(n=0\) verdiği için golden nugget değildir; buna rağmen ait olduğu çözüm ailesi daha sonra pozitif nugget'lar üretir.
\((U,V)=(17,7)\) alalım. Bu çift
$$17^2-5\cdot 7^2=289-245=44$$
eşitliğini sağlar ve \(17-7\) sayısı 5'e bölündüğü için
$$n=\frac{17-7}{5}=2$$
bulunur. Karşılık gelen ikinci dereceden denklem
$$5x^2+3x-2=0$$
olur; pozitif rasyonel kök
$$x=\frac{-3+7}{10}=\frac25$$
şeklindedir. Yani \(A_G(2/5)=2\). Yinelemeyi bir kez uygularsak \((293,131)\) elde edilir. Bu noktada \(U^2-5V^2=44\) hâlâ doğrudur, fakat \(293-7\) 5'e bölünmez; kodun yineleme ile bölünebilirlik filtresini ayrı tutmasının nedeni budur.
C++, Python ve Java uygulamaları yukarıdaki altı başlangıç çiftini sabit olarak alır ve
$$U' = 9U+20V,\qquad V' = 4U+9V$$
yinelemesini uygular. Her aile belirli sayıda adım ilerletilir. Bir iterasyon \(U>7\) ve \(U-7\) sayısı 5'e tam bölünme koşulunu sağladığında, \(n=(U-7)/5\) hesaplanır ve sıralı bir koleksiyona eklenir. Küme yapısı hem olası tekrarları temizler hem de değerleri sıralı tutar.
Bütün aileler üretildikten sonra uygulamalar nugget'ları küçükten büyüğe okur ve ilk 30 tanesini toplar. Uygulamalardan biri farklı bir istenen adet de kabul eder ve ilk beş nugget toplamının 222 olduğunu kontrol eden küçük bir doğrulama içerir; fakat üç dilde de kullanılan matematik aynıdır.
Sabit iterasyon derinliği fazlasıyla yeterlidir; çünkü büyüme katsayısı \(9+4\sqrt5\approx 17.944\) olduğundan sayılar üstel biçimde büyür. Her tohum için birkaç düzine adım, 30 geçerli nugget elde etmek için yeter de artar.
Mevcut haliyle algoritma pratikte sabit zamanda çalışır. 6 tohum ailesi ve aile başına 50 yineleme vardır; yani 300'den az Pell güncellemesi yapılır. Bunun ardından küçük bir sıralı kümeye ekleme ve ilk 30 değeri alma işlemi gelir.
Sabit sınırları soyutlarsak maliyet, üretilen Pell iterasyonu sayısıyla doğrusal, sıralı küme kullanıldığı için de buna küçük bir logaritmik çarpan eklenmiş haldedir. Bu problem boyutunda hem zaman hem bellek maliyeti ihmal edilebilir düzeydedir.
Sea \(G_1=1\), \(G_2=4\) y \(G_k=G_{k-1}+G_{k-2}\) para \(k\ge 3\). Su función generadora es
$$A_G(x)=\sum_{k=1}^{\infty} G_k x^k.$$
Un "golden nugget" es un entero positivo \(n\) para el cual la ecuación \(A_G(x)=n\) tiene una solución racional positiva \(x\). El objetivo es sumar los primeros 30 valores de ese tipo.
La clave no es buscar racionales al azar. Al simplificar la función generadora, la condición del nugget se convierte en una ecuación diofántica de tipo Pell, y las implementaciones producen todas las soluciones relevantes a partir de unos pocos pares iniciales.
La sucesión empieza como \(1,4,5,9,14,23,\dots\). La recurrencia sigue siendo la de Fibonacci, pero los valores iniciales cambian. Ese detalle modifica el numerador de la función generadora y, más adelante, el término constante de la ecuación de Pell.
Escribimos \(A_G(x)=x+4x^2+\sum_{k=3}^{\infty} G_k x^k\). Usando \(G_k=G_{k-1}+G_{k-2}\),
$$A_G(x)=x+4x^2+\sum_{k=3}^{\infty}(G_{k-1}+G_{k-2})x^k.$$
Reindexando ambos sumandos,
$$A_G(x)=x+4x^2+x\sum_{j=2}^{\infty}G_j x^j+x^2\sum_{j=1}^{\infty}G_j x^j=x+4x^2+x(A_G(x)-x)+x^2A_G(x).$$
Por tanto,
$$A_G(x)(1-x-x^2)=x+3x^2,$$
y la forma cerrada es
$$\boxed{A_G(x)=\frac{x+3x^2}{1-x-x^2}.}$$
Si imponemos \(A_G(x)=n\) con \(n\in \mathbb Z_{>0}\), obtenemos
$$n(1-x-x^2)=x+3x^2,$$
es decir,
$$\boxed{(n+3)x^2+(n+1)x-n=0.}$$
Esta ecuación cuadrática tiene una raíz racional si y solo si su discriminante es un cuadrado perfecto:
$$\Delta=(n+1)^2+4n(n+3)=5n^2+14n+1=m^2.$$
Recíprocamente, si \(m^2=5n^2+14n+1\), entonces
$$x=\frac{-\,(n+1)+m}{2(n+3)}$$
es racional, y además es positivo porque \(m^2-(n+1)^2=4n(n+3)>0\).
Multiplicamos la identidad del discriminante por 5:
$$25n^2+70n+5=5m^2.$$
Al completar el cuadrado,
$$25n^2+70n+49-44=5m^2,$$
llegamos a
$$\boxed{(5n+7)^2-5m^2=44.}$$
Definiendo
$$U=5n+7,\qquad V=m,$$
la condición queda como
$$\boxed{U^2-5V^2=44.}$$
Así, cada nugget corresponde a una solución positiva de esa ecuación, y cualquier solución con \(U>7\) y \(U-7\) múltiplo de 5 produce un nugget mediante
$$\boxed{n=\frac{U-7}{5}.}$$
El número \(9+4\sqrt5\) tiene norma 1, porque \(9^2-5\cdot4^2=1\). Por eso, multiplicar \(U+V\sqrt5\) por esa unidad lleva una solución de \(U^2-5V^2=44\) a otra:
$$U'=(9U+20V),\qquad V'=(4U+9V).$$
Al expandir se ve que
$$U'^2-5V'^2=U^2-5V^2.$$
Las ramas positivas relevantes pueden representarse con las seis semillas mínimas
$$(7,1),\ (8,2),\ (13,5),\ (17,7),\ (32,14),\ (43,19).$$
No todos los iterados producen un nugget. La recurrencia conserva la norma de Pell, pero no obliga a que \(U-7\) sea divisible por 5. Por eso las implementaciones recorren cada rama y aceptan solo los estados con \(U>7\) y \(U-7\equiv 0 \pmod 5\). Los primeros nuggets que sobreviven al filtro son
$$2,\ 5,\ 21,\ 42,\ 152,\ 296,\ 1050,\ 2037,\dots$$
La semilla \((7,1)\) representa el caso \(n=0\), así que no es un nugget por sí misma, pero pertenece a una rama válida que más adelante sí genera valores positivos.
Tomemos \((U,V)=(17,7)\). Se cumple
$$17^2-5\cdot 7^2=289-245=44,$$
y como \(17-7\) es divisible por 5, obtenemos
$$n=\frac{17-7}{5}=2.$$
La ecuación cuadrática correspondiente es
$$5x^2+3x-2=0,$$
cuya raíz racional positiva es
$$x=\frac{-3+7}{10}=\frac25.$$
Así que \(A_G(2/5)=2\). Si aplicamos una vez la recurrencia de Pell, llegamos a \((293,131)\). La invariante \(U^2-5V^2=44\) sigue siendo cierta, pero \(293-7\) ya no es múltiplo de 5; por eso el código separa la recurrencia del filtro de divisibilidad.
Las implementaciones en C++, Python y Java fijan las seis semillas anteriores e iteran
$$U' = 9U+20V,\qquad V' = 4U+9V.$$
Cada familia avanza un número fijo de pasos. Cuando un iterado cumple \(U>7\) y \(U-7\) divisible por 5, se convierte en un nugget mediante \(n=(U-7)/5\) y se inserta en una colección ordenada. Usar un conjunto ordenado es una forma directa de eliminar duplicados y mantener los valores preparados para la suma final.
Después de generar todas las ramas, las implementaciones leen los nuggets en orden creciente y suman los primeros 30. Una de las tres versiones también permite cambiar la cantidad solicitada y contiene una comprobación de que los primeros cinco nuggets suman 222, pero la matemática central es la misma en los tres lenguajes.
La profundidad fija de iteración basta de sobra porque el factor de crecimiento es \(9+4\sqrt5\approx 17.944\). Unas pocas decenas de pasos por semilla ya producen muchas más de 30 soluciones válidas.
Tal como está escrito, el algoritmo es esencialmente de tiempo constante. Hay 6 familias iniciales y 50 pasos de recurrencia por familia, es decir, menos de 300 actualizaciones de Pell, seguidas por inserciones en un conjunto ordenado pequeño y la extracción de los primeros 30 valores.
Si se ignoran los límites fijados a mano, el coste es lineal en el número de iterados de Pell generados, con un factor logarítmico adicional si se usa un conjunto ordenado para deduplicar y ordenar. Para la instancia concreta del problema, tanto el tiempo como la memoria son insignificantes.
设 \(G_1=1\)、\(G_2=4\)，并且对 \(k\ge 3\) 有 \(G_k=G_{k-1}+G_{k-2}\)。它的生成函数为
$$A_G(x)=\sum_{k=1}^{\infty} G_k x^k$$
所谓“golden nugget”，就是使方程 \(A_G(x)=n\) 拥有正有理解 \(x\) 的正整数 \(n\)。题目要求把前 30 个这样的整数相加。
这道题真正有效的切入点不是去枚举有理数 \(x\)。把生成函数化简以后，条件会变成一个 Pell 型丢番图方程，而实现代码正是从少量起始解出发，把所有相关分支系统地生成出来。
这个数列开头是 \(1,4,5,9,14,23,\dots\)。递推关系和 Fibonacci 一样，但初值不同。正是这个差异，使得生成函数的分子发生变化，最后得到的 Pell 型方程也不是最常见的 \(=4\) 形式，而是一个右端为 44 的版本。
先写成
$$A_G(x)=x+4x^2+\sum_{k=3}^{\infty} G_k x^k$$
利用 \(G_k=G_{k-1}+G_{k-2}\)，得到
$$A_G(x)=x+4x^2+\sum_{k=3}^{\infty}(G_{k-1}+G_{k-2})x^k$$
把两部分重新换指标后，
$$A_G(x)=x+4x^2+x\sum_{j=2}^{\infty}G_j x^j+x^2\sum_{j=1}^{\infty}G_j x^j=x+4x^2+x(A_G(x)-x)+x^2A_G(x)$$
因此
$$A_G(x)(1-x-x^2)=x+3x^2$$
也就是
$$\boxed{A_G(x)=\frac{x+3x^2}{1-x-x^2}}$$
令 \(A_G(x)=n\)，其中 \(n\) 是正整数，则
$$n(1-x-x^2)=x+3x^2$$
整理成
$$\boxed{(n+3)x^2+(n+1)x-n=0}$$
这个二次方程有有理根，当且仅当判别式是完全平方：
$$\Delta=(n+1)^2+4n(n+3)=5n^2+14n+1=m^2$$
反过来，如果 \(m^2=5n^2+14n+1\)，那么
$$x=\frac{-\,(n+1)+m}{2(n+3)}$$
就是一个有理根；并且因为 \(m^2-(n+1)^2=4n(n+3)>0\)，所以这个根还是正的。
把判别式关系乘以 5：
$$25n^2+70n+5=5m^2$$
配方得到
$$25n^2+70n+49-44=5m^2$$
因此
$$\boxed{(5n+7)^2-5m^2=44}$$
令
$$U=5n+7,\qquad V=m$$
就得到
$$\boxed{U^2-5V^2=44}$$
于是每一个 nugget 都对应于这个方程的一个正整数解；反过来，只要某个解满足 \(U>7\) 且 \(U-7\) 能被 5 整除，就能通过
$$\boxed{n=\frac{U-7}{5}}$$
恢复出一个 nugget。
\(9+4\sqrt5\) 的范数是 1，因为 \(9^2-5\cdot4^2=1\)。所以把 \(U+V\sqrt5\) 乘上这个单位以后，新的点仍然满足同一个 Pell 型方程：
$$U'=(9U+20V),\qquad V'=(4U+9V)$$
直接展开就能验证
$$U'^2-5V'^2=U^2-5V^2$$
对本题需要的正整数解来说，可以用下面六个最小正种子来代表相关分支：
$$(7,1),\ (8,2),\ (13,5),\ (17,7),\ (32,14),\ (43,19)$$
并不是每一次递推都会得到 nugget。这个递推只保证 \(U^2-5V^2\) 不变，并不保证 \(U-7\) 一定是 5 的倍数。所以实现代码的策略是：沿着每条分支不断递推，然后只保留满足 \(U>7\) 且 \(U-7\equiv 0 \pmod 5\) 的状态。这样筛出来的前几个 nugget 是
$$2,\ 5,\ 21,\ 42,\ 152,\ 296,\ 1050,\ 2037,\dots$$
其中种子 \((7,1)\) 自身对应 \(n=0\)，因此它本身不是正 nugget，但它所在的分支后来仍会产生合法的正值。
取 \((U,V)=(17,7)\)。它满足
$$17^2-5\cdot 7^2=289-245=44$$
并且 \(17-7\) 能被 5 整除，所以
$$n=\frac{17-7}{5}=2$$
对应的二次方程是
$$5x^2+3x-2=0$$
它的正有理根为
$$x=\frac{-3+7}{10}=\frac25$$
因此 \(A_G(2/5)=2\)。如果把这个解再递推一步，会得到 \((293,131)\)。此时不变量 \(U^2-5V^2=44\) 仍然成立，但 \(293-7\) 不能被 5 整除，所以它不是一个 nugget。这也正好解释了为什么实现中“递推”和“整除筛选”是两个分开的步骤。
C++、Python 和 Java 三个实现都把上面的六个种子直接写入程序，然后反复应用
$$U' = 9U+20V,\qquad V' = 4U+9V$$
每条分支都前进固定次数。只要某次状态满足 \(U>7\) 且 \(U-7\) 能被 5 整除，就把它转换成 \(n=(U-7)/5\)，并放入一个有序集合。使用集合的好处是可以顺手去重，而且天然按从小到大的顺序保存结果。
所有分支都生成完以后，程序按升序读出这些 nugget，并把最小的前 30 个相加。其中一个实现还支持修改要取的项数，并加入了“前 5 个 nugget 之和等于 222”的小型校验；不过三种语言的核心数学完全一致。
之所以固定迭代 50 次就足够，是因为增长因子 \(9+4\sqrt5\approx 17.944\) 很大，数值会指数级膨胀。对每个种子走几十步，就已经远远超过前 30 项所需的范围。
按照现在的写法，算法基本就是常数时间。共有 6 条种子分支，每条做 50 次递推，所以 Pell 状态更新不到 300 次，然后只需要向一个很小的有序集合插入元素，再取出前 30 个值。
如果把这些固定上界抽象掉，那么复杂度就是“生成多少个 Pell 迭代状态，就做多少工作”，再加上有序集合带来的对数因子。对于题目本身，这点时间和内存开销都可以忽略不计。
Пусть \(G_1=1\), \(G_2=4\), а для \(k\ge 3\) выполняется \(G_k=G_{k-1}+G_{k-2}\). Производящая функция равна
$$A_G(x)=\sum_{k=1}^{\infty} G_k x^k.$$
Под "golden nugget" понимается положительное целое число \(n\), для которого уравнение \(A_G(x)=n\) имеет положительное рациональное решение \(x\). Нужно найти сумму первых 30 таких чисел.
Эффективное решение не перебирает рациональные \(x\). После алгебраического преобразования задача сводится к диофантову уравнению типа Пелля, а реализации перечисляют нужные решения, начиная всего с нескольких стартовых пар.
Последовательность начинается как \(1,4,5,9,14,23,\dots\). Рекурсия совпадает с рекурсией Фибоначчи, но начальные значения другие. Из-за этого меняется числитель производящей функции и, как следствие, правая часть пеллевского уравнения.
Запишем
$$A_G(x)=x+4x^2+\sum_{k=3}^{\infty} G_k x^k.$$
Так как \(G_k=G_{k-1}+G_{k-2}\), имеем
$$A_G(x)=x+4x^2+\sum_{k=3}^{\infty}(G_{k-1}+G_{k-2})x^k.$$
После перенумерации сумм получаем
$$A_G(x)=x+4x^2+x\sum_{j=2}^{\infty}G_j x^j+x^2\sum_{j=1}^{\infty}G_j x^j=x+4x^2+x(A_G(x)-x)+x^2A_G(x).$$
Следовательно,
$$A_G(x)(1-x-x^2)=x+3x^2,$$
и потому
$$\boxed{A_G(x)=\frac{x+3x^2}{1-x-x^2}.}$$
Подставим \(A_G(x)=n\), где \(n\) положительно. Тогда
$$n(1-x-x^2)=x+3x^2,$$
то есть
$$\boxed{(n+3)x^2+(n+1)x-n=0.}$$
У этого квадратного уравнения рациональный корень существует тогда и только тогда, когда дискриминант является точным квадратом:
$$\Delta=(n+1)^2+4n(n+3)=5n^2+14n+1=m^2.$$
И обратно, если \(m^2=5n^2+14n+1\), то
$$x=\frac{-\,(n+1)+m}{2(n+3)}$$
рационален и положителен, поскольку \(m^2-(n+1)^2=4n(n+3)>0\).
Умножим условие на 5:
$$25n^2+70n+5=5m^2.$$
Дополним до квадрата:
$$25n^2+70n+49-44=5m^2,$$
откуда
$$\boxed{(5n+7)^2-5m^2=44.}$$
Если обозначить
$$U=5n+7,\qquad V=m,$$
то получаем
$$\boxed{U^2-5V^2=44.}$$
Значит, каждый nugget соответствует положительному решению этого уравнения, а любое решение с \(U>7\) и \(U-7\), делящимся на 5, возвращает nugget по формуле
$$\boxed{n=\frac{U-7}{5}.}$$
Число \(9+4\sqrt5\) имеет норму 1, потому что \(9^2-5\cdot4^2=1\). Поэтому умножение \(U+V\sqrt5\) на эту единицу переводит решение уравнения \(U^2-5V^2=44\) в другое решение:
$$U'=(9U+20V),\qquad V'=(4U+9V).$$
Непосредственное раскрытие скобок даёт
$$U'^2-5V'^2=U^2-5V^2.$$
Для положительных решений, нужных в задаче, достаточно шести минимальных стартовых представителей:
$$(7,1),\ (8,2),\ (13,5),\ (17,7),\ (32,14),\ (43,19).$$
Не каждый следующий член ветви даёт nugget. Рекуррентный переход сохраняет пеллевскую норму, но не гарантирует делимость \(U-7\) на 5. Поэтому реализации проходят по каждой ветви и принимают только состояния с \(U>7\) и \(U-7\equiv 0 \pmod 5\). Первые принятые значения таковы:
$$2,\ 5,\ 21,\ 42,\ 152,\ 296,\ 1050,\ 2037,\dots$$
Пара \((7,1)\) сама по себе соответствует \(n=0\), то есть ещё не является положительным nugget, но её ветвь позже даёт допустимые положительные числа.
Возьмём \((U,V)=(17,7)\). Тогда
$$17^2-5\cdot 7^2=289-245=44,$$
а так как \(17-7\) делится на 5, имеем
$$n=\frac{17-7}{5}=2.$$
Соответствующее квадратное уравнение:
$$5x^2+3x-2=0,$$
его положительный рациональный корень равен
$$x=\frac{-3+7}{10}=\frac25.$$
Следовательно, \(A_G(2/5)=2\). Если один раз применить рекуррентный переход, получится \((293,131)\). Инвариант \(U^2-5V^2=44\) остаётся верным, но \(293-7\) уже не делится на 5, поэтому такой шаг не даёт nugget. Именно поэтому в коде рекурсия и фильтр по делимости разделены.
Реализации на C++, Python и Java жёстко задают шесть стартовых пар и повторяют переход
$$U' = 9U+20V,\qquad V' = 4U+9V.$$
Каждая ветвь продвигается на фиксированное число шагов. Когда очередное состояние удовлетворяет условиям \(U>7\) и делимости \(U-7\) на 5, оно переводится в nugget по формуле \(n=(U-7)/5\) и помещается в упорядоченную коллекцию. Использование множества удобно: оно одновременно устраняет возможные повторы и хранит значения в отсортированном виде.
После генерации всех ветвей программы читают значения по возрастанию и суммируют первые 30. Одна из реализаций также умеет принимать другой требуемый размер префикса и содержит небольшую проверку, что сумма первых пяти nugget равна 222, но математическое ядро во всех трёх языках одно и то же.
Фиксированной глубины итерации более чем достаточно, потому что коэффициент роста равен \(9+4\sqrt5\approx 17.944\). Несколько десятков шагов на каждое стартовое значение уже дают намного больше 30 допустимых чисел.
В текущем виде алгоритм фактически работает за константное время. Есть 6 стартовых ветвей и 50 рекуррентных шагов на ветвь, то есть меньше 300 обновлений состояния Пелля, после чего остаются только вставки в небольшое упорядоченное множество и извлечение первых 30 элементов.
Если отвлечься от жёстко заданных констант, трудоёмкость линейна по числу сгенерированных итераций Пелля, плюс логарифмический множитель при использовании упорядоченного множества для устранения повторов и сортировки. Для данной задачи и время, и память пренебрежимо малы.
لتكن \(G_1=1\) و\(G_2=4\)، ولـ \(k\ge 3\) يكون \(G_k=G_{k-1}+G_{k-2}\). عندئذٍ تكون الدالة المولدة
$$A_G(x)=\sum_{k=1}^{\infty} G_k x^k.$$
والمقصود بـ "golden nugget" هو عدد صحيح موجب \(n\) بحيث تكون للمعادلة \(A_G(x)=n\) قيمة نسبية موجبة \(x\). المطلوب هو جمع أول 30 عددًا من هذا النوع.
الفكرة الحاسمة هنا ليست التجريب العشوائي لقيم نسبية لـ \(x\). بعد تبسيط الدالة المولدة يتحول الشرط إلى معادلة ديوفانتية من نوع بيل، ثم تقوم التطبيقات بتوليد جميع الحلول المهمة انطلاقًا من عدد صغير من الأزواج الابتدائية.
بداية المتتالية هي \(1,4,5,9,14,23,\dots\). إذن علاقة التراجع هي نفسها علاقة فيبوناتشي، لكن القيم الابتدائية مختلفة. وهذا بالضبط ما يغيّر بسط الدالة المولدة ويقود في النهاية إلى نسخة خاصة من معادلة بيل يكون طرفها الأيمن 44.
نكتب
$$A_G(x)=x+4x^2+\sum_{k=3}^{\infty} G_k x^k.$$
وباستخدام \(G_k=G_{k-1}+G_{k-2}\) نحصل على
$$A_G(x)=x+4x^2+\sum_{k=3}^{\infty}(G_{k-1}+G_{k-2})x^k.$$
وبعد إعادة الفهرسة يصبح
$$A_G(x)=x+4x^2+x\sum_{j=2}^{\infty}G_j x^j+x^2\sum_{j=1}^{\infty}G_j x^j=x+4x^2+x(A_G(x)-x)+x^2A_G(x).$$
ومن ثم
$$A_G(x)(1-x-x^2)=x+3x^2,$$
أي
$$\boxed{A_G(x)=\frac{x+3x^2}{1-x-x^2}.}$$
إذا وضعنا \(A_G(x)=n\) حيث \(n\) عدد صحيح موجب، فسنحصل على
$$n(1-x-x^2)=x+3x^2,$$
أي
$$\boxed{(n+3)x^2+(n+1)x-n=0.}$$
هذه المعادلة التربيعية تملك جذرًا نسبيًا إذا وفقط إذا كان مميزها مربعًا كاملاً:
$$\Delta=(n+1)^2+4n(n+3)=5n^2+14n+1=m^2.$$
وبالعكس، إذا تحقق \(m^2=5n^2+14n+1\)، فإن
$$x=\frac{-\,(n+1)+m}{2(n+3)}$$
يكون عددًا نسبيًا، وهو موجب لأن \(m^2-(n+1)^2=4n(n+3)>0\).
نضرب علاقة المميز في 5:
$$25n^2+70n+5=5m^2.$$
وبإكمال المربع نحصل على
$$25n^2+70n+49-44=5m^2,$$
ومن ثم
$$\boxed{(5n+7)^2-5m^2=44.}$$
إذا عرفنا
$$U=5n+7,\qquad V=m,$$
فإن الشرط يصبح
$$\boxed{U^2-5V^2=44.}$$
وهكذا فإن كل nugget يقابل حلاً صحيحًا موجبًا لهذه المعادلة، وكل حل يحقق \(U>7\) وأن \(U-7\) قابل للقسمة على 5 يعيد إلينا nugget عبر
$$\boxed{n=\frac{U-7}{5}.}$$
للعدد \(9+4\sqrt5\) معيار يساوي 1 لأن \(9^2-5\cdot4^2=1\). لذلك فإن ضرب \(U+V\sqrt5\) بهذه الوحدة يعطي حلاً جديدًا للمعادلة نفسها:
$$U'=(9U+20V),\qquad V'=(4U+9V).$$
وبالتوسيع المباشر نرى أن
$$U'^2-5V'^2=U^2-5V^2.$$
أما الفروع الموجبة ذات الصلة بهذه المسألة فيكفي تمثيلها بالأزواج الابتدائية الستة التالية:
$$(7,1),\ (8,2),\ (13,5),\ (17,7),\ (32,14),\ (43,19).$$
ليس كل تكرار يعطي nugget صالحًا. فالعلاقة التكرارية تحفظ معيار بيل، لكنها لا تفرض أن يكون \(U-7\) من مضاعفات 5. لهذا السبب تولد التطبيقات كل فرع ثم تحتفظ فقط بالحالات التي تحقق \(U>7\) و\(U-7\equiv 0 \pmod 5\). وأول القيم المقبولة هي
$$2,\ 5,\ 21,\ 42,\ 152,\ 296,\ 1050,\ 2037,\dots$$
الزوج \((7,1)\) نفسه يقابل \(n=0\)، ولذلك فهو ليس golden nugget موجبًا، لكنه ينتمي إلى فرع صحيح يولد لاحقًا قيمًا موجبة.
خذ \((U,V)=(17,7)\). عندئذٍ
$$17^2-5\cdot 7^2=289-245=44,$$
وبما أن \(17-7\) قابل للقسمة على 5، فإن
$$n=\frac{17-7}{5}=2.$$
فتصبح المعادلة التربيعية
$$5x^2+3x-2=0,$$
وجذرها النسبي الموجب هو
$$x=\frac{-3+7}{10}=\frac25.$$
إذن \(A_G(2/5)=2\). وإذا طبقنا علاقة بيل مرة واحدة نحصل على \((293,131)\). تبقى المساواة \(U^2-5V^2=44\) صحيحة، لكن \(293-7\) لا يقبل القسمة على 5، ولهذا يفصل الكود بين خطوة التكرار وخطوة التصفية.
تقوم تطبيقات C++ وPython وJava بتثبيت الأزواج الابتدائية الستة السابقة، ثم تكرر
$$U' = 9U+20V,\qquad V' = 4U+9V.$$
ويجري دفع كل فرع عددًا ثابتًا من الخطوات. وكلما حققت حالة ما الشرطين \(U>7\) وقابلية \(U-7\) للقسمة على 5، تُحوَّل إلى nugget بواسطة \(n=(U-7)/5\) وتُدرج في مجموعة مرتبة. استخدام المجموعة المرتبة وسيلة عملية لإزالة التكرارات والإبقاء على القيم مرتبة من أجل الجمع النهائي.
بعد توليد جميع الفروع، تقرأ التطبيقات القيم بترتيب تصاعدي وتجمع أول 30 منها. إحدى النسخ تسمح أيضًا بتغيير عدد العناصر المطلوبة وتحتوي على فحص صغير يؤكد أن مجموع أول خمسة nuggets يساوي 222، لكن البنية الرياضية الأساسية واحدة في اللغات الثلاث.
أما حد التكرار الثابت فمناسب جدًا لأن عامل النمو هو \(9+4\sqrt5\approx 17.944\)، أي أن القيم تنمو أسيًا بسرعة كبيرة. بضع عشرات من الخطوات لكل بذرة تكفي لإنتاج أكثر بكثير من 30 قيمة صالحة.
بصورته الحالية يعمل هذا الأسلوب بزمن ثابت عمليًا. لدينا 6 فروع ابتدائية و50 خطوة تكرارية لكل فرع، أي أقل من 300 تحديث لحالة بيل، ثم إدخالات في مجموعة مرتبة صغيرة واستخراج أول 30 قيمة.
وإذا تجاهلنا الحدود الثابتة المزروعة في الكود، فإن الكلفة تصبح خطية في عدد حالات بيل المولدة، مع عامل لوغاريتمي إضافي عند استخدام مجموعة مرتبة لإزالة التكرارات وترتيب القيم. بالنسبة إلى هذه المسألة، فإن الزمن والذاكرة كلاهما ضئيلان جدًا.