For each non-square integer \(D \le 1000\), Pell's equation
$$x^2 - Dy^2 = 1$$
has infinitely many positive integer solutions, and among them there is a unique fundamental solution with the smallest positive \(x\). The problem asks for the value of \(D\) whose fundamental solution has the largest \(x\). The search over \(D \le 1000\) ends at \(D = 661\).
A brute-force search in \(x\) or \(y\) is not realistic, because the minimal solution can already be enormous for moderate \(D\). The right viewpoint is to study the periodic continued fraction of \(\sqrt{D}\), because its convergents produce exactly the candidates that can solve Pell's equation.
The implementations do not guess solutions numerically. They generate the continued fraction data for \(\sqrt{D}\), turn that data into convergents, and stop at the first convergent that satisfies the Pell identity.
If \(D\) is not a square, then \(\sqrt{D}\) is a quadratic irrational, so its simple continued fraction is periodic:
$$\sqrt{D} = [a_0; \overline{a_1,a_2,\dots,a_r}].$$
The convergents of this expansion are the best rational approximations to \(\sqrt{D}\) in a precise number-theoretic sense. For Pell's equation, that matters because if
$$\frac{p}{q} \approx \sqrt{D},$$
then
$$p^2 - Dq^2$$
is forced to be small. The remarkable theorem behind the method is that the fundamental solution of \(x^2 - Dy^2 = 1\) appears among these convergents, so scanning convergents is enough.
The continued fraction is generated from the standard complete-quotient state. Start with
$$a_0 = \lfloor \sqrt{D} \rfloor,\qquad m_0 = 0,\qquad d_0 = 1.$$
At each stage define
$$\alpha_n = \frac{\sqrt{D} + m_n}{d_n},\qquad a_n = \lfloor \alpha_n \rfloor.$$
The next state is given by the recurrences used directly in the code:
$$m_{n+1} = d_n a_n - m_n,$$
$$d_{n+1} = \frac{D - m_{n+1}^2}{d_n},$$
$$a_{n+1} = \left\lfloor \frac{a_0 + m_{n+1}}{d_{n+1}} \right\rfloor.$$
Two invariants make this work. First, \(d_n\) always divides \(D - m_n^2\), so the division is exact. Second, each complete quotient keeps the form \((\sqrt{D}+m_n)/d_n\). Because only finitely many such states can occur for fixed \(D\), the sequence eventually repeats, which is exactly the periodicity of the continued fraction of \(\sqrt{D}\).
Once the coefficients \(a_n\) are available, the convergents are built from the usual two-step recurrence:
$$p_{-1}=1,\quad p_0=a_0,\qquad q_{-1}=0,\quad q_0=1,$$
$$p_{n+1}=a_{n+1}p_n+p_{n-1},\qquad q_{n+1}=a_{n+1}q_n+q_{n-1}.$$
Every convergent \(p_n/q_n\) is a better approximation to \(\sqrt{D}\), so the quantity
$$p_n^2 - D q_n^2$$
keeps landing on small integers such as \(-1\), \(1\), \(3\), or \(-4\). The first time it becomes exactly \(1\), the current numerator \(p_n\) is the fundamental \(x\). Classical theory says that this happens after one traversal of the repeating block when the period length is even and after two traversals when it is odd, but the implementations do not need to compute the period length explicitly. They simply keep iterating until the Pell test succeeds.
The problem statement already highlights \(D=13\), and it is a useful example because the first solution is not small. Here
$$\sqrt{13} = [3; \overline{1,1,1,1,6}].$$
The complete-quotient state begins
$$ (m,d,a) = (0,1,3) \to (3,4,1) \to (1,3,1) \to (2,3,1) \to (1,4,1) \to (3,1,6) \to \cdots $$
and the convergents are
$$3,\ \frac{4}{1},\ \frac{7}{2},\ \frac{11}{3},\ \frac{18}{5},\ \frac{119}{33},\ \frac{137}{38},\ \frac{256}{71},\ \frac{393}{109},\ \frac{649}{180}.$$
Evaluating the Pell expression shows the progression
$$-4,\ 3,\ -3,\ 4,\ -1,\ 4,\ -3,\ 3,\ -4,\ 1.$$
So the first hit of \(1\) occurs at
$$649^2 - 13 \cdot 180^2 = 1,$$
which means the fundamental solution is \((x,y)=(649,180)\). This is exactly the kind of loop the implementations perform for every non-square \(D\).
The C++, Python, and Java implementations scan \(D=2,3,\dots,1000\). If \(D\) is a perfect square, that case is skipped immediately, because \(x^2 - Dy^2 = 1\) would then factor in a way that leaves only the trivial \(y=0\) solution and no meaningful Pell search.
For each non-square \(D\), the implementation stores only the current continued-fraction state \((m,d,a)\) and the previous two convergents. After each update it checks whether the new pair satisfies \(p^2 - Dq^2 = 1\). The first success is returned as the minimal \(x\) for that \(D\). This avoids storing the entire period and avoids any separate parity logic.
Finally, the implementation compares that \(x\) against the best one seen so far and keeps the corresponding \(D\). The built-in sanity checks verify two small prefixes of the search: for \(D \le 7\) the answer is \(5\), and for \(D \le 13\) the answer is \(13\).
Let \(\ell_D\) be the number of continued-fraction coefficients processed for a given non-square \(D\) before the first solution is found. Then that case performs \(O(\ell_D)\) recurrence steps. The state variables \(m\), \(d\), and \(a\) stay small, but the convergents grow with the size of the fundamental solution, so the dominant work is big-integer arithmetic on numbers with \(O(\log x_D)\) bits.
Across all \(D \le 1000\), the total running time is the sum of those per-\(D\) costs and is easily practical for this range. Memory usage is \(O(\log x_{\max})\) bits, because the algorithm keeps only a constant number of big integers at any moment rather than the whole history of coefficients or convergents.
Für jede nichtquadratische ganze Zahl \(D \le 1000\) besitzt die Pell-Gleichung
$$x^2 - Dy^2 = 1$$
unendlich viele positive ganzzahlige Lösungen. Unter ihnen gibt es eine eindeutige Fundamentallösung mit dem kleinsten positiven \(x\). Gesucht ist dasjenige \(D\), für das dieses minimale \(x\) maximal wird. Die Suche über alle \(D \le 1000\) liefert schließlich \(D = 661\).
Brute Force über \(x\) oder \(y\) ist hier keine ernsthafte Option, weil die kleinste Lösung schon für relativ kleine Werte von \(D\) sehr groß werden kann. Der richtige Zugang ist deshalb die periodische Kettenbruchentwicklung von \(\sqrt{D}\), denn ihre Näherungsbrüche liefern genau die Kandidaten für Pell-Lösungen.
Die Implementierungen raten keine Lösungen. Sie erzeugen die Kettenbruchdaten von \(\sqrt{D}\), berechnen daraus Näherungsbrüche und stoppen beim ersten Näherungsbruch, der die Pell-Gleichung exakt erfüllt.
Ist \(D\) keine Quadratzahl, dann ist \(\sqrt{D}\) eine quadratische Irrationalzahl, und ihr einfacher Kettenbruch ist periodisch:
$$\sqrt{D} = [a_0; \overline{a_1,a_2,\dots,a_r}].$$
Die Näherungsbrüche dieser Entwicklung sind in präzisem Sinn die besten rationalen Approximationen an \(\sqrt{D}\). Für Pell ist das entscheidend, denn wenn
$$\frac{p}{q} \approx \sqrt{D},$$
dann ist auch
$$p^2 - Dq^2$$
zwangsläufig klein. Der grundlegende Satz hinter dem Verfahren sagt, dass die Fundamentallösung von \(x^2-Dy^2=1\) unter diesen Näherungsbrüchen auftaucht. Es reicht also, genau diese Folge zu untersuchen.
Die Kettenbruchentwicklung wird über den Standardzustand der vollständigen Quotienten erzeugt. Man beginnt mit
$$a_0 = \lfloor \sqrt{D} \rfloor,\qquad m_0 = 0,\qquad d_0 = 1.$$
In jedem Schritt setzt man
$$\alpha_n = \frac{\sqrt{D} + m_n}{d_n},\qquad a_n = \lfloor \alpha_n \rfloor.$$
Dann entstehen die nächsten Werte durch genau die Rekurrenzen, die auch im Code verwendet werden:
$$m_{n+1} = d_n a_n - m_n,$$
$$d_{n+1} = \frac{D - m_{n+1}^2}{d_n},$$
$$a_{n+1} = \left\lfloor \frac{a_0 + m_{n+1}}{d_{n+1}} \right\rfloor.$$
Dabei bleiben zwei Invarianten erhalten. Erstens teilt \(d_n\) stets die Zahl \(D-m_n^2\), also ist die Division exakt. Zweitens behält jeder vollständige Quotient die Form \((\sqrt{D}+m_n)/d_n\). Für festes \(D\) gibt es nur endlich viele solche Zustände, also muss sich die Folge wiederholen. Genau daraus entsteht die Periodizität der Kettenbruchentwicklung von \(\sqrt{D}\).
Sobald die Koeffizienten \(a_n\) bekannt sind, werden die Näherungsbrüche mit der üblichen Zweischritt-Rekurrenz berechnet:
$$p_{-1}=1,\quad p_0=a_0,\qquad q_{-1}=0,\quad q_0=1,$$
$$p_{n+1}=a_{n+1}p_n+p_{n-1},\qquad q_{n+1}=a_{n+1}q_n+q_{n-1}.$$
Jeder Näherungsbruch \(p_n/q_n\) approximiert \(\sqrt{D}\) genauer, daher nimmt
$$p_n^2 - D q_n^2$$
wiederholt kleine Werte wie \(-1\), \(1\), \(3\) oder \(-4\) an. Sobald dieser Ausdruck zum ersten Mal genau \(1\) wird, ist der aktuelle Zähler \(p_n\) das gesuchte minimale \(x\). Theoretisch geschieht das nach einer Periodendurchquerung bei gerader Periodenlänge und nach zwei Durchquerungen bei ungerader Periodenlänge. Die Implementierungen müssen diese Parität aber nicht separat bestimmen, weil sie die Pell-Bedingung einfach nach jedem Schritt testen.
Das Beispiel \(D=13\) aus der Aufgabenstellung ist besonders lehrreich, weil die erste Lösung schon deutlich größer ist. Hier gilt
$$\sqrt{13} = [3; \overline{1,1,1,1,6}].$$
Der Zustandsablauf beginnt mit
$$ (m,d,a) = (0,1,3) \to (3,4,1) \to (1,3,1) \to (2,3,1) \to (1,4,1) \to (3,1,6) \to \cdots $$
und die zugehörigen Näherungsbrüche lauten
$$3,\ \frac{4}{1},\ \frac{7}{2},\ \frac{11}{3},\ \frac{18}{5},\ \frac{119}{33},\ \frac{137}{38},\ \frac{256}{71},\ \frac{393}{109},\ \frac{649}{180}.$$
Setzt man diese Werte in den Pell-Ausdruck ein, erhält man
$$-4,\ 3,\ -3,\ 4,\ -1,\ 4,\ -3,\ 3,\ -4,\ 1.$$
Der erste Treffer mit \(1\) ist also
$$649^2 - 13 \cdot 180^2 = 1,$$
und damit ist die Fundamentallösung \((x,y)=(649,180)\). Genau diese Schleife führen die Implementierungen für jedes nichtquadratische \(D\) aus.
Die C++-, Python- und Java-Implementierungen durchlaufen \(D=2,3,\dots,1000\). Ist \(D\) eine Quadratzahl, wird dieser Fall sofort übersprungen, denn dann besitzt \(x^2-Dy^2=1\) keine nichttriviale positive Pell-Lösung mit \(y \gt 0\).
Für jedes nichtquadratische \(D\) speichert die Implementierung nur den aktuellen Kettenbruchzustand \((m,d,a)\) und die beiden letzten Näherungsbrüche. Nach jedem Update wird geprüft, ob das neue Paar \(p^2-Dq^2=1\) erfüllt. Der erste Erfolg liefert direkt das minimale \(x\) für dieses \(D\). Deshalb muss weder die ganze Periode gespeichert noch ihre Länge separat bestimmt werden.
Am Ende wird dieses \(x\) mit dem bisher größten Wert verglichen, und das zugehörige \(D\) wird gemerkt. Kleine eingebaute Plausibilitätsprüfungen bestätigen zwei Anfangsbereiche der Suche: Für \(D \le 7\) ist die Antwort \(5\), und für \(D \le 13\) ist die Antwort \(13\).
Sei \(\ell_D\) die Anzahl verarbeiteter Kettenbruchkoeffizienten für ein festes nichtquadratisches \(D\), bis die erste Lösung gefunden ist. Dann braucht dieser Fall \(O(\ell_D)\) Rekurrenzschritte. Die Zustandsgrößen \(m\), \(d\) und \(a\) bleiben klein, aber die Näherungsbrüche wachsen mit der Größe der Fundamentallösung. Die eigentliche Laufzeit wird daher von Operationen auf großen Ganzzahlen mit \(O(\log x_D)\) Bits bestimmt.
Über alle \(D \le 1000\) addieren sich diese Kosten, bleiben aber für diese Schranke sehr klein. Der Speicherbedarf beträgt \(O(\log x_{\max})\) Bits, weil nur eine konstante Anzahl aktueller und vorheriger großer Ganzzahlen gehalten wird und nicht die gesamte Historie der Koeffizienten oder Näherungsbrüche.
\(D \le 1000\) için kare olmayan her tam sayı üzerinde Pell denklemi
$$x^2 - Dy^2 = 1$$
sonsuz sayıda pozitif tamsayı çözüm üretir. Bunların içinde, pozitif \(x\) değeri en küçük olan tek bir temel çözüm vardır. Soru, temel çözümdeki \(x\) değeri en büyük olan \(D\)'yi istemektedir. Tarama tüm \(D \le 1000\) için yapıldığında sonuç \(D = 661\) olur.
\(x\) ya da \(y\) üzerinde kaba kuvvet araması yapmak pratik değildir; çünkü en küçük çözüm bile bazı orta büyüklükteki \(D\) değerlerinde çok hızlı büyür. Bu yüzden doğru matematiksel nesne \(\sqrt{D}\)'nin periyodik sürekli kesridir. O sürekli kesrin yakınsakları, Pell denklemini sağlayabilecek adayları sistemli biçimde verir.
Uygulamalar çözümü sayısal tahminle bulmaz. Önce \(\sqrt{D}\) için sürekli kesir verisini üretir, sonra bu veriden yakınsakları kurar ve Pell özdeşliğini ilk sağlayan yakınsakta durur.
\(D\) bir kare değilse \(\sqrt{D}\) ikinci dereceden irrasyoneldir ve basit sürekli kesri periyodiktir:
$$\sqrt{D} = [a_0; \overline{a_1,a_2,\dots,a_r}].$$
Bu açılımın yakınsakları, \(\sqrt{D}\)'ye en iyi rasyonel yaklaşımlar arasında yer alır. Pell denklemi için kritik nokta şudur:
$$\frac{p}{q} \approx \sqrt{D}$$
ise
$$p^2 - Dq^2$$
genellikle küçük bir tam sayı olur. Yöntemin dayandığı temel teorem, \(x^2-Dy^2=1\) denkleminin temel çözümünün bu yakınsaklardan biri olduğunu söyler. Dolayısıyla aranacak uzay, rastgele tüm kesirler değil, yalnızca bu düzenli yakınsak dizisidir.
Sürekli kesir, tam kesir durumları üzerinden üretilir. Başlangıç değerleri
$$a_0 = \lfloor \sqrt{D} \rfloor,\qquad m_0 = 0,\qquad d_0 = 1$$
şeklindedir. Her adımda
$$\alpha_n = \frac{\sqrt{D} + m_n}{d_n},\qquad a_n = \lfloor \alpha_n \rfloor$$
tanımlanır ve sonraki durum, kodda doğrudan kullanılan şu bağıntılarla elde edilir:
$$m_{n+1} = d_n a_n - m_n,$$
$$d_{n+1} = \frac{D - m_{n+1}^2}{d_n},$$
$$a_{n+1} = \left\lfloor \frac{a_0 + m_{n+1}}{d_{n+1}} \right\rfloor.$$
Burada iki önemli değişmez vardır. Birincisi, \(d_n\) her zaman \(D-m_n^2\) ifadesini böler; yani bölme tamdır. İkincisi, her ara ifade yine \((\sqrt{D}+m_n)/d_n\) biçiminde kalır. Sabit bir \(D\) için bu tür durumların sayısı sonlu olduğundan durumlar sonunda tekrar eder; periyodik sürekli kesir de tam olarak bu tekrarın sonucudur.
Katsayılar üretildikten sonra yakınsaklar standart iki adımlı bağıntıyla hesaplanır:
$$p_{-1}=1,\quad p_0=a_0,\qquad q_{-1}=0,\quad q_0=1,$$
$$p_{n+1}=a_{n+1}p_n+p_{n-1},\qquad q_{n+1}=a_{n+1}q_n+q_{n-1}.$$
Her yeni \(p_n/q_n\) kesri \(\sqrt{D}\)'ye biraz daha iyi yaklaşır; bu yüzden
$$p_n^2 - D q_n^2$$
ifadesi sık sık \(-1\), \(1\), \(3\) ya da \(-4\) gibi küçük değerlere iner. İlk kez tam olarak \(1\) elde edildiğinde mevcut pay \(p_n\), aranan temel \(x\) olur. Kuramsal olarak periyot uzunluğu çiftse bu başarı bir periyot dolaşımından sonra, tekse iki dolaşımdan sonra gelir. Uygulamalar ise bu pariteyi ayrıca hesaplamaz; her yakınsaktan sonra doğrudan Pell testini yapar.
Soruda verilen \(D=13\) örneği özellikle öğreticidir; çünkü ilk çözüm küçük değildir. Burada
$$\sqrt{13} = [3; \overline{1,1,1,1,6}]$$
olur. Durum zinciri şu şekilde başlar:
$$ (m,d,a) = (0,1,3) \to (3,4,1) \to (1,3,1) \to (2,3,1) \to (1,4,1) \to (3,1,6) \to \cdots $$
Buna karşılık gelen yakınsaklar ise
$$3,\ \frac{4}{1},\ \frac{7}{2},\ \frac{11}{3},\ \frac{18}{5},\ \frac{119}{33},\ \frac{137}{38},\ \frac{256}{71},\ \frac{393}{109},\ \frac{649}{180}$$
şeklindedir. Pell ifadesi sırasıyla
$$-4,\ 3,\ -3,\ 4,\ -1,\ 4,\ -3,\ 3,\ -4,\ 1$$
değerlerini verir. Dolayısıyla ilk gerçek çözüm
$$649^2 - 13 \cdot 180^2 = 1$$
olup temel çözüm \((x,y)=(649,180)\) olur. Program tam olarak bu döngüyü her kare olmayan \(D\) için tekrarlar.
C++, Python ve Java uygulamaları \(D=2,3,\dots,1000\) aralığını tarar. Eğer \(D\) bir tam kare ise o durum hemen geçilir; çünkü bu durumda \(x^2-Dy^2=1\) denkleminde \(y \gt 0\) için anlamlı bir Pell çözümü kalmaz.
Her kare olmayan \(D\) için uygulama yalnızca güncel sürekli kesir durumunu \((m,d,a)\) ve son iki yakınsağı tutar. Her güncellemeden sonra yeni çiftin \(p^2-Dq^2=1\) sağlayıp sağlamadığı kontrol edilir. İlk başarı, o \(D\) için minimal \(x\) değeridir. Böylece ne tüm periyodu saklamak ne de periyot uzunluğunu ayrıca çıkarmak gerekir.
Son adımda bu \(x\) değeri şimdiye kadar görülen en büyük değerle karşılaştırılır ve ilgili \(D\) korunur. Uygulamalardaki küçük doğrulama kontrolleri de bunu destekler: \(D \le 7\) için cevap \(5\), \(D \le 13\) için cevap \(13\) çıkar.
\(\ell_D\), belirli bir kare olmayan \(D\) için ilk çözüm bulunana kadar işlenen sürekli kesir katsayısı sayısı olsun. O zaman bu tek durum \(O(\ell_D)\) yineleme adımı yapar. \(m\), \(d\) ve \(a\) küçük kalır; asıl maliyet, temel çözüm büyüdükçe büyüyen yakınsaklar üzerinde yapılan büyük tamsayı işlemleridir. Bu sayılar yaklaşık \(O(\log x_D)\) bit uzunluğundadır.
Tüm \(D \le 1000\) üzerinde toplam çalışma süresi bu tekil maliyetlerin toplamıdır ve bu sınır için fazlasıyla pratiktir. Bellek kullanımı \(O(\log x_{\max})\) bittir; çünkü aynı anda yalnızca sabit sayıda büyük tamsayı tutulur, tüm katsayı ya da yakınsak geçmişi değil.
Para cada entero no cuadrado \(D \le 1000\), la ecuación de Pell
$$x^2 - Dy^2 = 1$$
tiene infinitas soluciones enteras positivas. Entre ellas hay una solución fundamental, la que tiene el menor \(x\) positivo. El problema pide el valor de \(D\) cuyo \(x\) fundamental es el mayor. Al recorrer todos los \(D \le 1000\), el resultado final es \(D = 661\).
Buscar por fuerza bruta en \(x\) o en \(y\) no funciona, porque incluso la solución mínima puede ser enorme. La estructura correcta es la fracción continua periódica de \(\sqrt{D}\): sus convergentes producen exactamente los candidatos que pueden satisfacer la identidad de Pell.
Las implementaciones no prueban valores al azar. Generan la fracción continua de \(\sqrt{D}\), convierten sus coeficientes en convergentes y se detienen en el primer convergente que cumple la ecuación.
Si \(D\) no es un cuadrado perfecto, entonces \(\sqrt{D}\) es una irracional cuadrática y su fracción continua simple es periódica:
$$\sqrt{D} = [a_0; \overline{a_1,a_2,\dots,a_r}].$$
Los convergentes de esta expansión son aproximaciones racionales excepcionalmente buenas de \(\sqrt{D}\). Eso importa porque, si
$$\frac{p}{q} \approx \sqrt{D},$$
entonces
$$p^2 - Dq^2$$
queda forzado a ser pequeño. El teorema clave dice que la solución fundamental de \(x^2-Dy^2=1\) aparece entre esos convergentes. Por tanto, no hace falta explorar todos los enteros posibles: basta con seguir una secuencia muy estructurada.
La fracción continua se genera mediante el estado estándar de los cocientes completos. Se empieza con
$$a_0 = \lfloor \sqrt{D} \rfloor,\qquad m_0 = 0,\qquad d_0 = 1.$$
En cada etapa se define
$$\alpha_n = \frac{\sqrt{D} + m_n}{d_n},\qquad a_n = \lfloor \alpha_n \rfloor.$$
El siguiente estado viene dado por las mismas fórmulas que usan directamente las implementaciones:
$$m_{n+1} = d_n a_n - m_n,$$
$$d_{n+1} = \frac{D - m_{n+1}^2}{d_n},$$
$$a_{n+1} = \left\lfloor \frac{a_0 + m_{n+1}}{d_{n+1}} \right\rfloor.$$
Hay dos invariantes importantes. Primero, \(d_n\) siempre divide a \(D-m_n^2\), así que la división es exacta. Segundo, cada cociente completo sigue teniendo la forma \((\sqrt{D}+m_n)/d_n\). Como para un \(D\) fijo sólo pueden aparecer finitos estados de este tipo, la secuencia termina repitiéndose, y esa repetición es precisamente la periodicidad de la fracción continua de \(\sqrt{D}\).
Una vez conocidos los coeficientes \(a_n\), los convergentes se construyen con la recurrencia habitual de dos términos:
$$p_{-1}=1,\quad p_0=a_0,\qquad q_{-1}=0,\quad q_0=1,$$
$$p_{n+1}=a_{n+1}p_n+p_{n-1},\qquad q_{n+1}=a_{n+1}q_n+q_{n-1}.$$
Cada convergente \(p_n/q_n\) aproxima mejor a \(\sqrt{D}\), así que la cantidad
$$p_n^2 - D q_n^2$$
va tomando enteros pequeños como \(-1\), \(1\), \(3\) o \(-4\). El primer momento en que vale exactamente \(1\) da la solución fundamental, y el numerador actual es el \(x\) buscado. La teoría clásica dice que, si la longitud del período es par, eso ocurre tras una vuelta del bloque repetitivo, y si es impar, tras dos vueltas. Las implementaciones no necesitan detectar esa paridad: simplemente comprueban la identidad de Pell después de cada convergente.
El ejemplo \(D=13\) del enunciado es especialmente útil porque la primera solución ya es bastante grande. Aquí
$$\sqrt{13} = [3; \overline{1,1,1,1,6}].$$
La secuencia de estados empieza como
$$ (m,d,a) = (0,1,3) \to (3,4,1) \to (1,3,1) \to (2,3,1) \to (1,4,1) \to (3,1,6) \to \cdots $$
y los convergentes correspondientes son
$$3,\ \frac{4}{1},\ \frac{7}{2},\ \frac{11}{3},\ \frac{18}{5},\ \frac{119}{33},\ \frac{137}{38},\ \frac{256}{71},\ \frac{393}{109},\ \frac{649}{180}.$$
Si evaluamos la expresión de Pell, obtenemos
$$-4,\ 3,\ -3,\ 4,\ -1,\ 4,\ -3,\ 3,\ -4,\ 1.$$
Por lo tanto, el primer acierto real es
$$649^2 - 13 \cdot 180^2 = 1,$$
de modo que la solución fundamental es \((x,y)=(649,180)\). Ese mismo ciclo es el que repite el algoritmo para cada \(D\) no cuadrado.
Las implementaciones en C++, Python y Java recorren \(D=2,3,\dots,1000\). Si \(D\) es un cuadrado perfecto, ese caso se descarta enseguida, porque entonces \(x^2-Dy^2=1\) no deja una búsqueda no trivial de Pell con \(y \gt 0\).
Para cada \(D\) no cuadrado, la implementación mantiene sólo el estado actual \((m,d,a)\) de la fracción continua y los dos convergentes anteriores. Tras cada actualización comprueba si el nuevo par satisface \(p^2-Dq^2=1\). El primer éxito se devuelve como el \(x\) mínimo para ese \(D\). Así se evita guardar todo el período y también se evita una lógica separada para la paridad del período.
Al final, ese \(x\) se compara con el mejor visto hasta el momento y se conserva el \(D\) correspondiente. Las comprobaciones internas validan dos prefijos pequeños del barrido: para \(D \le 7\) la respuesta es \(5\), y para \(D \le 13\) la respuesta es \(13\).
Sea \(\ell_D\) el número de coeficientes de la fracción continua procesados para un \(D\) no cuadrado antes de encontrar la primera solución. Entonces ese caso realiza \(O(\ell_D)\) iteraciones. Las variables \(m\), \(d\) y \(a\) permanecen pequeñas, pero los convergentes crecen con el tamaño de la solución fundamental, así que el coste dominante es la aritmética de enteros grandes sobre números de \(O(\log x_D)\) bits.
Sumando sobre todos los \(D \le 1000\), el tiempo total sigue siendo muy cómodo para este rango. El espacio usado es \(O(\log x_{\max})\) bits, porque el algoritmo conserva sólo una cantidad constante de enteros grandes y no toda la historia de coeficientes o convergentes.
对每个不超过 \(1000\) 的非平方整数 \(D\)，佩尔方程
$$x^2 - Dy^2 = 1$$
都有无穷多个正整数解。其中存在唯一的基本解，也就是正 \(x\) 最小的那组解。题目要求找出使这个最小 \(x\) 最大的 \(D\)。把所有 \(D \le 1000\) 扫描完以后，得到的结果是 \(D = 661\)。
如果直接枚举 \(x\) 或 \(y\)，计算会很快失控，因为最小解本身就可能非常大。真正适合这个问题的对象是 \(\sqrt{D}\) 的周期连分数展开。它的渐近分数不会随机出现，而是恰好给出所有最重要的候选值，其中就包含佩尔方程的基本解。
这些实现并不是靠试错去碰运气。它们先生成 \(\sqrt{D}\) 的连分数系数，再用这些系数递推渐近分数，并在每一步检查当前渐近分数是否已经满足佩尔恒等式。
当 \(D\) 不是完全平方数时，\(\sqrt{D}\) 是二次无理数，它的简单连分数一定是周期性的：
$$\sqrt{D} = [a_0; \overline{a_1,a_2,\dots,a_r}].$$
这个展开的渐近分数是 \(\sqrt{D}\) 的最佳有理逼近之一。对于佩尔方程，这一点非常关键，因为如果
$$\frac{p}{q} \approx \sqrt{D},$$
那么
$$p^2 - Dq^2$$
就会被压缩成一个很小的整数。支撑整个方法的经典定理告诉我们：\(x^2-Dy^2=1\) 的基本解一定出现在这些渐近分数之中。因此无需在所有整数上盲搜，只要沿着连分数给出的结构化序列向前推进即可。
连分数系数由完整商状态递推产生。初值为
$$a_0 = \lfloor \sqrt{D} \rfloor,\qquad m_0 = 0,\qquad d_0 = 1.$$
在第 \(n\) 步，定义
$$\alpha_n = \frac{\sqrt{D} + m_n}{d_n},\qquad a_n = \lfloor \alpha_n \rfloor.$$
然后通过下列公式进入下一步：
$$m_{n+1} = d_n a_n - m_n,$$
$$d_{n+1} = \frac{D - m_{n+1}^2}{d_n},$$
$$a_{n+1} = \left\lfloor \frac{a_0 + m_{n+1}}{d_{n+1}} \right\rfloor.$$
这组递推之所以可靠，是因为有两个关键不变量。第一，\(d_n\) 总能整除 \(D-m_n^2\)，所以除法始终是精确的。第二，每个完整商始终保持 \((\sqrt{D}+m_n)/d_n\) 这种形式。对于固定的 \(D\)，可出现的状态数量有限，因此状态最终必然重复，而这种重复正是 \(\sqrt{D}\) 连分数的周期性来源。
一旦系数 \(a_n\) 被生成出来，渐近分数就用标准的二阶递推来构造：
$$p_{-1}=1,\quad p_0=a_0,\qquad q_{-1}=0,\quad q_0=1,$$
$$p_{n+1}=a_{n+1}p_n+p_{n-1},\qquad q_{n+1}=a_{n+1}q_n+q_{n-1}.$$
随着 \(p_n/q_n\) 越来越接近 \(\sqrt{D}\)，表达式
$$p_n^2 - D q_n^2$$
会不断落到很小的整数上，例如 \(-1\)、\(1\)、\(3\)、\(-4\)。第一次精确等于 \(1\) 的那一步，就是我们要找的基本解；当时的分子 \(p_n\) 就是最小的正 \(x\)。理论上，如果周期长度是偶数，第一次得到 \(1\) 会出现在重复块走完一遍之后；如果周期长度是奇数，则通常要走两遍。实现并不需要显式求出周期长度或判断奇偶性，因为它在每次更新后都会直接检查佩尔恒等式。
题目描述里已经给出了 \(D=13\)，这个例子非常合适，因为它说明最小解并不一定很小。这里有
$$\sqrt{13} = [3; \overline{1,1,1,1,6}].$$
对应的状态序列开头为
$$ (m,d,a) = (0,1,3) \to (3,4,1) \to (1,3,1) \to (2,3,1) \to (1,4,1) \to (3,1,6) \to \cdots $$
渐近分数依次是
$$3,\ \frac{4}{1},\ \frac{7}{2},\ \frac{11}{3},\ \frac{18}{5},\ \frac{119}{33},\ \frac{137}{38},\ \frac{256}{71},\ \frac{393}{109},\ \frac{649}{180}.$$
把这些值代入佩尔表达式，会得到
$$-4,\ 3,\ -3,\ 4,\ -1,\ 4,\ -3,\ 3,\ -4,\ 1.$$
因此第一次真正命中 \(1\) 的地方是
$$649^2 - 13 \cdot 180^2 = 1,$$
所以基本解是 \((x,y)=(649,180)\)。程序对每个非平方 \(D\) 做的事情，本质上就是重复这一套状态更新与检测流程。
C++、Python 和 Java 实现都会按顺序扫描 \(D=2,3,\dots,1000\)。如果某个 \(D\) 是完全平方数，就立刻跳过，因为那时 \(x^2-Dy^2=1\) 不会产生带 \(y \gt 0\) 的非平凡佩尔搜索问题。
对于每个非平方 \(D\)，实现只保存当前的连分数状态 \((m,d,a)\) 以及前两个渐近分数。每次更新以后，都立即检查新的 \((p,q)\) 是否满足 \(p^2-Dq^2=1\)。第一次成功时，当前分子就是该 \(D\) 的最小 \(x\)。这样就不需要存下整个周期，也不需要额外写一套“先求周期长度、再根据奇偶决定停点”的逻辑。
最后，程序把这个 \(x\) 与目前见过的最大值比较，并保留对应的 \(D\)。实现里还带有两个小型正确性检查：当上界取 \(7\) 时答案应为 \(5\)，当上界取 \(13\) 时答案应为 \(13\)。
设 \(\ell_D\) 表示对某个非平方 \(D\) 来说，在找到第一组解之前处理了多少个连分数系数。那么该 \(D\) 的工作量就是 \(O(\ell_D)\) 次递推。状态变量 \(m\)、\(d\)、\(a\) 本身都很小，真正占时间的是大整数上的运算，因为渐近分数的大小会随基本解一起增长，大约需要 \(O(\log x_D)\) 位来表示。
把所有 \(D \le 1000\) 的成本相加，整体运行时间在这个范围内依然很轻松。空间复杂度是 \(O(\log x_{\max})\) 位，因为算法任何时刻只保留常数个大整数，而不是保存整段系数序列或全部渐近分数历史。
Для каждого не являющегося квадратом целого числа \(D \le 1000\) уравнение Пелля
$$x^2 - Dy^2 = 1$$
имеет бесконечно много положительных целочисленных решений. Среди них есть единственное фундаментальное решение, то есть решение с наименьшим положительным \(x\). Требуется найти такое \(D\), для которого это минимальное \(x\) максимально. При полном переборе всех \(D \le 1000\) получается ответ \(D = 661\).
Перебирать \(x\) или \(y\) напрямую бессмысленно: даже минимальное решение может оказаться огромным. Правильный объект здесь - периодическая цепная дробь для \(\sqrt{D}\). Ее подходящие дроби образуют именно ту последовательность, в которой и появляется фундаментальное решение.
Во всех реализациях решение не угадывается перебором. Сначала строится цепная дробь для \(\sqrt{D}\), затем по ее коэффициентам вычисляются подходящие дроби, и процесс останавливается в первый момент, когда выполняется тождество Пелля.
Если \(D\) не является полным квадратом, то \(\sqrt{D}\) - квадратическая иррациональность, а ее простая цепная дробь периодична:
$$\sqrt{D} = [a_0; \overline{a_1,a_2,\dots,a_r}].$$
Подходящие дроби этой записи дают особенно хорошие рациональные приближения к \(\sqrt{D}\). Для уравнения Пелля это важно, потому что из приближения
$$\frac{p}{q} \approx \sqrt{D}$$
следует, что значение
$$p^2 - Dq^2$$
становится маленьким целым числом. Классический результат утверждает, что фундаментальное решение уравнения \(x^2-Dy^2=1\) обязательно возникает среди этих подходящих дробей. Поэтому вместо хаотического поиска по всем парам \((x,y)\) достаточно идти по строго определенной последовательности.
Цепная дробь строится через стандартное состояние полных частных. Начальные значения таковы:
$$a_0 = \lfloor \sqrt{D} \rfloor,\qquad m_0 = 0,\qquad d_0 = 1.$$
На \(n\)-м шаге вводятся
$$\alpha_n = \frac{\sqrt{D} + m_n}{d_n},\qquad a_n = \lfloor \alpha_n \rfloor.$$
Далее выполняются рекурсии, которые буквально реализованы в коде:
$$m_{n+1} = d_n a_n - m_n,$$
$$d_{n+1} = \frac{D - m_{n+1}^2}{d_n},$$
$$a_{n+1} = \left\lfloor \frac{a_0 + m_{n+1}}{d_{n+1}} \right\rfloor.$$
Здесь важны два инварианта. Во-первых, \(d_n\) всегда делит \(D-m_n^2\), так что деление остается точным. Во-вторых, каждое полное частное снова имеет вид \((\sqrt{D}+m_n)/d_n\). Для фиксированного \(D\) таких состояний конечное число, значит, рано или поздно состояние повторится. Именно это повторение и создает период цепной дроби для \(\sqrt{D}\).
Когда коэффициенты \(a_n\) уже известны, подходящие дроби вычисляются стандартной двухшаговой рекурсией:
$$p_{-1}=1,\quad p_0=a_0,\qquad q_{-1}=0,\quad q_0=1,$$
$$p_{n+1}=a_{n+1}p_n+p_{n-1},\qquad q_{n+1}=a_{n+1}q_n+q_{n-1}.$$
Каждая новая дробь \(p_n/q_n\) лучше приближает \(\sqrt{D}\), поэтому выражение
$$p_n^2 - D q_n^2$$
часто принимает небольшие значения вроде \(-1\), \(1\), \(3\) или \(-4\). В первый момент, когда оно становится ровно \(1\), числитель \(p_n\) и есть искомое минимальное \(x\). Теория говорит, что при четной длине периода это происходит после одного прохода по повторяющемуся блоку, а при нечетной - после двух. Но реализациям не нужно отдельно вычислять длину периода: достаточно проверять тождество Пелля после каждого шага.
Пример \(D=13\) из условия особенно полезен, потому что первая положительная единица появляется не сразу. Здесь
$$\sqrt{13} = [3; \overline{1,1,1,1,6}].$$
Последовательность состояний начинается так:
$$ (m,d,a) = (0,1,3) \to (3,4,1) \to (1,3,1) \to (2,3,1) \to (1,4,1) \to (3,1,6) \to \cdots $$
Соответствующие подходящие дроби равны
$$3,\ \frac{4}{1},\ \frac{7}{2},\ \frac{11}{3},\ \frac{18}{5},\ \frac{119}{33},\ \frac{137}{38},\ \frac{256}{71},\ \frac{393}{109},\ \frac{649}{180}.$$
Если подставить их в выражение Пелля, получим
$$-4,\ 3,\ -3,\ 4,\ -1,\ 4,\ -3,\ 3,\ -4,\ 1.$$
Значит, первый настоящий успех - это
$$649^2 - 13 \cdot 180^2 = 1,$$
и фундаментальное решение равно \((x,y)=(649,180)\). Именно такую процедуру выполняет программа для каждого не-квадратного \(D\).
Реализации на C++, Python и Java перебирают \(D=2,3,\dots,1000\). Если \(D\) является квадратом, этот случай сразу пропускается, потому что тогда \(x^2-Dy^2=1\) не дает нетривиального поиска Пелля с \(y \gt 0\).
Для каждого не-квадратного \(D\) хранится только текущее состояние цепной дроби \((m,d,a)\) и две последние подходящие дроби. После каждого обновления проверяется, выполняется ли равенство \(p^2-Dq^2=1\). Первый успех сразу дает минимальное \(x\) для данного \(D\). Поэтому не нужно сохранять весь период и не нужна отдельная логика для четности длины периода.
Затем найденное \(x\) сравнивается с лучшим значением, встретившимся ранее, и вместе с ним сохраняется соответствующее \(D\). Во встроенных проверках подтверждаются два маленьких префикса перебора: при \(D \le 7\) ответ равен \(5\), а при \(D \le 13\) ответ равен \(13\).
Пусть \(\ell_D\) - число коэффициентов цепной дроби, обработанных для фиксированного не-квадратного \(D\) до нахождения первого решения. Тогда для этого \(D\) выполняется \(O(\ell_D)\) шагов рекурсии. Переменные состояния \(m\), \(d\) и \(a\) малы, а основная стоимость связана с арифметикой больших чисел, потому что подходящие дроби растут вместе с фундаментальным решением и занимают \(O(\log x_D)\) бит.
Если просуммировать эту стоимость по всем \(D \le 1000\), получится вполне небольшое время работы для заданного диапазона. Память составляет \(O(\log x_{\max})\) бит, поскольку в любой момент сохраняется лишь константное число больших целых чисел, а не вся история коэффициентов или подходящих дробей.
لكل عدد صحيح غير مربع \(D \le 1000\)، فإن معادلة بيل
$$x^2 - Dy^2 = 1$$
لها عدد لا نهائي من الحلول الصحيحة الموجبة. ومن بين هذه الحلول يوجد حل أساسي وحيد، وهو الحل الذي يملك أصغر قيمة موجبة لـ \(x\). المطلوب هو إيجاد قيمة \(D\) التي تجعل هذا \(x\) الأساسي أكبر ما يمكن. وعند فحص جميع القيم حتى \(1000\)، تكون النتيجة النهائية هي \(D = 661\).
البحث المباشر في قيم \(x\) أو \(y\) غير عملي إطلاقًا، لأن أصغر حل قد يكون كبيرًا جدًا. البنية الصحيحة للمسألة تأتي من الكسر المستمر الدوري لـ \(\sqrt{D}\)، لأن متقارباته تعطي بالضبط المرشحين المهمين الذين يمكن أن يحققوا هوية بيل.
التنفيذات لا تخمن الحلول عدديًا. هي تولد أولًا معاملات الكسر المستمر لـ \(\sqrt{D}\)، ثم تبني منها المتقاربات، وتتوقف عند أول متقارب يحقق معادلة بيل بدقة.
إذا لم يكن \(D\) مربعًا كاملًا، فإن \(\sqrt{D}\) عدد غير نسبي تربيعي، ولذلك يكون كسره المستمر البسيط دوريًا:
$$\sqrt{D} = [a_0; \overline{a_1,a_2,\dots,a_r}].$$
متقاربات هذا التوسع هي من أفضل التقريبات الكسرية الممكنة لـ \(\sqrt{D}\). وهذه النقطة مهمة لأننا إذا كتبنا
$$\frac{p}{q} \approx \sqrt{D},$$
فإن الكمية
$$p^2 - Dq^2$$
تصبح عددًا صحيحًا صغيرًا. والنظرية الكلاسيكية تقول إن الحل الأساسي للمعادلة \(x^2-Dy^2=1\) يظهر داخل هذه المتقاربات نفسها. لذلك لا نحتاج إلى تجربة جميع الأزواج الممكنة \((x,y)\)، بل يكفي أن نتتبع هذا التسلسل المنتظم.
يتم توليد معاملات الكسر المستمر من خلال حالة القسمة الكاملة القياسية. نبدأ بالقيم
$$a_0 = \lfloor \sqrt{D} \rfloor,\qquad m_0 = 0,\qquad d_0 = 1.$$
وفي كل خطوة نعرّف
$$\alpha_n = \frac{\sqrt{D} + m_n}{d_n},\qquad a_n = \lfloor \alpha_n \rfloor.$$
ثم نحصل على الحالة التالية من العلاقات نفسها المستخدمة في التنفيذ:
$$m_{n+1} = d_n a_n - m_n,$$
$$d_{n+1} = \frac{D - m_{n+1}^2}{d_n},$$
$$a_{n+1} = \left\lfloor \frac{a_0 + m_{n+1}}{d_{n+1}} \right\rfloor.$$
هناك ثابتان مهمان هنا. أولًا، إن \(d_n\) يقسم دائمًا العدد \(D-m_n^2\)، ولذلك يكون القسمة تامة من دون كسور. وثانيًا، يبقى كل خارج كامل على الصورة \((\sqrt{D}+m_n)/d_n\). وبما أن عدد الحالات الممكنة محدود عند تثبيت \(D\)، فلا بد أن تتكرر الحالة في النهاية، وهذا التكرار هو بالضبط أصل الدورية في الكسر المستمر لـ \(\sqrt{D}\).
بعد توليد معاملات الكسر المستمر، تُبنى المتقاربات باستخدام علاقة رجوعية من خطوتين:
$$p_{-1}=1,\quad p_0=a_0,\qquad q_{-1}=0,\quad q_0=1,$$
$$p_{n+1}=a_{n+1}p_n+p_{n-1},\qquad q_{n+1}=a_{n+1}q_n+q_{n-1}.$$
كل متقارب \(p_n/q_n\) يقترب أكثر من \(\sqrt{D}\)، ولذلك فإن التعبير
$$p_n^2 - D q_n^2$$
يأخذ مرارًا قيَمًا صحيحة صغيرة مثل \(-1\) و\(1\) و\(3\) و\(-4\). وأول مرة نحصل فيها على القيمة \(1\) تحديدًا يكون البسط الحالي \(p_n\) هو أصغر \(x\) موجب مطلوب. ومن الناحية النظرية، إذا كان طول الدورة زوجيًا يظهر هذا النجاح بعد مرور واحد على الجزء الدوري، وإذا كان فرديًا فقد نحتاج إلى مرورين. لكن التنفيذ لا يحتاج إلى استخراج طول الدورة أو فحص فرديته، لأنه يختبر شرط بيل بعد كل متقارب مباشرة.
المثال \(D=13\) المذكور في نص المسألة مفيد جدًا، لأنه يبين أن الحل الأساسي قد لا يكون صغيرًا. في هذه الحالة لدينا
$$\sqrt{13} = [3; \overline{1,1,1,1,6}].$$
وتبدأ سلسلة الحالات بالشكل
$$ (m,d,a) = (0,1,3) \to (3,4,1) \to (1,3,1) \to (2,3,1) \to (1,4,1) \to (3,1,6) \to \cdots $$
أما المتقاربات المقابلة فهي
$$3,\ \frac{4}{1},\ \frac{7}{2},\ \frac{11}{3},\ \frac{18}{5},\ \frac{119}{33},\ \frac{137}{38},\ \frac{256}{71},\ \frac{393}{109},\ \frac{649}{180}.$$
وعند التعويض في تعبير بيل نحصل على القيم
$$-4,\ 3,\ -3,\ 4,\ -1,\ 4,\ -3,\ 3,\ -4,\ 1.$$
إذن أول إصابة حقيقية للقيمة \(1\) هي
$$649^2 - 13 \cdot 180^2 = 1,$$
ومن ثم يكون الحل الأساسي هو \((x,y)=(649,180)\). وهذا هو النمط نفسه الذي تكرره الخوارزمية لكل \(D\) غير مربع.
تنفذ نسخ C++ وPython وJava مسحًا للقيم \(D=2,3,\dots,1000\). وإذا كانت \(D\) مربعًا كاملًا، يتم تجاوزها فورًا، لأن المعادلة \(x^2-Dy^2=1\) لا تعطي عندئذ بحثًا غير تافه من نوع بيل مع \(y \gt 0\).
لكل \(D\) غير مربع، يحتفظ التنفيذ فقط بالحالة الحالية للكسر المستمر \((m,d,a)\) وبآخر متقاربين. وبعد كل تحديث، يتم فحص ما إذا كان الزوج الجديد يحقق \(p^2-Dq^2=1\). أول نجاح يعطينا مباشرة أصغر \(x\) لذلك \(D\). وبهذا لا نحتاج إلى تخزين الدورة كاملة ولا إلى إضافة منطق خاص لتحديد زوجية طولها أو فرديته.
في النهاية تتم مقارنة هذا \(x\) بأفضل قيمة شوهدت حتى الآن، ويتم الاحتفاظ بقيمة \(D\) الموافقة لها. كما أن اختبارات التحقق الصغيرة المضمنة تؤكد نتيجتين جزئيتين: عندما يكون الحد الأعلى \(7\) تكون الإجابة \(5\)، وعندما يكون \(13\) تكون الإجابة \(13\).
لنرمز بـ \(\ell_D\) إلى عدد معاملات الكسر المستمر التي تمت معالجتها لعدد غير مربع ثابت \(D\) قبل الوصول إلى أول حل. عندئذ يحتاج هذا المثال إلى \(O(\ell_D)\) خطوة تكرارية. تبقى المتغيرات \(m\) و\(d\) و\(a\) صغيرة، لكن المتقاربات نفسها تكبر مع كبر الحل الأساسي، ولذلك يكون الجزء المكلف فعليًا هو حسابات الأعداد الصحيحة الكبيرة على أعداد طولها \(O(\log x_D)\) بت.
وعند جمع هذه الكلفة على جميع \(D \le 1000\)، يبقى الزمن الكلي عمليًا جدًا لهذا المجال. أما الذاكرة فهي \(O(\log x_{\max})\) بت، لأن الخوارزمية لا تحتفظ إلا بعدد ثابت من الأعداد الكبيرة في كل لحظة، ولا تخزن التاريخ الكامل للمعاملات أو المتقاربات.