064 : 奇数周期の平方根

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

$\displaystyle \sqrt{N} = a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{a3 + \dots}}}$

例えば, $\sqrt{23}$を考えよう.

$\displaystyle \sqrt{23} = 4 + \sqrt{23} - 4 = 4 + \frac{1}{\frac{1}{\sqrt{23} - 4}} = 4 + \frac{1}{1 + \frac{\sqrt{23} - 3}{7}}$

となる.

この操作を続けていくと,

$\displaystyle \sqrt{23} = 4 + \frac{1}{1 + \frac{1}{3 + \frac{1}{1 + \frac{1}{8 + \dots}}}}$

を得る.

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

• $\displaystyle a_0 = 4, \frac{1}{\sqrt{23}-4} = \frac{\sqrt{23}+4}{7} = 1 + \frac{\sqrt{23}-3}{7}$

• $\displaystyle a_1 = 1, \frac{7}{\sqrt{23}-3} = \frac{7(\sqrt{23}+3)}{14} = 3 + \frac{\sqrt{23}-3}{2}$

• $\displaystyle a_2 = 3, \frac{2}{\sqrt{23}-3} = \frac{2(\sqrt{23}+3)}{14} = 1 + \frac{\sqrt{23}-4}{7}$

• $\displaystyle a_3 = 1, \frac{7}{\sqrt{23}-4} = \frac{7(\sqrt{23}+4}{7} = 8 + (\sqrt{23}-4)$

• $\displaystyle a_4 = 8, \frac{1}{\sqrt{23}-4} = \frac{\sqrt{23}+4}{7} = 1 + \frac{\sqrt{23}-3}{7}$

• $\displaystyle a_5 = 1, \frac{7}{\sqrt{23}-3} = \frac{7(\sqrt{23}+3)}{14} = 3 + \frac{\sqrt{23}-3}{2}$

• $\displaystyle a_6 = 3, \frac{2}{\sqrt{23}-3} = \frac{2(\sqrt{23}+3)}{14} = 1 + \frac{\sqrt{23}-4}{7}$

• $\displaystyle a_7 = 1, \frac{7}{\sqrt{23}-4} = \frac{7(\sqrt{23}+4)}{7} = 8 + (\sqrt{23}-4)$

よって, この操作は繰り返しになることが分かる. 表記を簡潔にするために, $\sqrt{23} = [4;(1,3,1,8)]$と表す. $(1,3,1,8)$のブロックは無限に繰り返される項を表している.

最初の10個の無理数である平方根を連分数で表すと以下になる.

• $\sqrt{2}=[1;(2)]$, 周期 1

• $\sqrt{3}=[1;(1,2)]$, 周期 2

• $\sqrt{5}=[2;(4)]$, 周期 1

• $\sqrt{6}=[2;(2,4)]$, 周期 2

• $\sqrt{7}=[2;(1,1,1,4)]$, 周期 4

• $\sqrt{8}=[2;(1,4)]$, 周期 2

• $\sqrt{10}=[3;(6)]$, 周期 1

• $\sqrt{11}=[3;(3,6)]$, 周期 2

• $\sqrt{12}= [3;(2,6)]$, 周期 2

• $\sqrt{13}=[3;(1,1,1,1,6)]$, 周期 5

$N ≤ 13$で奇数の周期をもつ平方根は丁度4つある.

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