For each integer \(N\) with \(2 \le N \le 10{,}000\), we ignore perfect squares and study the simple continued fraction of \(\sqrt{N}\). For every non-square \(N\), that expansion has the form \(\sqrt{N}=[a_0;\overline{a_1,a_2,\dots,a_r}]\), and the task is to count how many values of \(N\) have odd period length \(r\).
The small example up to \(N=13\) already shows what is being counted: the odd periods occur for \(N=2,5,10,13\), so the count there is \(4\). The full problem asks for the same test over the whole range up to \(10{,}000\).
The decisive observation is that the period is encoded by a very small integer state. Once the continued fraction of \(\sqrt{N}\) is written through its complete quotients, the entire problem reduces to iterating an exact recurrence on integers and checking whether the resulting period length is odd.
Let \(a_0=\lfloor \sqrt{N}\rfloor\). If \(a_0^2=N\), then \(\sqrt{N}\) is an integer and there is no periodic part at all, so such values are skipped immediately. For a non-square \(N\), we begin with
$$\alpha_0=\sqrt{N}=\frac{\sqrt{N}+0}{1}.$$
At every stage we write the current complete quotient in the standard quadratic-irrational form
$$\alpha_k=\frac{\sqrt{N}+m_k}{d_k},\qquad a_k=\lfloor \alpha_k \rfloor,$$
with initial values \(m_0=0\), \(d_0=1\), and \(a_0=\lfloor \sqrt{N}\rfloor\). A continued-fraction step removes the integer part \(a_k\) and inverts the remaining fractional part.
By definition of a simple continued fraction, the next complete quotient is
$$\alpha_{k+1}=\frac{1}{\alpha_k-a_k}.$$
Substituting \(\alpha_k=(\sqrt{N}+m_k)/d_k\) and rationalizing the denominator gives
$$\alpha_{k+1}=\frac{d_k}{\sqrt{N}+m_k-a_kd_k} =\frac{d_k(\sqrt{N}+a_kd_k-m_k)}{N-(a_kd_k-m_k)^2}.$$
This suggests the standard definitions
$$m_{k+1}=d_ka_k-m_k,\qquad d_{k+1}=\frac{N-m_{k+1}^2}{d_k},$$
so that the next state again has the same form,
$$\alpha_{k+1}=\frac{\sqrt{N}+m_{k+1}}{d_{k+1}}.$$
Its integer part is then
$$a_{k+1}=\left\lfloor \frac{\sqrt{N}+m_{k+1}}{d_{k+1}} \right\rfloor =\left\lfloor \frac{a_0+m_{k+1}}{d_{k+1}} \right\rfloor,$$
because \(a_0 < \sqrt{N} < a_0+1\). These are exactly the update formulas used by the implementations.
The recurrence never needs floating-point arithmetic after the initial floor. If \(d_k\mid (N-m_k^2)\), then from \(m_{k+1}=d_ka_k-m_k\) we have
$$m_{k+1}\equiv -m_k \pmod{d_k},\qquad m_{k+1}^2\equiv m_k^2 \pmod{d_k}.$$
Therefore \(d_k\mid (N-m_{k+1}^2)\), so
$$d_{k+1}=\frac{N-m_{k+1}^2}{d_k}$$
is an integer at every step. Since \(d_0=1\), exact divisibility holds inductively for the entire loop. This is why the C++, Python, and Java implementations can work purely with integers.
For square roots of non-squares, the continued fraction is periodic, and the closing state of one full period is the distinguished reduced surd
$$m_k=a_0,\qquad d_k=1.$$
If this state occurs, then
$$a_k=\left\lfloor \sqrt{N}+a_0 \right\rfloor=2a_0,$$
so reaching \((m_k,d_k)=(a_0,1)\) certainly produces \(a_k=2a_0\).
The converse is just as important. In the reduced square-root process one has \(0 \le m_k < \sqrt{N} < a_0+1\), so if \(a_k=2a_0\), then
$$2a_0 \le \frac{a_0+m_k}{d_k} < \frac{2a_0+1}{d_k}.$$
The left inequality is impossible unless \(d_k=1\). Once \(d_k=1\), the formula becomes \(2a_0=\lfloor a_0+m_k\rfloor\), and since \(m_k\) is an integer with \(m_k<a_0+1\), it follows that \(m_k=a_0\). Thus the first appearance of \(a_k=2a_0\) is exactly the first return to the closing state, which means one full period has been completed.
Take \(N=23\). Then \(a_0=\lfloor \sqrt{23}\rfloor=4\). Iterating the recurrence produces
$$ (m_1,d_1,a_1)=(4,7,1),\quad (m_2,d_2,a_2)=(3,2,3),\quad (m_3,d_3,a_3)=(3,7,1),\quad (m_4,d_4,a_4)=(4,1,8). $$
Because \(a_4=8=2a_0\), the period length is \(4\), so
$$\sqrt{23}=[4;\overline{1,3,1,8}].$$
For contrast, \(\sqrt{13}=[3;\overline{1,1,1,1,6}]\) reaches \(2a_0=6\) after \(5\) steps, so it contributes to the odd-period count.
Once the period length \(r(N)\) is known for one non-square \(N\), the original problem becomes the count
$$\#\{\,N: 2 \le N \le 10{,}000,\ N \notin \{m^2 : m \in \mathbb{Z}\},\ r(N)\equiv 1 \pmod 2\,\}.$$
Each value of \(N\) is completely independent. There is no interaction between different square roots, so the global answer is obtained by running the same period-finding routine once for every candidate \(N\).
The implementation first computes \(a_0=\lfloor \sqrt{N}\rfloor\) with an integer square-root operation. If \(a_0^2=N\), it returns period length \(0\) immediately. Otherwise it initializes the state with \(m=0\), \(d=1\), \(a=a_0\), then repeatedly applies the three recurrence updates and increments a period counter.
The stopping rule is deliberately minimal: the loop ends at the first \(a=2a_0\). Because that condition is mathematically equivalent to the closing state \((m,d)=(a_0,1)\), the implementation does not need a hash set or any other structure to remember earlier states.
After period computation is available for a single \(N\), the outer routine scans all integers from \(2\) to the chosen limit, tests whether the returned period is odd, and increments the answer if it is. The default limit is \(10{,}000\).
The C++, Python, and Java implementations also include a small built-in checkpoint from the statement: up to \(13\), the correct count of odd periods is \(4\). That single test validates the recurrence, the stopping condition, and the parity check together.
For a fixed \(N\), each iteration of the continued-fraction loop performs only \(O(1)\) integer work, so the cost is proportional to the period length \(r(N)\). Classical theory gives the worst-case upper bound \(r(N)=O(\sqrt{N})\), which leads to
$$\sum_{N=2}^{L} O(\sqrt{N}) = O(L^{3/2})$$
for an overall limit \(L\). With \(L=10{,}000\), this is easily small enough for a fast computation.
Memory usage is \(O(1)\). The algorithm stores only the current state \((m,d,a)\), the initial floor \(a_0\), the current period length, and the global counter of odd periods.
Für jede ganze Zahl \(N\) mit \(2 \le N \le 10{,}000\) werden perfekte Quadrate verworfen, und für jede verbleibende Zahl wird der einfache Kettenbruch von \(\sqrt{N}\) betrachtet. Für jedes nichtquadratische \(N\) hat diese Entwicklung die Form \(\sqrt{N}=[a_0;\overline{a_1,a_2,\dots,a_r}]\), und gesucht ist die Anzahl der Werte mit ungerader Periodenlänge \(r\).
Schon das kleine Beispiel bis \(N=13\) zeigt, was gezählt wird: Ungerade Perioden treten dort bei \(N=2,5,10,13\) auf, also insgesamt \(4\) Mal. Im eigentlichen Problem wird derselbe Test für alle \(N \le 10{,}000\) durchgeführt.
Der entscheidende Punkt ist, dass die Periode durch einen sehr kleinen Ganzzahlzustand beschrieben werden kann. Sobald man den Kettenbruch von \(\sqrt{N}\) über seine vollständigen Quotienten formuliert, reduziert sich das ganze Problem auf eine exakte Rekursion mit Ganzzahlen und einen abschließenden Paritätstest.
Setze \(a_0=\lfloor \sqrt{N}\rfloor\). Falls \(a_0^2=N\) gilt, dann ist \(\sqrt{N}\) ganzzahlig und besitzt überhaupt keinen periodischen Teil; solche Werte werden daher sofort übersprungen. Für ein nichtquadratisches \(N\) starten wir mit
$$\alpha_0=\sqrt{N}=\frac{\sqrt{N}+0}{1}.$$
In jedem Schritt schreiben wir den aktuellen vollständigen Quotienten in der Standardform einer quadratischen Irrationalzahl als
$$\alpha_k=\frac{\sqrt{N}+m_k}{d_k},\qquad a_k=\lfloor \alpha_k \rfloor,$$
mit Anfangswerten \(m_0=0\), \(d_0=1\) und \(a_0=\lfloor \sqrt{N}\rfloor\). Ein Kettenbruchschritt entfernt den ganzzahligen Anteil \(a_k\) und invertiert den verbleibenden Bruchteil.
Nach der Definition des einfachen Kettenbruchs ist der nächste vollständige Quotient
$$\alpha_{k+1}=\frac{1}{\alpha_k-a_k}.$$
Setzt man \(\alpha_k=(\sqrt{N}+m_k)/d_k\) ein und rationalisiert den Nenner, so erhält man
$$\alpha_{k+1}=\frac{d_k}{\sqrt{N}+m_k-a_kd_k} =\frac{d_k(\sqrt{N}+a_kd_k-m_k)}{N-(a_kd_k-m_k)^2}.$$
Damit bieten sich die Standarddefinitionen
$$m_{k+1}=d_ka_k-m_k,\qquad d_{k+1}=\frac{N-m_{k+1}^2}{d_k}$$
an, sodass der neue Zustand wieder dieselbe Form hat:
$$\alpha_{k+1}=\frac{\sqrt{N}+m_{k+1}}{d_{k+1}}.$$
Sein ganzzahliger Anteil ist dann
$$a_{k+1}=\left\lfloor \frac{\sqrt{N}+m_{k+1}}{d_{k+1}} \right\rfloor =\left\lfloor \frac{a_0+m_{k+1}}{d_{k+1}} \right\rfloor,$$
denn es gilt \(a_0 < \sqrt{N} < a_0+1\). Genau diese Formeln werden in den Implementierungen verwendet.
Nach dem Start wird nirgends mehr Gleitkomma benötigt. Gilt in einem Schritt \(d_k\mid (N-m_k^2)\), dann folgt aus \(m_{k+1}=d_ka_k-m_k\)
$$m_{k+1}\equiv -m_k \pmod{d_k},\qquad m_{k+1}^2\equiv m_k^2 \pmod{d_k}.$$
Daher teilt \(d_k\) auch \(N-m_{k+1}^2\), also ist
$$d_{k+1}=\frac{N-m_{k+1}^2}{d_k}$$
in jedem Schritt eine ganze Zahl. Weil \(d_0=1\) gilt, bleibt diese Exaktheit induktiv während der gesamten Schleife erhalten. Deshalb arbeiten die C++-, Python- und Java-Implementierungen ausschließlich mit Ganzzahlen.
Für Quadratwurzeln nichtquadratischer Zahlen ist der Kettenbruch periodisch, und der Abschlusspunkt einer vollen Periode ist die ausgezeichnete reduzierte Form
$$m_k=a_0,\qquad d_k=1.$$
Tritt dieser Zustand ein, dann gilt sofort
$$a_k=\left\lfloor \sqrt{N}+a_0 \right\rfloor=2a_0,$$
also liefert \((m_k,d_k)=(a_0,1)\) sicher \(a_k=2a_0\).
Umgekehrt ist ebenso wichtig: Im reduzierten Prozess gilt \(0 \le m_k < \sqrt{N} < a_0+1\). Falls also \(a_k=2a_0\) ist, folgt
$$2a_0 \le \frac{a_0+m_k}{d_k} < \frac{2a_0+1}{d_k}.$$
Die linke Ungleichung ist nur möglich, wenn \(d_k=1\) gilt. Dann wird daraus \(2a_0=\lfloor a_0+m_k\rfloor\), und da \(m_k\) ganzzahlig mit \(m_k<a_0+1\) ist, muss \(m_k=a_0\) folgen. Das erste Auftreten von \(a_k=2a_0\) ist also genau die erste Rückkehr in den Abschlusspunkt, also genau eine vollständige Periode.
Für \(N=23\) ist \(a_0=\lfloor \sqrt{23}\rfloor=4\). Die Rekursion liefert
$$ (m_1,d_1,a_1)=(4,7,1),\quad (m_2,d_2,a_2)=(3,2,3),\quad (m_3,d_3,a_3)=(3,7,1),\quad (m_4,d_4,a_4)=(4,1,8). $$
Da \(a_4=8=2a_0\) ist, beträgt die Periodenlänge \(4\), also
$$\sqrt{23}=[4;\overline{1,3,1,8}].$$
Zum Vergleich: \(\sqrt{13}=[3;\overline{1,1,1,1,6}]\) erreicht \(2a_0=6\) erst nach \(5\) Schritten und trägt deshalb zur Anzahl der ungeraden Perioden bei.
Ist die Periodenlänge \(r(N)\) für ein einzelnes nichtquadratisches \(N\) bekannt, dann lautet das Gesamtproblem einfach
$$\#\{\,N: 2 \le N \le 10{,}000,\ N \notin \{m^2 : m \in \mathbb{Z}\},\ r(N)\equiv 1 \pmod 2\,\}.$$
Jeder Wert von \(N\) ist dabei unabhängig von allen anderen. Die globale Antwort entsteht also, indem dieselbe Periodensuche einmal für jedes Kandidaten-\(N\) ausgeführt wird.
Die Implementierung berechnet zuerst \(a_0=\lfloor \sqrt{N}\rfloor\) mit einer ganzzahligen Quadratwurzel. Falls \(a_0^2=N\), wird sofort die Periodenlänge \(0\) zurückgegeben. Andernfalls startet der Zustand mit \(m=0\), \(d=1\), \(a=a_0\), und die drei Rekursionsschritte werden wiederholt ausgeführt, während ein Periodenzähler mitläuft.
Die Abbruchbedingung ist bewusst knapp: Die Schleife endet beim ersten \(a=2a_0\). Weil diese Bedingung mathematisch genau dem Abschlusspunkt \((m,d)=(a_0,1)\) entspricht, muss die Implementierung keine bereits gesehenen Zustände speichern.
Sobald die Periodenlänge für ein einzelnes \(N\) bestimmt werden kann, iteriert die äußere Routine über alle Zahlen von \(2\) bis zur gewählten Grenze, prüft die Parität der zurückgegebenen Periode und erhöht die Antwort genau dann, wenn sie ungerade ist. Die Standardgrenze ist \(10{,}000\).
Außerdem enthalten die Implementierungen einen kleinen eingebauten Kontrolltest aus der Aufgabenstellung: Bis \(13\) gibt es genau \(4\) ungerade Perioden. Damit werden Rekursion, Abbruchbedingung und Paritätstest in einem Schritt geprüft.
Für festes \(N\) kostet jede Iteration der Kettenbruchschleife nur \(O(1)\) Ganzzahloperationen, also ist der Aufwand proportional zur Periodenlänge \(r(N)\). Die klassische Theorie liefert die obere Schranke \(r(N)=O(\sqrt{N})\), und daraus folgt für eine Grenze \(L\)
$$\sum_{N=2}^{L} O(\sqrt{N}) = O(L^{3/2}).$$
Für \(L=10{,}000\) ist das ohne Weiteres schnell genug.
Der Speicherbedarf ist \(O(1)\). Gespeichert werden nur der aktuelle Zustand \((m,d,a)\), der Anfangswert \(a_0\), die bisherige Periodenlänge und der globale Zähler der ungeraden Perioden.
\(2 \le N \le 10{,}000\) aralığındaki her tamsayı için önce tam kareler elenir, sonra \(\sqrt{N}\)'nin basit sürekli kesir açılımı incelenir. Kare olmayan her \(N\) için bu açılım \(\sqrt{N}=[a_0;\overline{a_1,a_2,\dots,a_r}]\) biçimindedir ve istenen şey, dönem uzunluğu \(r\) tek olan \(N\) değerlerinin sayısını bulmaktır.
\(N=13\)'e kadar olan küçük örnek neyin sayıldığını açıkça gösterir: tek dönemler \(N=2,5,10,13\) için ortaya çıkar, yani sayı \(4\)'tür. Asıl problem, aynı testi \(10{,}000\)'e kadar bütün uygun sayılar için yapar.
Temel gözlem, dönemin çok küçük bir tamsayı durumu içinde kodlanmış olmasıdır. \(\sqrt{N}\)'nin sürekli kesrini tam bölüm durumları üzerinden yazınca, bütün problem tamsayılar üzerinde çalışan kesin bir yinelemeye ve en sonda bir tek-çift kontrolüne iner.
\(a_0=\lfloor \sqrt{N}\rfloor\) olsun. Eğer \(a_0^2=N\) ise, \(\sqrt{N}\) zaten tamsayıdır ve periyodik kısım yoktur; bu nedenle bu değerler hemen atlanır. Kare olmayan bir \(N\) için başlangıç durumu
$$\alpha_0=\sqrt{N}=\frac{\sqrt{N}+0}{1}$$
şeklindedir. Her adımda mevcut tam bölüm durumu şu standart ikinci dereceden irrasyonel biçimde yazılır:
$$\alpha_k=\frac{\sqrt{N}+m_k}{d_k},\qquad a_k=\lfloor \alpha_k \rfloor,$$
burada başlangıç değerleri \(m_0=0\), \(d_0=1\) ve \(a_0=\lfloor \sqrt{N}\rfloor\)'dür. Sürekli kesrin bir adımı, tam kısmı \(a_k\)'yı ayırır ve geriye kalan kesri ters çevirir.
Basit sürekli kesrin tanımı gereği bir sonraki tam bölüm durumu
$$\alpha_{k+1}=\frac{1}{\alpha_k-a_k}$$
olur. \(\alpha_k=(\sqrt{N}+m_k)/d_k\) yazıp paydayı rasyonelleştirince
$$\alpha_{k+1}=\frac{d_k}{\sqrt{N}+m_k-a_kd_k} =\frac{d_k(\sqrt{N}+a_kd_k-m_k)}{N-(a_kd_k-m_k)^2}$$
elde edilir. Bu da standart tanımları doğurur:
$$m_{k+1}=d_ka_k-m_k,\qquad d_{k+1}=\frac{N-m_{k+1}^2}{d_k}.$$
Böylece yeni durum yine aynı biçimdedir:
$$\alpha_{k+1}=\frac{\sqrt{N}+m_{k+1}}{d_{k+1}}.$$
Sonraki tam kısım da
$$a_{k+1}=\left\lfloor \frac{\sqrt{N}+m_{k+1}}{d_{k+1}} \right\rfloor =\left\lfloor \frac{a_0+m_{k+1}}{d_{k+1}} \right\rfloor$$
şeklindedir; çünkü \(a_0 < \sqrt{N} < a_0+1\). C++, Python ve Java uygulamalarının kullandığı yineleme tam olarak budur.
Başlangıçtan sonra kayan noktalı sayı hesabına hiç ihtiyaç yoktur. Eğer bir adımda \(d_k\mid (N-m_k^2)\) ise, \(m_{k+1}=d_ka_k-m_k\) olduğundan
$$m_{k+1}\equiv -m_k \pmod{d_k},\qquad m_{k+1}^2\equiv m_k^2 \pmod{d_k}$$
olur. Dolayısıyla \(d_k\), \(N-m_{k+1}^2\)'yi de böler ve
$$d_{k+1}=\frac{N-m_{k+1}^2}{d_k}$$
her zaman bir tamsayıdır. \(d_0=1\) olduğu için bu kesin bölünebilme özelliği tüm döngü boyunca tümevarımla korunur. Kodların yalnızca tamsayılarla çalışabilmesinin nedeni budur.
Kare olmayan sayıların karekökleri için sürekli kesir periyodiktir ve tam bir dönemin kapanış durumu şu ayırt edici indirgenmiş biçimdir:
$$m_k=a_0,\qquad d_k=1.$$
Bu durum gerçekleşirse hemen
$$a_k=\left\lfloor \sqrt{N}+a_0 \right\rfloor=2a_0$$
elde edilir; yani \((m_k,d_k)=(a_0,1)\) durumu mutlaka \(a_k=2a_0\) üretir.
Tersi de aynı ölçüde önemlidir. İndirgenmiş süreçte \(0 \le m_k < \sqrt{N} < a_0+1\) olduğundan, eğer \(a_k=2a_0\) ise
$$2a_0 \le \frac{a_0+m_k}{d_k} < \frac{2a_0+1}{d_k}$$
yazılır. Soldaki eşitsizlik ancak \(d_k=1\) ise mümkün olur. Sonra \(2a_0=\lfloor a_0+m_k\rfloor\) kalır; \(m_k\) tamsayı ve \(m_k<a_0+1\) olduğundan zorunlu olarak \(m_k=a_0\) çıkar. Demek ki \(a_k=2a_0\)'nın ilk görünüşü, kapanış durumuna ilk dönüşle aynıdır; yani tam bir dönem tamamlanmıştır.
\(N=23\) için \(a_0=\lfloor \sqrt{23}\rfloor=4\) olur. Yineleme şu üçlüleri verir:
$$ (m_1,d_1,a_1)=(4,7,1),\quad (m_2,d_2,a_2)=(3,2,3),\quad (m_3,d_3,a_3)=(3,7,1),\quad (m_4,d_4,a_4)=(4,1,8). $$
\(a_4=8=2a_0\) olduğuna göre dönem uzunluğu \(4\)'tür ve
$$\sqrt{23}=[4;\overline{1,3,1,8}]$$
elde edilir. Karşılaştırma için \(\sqrt{13}=[3;\overline{1,1,1,1,6}]\), \(2a_0=6\)'ya \(5\) adımda ulaşır; bu yüzden tek dönem sayısına katkı verir.
Bir tek kare olmayan \(N\) için dönem uzunluğu \(r(N)\) bulunduğunda, özgün problem aslında şu sayımı yapmaktır:
$$\#\{\,N: 2 \le N \le 10{,}000,\ N \notin \{m^2 : m \in \mathbb{Z}\},\ r(N)\equiv 1 \pmod 2\,\}.$$
Her \(N\) değeri diğerlerinden tamamen bağımsızdır. Bu yüzden toplam cevap, aynı dönem bulma yordamını bütün aday sayılar için tek tek çalıştırarak elde edilir.
Uygulama önce tamsayı kareköküyle \(a_0=\lfloor \sqrt{N}\rfloor\) değerini bulur. Eğer \(a_0^2=N\) ise, dönem uzunluğunu hemen \(0\) döndürür. Aksi halde durum \(m=0\), \(d=1\), \(a=a_0\) ile başlatılır; sonra üç yineleme güncellemesi art arda uygulanır ve bir dönem sayacı artırılır.
Durdurma kuralı özellikle sadedir: döngü, ilk \(a=2a_0\) olduğunda biter. Bu koşul matematiksel olarak kapanış durumu \((m,d)=(a_0,1)\) ile eşdeğer olduğu için, uygulamanın daha önce görülen durumları saklamasına gerek kalmaz.
Tek bir \(N\) için dönem hesabı hazır olduktan sonra dış döngü \(2\)'den seçilen sınıra kadar bütün sayıları gezer, dönen dönemin tek olup olmadığını kontrol eder ve tekse cevabı bir artırır. Varsayılan üst sınır \(10{,}000\)'dir.
C++, Python ve Java uygulamaları ayrıca soru metnindeki küçük kontrolü de içerir: \(13\)'e kadar tek dönem sayısı tam olarak \(4\)'tür. Bu tek test yinelemeyi, durdurma koşulunu ve parite kontrolünü aynı anda doğrular.
Sabit bir \(N\) için sürekli kesir döngüsünün her adımı yalnızca \(O(1)\) tamsayı işlemi yapar; dolayısıyla maliyet dönem uzunluğu \(r(N)\) ile orantılıdır. Klasik teori en kötü durumda \(r(N)=O(\sqrt{N})\) üst sınırını verir ve bu da üst sınırı \(L\) olan tarama için
$$\sum_{N=2}^{L} O(\sqrt{N}) = O(L^{3/2})$$
sonucunu doğurur. \(L=10{,}000\) için bu rahatlıkla hızlıdır.
Bellek kullanımı \(O(1)\)'dir. Algoritma yalnızca anlık durum \((m,d,a)\), başlangıç taban değeri \(a_0\), o ana kadarki dönem uzunluğu ve tek dönemlerin toplam sayısını tutar.
Para cada entero \(N\) con \(2 \le N \le 10{,}000\), primero se descartan los cuadrados perfectos y luego se estudia la fracción continua simple de \(\sqrt{N}\). Para todo \(N\) no cuadrado, dicha expansión tiene la forma \(\sqrt{N}=[a_0;\overline{a_1,a_2,\dots,a_r}]\), y el objetivo es contar cuántos valores de \(N\) tienen una longitud de período \(r\) impar.
El ejemplo pequeño hasta \(N=13\) ya deja claro qué se está contando: los períodos impares aparecen para \(N=2,5,10,13\), así que allí el total es \(4\). El problema completo aplica exactamente la misma prueba a todos los \(N \le 10{,}000\).
La observación clave es que el período queda codificado en un estado entero muy pequeño. Una vez que la fracción continua de \(\sqrt{N}\) se escribe mediante sus cocientes completos, todo el problema se reduce a iterar una recurrencia exacta de enteros y comprobar si la longitud obtenida es impar.
Sea \(a_0=\lfloor \sqrt{N}\rfloor\). Si \(a_0^2=N\), entonces \(\sqrt{N}\) es un entero y no existe parte periódica, así que esos valores se omiten de inmediato. Para un \(N\) no cuadrado comenzamos con
$$\alpha_0=\sqrt{N}=\frac{\sqrt{N}+0}{1}.$$
En cada etapa escribimos el cociente completo actual en la forma estándar
$$\alpha_k=\frac{\sqrt{N}+m_k}{d_k},\qquad a_k=\lfloor \alpha_k \rfloor,$$
con valores iniciales \(m_0=0\), \(d_0=1\) y \(a_0=\lfloor \sqrt{N}\rfloor\). Un paso de fracción continua separa la parte entera \(a_k\) e invierte la parte fraccionaria restante.
Por definición de fracción continua simple, el siguiente cociente completo satisface
$$\alpha_{k+1}=\frac{1}{\alpha_k-a_k}.$$
Si sustituimos \(\alpha_k=(\sqrt{N}+m_k)/d_k\) y racionalizamos el denominador, obtenemos
$$\alpha_{k+1}=\frac{d_k}{\sqrt{N}+m_k-a_kd_k} =\frac{d_k(\sqrt{N}+a_kd_k-m_k)}{N-(a_kd_k-m_k)^2}.$$
Eso conduce a las definiciones estándar
$$m_{k+1}=d_ka_k-m_k,\qquad d_{k+1}=\frac{N-m_{k+1}^2}{d_k},$$
de modo que el nuevo estado vuelve a tener la misma forma:
$$\alpha_{k+1}=\frac{\sqrt{N}+m_{k+1}}{d_{k+1}}.$$
Su parte entera es entonces
$$a_{k+1}=\left\lfloor \frac{\sqrt{N}+m_{k+1}}{d_{k+1}} \right\rfloor =\left\lfloor \frac{a_0+m_{k+1}}{d_{k+1}} \right\rfloor,$$
porque \(a_0 < \sqrt{N} < a_0+1\). Estas son exactamente las fórmulas que usan las implementaciones.
Después del piso inicial ya no hace falta aritmética en punto flotante. Si en una etapa se cumple \(d_k\mid (N-m_k^2)\), entonces, como \(m_{k+1}=d_ka_k-m_k\), se tiene
$$m_{k+1}\equiv -m_k \pmod{d_k},\qquad m_{k+1}^2\equiv m_k^2 \pmod{d_k}.$$
Por lo tanto, \(d_k\) también divide a \(N-m_{k+1}^2\), y así
$$d_{k+1}=\frac{N-m_{k+1}^2}{d_k}$$
es entero en cada paso. Como \(d_0=1\), esta divisibilidad exacta se conserva por inducción durante todo el proceso. Esa es la razón por la que las implementaciones en C++, Python y Java trabajan solamente con enteros.
Para raíces cuadradas de números no cuadrados, la fracción continua es periódica, y el estado que cierra un período completo es el surdo reducido distinguido
$$m_k=a_0,\qquad d_k=1.$$
Si ese estado aparece, entonces
$$a_k=\left\lfloor \sqrt{N}+a_0 \right\rfloor=2a_0,$$
de modo que llegar a \((m_k,d_k)=(a_0,1)\) implica automáticamente \(a_k=2a_0\).
La recíproca es igual de importante. En el proceso reducido se cumple \(0 \le m_k < \sqrt{N} < a_0+1\), así que si \(a_k=2a_0\), entonces
$$2a_0 \le \frac{a_0+m_k}{d_k} < \frac{2a_0+1}{d_k}.$$
La desigualdad de la izquierda solo es posible si \(d_k=1\). Entonces queda \(2a_0=\lfloor a_0+m_k\rfloor\), y como \(m_k\) es entero con \(m_k<a_0+1\), necesariamente \(m_k=a_0\). Por tanto, la primera aparición de \(a_k=2a_0\) coincide exactamente con el primer regreso al estado de cierre, es decir, con un período completo.
Tomemos \(N=23\). Entonces \(a_0=\lfloor \sqrt{23}\rfloor=4\). La recurrencia produce
$$ (m_1,d_1,a_1)=(4,7,1),\quad (m_2,d_2,a_2)=(3,2,3),\quad (m_3,d_3,a_3)=(3,7,1),\quad (m_4,d_4,a_4)=(4,1,8). $$
Como \(a_4=8=2a_0\), la longitud del período es \(4\), y por eso
$$\sqrt{23}=[4;\overline{1,3,1,8}].$$
En cambio, \(\sqrt{13}=[3;\overline{1,1,1,1,6}]\) alcanza \(2a_0=6\) tras \(5\) pasos, por lo que sí aporta al conteo de períodos impares.
Una vez conocida la longitud del período \(r(N)\) para un solo \(N\) no cuadrado, el problema original no es más que el conteo
$$\#\{\,N: 2 \le N \le 10{,}000,\ N \notin \{m^2 : m \in \mathbb{Z}\},\ r(N)\equiv 1 \pmod 2\,\}.$$
Cada valor de \(N\) es completamente independiente de los demás. Por eso, la respuesta global se obtiene ejecutando el mismo cálculo de período una vez por cada candidato.
La implementación empieza calculando \(a_0=\lfloor \sqrt{N}\rfloor\) mediante una raíz cuadrada entera. Si \(a_0^2=N\), devuelve inmediatamente longitud de período \(0\). En caso contrario inicializa el estado con \(m=0\), \(d=1\), \(a=a_0\), y luego aplica repetidamente las tres actualizaciones de la recurrencia mientras incrementa un contador de período.
La condición de parada es deliberadamente mínima: el bucle termina en la primera aparición de \(a=2a_0\). Como esa condición es matemáticamente equivalente al estado de cierre \((m,d)=(a_0,1)\), no hace falta almacenar estados anteriores en ninguna tabla o conjunto.
Una vez disponible el cálculo del período para un valor individual, la rutina exterior recorre todos los enteros desde \(2\) hasta el límite elegido, comprueba si el período devuelto es impar y suma \(1\) al resultado cuando corresponde. El límite por defecto es \(10{,}000\).
Las implementaciones en C++, Python y Java incluyen además una comprobación pequeña tomada del enunciado: hasta \(13\), el número correcto de períodos impares es \(4\). Esa prueba valida a la vez la recurrencia, la condición de parada y la comprobación de paridad.
Para un \(N\) fijo, cada iteración del bucle de fracción continua realiza solo \(O(1)\) operaciones enteras, de modo que el costo es proporcional a la longitud del período \(r(N)\). La teoría clásica da la cota superior \(r(N)=O(\sqrt{N})\), y por tanto para un límite \(L\) se obtiene
$$\sum_{N=2}^{L} O(\sqrt{N}) = O(L^{3/2}).$$
Con \(L=10{,}000\), ese volumen de trabajo es claramente pequeño.
El uso de memoria es \(O(1)\). Solo se guardan el estado actual \((m,d,a)\), el valor inicial \(a_0\), la longitud del período en curso y el contador global de períodos impares.
对于每个满足 \(2 \le N \le 10{,}000\) 的整数，先去掉完全平方数，再研究 \(\sqrt{N}\) 的简单连分数展开。对每个非平方 \(N\)，它都可以写成 \(\sqrt{N}=[a_0;\overline{a_1,a_2,\dots,a_r}]\)，题目要求统计其中周期长度 \(r\) 为奇数的 \(N\) 有多少个。
题目给出的较小范围已经说明了要数什么：在 \(N \le 13\) 时，奇周期出现在 \(N=2,5,10,13\)，所以个数是 \(4\)。完整问题只是把同样的判断扩展到所有 \(N \le 10{,}000\)。
核心观察是，周期完全由一个很小的整数状态决定。只要把 \(\sqrt{N}\) 的连分数过程写成“完整商”的演化，整个问题就会变成一个只用整数的精确递推，再加上最后对周期奇偶性的判断。
记 \(a_0=\lfloor \sqrt{N}\rfloor\)。如果 \(a_0^2=N\)，那么 \(\sqrt{N}\) 本身就是整数，根本没有周期部分，这种 \(N\) 可以立刻跳过。对于非平方 \(N\)，我们从
$$\alpha_0=\sqrt{N}=\frac{\sqrt{N}+0}{1}$$
开始。在每一步中，都把当前完整商写成标准的二次无理数形式
$$\alpha_k=\frac{\sqrt{N}+m_k}{d_k},\qquad a_k=\lfloor \alpha_k \rfloor,$$
其中初值为 \(m_0=0\)、\(d_0=1\)、\(a_0=\lfloor \sqrt{N}\rfloor\)。连分数的一步操作，就是先取出整数部分 \(a_k\)，再把剩下的分数部分取倒数。
按照简单连分数的定义，下一个完整商满足
$$\alpha_{k+1}=\frac{1}{\alpha_k-a_k}.$$
把 \(\alpha_k=(\sqrt{N}+m_k)/d_k\) 代入并有理化分母，就得到
$$\alpha_{k+1}=\frac{d_k}{\sqrt{N}+m_k-a_kd_k} =\frac{d_k(\sqrt{N}+a_kd_k-m_k)}{N-(a_kd_k-m_k)^2}.$$
这自然导出标准递推定义
$$m_{k+1}=d_ka_k-m_k,\qquad d_{k+1}=\frac{N-m_{k+1}^2}{d_k},$$
于是新的状态再次具有相同形式：
$$\alpha_{k+1}=\frac{\sqrt{N}+m_{k+1}}{d_{k+1}}.$$
它的整数部分就是
$$a_{k+1}=\left\lfloor \frac{\sqrt{N}+m_{k+1}}{d_{k+1}} \right\rfloor =\left\lfloor \frac{a_0+m_{k+1}}{d_{k+1}} \right\rfloor,$$
因为 \(a_0 < \sqrt{N} < a_0+1\)。这正是实现中使用的三条更新公式。
除了最开始求一次整数平方根之外，后面不需要任何浮点运算。若某一步满足 \(d_k\mid (N-m_k^2)\)，那么由 \(m_{k+1}=d_ka_k-m_k\) 可知
$$m_{k+1}\equiv -m_k \pmod{d_k},\qquad m_{k+1}^2\equiv m_k^2 \pmod{d_k}.$$
于是 \(d_k\) 也整除 \(N-m_{k+1}^2\)，从而
$$d_{k+1}=\frac{N-m_{k+1}^2}{d_k}$$
在每一步都是整数。由于初始时 \(d_0=1\)，这个整除不变性会通过递推一直保持下去。这就是为什么 C++、Python 和 Java 实现都可以只用整数完成全部计算。
对非平方数的平方根，连分数一定是周期性的，而一个完整周期的结束状态恰好是这个特殊的约化二次无理数
$$m_k=a_0,\qquad d_k=1.$$
如果到了这个状态，那么立刻有
$$a_k=\left\lfloor \sqrt{N}+a_0 \right\rfloor=2a_0,$$
因此 \((m_k,d_k)=(a_0,1)\) 必然对应 \(a_k=2a_0\)。
反过来同样重要。在这个约化过程中始终有 \(0 \le m_k < \sqrt{N} < a_0+1\)。如果某一步出现 \(a_k=2a_0\)，那么就有
$$2a_0 \le \frac{a_0+m_k}{d_k} < \frac{2a_0+1}{d_k}.$$
左边这个不等式只有在 \(d_k=1\) 时才可能成立。此时又得到 \(2a_0=\lfloor a_0+m_k\rfloor\)，而 \(m_k\) 是整数且满足 \(m_k<a_0+1\)，所以只能有 \(m_k=a_0\)。也就是说，第一次出现 \(a_k=2a_0\) 时，恰好就是第一次回到周期闭合状态，因此一个完整周期已经走完。
取 \(N=23\)，则 \(a_0=\lfloor \sqrt{23}\rfloor=4\)。递推序列给出
$$ (m_1,d_1,a_1)=(4,7,1),\quad (m_2,d_2,a_2)=(3,2,3),\quad (m_3,d_3,a_3)=(3,7,1),\quad (m_4,d_4,a_4)=(4,1,8). $$
因为 \(a_4=8=2a_0\)，所以周期长度是 \(4\)，因此
$$\sqrt{23}=[4;\overline{1,3,1,8}].$$
再看一个奇周期例子：\(\sqrt{13}=[3;\overline{1,1,1,1,6}]\)，它在第 \(5\) 步才达到 \(2a_0=6\)，所以会被计入最终答案。
当某个非平方 \(N\) 的周期长度 \(r(N)\) 已经求出之后，原题其实就是在统计
$$\#\{\,N: 2 \le N \le 10{,}000,\ N \notin \{m^2 : m \in \mathbb{Z}\},\ r(N)\equiv 1 \pmod 2\,\}.$$
不同的 \(N\) 之间完全独立，不存在任何交叉影响。因此总答案就是对每个候选 \(N\) 单独运行一次同样的周期计算。
实现首先用整数平方根求出 \(a_0=\lfloor \sqrt{N}\rfloor\)。如果 \(a_0^2=N\)，就立即返回周期长度 \(0\)。否则把状态初始化为 \(m=0\)、\(d=1\)、\(a=a_0\)，然后反复执行上面的三条递推更新，并在每轮把周期计数加一。
停止条件非常直接：第一次出现 \(a=2a_0\) 时就结束循环。由于这个条件在数学上与闭合状态 \((m,d)=(a_0,1)\) 完全等价，所以实现根本不需要记录过去见过的状态。
有了单个 \(N\) 的周期求法之后，外层过程只需从 \(2\) 遍历到给定上界，检查返回的周期长度是否为奇数；若为奇数，就把答案加一。默认上界是 \(10{,}000\)。
C++、Python 和 Java 三个实现还都带有一个小型自检：在 \(13\) 以内，奇周期的正确个数是 \(4\)。这个检查同时验证了递推、停止条件和奇偶判断。
对固定的 \(N\)，连分数循环的每一步只做 \(O(1)\) 次整数运算，因此耗时与周期长度 \(r(N)\) 成正比。经典理论给出的最坏情形上界是 \(r(N)=O(\sqrt{N})\)，所以对上界 \(L\) 的总复杂度满足
$$\sum_{N=2}^{L} O(\sqrt{N}) = O(L^{3/2}).$$
当 \(L=10{,}000\) 时，这个计算量非常小。
空间复杂度是 \(O(1)\)。算法只保存当前状态 \((m,d,a)\)、初始值 \(a_0\)、当前周期长度，以及奇周期总数的计数器。
Для каждого целого числа \(N\) из диапазона \(2 \le N \le 10{,}000\) сначала отбрасываются полные квадраты, а затем рассматривается простая непрерывная дробь для \(\sqrt{N}\). Для любого неквадратного \(N\) она имеет вид \(\sqrt{N}=[a_0;\overline{a_1,a_2,\dots,a_r}]\), и нужно посчитать, для скольких значений \(N\) длина периода \(r\) нечётна.
Небольшой пример до \(N=13\) сразу показывает, что именно считается: нечётные периоды возникают у \(N=2,5,10,13\), то есть всего \(4\) раза. В полной задаче тот же тест выполняется для всех \(N \le 10{,}000\).
Ключевое наблюдение состоит в том, что период зашит в очень маленьком целочисленном состоянии. Как только разложение \(\sqrt{N}\) записано через полные частные, вся задача сводится к точной рекурсии на целых числах и к проверке чётности полученной длины периода.
Положим \(a_0=\lfloor \sqrt{N}\rfloor\). Если \(a_0^2=N\), то \(\sqrt{N}\) уже является целым числом, и никакой периодической части нет; такие значения сразу пропускаются. Для неквадратного \(N\) стартуем с
$$\alpha_0=\sqrt{N}=\frac{\sqrt{N}+0}{1}.$$
На каждом шаге текущая полная частная записывается в стандартной форме квадратичной иррациональности
$$\alpha_k=\frac{\sqrt{N}+m_k}{d_k},\qquad a_k=\lfloor \alpha_k \rfloor,$$
где начальные значения равны \(m_0=0\), \(d_0=1\), \(a_0=\lfloor \sqrt{N}\rfloor\). Один шаг непрерывной дроби означает: отделить целую часть \(a_k\), а затем обратить оставшуюся дробную часть.
По определению простой непрерывной дроби следующая полная частная удовлетворяет равенству
$$\alpha_{k+1}=\frac{1}{\alpha_k-a_k}.$$
Подставляя \(\alpha_k=(\sqrt{N}+m_k)/d_k\) и рационализуя знаменатель, получаем
$$\alpha_{k+1}=\frac{d_k}{\sqrt{N}+m_k-a_kd_k} =\frac{d_k(\sqrt{N}+a_kd_k-m_k)}{N-(a_kd_k-m_k)^2}.$$
Отсюда естественно ввести стандартные величины
$$m_{k+1}=d_ka_k-m_k,\qquad d_{k+1}=\frac{N-m_{k+1}^2}{d_k},$$
после чего новый шаг снова имеет тот же вид:
$$\alpha_{k+1}=\frac{\sqrt{N}+m_{k+1}}{d_{k+1}}.$$
Его целая часть равна
$$a_{k+1}=\left\lfloor \frac{\sqrt{N}+m_{k+1}}{d_{k+1}} \right\rfloor =\left\lfloor \frac{a_0+m_{k+1}}{d_{k+1}} \right\rfloor,$$
поскольку \(a_0 < \sqrt{N} < a_0+1\). Именно эти формулы используются во всех реализациях.
После начального вычисления целой части плавающая арифметика больше не нужна. Если на некотором шаге выполняется \(d_k\mid (N-m_k^2)\), то из равенства \(m_{k+1}=d_ka_k-m_k\) следует
$$m_{k+1}\equiv -m_k \pmod{d_k},\qquad m_{k+1}^2\equiv m_k^2 \pmod{d_k}.$$
Значит, \(d_k\) делит и \(N-m_{k+1}^2\), поэтому
$$d_{k+1}=\frac{N-m_{k+1}^2}{d_k}$$
остаётся целым числом на каждом шаге. Так как \(d_0=1\), эта точная делимость сохраняется по индукции во всём процессе. Именно поэтому реализации на C++, Python и Java могут работать исключительно с целыми числами.
Для квадратных корней неквадратных чисел непрерывная дробь периодична, а состояние, замыкающее один полный период, имеет специальный вид
$$m_k=a_0,\qquad d_k=1.$$
Если это состояние достигнуто, то сразу получается
$$a_k=\left\lfloor \sqrt{N}+a_0 \right\rfloor=2a_0,$$
то есть \((m_k,d_k)=(a_0,1)\) обязательно даёт \(a_k=2a_0\).
Обратное утверждение не менее важно. В редуцированном процессе выполняется \(0 \le m_k < \sqrt{N} < a_0+1\). Поэтому если \(a_k=2a_0\), то
$$2a_0 \le \frac{a_0+m_k}{d_k} < \frac{2a_0+1}{d_k}.$$
Левая часть возможна только при \(d_k=1\). Тогда остаётся \(2a_0=\lfloor a_0+m_k\rfloor\), а поскольку \(m_k\) целое и \(m_k<a_0+1\), вынужденно получаем \(m_k=a_0\). Следовательно, первое появление \(a_k=2a_0\) совпадает с первым возвращением в замыкающее состояние, то есть с концом первого полного периода.
Возьмём \(N=23\). Тогда \(a_0=\lfloor \sqrt{23}\rfloor=4\). Рекурсия даёт последовательность
$$ (m_1,d_1,a_1)=(4,7,1),\quad (m_2,d_2,a_2)=(3,2,3),\quad (m_3,d_3,a_3)=(3,7,1),\quad (m_4,d_4,a_4)=(4,1,8). $$
Поскольку \(a_4=8=2a_0\), длина периода равна \(4\), и потому
$$\sqrt{23}=[4;\overline{1,3,1,8}].$$
Для сравнения, \(\sqrt{13}=[3;\overline{1,1,1,1,6}]\) достигает \(2a_0=6\) только через \(5\) шагов, поэтому попадает в итоговый счётчик нечётных периодов.
Когда длина периода \(r(N)\) для одного неквадратного \(N\) уже найдена, исходная задача превращается просто в подсчёт
$$\#\{\,N: 2 \le N \le 10{,}000,\ N \notin \{m^2 : m \in \mathbb{Z}\},\ r(N)\equiv 1 \pmod 2\,\}.$$
Разные значения \(N\) полностью независимы друг от друга. Поэтому общий ответ получается простым повторением одной и той же процедуры поиска периода для каждого кандидата.
Сначала реализация находит \(a_0=\lfloor \sqrt{N}\rfloor\) с помощью целочисленного извлечения квадратного корня. Если \(a_0^2=N\), сразу возвращается период длины \(0\). Иначе состояние инициализируется как \(m=0\), \(d=1\), \(a=a_0\), после чего три рекуррентных обновления выполняются снова и снова, а счётчик периода увеличивается на каждом шаге.
Условие остановки специально выбрано минимальным: цикл заканчивается при первом появлении \(a=2a_0\). Поскольку это условие математически эквивалентно замыкающему состоянию \((m,d)=(a_0,1)\), программе не нужен ни хеш-набор, ни какая-либо другая память для уже встречавшихся состояний.
После того как длина периода для одного значения уже умеет вычисляться, внешняя часть программы проходит по всем целым от \(2\) до выбранной границы, проверяет чётность найденного периода и прибавляет \(1\) к ответу, если период нечётный. Граница по умолчанию равна \(10{,}000\).
Во всех трёх реализациях есть и небольшой встроенный контрольный тест из условия задачи: до \(13\) правильное число нечётных периодов равно \(4\). Эта проверка одновременно подтверждает корректность рекурсии, условия остановки и проверки чётности.
Для фиксированного \(N\) каждая итерация цикла непрерывной дроби выполняет только \(O(1)\) целочисленных операций, так что стоимость пропорциональна длине периода \(r(N)\). Классическая теория даёт верхнюю оценку \(r(N)=O(\sqrt{N})\), а значит для границы \(L\) получаем
$$\sum_{N=2}^{L} O(\sqrt{N}) = O(L^{3/2}).$$
При \(L=10{,}000\) этот объём работы очень мал.
Память имеет порядок \(O(1)\). Хранятся только текущее состояние \((m,d,a)\), начальное значение \(a_0\), текущая длина периода и общий счётчик нечётных периодов.
لكل عدد صحيح \(N\) يحقق \(2 \le N \le 10{,}000\)، نستبعد أولًا المربعات الكاملة، ثم ندرس الكسر المستمر البسيط للجذر \(\sqrt{N}\). لكل \(N\) غير مربع يكون هذا التمثيل على الصورة \(\sqrt{N}=[a_0;\overline{a_1,a_2,\dots,a_r}]\)، والمطلوب هو عدّ القيم التي يكون فيها طول الفترة \(r\) عددًا فرديًا.
حتى المثال الصغير عند \(N \le 13\) يوضح ما الذي يُعدّ بالضبط: الفترات الفردية تظهر عند \(N=2,5,10,13\)، ولذلك يكون العدد هناك \(4\). المسألة الكاملة تطبق الاختبار نفسه على جميع القيم حتى \(10{,}000\).
الفكرة الحاسمة هي أن الفترة ممثلة بحالة عددية صغيرة جدًا. ما إن نكتب الكسر المستمر لـ \(\sqrt{N}\) عبر الكسور الكاملة، حتى تتحول المسألة كلها إلى علاقة تراجعية دقيقة على أعداد صحيحة، ثم إلى فحص بسيط لما إذا كان طول الفترة فرديًا أم لا.
لنضع \(a_0=\lfloor \sqrt{N}\rfloor\). إذا تحقق \(a_0^2=N\)، فإن \(\sqrt{N}\) عدد صحيح أصلًا ولا توجد أي قطعة دورية، ولهذا تُهمَل هذه القيم مباشرة. أما إذا كان \(N\) غير مربع فنبدأ من
$$\alpha_0=\sqrt{N}=\frac{\sqrt{N}+0}{1}.$$
وفي كل مرحلة نكتب الكسر الكامل الحالي في الصورة القياسية للعدد غير النسبي التربيعي:
$$\alpha_k=\frac{\sqrt{N}+m_k}{d_k},\qquad a_k=\lfloor \alpha_k \rfloor,$$
مع القيم الابتدائية \(m_0=0\)، \(d_0=1\)، و\(a_0=\lfloor \sqrt{N}\rfloor\). خطوة الكسر المستمر تعني أخذ الجزء الصحيح \(a_k\) ثم قلب الباقي الكسري.
بحسب تعريف الكسر المستمر البسيط، فإن الكسر الكامل التالي يحقق
$$\alpha_{k+1}=\frac{1}{\alpha_k-a_k}.$$
وبالتعويض عن \(\alpha_k=(\sqrt{N}+m_k)/d_k\) ثم ترشيد المقام نحصل على
$$\alpha_{k+1}=\frac{d_k}{\sqrt{N}+m_k-a_kd_k} =\frac{d_k(\sqrt{N}+a_kd_k-m_k)}{N-(a_kd_k-m_k)^2}.$$
ومن هنا تظهر التعريفات القياسية
$$m_{k+1}=d_ka_k-m_k,\qquad d_{k+1}=\frac{N-m_{k+1}^2}{d_k},$$
بحيث يعود الشكل نفسه من جديد:
$$\alpha_{k+1}=\frac{\sqrt{N}+m_{k+1}}{d_{k+1}}.$$
أما الجزء الصحيح التالي فيكون
$$a_{k+1}=\left\lfloor \frac{\sqrt{N}+m_{k+1}}{d_{k+1}} \right\rfloor =\left\lfloor \frac{a_0+m_{k+1}}{d_{k+1}} \right\rfloor,$$
لأن \(a_0 < \sqrt{N} < a_0+1\). وهذه هي الصيغ نفسها التي تستخدمها التطبيقات.
بعد أخذ الجزء الصحيح الأول لا نحتاج إلى أي حساب عشري تقريبي. إذا كان \(d_k\mid (N-m_k^2)\) في خطوة ما، فإن العلاقة \(m_{k+1}=d_ka_k-m_k\) تعطي
$$m_{k+1}\equiv -m_k \pmod{d_k},\qquad m_{k+1}^2\equiv m_k^2 \pmod{d_k}.$$
ومن ثم فإن \(d_k\) يقسم أيضًا \(N-m_{k+1}^2\)، وبالتالي يكون
$$d_{k+1}=\frac{N-m_{k+1}^2}{d_k}$$
عددًا صحيحًا في كل خطوة. وبما أن \(d_0=1\)، فإن خاصية القسمة التامة تبقى صحيحة بالاستقراء طوال الحلقة. ولهذا تستطيع تطبيقات C++ وPython وJava الاعتماد على الحساب الصحيح فقط.
بالنسبة إلى جذور الأعداد غير المربعة، يكون الكسر المستمر دوريًا، وتكون حالة إغلاق فترة كاملة هي الصورة المختزلة المميزة
$$m_k=a_0,\qquad d_k=1.$$
إذا وصلنا إلى هذه الحالة، فإننا نحصل مباشرة على
$$a_k=\left\lfloor \sqrt{N}+a_0 \right\rfloor=2a_0,$$
أي إن الوصول إلى \((m_k,d_k)=(a_0,1)\) يضمن تلقائيًا أن \(a_k=2a_0\).
والعكس مهم بالقدر نفسه. ففي المسار المختزل لدينا دائمًا \(0 \le m_k < \sqrt{N} < a_0+1\). فإذا ظهر \(a_k=2a_0\)، لزم أن
$$2a_0 \le \frac{a_0+m_k}{d_k} < \frac{2a_0+1}{d_k}.$$
ولا يمكن أن تتحقق المتباينة اليسرى إلا إذا كان \(d_k=1\). وعندها تصبح الصيغة \(2a_0=\lfloor a_0+m_k\rfloor\)، وبما أن \(m_k\) عدد صحيح و\(m_k<a_0+1\)، فلا بد أن يكون \(m_k=a_0\). إذن أول ظهور للقيمة \(a_k=2a_0\) يطابق تمامًا أول عودة إلى حالة الإغلاق، أي نهاية أول فترة كاملة.
لنأخذ \(N=23\). عندئذٍ يكون \(a_0=\lfloor \sqrt{23}\rfloor=4\). تعطي العلاقة التراجعية السلسلة
$$ (m_1,d_1,a_1)=(4,7,1),\quad (m_2,d_2,a_2)=(3,2,3),\quad (m_3,d_3,a_3)=(3,7,1),\quad (m_4,d_4,a_4)=(4,1,8). $$
وبما أن \(a_4=8=2a_0\)، فإن طول الفترة يساوي \(4\)، ومن ثم
$$\sqrt{23}=[4;\overline{1,3,1,8}].$$
وللمقارنة، فإن \(\sqrt{13}=[3;\overline{1,1,1,1,6}]\) يصل إلى \(2a_0=6\) بعد \(5\) خطوات، ولذلك يدخل في عدّ الفترات الفردية.
بعد معرفة طول الفترة \(r(N)\) لقيمة واحدة غير مربعة من \(N\)، تصبح المسألة الأصلية مجرد حساب
$$\#\{\,N: 2 \le N \le 10{,}000,\ N \notin \{m^2 : m \in \mathbb{Z}\},\ r(N)\equiv 1 \pmod 2\,\}.$$
كل قيمة من \(N\) مستقلة تمامًا عن غيرها. لذلك يُبنى الجواب الكلي بتكرار إجراء حساب الفترة نفسه مرة واحدة لكل قيمة مرشحة.
تبدأ الشيفرة بحساب \(a_0=\lfloor \sqrt{N}\rfloor\) باستخدام جذر تربيعي صحيح. فإذا كان \(a_0^2=N\)، تُرجع طول فترة يساوي \(0\) فورًا. وإلا فإنها تهيّئ الحالة إلى \(m=0\)، \(d=1\)، \(a=a_0\)، ثم تكرر تحديثات العلاقة الثلاثية مع زيادة عدّاد الفترة في كل دورة.
قاعدة التوقف مقصودة في بساطتها: تنتهي الحلقة عند أول ظهور لـ \(a=2a_0\). وبما أن هذا الشرط مكافئ رياضيًا لحالة الإغلاق \((m,d)=(a_0,1)\)، فلا توجد حاجة إلى تخزين الحالات السابقة في مجموعة أو جدول.
بعد توفر حساب الفترة لقيمة واحدة، تمر الحلقة الخارجية على جميع الأعداد من \(2\) إلى الحد المختار، وتفحص ما إذا كان طول الفترة الناتج فرديًا؛ فإذا كان كذلك زادت الجواب بمقدار واحد. الحد الافتراضي هو \(10{,}000\).
وتحتوي تطبيقات C++ وPython وJava أيضًا على اختبار تحقق صغير مأخوذ من نص المسألة: حتى \(13\) يجب أن يكون عدد الفترات الفردية مساويًا لـ \(4\). هذا الفحص يؤكد في وقت واحد صحة العلاقة التراجعية وشرط التوقف وفحص الفردية.
بالنسبة إلى قيمة ثابتة من \(N\)، كل دورة في حلقة الكسر المستمر تنفذ \(O(1)\) من العمليات الصحيحة، ولذلك تكون الكلفة متناسبة مع طول الفترة \(r(N)\). وتعطي النظرية الكلاسيكية حدًا أعلى هو \(r(N)=O(\sqrt{N})\)، ومن ثم نحصل عند حد أعلى \(L\) على
$$\sum_{N=2}^{L} O(\sqrt{N}) = O(L^{3/2}).$$
وعندما يكون \(L=10{,}000\)، يكون هذا العبء الحسابي صغيرًا جدًا.
استخدام الذاكرة هو \(O(1)\). فالخوارزمية تحتفظ فقط بالحالة الحالية \((m,d,a)\)، والقيمة الابتدائية \(a_0\)، وطول الفترة الجاري حسابه، والعدّاد العام للفترات الفردية.