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

gracias · 发表于 2012-3-13 00:37:19

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

在project euler上遇到的一道题. 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))

复制代码

liangbch · 发表于 2012-3-13 10:05:39

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

liangbch · 发表于 2012-3-13 10:10:06

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

liangbch · 发表于 2012-3-13 10:18:18

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

gxqcn · 发表于 2012-3-13 10:27:41

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

mathematica · 发表于 2012-3-13 10:41:51

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

mathematica · 发表于 2012-3-13 11:26:36

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

mathematica · 发表于 2012-3-13 12:25:52

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

mathematica · 发表于 2012-3-13 12:39:43

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

mathematica · 发表于 2012-3-13 15:05:38

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

账号		自动登录	找回密码
密码			欢迎注册

[求助] sqrt(n) 连分数周期的奇偶性

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。