Project Euler にチャレンジ:Problem 64

← Problem 63  Problem 65 →

Problem 64[奇数周期の平方根(Odd period square roots)]

すべての平方根は、連分数として記述されると、周期的になり、次の形式で書くことができます。

√N = a0 + 1/(a1 + 1/(a2 + 1/a3+......))

例えば、√23 を考えてみると、

√23 = 4 + √23 - 4 = 4 + 1/(1/(√23-4)) = 4 + 1/(1 + (√23 - 3/7)

これを続けていくと、以下のようになります。

√23 = 4 + 1/(1 + 1 / ( 3 + 1/(1+1/(8+.....))))

このプロセスは以下のように記載することができます。

a0 = 4,1/(√23 - 4) = 1 + (√23 - 3)/7
a1 = 1,7/(√23 - 3) = 3 + (√23 - 3)/2
a2 = 3,2/(√23 - 3) = 1 + (√23 - 4)/7
a3 = 1,7/(√23 - 4) = 8 + √23 - 4
a4 = 8,1/(√23 - 4) = 1 + (√23 - 3)/7
a5 = 1,7/(√23 - 3) = 3 + (√23 - 3)/2
a6 = 3,2/(√23 - 3) = 1 + (√23 - 4)/7
a7 = 1,7/(√23 - 4) = 8 + √23 - 4

この順番は繰り返しています。簡潔にするために、√23 = [4;(1,3,1,8)] と記載します。
(1,3,1,8) が繰り返しの部分になります。

最初の10個の無理数の平方根を記載すると以下になります。

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

周期が奇数になる数は N ≦ 13 の範囲では、4つあります。

N ≦ 10,000 の範囲で周期が奇数になるものはいくつか。