Problem 64

Odd Period Square Roots

All square roots are periodic when written as continued fractions and can be written in the form:

$\sqrt{N} = a_{0} + \frac{1}{a_{1} + \frac{1}{a_{2} + \frac{1}{a_{3} + \dots}}}$

For example, let us consider $\sqrt{23}$ :

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

If we continue we would get the following expansion:

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

The process can be summarised as follows:

$a_{0} = 4, \frac{1}{\sqrt{23} - 4} = \frac{\sqrt{23} + 4}{7} = 1 + \frac{\sqrt{23} - 3}{7}$

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

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

$a_{3} = 1, \frac{7}{\sqrt{23} - 4} = \frac{7 (\sqrt{23} + 4)}{7} = 8 + \sqrt{23} - 4$

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

$a_{5} = 1, \frac{7}{\sqrt{23} - 3} = \frac{7 (\sqrt{23} + 3)}{14} = 3 + \frac{\sqrt{23} - 3}{2}$

$a_{6} = 3, \frac{2}{\sqrt{23} - 3} = \frac{2 (\sqrt{23} + 3)}{14} = 1 + \frac{\sqrt{23} - 4}{7}$

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

It can be seen that the sequence is repeating. For conciseness, we use the notation $\sqrt{23} = [4; (1, 3, 1, 8)]$ , to indicate that the block $(1, 3, 1, 8)$ repeats indefinitely.

The first ten continued fraction representations of (irrational) square roots are:

$\sqrt{2} = [1; (2)]$ , period= $1$

$\sqrt{3} = [1; (1, 2)]$ , period= $2$

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

$\sqrt{6} = [2; (2, 4)]$ , period= $2$

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

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

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

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

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

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

Exactly four continued fractions, for $N \leq 13$ , have an odd period.

How many continued fractions for $N \leq 10000$ have an odd period?

奇周期平方根

所有的平方根写成如下连分数表示时都是周期性重复的：

$\sqrt{N} = a_{0} + \frac{1}{a_{1} + \frac{1}{a_{2} + \frac{1}{a_{3} + \dots}}}$

例如，让我们考虑 $\sqrt{23}$ ：

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

如果我们继续展开，会得到：

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

这个过程可以总结如下：

可以看出序列正在重复。我们将其简记为 $\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 \leq 13$ 中，恰好有 $4$ 个连分数表示的周期是奇数。

在 $N \leq 10000$ 中，有多少个连分数表示的周期是奇数？