sqrt(n) 连分数周期的奇偶性
在projecteuler上遇到的一道题.http://projecteuler.net/problem=64
求\sqrt{n}的连分数展开的周期的奇偶性,使用pari/gp用以下代码很多数都求不出来或者不正确, 请大家指点
f(x)={
r = sqrt(x);
r = r0 = r-floor(r);
p= 0.00000001 ;
rt= s = 0;
while(abs(r0 -rt) > p , s++ ;r = 1/r ;rt = r - floor(r);r = rt );
return (s % 2);
}
for(i=2,10^4,if(ispower(i,2)==0 && f(i)==1,cnt++);print(i ,":" ,cnt)) 1. 求出$sqrt(n)$的第一项$a_0, a_0=\floor\sqrt n$, 即平方根向下取整。
2. 逐次求出$a_1,a_2,a_3,a_4,...$，并判断是否$a_i=2a_0$, 是则其连分数的周期为`i`.
例如$sqrt(13)$=<3,1,1,1,1,6>, $a_0=3, a_5=2a_0$,故其周期为5
再如$sqrt(61)$=<7,1,4,3,1,2,2,1,3,4,1,14>, $a_0=7, a_11=2a_0$,故其周期为11 求$sqrt(n)$的连分数展开可参阅wiki 词条 Methods of computing square roots 中的Continued fraction expansion 一节 以下的内容是摘自我的一个研究报告，未发表，转载请注明出处。
记 contfrac($sqrt D$)的周期为T(D).
文献给出的一个初略的周期的上界$O(ln(D)*sqrt(D))$ . 而我的探索表明，T(D)<c(D)√D，c(D)趋势缓慢增长。下表给出了c(D)增长曲线的峰点。
D c(D)(近似值) 备注
7 1.51 c(7)是第1个大于1.5者
1726 2.12 c(1726)是第1个大于2者，下同不注。
111094 2.50
289111 2.60
969406 2.71
2237134 2.82
10393111 2.90
39803611 3.01
可以看出， c(D)增长越来越慢，实际上，>3.0的c(D)非常少，D在1亿以内共有9个，他们是39803611, 40781911, 55839694, 78986779, 83808631, 85181539,86156599,91358446和97544899，c(D)最大约为3.0319.
另外，我亦发现，如果T(D)很大，那么D一般包含很少的素因子。上表中这些数或者是一个素数，或者是2和一个素数的乘积。周期很大和很小的数都不太常见，T(n^2 +1)=1.
Weisstein, Eric W,”Periodic continued Fraction” from MathWorld 厉害，连私房菜都端上来了。:) 猜想1: 好像只要含有4k+3的质因子, 然后周期就是偶数,不含有4k+3的质因子,周期就是奇数（完全平方数除外）
猜想2: $T(a^2+b^2)$是偶数，否则就是奇数。 contfrac(sqrt(163))计算根号163的连分数!我说的是用pari/gp 猜想2的第一个反例是3*5=15 对于非平方整数:
如果含有了4k+3的质数因子,那么肯定是偶数,
如果不含有4k+3的质数因子,那么是不是就是奇数了呢?这个我还不知道! 这个问题比较难的,我上面的回答只是正确了一小部分,离正确答案还有些远