The continued fraction for \(\sqrt{2}\) is
$$\sqrt{2}=1+\cfrac{1}{2+\cfrac{1}{2+\cfrac{1}{2+\cdots}}}=[1;2,2,2,\dots].$$
If we truncate this infinite expression after finitely many layers, we obtain the convergents \(3/2, 7/5, 17/12, 41/29, \dots\). The problem asks how many of the first 1000 convergents have a numerator with more decimal digits than the denominator.
The key point is that we never need a floating-point approximation of \(\sqrt{2}\). Each convergent can be generated exactly from the previous one using only integer arithmetic.
Let the \(k\)-th convergent be
$$x_k=\frac{n_k}{d_k}, \qquad x_1=\frac{3}{2}.$$
We want to count the indices \(k \le 1000\) for which \(n_k\) has more decimal digits than \(d_k\).
If \(x_k\) is one convergent, then adding one more layer of the continued fraction gives
$$x_{k+1}=1+\frac{1}{1+x_k}.$$
Now substitute \(x_k=n_k/d_k\):
$$x_{k+1}=1+\frac{1}{1+n_k/d_k}=1+\frac{d_k}{n_k+d_k}=\frac{n_k+2d_k}{n_k+d_k}.$$
Therefore the exact integer update is
$$n_{k+1}=n_k+2d_k,\qquad d_{k+1}=n_k+d_k.$$
This is the central object in the solution. The implementations keep only the current pair \((n_k,d_k)\) and repeatedly apply this map.
The one-step map can be rewritten as a second-order recurrence. Eliminating \(d_k\) gives
$$n_{k+2}=2n_{k+1}+n_k,$$
and eliminating \(n_k\) gives
$$d_{k+2}=2d_{k+1}+d_k.$$
So the numerators and denominators follow the same linear recurrence as the companion Pell numbers and the Pell numbers. This already explains why the numbers grow quickly but still remain easy to generate: every step uses only additions.
The recurrence preserves several useful facts.
First,
$$n_{k+1}-d_{k+1}=d_k>0,$$
so every convergent is bigger than \(1\).
Second, the fractions stay reduced, because
$$\gcd(n_k+2d_k,n_k+d_k)=\gcd(d_k,n_k+d_k)=\gcd(n_k,d_k).$$
Starting from \(\gcd(3,2)=1\), every later pair is also coprime.
Most importantly, the Pell-type invariant alternates sign:
$$n_k^2-2d_k^2=(-1)^{k+1}.$$
This follows from the update, since
$$\left(n_k+2d_k\right)^2-2\left(n_k+d_k\right)^2=-(n_k^2-2d_k^2).$$
Because the initial pair \((3,2)\) gives \(3^2-2\cdot 2^2=1\), the sign flips at every step. As a consequence, the convergents alternate around \(\sqrt{2}\), and the error is
$$\left|\frac{n_k}{d_k}-\sqrt{2}\right|=\frac{1}{d_k\left(n_k+d_k\sqrt{2}\right)}.$$
That is why these rational approximations become accurate very quickly.
A positive integer \(m\) has
$$\lfloor \log_{10} m \rfloor + 1$$
decimal digits. Therefore the condition in the problem is simply
$$\lfloor \log_{10} n_k \rfloor > \lfloor \log_{10} d_k \rfloor.$$
Since \(n_k/d_k \to \sqrt{2}\), numerator and denominator usually have almost the same size. A hit occurs exactly when the numerator has crossed a power of ten but the denominator has not yet done so. The code does not need logarithms, though; it can compare decimal lengths directly.
Starting from \((n_1,d_1)=(3,2)\), the recurrence gives
$$ (3,2)\to(7,5)\to(17,12)\to(41,29)\to(99,70)\to(239,169)\to(577,408)\to(1393,985). $$
The first seven listed convergents have matching digit counts in numerator and denominator. The eighth one, \(1393/985\), has 4 digits in the numerator and 3 in the denominator, so it is the first success. This is exactly the checkpoint used by the implementations: among the first 8 expansions, the count is 1.
The C++, Python, and Java implementations begin with the first convergent \(3/2\). They store the current numerator, the current denominator, and a counter for successful cases.
Each loop iteration checks whether the current numerator has more decimal digits than the current denominator. After that, it updates the pair by
$$ (n,d)\mapsto(n+2d,\;n+d). $$
No division is required, and there is no risk of floating-point rounding error because the whole computation stays in exact integer arithmetic.
After 1000 expansions the numbers have far more than 64 bits, so the implementations rely on arbitrary-precision integers. That is still inexpensive here because each step performs only a doubling, two additions, and two decimal-length checks. They also verify the known checkpoint that the first 8 expansions produce exactly 1 success, which validates both the recurrence and the counting logic.
For a general limit of \(N\) expansions, the convergents grow like \((1+\sqrt{2})^N\), so the largest numerator and denominator have \(\Theta(N)\) decimal digits. One loop iteration therefore costs \(\Theta(k)\) digit work when the current values have \(k\) digits.
Summing over all iterations gives \(\Theta(N^2)\) time in digit operations. The memory usage is \(\Theta(N)\) digits, because the algorithm stores only the current pair and a few temporary big integers. For the concrete case \(N=1000\), the numbers are only about 383 digits long, so the program is comfortably fast.
Der Kettenbruch von \(\sqrt{2}\) lautet
$$\sqrt{2}=1+\cfrac{1}{2+\cfrac{1}{2+\cfrac{1}{2+\cdots}}}=[1;2,2,2,\dots].$$
Wenn man diesen unendlichen Ausdruck nach endlich vielen Schichten abschneidet, entstehen die Konvergenten \(3/2, 7/5, 17/12, 41/29, \dots\). Gesucht ist, wie viele der ersten 1000 Konvergenten im Zähler mehr Dezimalstellen als im Nenner haben.
Wesentlich ist, dass dafür keine Gleitkomma-Näherung von \(\sqrt{2}\) gebraucht wird. Jeder Konvergente lässt sich exakt aus dem vorherigen mit reiner Ganzzahlarithmetik erzeugen.
Bezeichne den \(k\)-ten Konvergenten mit
$$x_k=\frac{n_k}{d_k}, \qquad x_1=\frac{3}{2}.$$
Wir zählen also die Indizes \(k \le 1000\), für die \(n_k\) mehr Dezimalstellen besitzt als \(d_k\).
Wenn \(x_k\) ein Konvergenter ist, dann entsteht der nächste durch Einfügen einer weiteren Schicht im Kettenbruch:
$$x_{k+1}=1+\frac{1}{1+x_k}.$$
Setzt man \(x_k=n_k/d_k\), erhält man
$$x_{k+1}=1+\frac{1}{1+n_k/d_k}=1+\frac{d_k}{n_k+d_k}=\frac{n_k+2d_k}{n_k+d_k}.$$
Damit lautet die exakte Rekursion
$$n_{k+1}=n_k+2d_k,\qquad d_{k+1}=n_k+d_k.$$
Genau diese Zustandsaktualisierung verwenden die Implementierungen. Mehr Information als das aktuelle Paar \((n_k,d_k)\) ist nicht nötig.
Aus der Einschritt-Abbildung kann man eine lineare Rekurrenz zweiter Ordnung gewinnen. Eliminiert man \(d_k\), folgt
$$n_{k+2}=2n_{k+1}+n_k,$$
und entsprechend für die Nenner
$$d_{k+2}=2d_{k+1}+d_k.$$
Zähler und Nenner gehorchen also derselben linearen Rekursion wie die begleitenden Pell-Zahlen bzw. die Pell-Zahlen. Das erklärt zugleich das schnelle Wachstum und die einfache Berechenbarkeit: jeder Schritt besteht nur aus Additionen.
Aus der Rekursion folgen mehrere nützliche Eigenschaften.
Zunächst gilt
$$n_{k+1}-d_{k+1}=d_k>0,$$
also ist jeder Konvergente größer als \(1\).
Außerdem bleiben die Brüche vollständig gekürzt, denn
$$\gcd(n_k+2d_k,n_k+d_k)=\gcd(d_k,n_k+d_k)=\gcd(n_k,d_k).$$
Mit dem Startwert \(\gcd(3,2)=1\) sind also alle späteren Paare teilerfremd.
Die wichtigste Invariante ist die Pell-Identität mit wechselndem Vorzeichen:
$$n_k^2-2d_k^2=(-1)^{k+1}.$$
Sie folgt direkt aus der Aktualisierung, denn
$$\left(n_k+2d_k\right)^2-2\left(n_k+d_k\right)^2=-(n_k^2-2d_k^2).$$
Da \((3,2)\) den Wert \(3^2-2\cdot 2^2=1\) liefert, wechselt das Vorzeichen bei jedem Schritt. Dadurch liegen die Konvergenten abwechselnd über und unter \(\sqrt{2}\), und der Fehler ist
$$\left|\frac{n_k}{d_k}-\sqrt{2}\right|=\frac{1}{d_k\left(n_k+d_k\sqrt{2}\right)}.$$
Das zeigt, warum die Näherungen so schnell sehr präzise werden.
Eine positive ganze Zahl \(m\) besitzt
$$\lfloor \log_{10} m \rfloor + 1$$
Dezimalstellen. Die Bedingung der Aufgabe ist also äquivalent zu
$$\lfloor \log_{10} n_k \rfloor > \lfloor \log_{10} d_k \rfloor.$$
Da \(n_k/d_k \to \sqrt{2}\), sind Zähler und Nenner meistens fast gleich groß. Ein Treffer entsteht genau dann, wenn der Zähler bereits die nächste Zehnerpotenz überschritten hat, der Nenner aber noch nicht. Der Code benötigt dafür keine Logarithmen; der Vergleich der Stellenlängen genügt.
Ausgehend von \((n_1,d_1)=(3,2)\) erhält man
$$ (3,2)\to(7,5)\to(17,12)\to(41,29)\to(99,70)\to(239,169)\to(577,408)\to(1393,985). $$
Bei den ersten sieben aufgeführten Konvergenten haben Zähler und Nenner gleich viele Stellen. Beim achten, \(1393/985\), hat der Zähler 4 Stellen und der Nenner 3. Genau das ist der Prüfpunkt der Implementierungen: Unter den ersten 8 Erweiterungen gibt es genau 1 Treffer.
Die C++-, Python- und Java-Implementierungen beginnen beim ersten Konvergenten \(3/2\). Gespeichert werden nur der aktuelle Zähler, der aktuelle Nenner und ein Zähler für erfolgreiche Fälle.
In jeder Schleifeniteration wird zuerst geprüft, ob der aktuelle Zähler mehr Dezimalstellen hat als der aktuelle Nenner. Danach wird das Paar durch
$$ (n,d)\mapsto(n+2d,\;n+d) $$
ersetzt. Divisionen kommen nicht vor, und Rundungsfehler durch Gleitkommazahlen können nicht auftreten, weil die gesamte Rechnung exakt in Ganzzahlen bleibt.
Nach 1000 Erweiterungen liegen die Werte weit außerhalb des 64-Bit-Bereichs, daher nutzen die Implementierungen Ganzzahlen beliebiger Präzision. Der Aufwand bleibt trotzdem klein, weil jeder Schritt nur eine Verdopplung, zwei Additionen und zwei Stellenlängen-Vergleiche benötigt. Zusätzlich wird überprüft, dass die ersten 8 Erweiterungen genau 1 Treffer liefern; damit werden Rekursion und Zähllogik zugleich abgesichert.
Für ein allgemeines Limit von \(N\) Erweiterungen wachsen die Konvergenten wie \((1+\sqrt{2})^N\), also besitzen Zähler und Nenner am Ende \(\Theta(N)\) Dezimalstellen. Eine Iteration kostet daher \(\Theta(k)\) Stellenoperationen, wenn die aktuellen Werte \(k\) Stellen haben.
Über alle Iterationen aufsummiert ergibt das \(\Theta(N^2)\) Zeit in Stellenoperationen. Der Speicherverbrauch beträgt \(\Theta(N)\) Stellen, weil nur das aktuelle Paar und wenige temporäre große Zahlen gehalten werden. Für den konkreten Fall \(N=1000\) haben die Zahlen nur ungefähr 383 Stellen, daher läuft das Programm bequem schnell.
\(\sqrt{2}\) için sürekli kesir açılımı şöyledir:
$$\sqrt{2}=1+\cfrac{1}{2+\cfrac{1}{2+\cfrac{1}{2+\cdots}}}=[1;2,2,2,\dots].$$
Bu sonsuz ifade sonlu bir yerde kesildiğinde \(3/2, 7/5, 17/12, 41/29, \dots\) yakınsakları elde edilir. Soru, ilk 1000 yakınsaktan kaç tanesinde payın ondalık basamak sayısının paydadan büyük olduğunu soruyor.
Buradaki önemli nokta, \(\sqrt{2}\) için kayan noktalı bir yaklaşık değer kullanmak zorunda olmamamızdır. Her yakınsak, bir önceki yakınsaktan yalnızca tam sayı işlemleriyle tam olarak üretilebilir.
\(k\). yakınsağı
$$x_k=\frac{n_k}{d_k}, \qquad x_1=\frac{3}{2}$$
olarak gösterelim. O halde çözmemiz gereken şey, \(k \le 1000\) için \(n_k\)'nın basamak sayısının \(d_k\)'nın basamak sayısından büyük olduğu durumları saymaktır.
Eğer \(x_k\) bir yakınsaksa, bir katman daha eklenince sonraki yakınsak
$$x_{k+1}=1+\frac{1}{1+x_k}$$
olur. Şimdi \(x_k=n_k/d_k\) yazalım:
$$x_{k+1}=1+\frac{1}{1+n_k/d_k}=1+\frac{d_k}{n_k+d_k}=\frac{n_k+2d_k}{n_k+d_k}.$$
Böylece tam sayı güncellemesi
$$n_{k+1}=n_k+2d_k,\qquad d_{k+1}=n_k+d_k$$
şeklinde elde edilir. Çözümün merkezindeki matematiksel nesne budur. Uygulamalar yalnızca \((n_k,d_k)\) çiftini tutup bu dönüşümü tekrarlar.
Bu tek adımlık dönüşüm ikinci dereceden bir lineer reküransa da çevrilebilir. \(d_k\) elimine edilirse
$$n_{k+2}=2n_{k+1}+n_k,$$
\(n_k\) elimine edilirse de
$$d_{k+2}=2d_{k+1}+d_k$$
elde edilir. Yani paylar ve paydalar, tamamlayıcı Pell sayıları ile Pell sayılarının sağladığı aynı reküransı izler. Bu hem hızlı büyümeyi hem de hesaplamanın neden kolay kaldığını açıklar: her adım yalnızca toplamadır.
Rekürans birkaç yararlı özelliği korur.
Önce
$$n_{k+1}-d_{k+1}=d_k>0$$
olduğundan her yakınsak \(1\)'den büyüktür.
Ayrıca kesirler sade kalır, çünkü
$$\gcd(n_k+2d_k,n_k+d_k)=\gcd(d_k,n_k+d_k)=\gcd(n_k,d_k).$$
Başlangıçta \(\gcd(3,2)=1\) olduğundan bütün sonraki çiftler de aralarında asaldır.
En önemli değişmez, işareti her adımda değişen Pell özdeşliğidir:
$$n_k^2-2d_k^2=(-1)^{k+1}.$$
Bu, güncellemeden doğrudan gelir; çünkü
$$\left(n_k+2d_k\right)^2-2\left(n_k+d_k\right)^2=-(n_k^2-2d_k^2).$$
İlk çift \((3,2)\) için \(3^2-2\cdot 2^2=1\) olduğundan işaret her adımda tersine döner. Sonuç olarak yakınsaklar \(\sqrt{2}\)'nin bir üstünde ve bir altında sırayla yer alır; hata da
$$\left|\frac{n_k}{d_k}-\sqrt{2}\right|=\frac{1}{d_k\left(n_k+d_k\sqrt{2}\right)}$$
olur. Bu yüzden yaklaşım çok hızlı biçimde hassaslaşır.
Pozitif bir tam sayı \(m\),
$$\lfloor \log_{10} m \rfloor + 1$$
adet ondalık basamağa sahiptir. Dolayısıyla sorudaki koşul doğrudan
$$\lfloor \log_{10} n_k \rfloor > \lfloor \log_{10} d_k \rfloor$$
eşitsizliğine denktir. \(n_k/d_k \to \sqrt{2}\) olduğu için pay ve payda çoğu zaman birbirine çok yakındır. Bir başarı ancak pay bir sonraki \(10\) kuvvetini geçmişken payda henüz geçmemişse oluşur. Kodun logaritma hesaplamasına ihtiyacı yoktur; doğrudan basamak sayısını karşılaştırmak yeterlidir.
\((n_1,d_1)=(3,2)\) ile başlayıp reküransı uygularsak
$$ (3,2)\to(7,5)\to(17,12)\to(41,29)\to(99,70)\to(239,169)\to(577,408)\to(1393,985) $$
elde edilir. İlk yedi listelenen yakınsakta pay ve payda aynı sayıda basamağa sahiptir. Sekizinci kesir olan \(1393/985\) ise payda 3 basamaklıyken payı 4 basamaklı olduğu için ilk başarılı örnektir. Uygulamaların kullandığı kontrol de tam budur: ilk 8 açılım içinde başarı sayısı 1 olmalıdır.
C++, Python ve Java uygulamaları soruda verilen ilk yakınsak olan \(3/2\) ile başlar. Yalnızca mevcut pay, mevcut payda ve başarılı durumların sayacı tutulur.
Her döngü adımında önce mevcut payın basamak sayısının mevcut paydanın basamak sayısından büyük olup olmadığı kontrol edilir. Ardından çift
$$ (n,d)\mapsto(n+2d,\;n+d) $$
şeklinde güncellenir. Hiç bölüm alma yoktur ve tüm hesap tam sayılar üzerinde yapıldığı için kayan nokta yuvarlama hatası oluşmaz.
1000 açılım sonunda değerler 64 bit sınırını çok aşar, bu yüzden uygulamalar keyfi büyüklükte tam sayılar kullanır. Buna rağmen maliyet küçüktür; her adım bir katına çıkarma, iki toplama ve iki basamak sayısı kontrolünden ibarettir. Ayrıca ilk 8 açılımın tam olarak 1 başarı verdiği doğrulanır; bu test hem reküransın hem de sayım mantığının doğru kurulduğunu gösterir.
Genel olarak \(N\) açılım için yakınsaklar \((1+\sqrt{2})^N\) gibi büyür; bu yüzden en büyük pay ve payda \(\Theta(N)\) ondalık basamağa sahiptir. O halde mevcut sayıların \(k\) basamaklı olduğu bir iterasyonun maliyeti \(\Theta(k)\) basamak işlemidir.
Tüm iterasyonlar toplanınca toplam süre, basamak işlemleri cinsinden \(\Theta(N^2)\) olur. Bellek kullanımı \(\Theta(N)\) basamaktır; çünkü yalnızca mevcut çift ve birkaç geçici büyük tam sayı tutulur. Somut durumda \(N=1000\) iken sayılar yaklaşık 383 basamaklıdır, dolayısıyla program rahatlıkla hızlı çalışır.
La fracción continua de \(\sqrt{2}\) es
$$\sqrt{2}=1+\cfrac{1}{2+\cfrac{1}{2+\cfrac{1}{2+\cdots}}}=[1;2,2,2,\dots].$$
Si truncamos esa expresión infinita tras un número finito de capas, obtenemos los convergentes \(3/2, 7/5, 17/12, 41/29, \dots\). El problema pide contar cuántos de los primeros 1000 convergentes tienen un numerador con más cifras decimales que el denominador.
La observación clave es que no hace falta aproximar \(\sqrt{2}\) con números en coma flotante. Cada convergente se genera exactamente a partir del anterior usando solo aritmética entera.
Denotemos el \(k\)-ésimo convergente por
$$x_k=\frac{n_k}{d_k}, \qquad x_1=\frac{3}{2}.$$
El objetivo es contar los índices \(k \le 1000\) para los que \(n_k\) tiene más cifras decimales que \(d_k\).
Si \(x_k\) es un convergente, entonces al añadir una capa más de la fracción continua obtenemos
$$x_{k+1}=1+\frac{1}{1+x_k}.$$
Sustituyendo \(x_k=n_k/d_k\), se obtiene
$$x_{k+1}=1+\frac{1}{1+n_k/d_k}=1+\frac{d_k}{n_k+d_k}=\frac{n_k+2d_k}{n_k+d_k}.$$
Por tanto, la actualización exacta es
$$n_{k+1}=n_k+2d_k,\qquad d_{k+1}=n_k+d_k.$$
Ese es el objeto central de la solución. Las implementaciones solo conservan el par actual \((n_k,d_k)\) y repiten esta transformación.
La transformación de un paso puede reescribirse como una recurrencia lineal de segundo orden. Si eliminamos \(d_k\), aparece
$$n_{k+2}=2n_{k+1}+n_k,$$
y si eliminamos \(n_k\), aparece
$$d_{k+2}=2d_{k+1}+d_k.$$
Así, numeradores y denominadores siguen la misma recurrencia que los números de Pell complementarios y los números de Pell. Eso explica tanto el crecimiento rápido como la sencillez computacional: cada paso utiliza solo sumas.
La recurrencia conserva varias propiedades útiles.
En primer lugar,
$$n_{k+1}-d_{k+1}=d_k>0,$$
de modo que todo convergente es mayor que \(1\).
Además, las fracciones permanecen irreducibles, porque
$$\gcd(n_k+2d_k,n_k+d_k)=\gcd(d_k,n_k+d_k)=\gcd(n_k,d_k).$$
Como \(\gcd(3,2)=1\), todos los pares posteriores también son coprimos.
La invariante más importante es la identidad de Pell con signo alternante:
$$n_k^2-2d_k^2=(-1)^{k+1}.$$
Sale directamente de la actualización, ya que
$$\left(n_k+2d_k\right)^2-2\left(n_k+d_k\right)^2=-(n_k^2-2d_k^2).$$
Puesto que el par inicial \((3,2)\) da \(3^2-2\cdot 2^2=1\), el signo se invierte en cada paso. En consecuencia, los convergentes alternan por encima y por debajo de \(\sqrt{2}\), y el error vale
$$\left|\frac{n_k}{d_k}-\sqrt{2}\right|=\frac{1}{d_k\left(n_k+d_k\sqrt{2}\right)}.$$
Eso muestra por qué estas aproximaciones racionales se vuelven precisas tan deprisa.
Un entero positivo \(m\) tiene
$$\lfloor \log_{10} m \rfloor + 1$$
cifras decimales. Por tanto, la condición del problema equivale a
$$\lfloor \log_{10} n_k \rfloor > \lfloor \log_{10} d_k \rfloor.$$
Como \(n_k/d_k \to \sqrt{2}\), numerador y denominador suelen tener tamaños muy parecidos. Un acierto ocurre exactamente cuando el numerador ya ha cruzado una potencia de diez y el denominador todavía no. El código no necesita calcular logaritmos; basta con comparar las longitudes decimales exactas.
Partiendo de \((n_1,d_1)=(3,2)\), la recurrencia produce
$$ (3,2)\to(7,5)\to(17,12)\to(41,29)\to(99,70)\to(239,169)\to(577,408)\to(1393,985). $$
Los siete primeros convergentes listados tienen el mismo número de cifras en numerador y denominador. El octavo, \(1393/985\), tiene 4 cifras arriba y 3 abajo, así que es el primer éxito. Ese es exactamente el punto de control usado por las implementaciones: entre las primeras 8 expansiones, la cuenta debe ser 1.
Las implementaciones en C++, Python y Java arrancan en el primer convergente \(3/2\). Solo mantienen el numerador actual, el denominador actual y un contador de casos favorables.
En cada iteración del bucle se comprueba primero si el numerador actual tiene más cifras decimales que el denominador actual. Después se sustituye el par por
$$ (n,d)\mapsto(n+2d,\;n+d). $$
No hace falta dividir, y no hay riesgo de error de redondeo porque todo se mantiene en aritmética entera exacta.
Tras 1000 expansiones, los valores quedan muy por encima del rango de 64 bits, así que las implementaciones usan enteros de precisión arbitraria. Aun así, el coste es pequeño porque cada paso requiere solo un duplicado, dos sumas y dos consultas de longitud decimal. Además, verifican el control conocido de que las primeras 8 expansiones producen exactamente 1 éxito, lo que valida simultáneamente la recurrencia y la lógica del conteo.
Para un límite general de \(N\) expansiones, los convergentes crecen como \((1+\sqrt{2})^N\), de modo que el numerador y el denominador más grandes tienen \(\Theta(N)\) cifras decimales. Por ello, una iteración cuesta \(\Theta(k)\) operaciones sobre cifras cuando los valores actuales tienen \(k\) cifras.
Al sumar todas las iteraciones, el tiempo total es \(\Theta(N^2)\) en operaciones sobre cifras. El uso de memoria es \(\Theta(N)\) cifras, porque el algoritmo guarda solo el par actual y unos pocos enteros grandes temporales. En el caso concreto \(N=1000\), los números tienen solo unas 383 cifras, así que el programa resulta muy ligero.
\(\sqrt{2}\) 的连分数展开为
$$\sqrt{2}=1+\cfrac{1}{2+\cfrac{1}{2+\cfrac{1}{2+\cdots}}}=[1;2,2,2,\dots].$$
把这个无限表达式截断，就会得到一串收敛分数：\(3/2, 7/5, 17/12, 41/29, \dots\)。题目要求统计前 1000 个收敛分数中，有多少个分子的十进制位数严格多于分母。
关键点在于，整个过程完全不需要用浮点数去近似 \(\sqrt{2}\)。每一个收敛分数都可以由前一个收敛分数通过纯整数运算精确生成。
设第 \(k\) 个收敛分数为
$$x_k=\frac{n_k}{d_k}, \qquad x_1=\frac{3}{2}.$$
那么问题就变成统计所有满足 \(k \le 1000\) 且 \(n_k\) 的十进制位数大于 \(d_k\) 的下标。
如果 \(x_k\) 是当前收敛分数，那么再向连分数内部多加一层，就会得到下一个收敛分数：
$$x_{k+1}=1+\frac{1}{1+x_k}.$$
把 \(x_k=n_k/d_k\) 代入，可得
$$x_{k+1}=1+\frac{1}{1+n_k/d_k}=1+\frac{d_k}{n_k+d_k}=\frac{n_k+2d_k}{n_k+d_k}.$$
于是得到最核心的整数递推：
$$n_{k+1}=n_k+2d_k,\qquad d_{k+1}=n_k+d_k.$$
这正是实现中反复执行的状态转移。程序只需要保留当前的 \((n_k,d_k)\)，不需要保存更长的历史。
这个单步递推还可以改写成二阶线性递推。消去 \(d_k\) 以后得到
$$n_{k+2}=2n_{k+1}+n_k,$$
消去 \(n_k\) 则得到
$$d_{k+2}=2d_{k+1}+d_k.$$
也就是说，分子和分母都满足与 Pell 数列及其伴随数列相同的递推关系。这解释了两个现象：数值增长很快，但计算本身仍然很便宜，因为每一步都只有加法。
这个递推保持了若干非常有用的性质。
首先，
$$n_{k+1}-d_{k+1}=d_k>0,$$
所以每个收敛分数都大于 \(1\)。
其次，分数始终是既约的，因为
$$\gcd(n_k+2d_k,n_k+d_k)=\gcd(d_k,n_k+d_k)=\gcd(n_k,d_k).$$
初始时 \(\gcd(3,2)=1\)，所以以后所有分子分母也都互素。
最重要的不变量是 Pell 型恒等式，它的符号每一步交替一次：
$$n_k^2-2d_k^2=(-1)^{k+1}.$$
这可以直接由更新公式验证，因为
$$\left(n_k+2d_k\right)^2-2\left(n_k+d_k\right)^2=-(n_k^2-2d_k^2).$$
而初始对 \((3,2)\) 满足 \(3^2-2\cdot 2^2=1\)，因此符号会一步一翻。于是这些收敛分数会在 \(\sqrt{2}\) 的上下两侧交替出现，而且误差满足
$$\left|\frac{n_k}{d_k}-\sqrt{2}\right|=\frac{1}{d_k\left(n_k+d_k\sqrt{2}\right)}.$$
这说明它们会非常快地逼近 \(\sqrt{2}\)。
任意正整数 \(m\) 的十进制位数都是
$$\lfloor \log_{10} m \rfloor + 1.$$
因此题目的条件等价于
$$\lfloor \log_{10} n_k \rfloor > \lfloor \log_{10} d_k \rfloor.$$
由于 \(n_k/d_k \to \sqrt{2}\)，分子和分母通常规模非常接近。只有当分子刚刚跨过某个 \(10\) 的幂，而分母还没有跨过去时，分子才会多出一位。实现并不需要真的计算对数，直接比较整数转成十进制后的长度就可以了。
从 \((n_1,d_1)=(3,2)\) 出发，递推会产生
$$ (3,2)\to(7,5)\to(17,12)\to(41,29)\to(99,70)\to(239,169)\to(577,408)\to(1393,985). $$
前面列出的前七个收敛分数中，分子和分母的位数都相同。第八个分数 \(1393/985\) 的分子有 4 位，分母有 3 位，因此它是第一个满足条件的例子。这也正是实现所使用的检查点：前 8 个展开中，答案必须是 1。
C++、Python 和 Java 的实现都从题目中的第一个收敛分数 \(3/2\) 出发。它们只维护当前分子、当前分母以及满足条件的次数。
每次循环先判断当前分子的十进制位数是否大于当前分母。然后把当前二元组更新为
$$ (n,d)\mapsto(n+2d,\;n+d). $$
整个过程中不需要做除法，也不会出现浮点舍入误差，因为所有计算都保持在精确的大整数范围内。
经过 1000 次展开后，数值早已超出 64 位整数范围，因此实现都依赖任意精度整数。不过这道题的运算仍然很轻，因为每一步只有一次倍增、两次加法和两次十进制长度比较。实现还会验证一个已知检查点：前 8 个展开中恰好有 1 个满足条件。这能同时确认递推公式和计数逻辑没有写错。
若一般化到前 \(N\) 个展开，收敛分数的规模大约按 \((1+\sqrt{2})^N\) 增长，因此最大的分子和分母都有 \(\Theta(N)\) 个十进制数字。当当前数字长度为 \(k\) 时，一次循环的代价就是 \(\Theta(k)\) 个数字级操作。
把全部 \(N\) 次迭代加起来，总时间复杂度为 \(\Theta(N^2)\) 个数字级操作。空间复杂度为 \(\Theta(N)\) 个数字，因为算法只保存当前这一对大整数和少量临时变量。对题目给定的 \(N=1000\) 而言，数字长度只有大约 383 位，所以运行非常轻松。
Непрерывная дробь для \(\sqrt{2}\) имеет вид
$$\sqrt{2}=1+\cfrac{1}{2+\cfrac{1}{2+\cfrac{1}{2+\cdots}}}=[1;2,2,2,\dots].$$
Если обрывать это бесконечное выражение после конечного числа слоёв, получаются подходящие дроби \(3/2, 7/5, 17/12, 41/29, \dots\). Требуется подсчитать, у скольких из первых 1000 таких дробей числитель содержит больше десятичных цифр, чем знаменатель.
Главное наблюдение состоит в том, что никакого приближения \(\sqrt{2}\) вещественными числами не нужно. Каждая подходящая дробь получается из предыдущей точно, только с помощью целочисленной арифметики.
Обозначим \(k\)-ю подходящую дробь через
$$x_k=\frac{n_k}{d_k}, \qquad x_1=\frac{3}{2}.$$
Тогда нужно посчитать все индексы \(k \le 1000\), для которых у \(n_k\) десятичных цифр больше, чем у \(d_k\).
Если \(x_k\) уже известна, то добавление ещё одного слоя непрерывной дроби даёт
$$x_{k+1}=1+\frac{1}{1+x_k}.$$
Подставляя \(x_k=n_k/d_k\), получаем
$$x_{k+1}=1+\frac{1}{1+n_k/d_k}=1+\frac{d_k}{n_k+d_k}=\frac{n_k+2d_k}{n_k+d_k}.$$
Следовательно, точное обновление пар целых чисел имеет вид
$$n_{k+1}=n_k+2d_k,\qquad d_{k+1}=n_k+d_k.$$
Это и есть центральный математический объект решения. Реализации хранят только текущую пару \((n_k,d_k)\) и многократно применяют это преобразование.
Одношаговое преобразование можно переписать как линейную рекуррентность второго порядка. Если исключить \(d_k\), получится
$$n_{k+2}=2n_{k+1}+n_k,$$
а если исключить \(n_k\), то
$$d_{k+2}=2d_{k+1}+d_k.$$
Значит, числители и знаменатели подчиняются той же рекуррентности, что и числа Пелля и их сопутствующая последовательность. Это объясняет, почему величины быстро растут, но вычисление остаётся простым: на каждом шаге нужны только сложения.
Рекуррентность сохраняет несколько полезных свойств.
Во-первых,
$$n_{k+1}-d_{k+1}=d_k>0,$$
поэтому каждая подходящая дробь больше \(1\).
Во-вторых, дроби остаются несократимыми, поскольку
$$\gcd(n_k+2d_k,n_k+d_k)=\gcd(d_k,n_k+d_k)=\gcd(n_k,d_k).$$
Так как \(\gcd(3,2)=1\), все последующие пары тоже взаимно просты.
Самый важный инвариант - знакочередующаяся тождественность Пелля:
$$n_k^2-2d_k^2=(-1)^{k+1}.$$
Она напрямую следует из обновления, потому что
$$\left(n_k+2d_k\right)^2-2\left(n_k+d_k\right)^2=-(n_k^2-2d_k^2).$$
Начальная пара \((3,2)\) даёт \(3^2-2\cdot 2^2=1\), поэтому знак меняется на каждом шаге. Отсюда следует, что подходящие дроби поочерёдно лежат выше и ниже \(\sqrt{2}\), а ошибка равна
$$\left|\frac{n_k}{d_k}-\sqrt{2}\right|=\frac{1}{d_k\left(n_k+d_k\sqrt{2}\right)}.$$
Именно поэтому такие рациональные приближения становятся очень точными уже после немногих шагов.
У положительного целого числа \(m\) количество десятичных цифр равно
$$\lfloor \log_{10} m \rfloor + 1.$$
Следовательно, условие задачи эквивалентно неравенству
$$\lfloor \log_{10} n_k \rfloor > \lfloor \log_{10} d_k \rfloor.$$
Поскольку \(n_k/d_k \to \sqrt{2}\), числитель и знаменатель обычно имеют почти одинаковый масштаб. Успех случается тогда, когда числитель уже пересёк очередную степень десяти, а знаменатель ещё нет. На практике логарифмы не нужны: достаточно сравнивать длины десятичных записей.
Начиная с \((n_1,d_1)=(3,2)\), рекуррентность порождает
$$ (3,2)\to(7,5)\to(17,12)\to(41,29)\to(99,70)\to(239,169)\to(577,408)\to(1393,985). $$
У первых семи перечисленных дробей число цифр в числителе и знаменателе совпадает. Восьмая дробь \(1393/985\) уже имеет 4 цифры сверху и 3 снизу, поэтому это первый успешный случай. Именно этот факт используется как контрольная точка: среди первых 8 разложений ответ должен быть равен 1.
Реализации на C++, Python и Java начинают с первой подходящей дроби \(3/2\). Они хранят только текущий числитель, текущий знаменатель и счётчик успешных случаев.
На каждой итерации сначала проверяется, больше ли число десятичных цифр у текущего числителя, чем у текущего знаменателя. Затем пара заменяется по правилу
$$ (n,d)\mapsto(n+2d,\;n+d). $$
Деления не требуется, и ошибок округления быть не может, потому что вся арифметика остаётся точной целочисленной.
После 1000 шагов значения далеко выходят за пределы 64-битного диапазона, поэтому используются целые числа произвольной длины. Однако вычисление всё равно дёшево: на каждом шаге нужны только одно удвоение, два сложения и две проверки длины десятичной записи. Кроме того, реализации проверяют известный факт, что первые 8 разложений дают ровно 1 успешный случай; это одновременно подтверждает корректность рекуррентности и подсчёта.
Для общего ограничения \(N\) подходящие дроби растут как \((1+\sqrt{2})^N\), поэтому наибольшие числитель и знаменатель имеют \(\Theta(N)\) десятичных цифр. Значит, одна итерация стоит \(\Theta(k)\) операций над цифрами, если текущие значения имеют \(k\) цифр.
Суммарно это даёт \(\Theta(N^2)\) времени в цифро-операциях. Память составляет \(\Theta(N)\) цифр, так как алгоритм хранит только текущую пару и несколько временных длинных целых. Для конкретного случая \(N=1000\) числа имеют лишь около 383 цифр, так что программа работает очень быстро.
يمكن كتابة \(\sqrt{2}\) على صورة كسر مستمر بالشكل
$$\sqrt{2}=1+\cfrac{1}{2+\cfrac{1}{2+\cfrac{1}{2+\cdots}}}=[1;2,2,2,\dots].$$
وعند قطع هذا التعبير اللانهائي بعد عدد محدود من الطبقات نحصل على المتقاربات \(3/2, 7/5, 17/12, 41/29, \dots\). المطلوب هو عدّ كم واحدًا من أول 1000 متقارب يملك بسطًا عدد أرقامه العشرية أكبر من عدد أرقام المقام.
الفكرة الأساسية أن المسألة لا تحتاج إلى تقريب عشري لـ \(\sqrt{2}\) ولا إلى حسابات فاصلة عائمة. كل متقارب ينتج بدقة من المتقارب السابق باستخدام حسابات صحيحة فقط.
لنكتب المتقارب رقم \(k\) على الصورة
$$x_k=\frac{n_k}{d_k}, \qquad x_1=\frac{3}{2}.$$
وعندئذ تصبح المسألة هي عدّ جميع القيم \(k \le 1000\) التي يكون فيها عدد أرقام \(n_k\) أكبر من عدد أرقام \(d_k\).
إذا كان \(x_k\) هو المتقارب الحالي، فإن إضافة طبقة جديدة داخل الكسر المستمر تعطي
$$x_{k+1}=1+\frac{1}{1+x_k}.$$
وبالتعويض عن \(x_k=n_k/d_k\) نحصل على
$$x_{k+1}=1+\frac{1}{1+n_k/d_k}=1+\frac{d_k}{n_k+d_k}=\frac{n_k+2d_k}{n_k+d_k}.$$
إذن التحديث الصحيح للأعداد الصحيحة هو
$$n_{k+1}=n_k+2d_k,\qquad d_{k+1}=n_k+d_k.$$
هذه هي البنية الرياضية المركزية في الحل. التنفيذات تحتفظ فقط بالزوج الحالي \((n_k,d_k)\) وتكرر هذا التحويل.
يمكن إعادة كتابة هذا التحديث على صورة علاقة خطية من الرتبة الثانية. إذا حذفنا \(d_k\) نحصل على
$$n_{k+2}=2n_{k+1}+n_k,$$
وإذا حذفنا \(n_k\) نحصل على
$$d_{k+2}=2d_{k+1}+d_k.$$
إذن البسوط والمقامات تتبعان نفس العلاقة التي تظهر في أعداد Pell وفي المتتالية المرافقة لها. وهذا يفسر أمرين معًا: القيم تنمو بسرعة، لكن الحساب نفسه يظل بسيطًا لأن كل خطوة لا تحتوي إلا على جمع.
العلاقة العودية السابقة تحافظ على عدة خواص مهمة.
أولًا،
$$n_{k+1}-d_{k+1}=d_k>0,$$
ومن ثم فكل متقارب أكبر من \(1\).
وثانيًا، تبقى الكسور في أبسط صورة لأن
$$\gcd(n_k+2d_k,n_k+d_k)=\gcd(d_k,n_k+d_k)=\gcd(n_k,d_k).$$
ومادام \(\gcd(3,2)=1\) في البداية، فإن كل الأزواج اللاحقة تبقى متباينة أوليًا.
أما الثابت الأهم فهو هوية Pell ذات الإشارة المتناوبة:
$$n_k^2-2d_k^2=(-1)^{k+1}.$$
وهذه تخرج مباشرة من التحديث لأن
$$\left(n_k+2d_k\right)^2-2\left(n_k+d_k\right)^2=-(n_k^2-2d_k^2).$$
وبما أن الزوج الابتدائي \((3,2)\) يحقق \(3^2-2\cdot 2^2=1\)، فإن الإشارة تنقلب في كل خطوة. ونتيجة لذلك تتناوب المتقاربات فوق \(\sqrt{2}\) وتحته، كما أن الخطأ يساوي
$$\left|\frac{n_k}{d_k}-\sqrt{2}\right|=\frac{1}{d_k\left(n_k+d_k\sqrt{2}\right)}.$$
وهذا يوضح لماذا تصبح هذه الكسور دقيقة جدًا بسرعة كبيرة.
كل عدد صحيح موجب \(m\) يملك
$$\lfloor \log_{10} m \rfloor + 1$$
رقمًا عشريًا. لذلك فإن شرط المسألة يكافئ ببساطة
$$\lfloor \log_{10} n_k \rfloor > \lfloor \log_{10} d_k \rfloor.$$
وبما أن \(n_k/d_k \to \sqrt{2}\)، فإن البسط والمقام يكونان في العادة متقاربين جدًا في الحجم. الحالة المطلوبة تظهر فقط عندما يكون البسط قد تجاوز قوة جديدة للعدد \(10\) بينما لم يصل المقام إليها بعد. التنفيذ لا يحتاج إلى حساب اللوغاريتمات فعلًا؛ يكفي أن يقارن أطوال التمثيل العشري للأعداد الصحيحة الدقيقة.
بدءًا من \((n_1,d_1)=(3,2)\)، تعطي العلاقة العودية
$$ (3,2)\to(7,5)\to(17,12)\to(41,29)\to(99,70)\to(239,169)\to(577,408)\to(1393,985). $$
في الكسور السبعة الأولى المذكورة يكون عدد أرقام البسط مساويًا لعدد أرقام المقام. أما الكسر الثامن \(1393/985\) ففيه للبسط 4 أرقام وللمقام 3، ولذلك فهو أول حالة ناجحة. وهذه هي نقطة التحقق نفسها المستخدمة في التنفيذات: ضمن أول 8 توسعات يجب أن يكون العدد 1.
تنطلق تنفيذات C++ وPython وJava من أول متقارب مذكور في المسألة، وهو \(3/2\). وهي تحتفظ فقط بالبسط الحالي والمقام الحالي وعدّاد للحالات الناجحة.
في كل دورة من الحلقة يُفحَص أولًا ما إذا كان عدد أرقام البسط الحالي أكبر من عدد أرقام المقام الحالي. ثم يُحدَّث الزوج وفق القاعدة
$$ (n,d)\mapsto(n+2d,\;n+d). $$
ولا توجد أي عملية قسمة، ولا يوجد أي خطر من أخطاء التقريب العشري، لأن الحساب كله يبقى داخل حسابات صحيحة دقيقة.
بعد 1000 توسعة تصبح القيم أكبر بكثير من مدى 64 بت، لذلك تعتمد التنفيذات على أعداد صحيحة غير محدودة السعة. ومع ذلك يبقى الحمل الحسابي صغيرًا لأن كل خطوة تحتاج فقط إلى مضاعفة واحدة وجمعين وفحصين لطول التمثيل العشري. كما تتحقق التنفيذات من نقطة فحص معروفة، وهي أن أول 8 توسعات تعطي حالة ناجحة واحدة بالضبط، وبذلك يتم التأكد من صحة كل من العلاقة العودية ومنطق العد.
إذا عممنا المسألة إلى أول \(N\) توسعة، فإن المتقاربات تنمو تقريبًا مثل \((1+\sqrt{2})^N\)، ولذلك فإن أكبر بسط وأكبر مقام يملكان \(\Theta(N)\) رقمًا عشريًا. ومن ثم فإن كلفة دورة واحدة تكون \(\Theta(k)\) عمليات على الأرقام عندما تكون القيم الحالية بطول \(k\) أرقام.
وبجمع هذه الكلفة على جميع الدورات نحصل على زمن إجمالي \(\Theta(N^2)\) من حيث عمليات الأرقام. أما الذاكرة فهي \(\Theta(N)\) رقمًا لأن الخوارزمية تخزن الزوج الحالي فقط مع عدد صغير من القيم المؤقتة. وفي الحالة المحددة \(N=1000\) لا يتجاوز طول الأعداد نحو 383 رقمًا، لذا يكون التنفيذ سريعًا جدًا عمليًا.