Alle Quadratwurzeln sind periodisch, wenn sie als Kettenbrüche geschrieben werden können, und können in folgender Form geschrieben werden:

N = a0 +
1
  a1 +
1
    a2 +
1
      a3 + ...

Beispiel: Stellen wir uns √23 vor:

√23 = 4 + √23 — 4 = 4 + 
1
 = 4 + 
1
 
1
√23—4
  1 + 
√23 – 3
7

Wenn wir dies weiterführen würden, würden wir die folgende Erweiterung erhalten:

√23 = 4 +
1
  1 +
1
    3 +
1
      1 +
1
        8 + ...

Der Prozess kann wie folgt zusammengefasst werden:

a_(0) = 4,  
1
√23—4
 = 
√23+4
7
 = 1 + 
√23—3
7
a_(1) = 1,  
7
√23—3
 = 
7(√23+3)
14
 = 3 + 
√23—3
2
a_(2) = 3,  
2
√23—3
 = 
2(√23+3)
14
 = 1 + 
√23—4
7
a_(3) = 1,  
7
√23—4
 = 
7(√23+4)
7
 = 8 +  √23—4
a_(4) = 8,  
1
√23—4
 = 
√23+4
7
 = 1 + 
√23—3
7
a_(5) = 1,  
7
√23—3
 = 
7(√23+3)
14
 = 3 + 
√23—3
2
a_(6) = 3,  
2
√23—3
 = 
2(√23+3)
14
 = 1 + 
√23—4
7
a_(7) = 1,  
7
√23—4
 = 
7(√23+4)
7
 = 8 +  √23—4

Es ist zu sehen, dass sich die Folge wiederholt. Für Prägnanz benutzen wir die Schreibweise √23 = [4;(1,3,1,8)], um zu zeigen, dass der Block (1,3,1,8) sich unendlich wiederholt.

Die ersten zehn Kettenbruchdarstellungen von (irrationalen) Quadratwurzeln sind:

√2=[1;(2)], Periode=1
√3=[1;(1,2)], Periode=2
√5=[2;(4)], Periode=1
√6=[2;(2,4)], Periode=2
√7=[2;(1,1,1,4)], Periode=4
√8=[2;(1,4)], Periode=2
√10=[3;(6)], Periode=1
√11=[3;(3,6)], Periode=2
√12= [3;(2,6)], Periode=2
√13=[3;(1,1,1,1,6)], period=5

Genau 4 Kettenbrüche, für N ≤ 13, haben eine ungerade Periodenlänge.

Wie viele Kettenbrüche, für N ≤ 10000, haben eine ungerade Periode?

Diese Aufgabe auf projecteuler.net