所有自然数的平方根写成如下连分数表示时其系数$a_n$都是周期序列： $$ \sqrt{N}=a_0+\frac{1}{a_1+\frac{1}{a_2+\frac{1}{a_3+…}}}.$$ 例如 $$ \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+…}}}}.$$ 这一过程可以总结如下： \begin{align*} a_0&=4, \quad\frac 1 {\sqrt{23}-4}=\frac {\sqrt{23}+4} 7=1+\frac {\sqrt{23}-3} 7 \\ a_1&=1, \quad\frac 7 {\sqrt{23}-3}=\frac {7(\sqrt{23}+3)} {14}=3+\frac {\sqrt{23}-3} 2 \\ a_2&=3, \quad\frac 2 {\sqrt{23}-3}=\frac {2(\sqrt{23}+3)} {14}=1+\frac {\sqrt{23}-4} 7 \\ a_3&=1, \quad\frac 7 {\sqrt{23}-4}=\frac {7(\sqrt{23}+4)} 7=8+\sqrt{23}-4 \\ a_4&=8, \quad\frac 1 {\sqrt{23}-4}=\frac {\sqrt{23}+4} 7=1+\frac {\sqrt{23}-3} 7 \\ a_5&=1, \quad\frac 7 {\sqrt{23}-3}=\frac {7 (\sqrt{23}+3)} {14}=3+\frac {\sqrt{23}-3} 2 \\ a_6&=3, \quad\frac 2 {\sqrt{23}-3}=\frac {2(\sqrt{23}+3)} {14}=1+\frac {\sqrt{23}-4} 7 \\ a_7&=1, \quad\frac 7 {\sqrt{23}-4}=\frac {7(\sqrt{23}+4)} {7}=8+\sqrt{23}-4 \\ \end{align*} 可以看出序列具有周期性。我们将其记为$\sqrt{23} = [4;(1,3,1,8)]$，表示$(1,3,1,8)$是循环节。

自然数的平方根中的前十个无理数的连分数表示是

$\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。

其中恰有四个连分数的周期是奇数。

用连分数表示不超过一万的自然数的平方根，其中周期是奇数的有几个？

本题难度:

解答

过程很容易理解，不过自行实现符号计算比较麻烦，我从wikipedia摘录并修改了算法，原理可参考stackexchange的说明。结果是$1322$。

import math

sq=set([i*i for i in range(101)])
t=0
for n in range(2,10001):
    if n not in sq:
        s=int(math.sqrt(n))
        r=s
        k=1
        p=0
        while k!=1 or p==0:
            k=(n-r*r)/k
            r=(s+r)/k*k-r
            p+=1
        t+=p%2
print t