Problem 64 の変更点

• 追加された行はこの色です。
• 削除された行はこの色です。
• Problem 64 へ行く。

*[[Problem 64:http://projecteuler.net/problem=64]] 「奇数周期の平方根」 [#ub2fd43e]

平方根は連分数の形で表したときに周期的であり, 以下の形で書ける:

√&tex{N}; = &tex{a_{0} + 1 / (a_{1} + 1 / (a_{2} + 1 / (a_{3} + ...)))};

例えば, √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 + ...))))

を得る.

操作を纏めると以下になる:

-&tex{a_{0}}; = 4, 1/(√23-4) = (√23+4)/7 = 1 + (√23-3)/7
-&tex{a_{1}}; = 1, 7/(√23-3) = 7(√23+3)/14 = 3 + (√23-3)/2
-&tex{a_{2}}; = 3, 2/(√23-3) = 2(√23+3)/14 = 1 + (√23-4)/7
-&tex{a_{3}}; = 1, 7/(√23-4) = 7(√23+4)/7 = 8 + (√23-4)
-&tex{a_{4}}; = 8, 1/(√23-4) = (√23+4)/7 = 1 + (√23-3)/7
-&tex{a_{5}}; = 1, 7/(√23-3) = 7(√23+3)/14 = 3 + (√23-3)/2
-&tex{a_{6}}; = 3, 2/(√23-3) = 2(√23+3)/14 = 1 + (√23-4)/7
-&tex{a_{7}}; = 1, 7/(√23-4) = 7(√23+4)/7 = 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;(4)], period=1
-√6=[2;(2,4)], period=2
-√7=[2;(1,1,1,4)], period=4
-√8=[2;(1,4)], period=2
-√10=[3;(6)], period=1
-√11=[3;(3,6)], period=2
-√12= [3;(2,6)], period=2
-√13=[3;(1,1,1,1,6)], period=5

&tex{N}; ≤ 13で奇数の周期をもつ平方根は丁度4つある.

&tex{N}; ≤ 10000 について奇数の周期をもつ平方根が何個あるか答えよ.