# 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$$ について奇数の周期をもつ平方根が何個あるか答えよ.
