$sqrt(n)$连分数周期的奇偶性

cfan2021

在project  euler上遇到的一道题.
http://projecteuler.net/problem=64
求$\sqrt{n}$的连分数展开的周期的奇偶性,使用pari/gp用以下代码很多数都求不出来或者不正确, 请大家指点

1. 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))

复制代码

ucobiit

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

AzertVab

求$sqrt(n)$的连分数展开可参阅wiki 词条 Methods of computing square roots中的Continued fraction expansion 一节

oabipalehov

以下的内容是摘自我的一个研究报告，未发表，转载请注明出处。
记 contfrac($sqrt D$)的周期为T(D).
文献[1]给出的一个初略的周期的上界$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.

[1] Weisstein, Eric W,”Periodic continued Fraction” from MathWorld

iwejinawiciru

厉害，连私房菜都端上来了。

epezzaqegazeu

猜想1: 好像只要含有4k+3的质因子, 然后周期就是偶数,不含有4k+3的质因子,周期就是奇数（完全平方数除外）
猜想2: $T(a^2+b^2)$是偶数，否则就是奇数。

JamesTeest

contfrac(sqrt(163))计算根号163的连分数!  我说的是用pari/gp

ogemama

猜想2的第一个反例是3*5=15

渐行渐远

对于非平方整数:
如果含有了4k+3的质数因子,那么肯定是偶数,
如果不含有4k+3的质数因子,那么是不是就是奇数了呢?这个我还不知道!

Jeninslots

这个问题比较难的,我上面的回答只是正确了一小部分,离正确答案还有些远