数学研发论坛

 找回密码
 欢迎注册
查看: 19582|回复: 20

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

[复制链接]
发表于 2012-3-13 00:37:19 | 显示全部楼层 |阅读模式

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

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

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

  1. f(x)={
  2.    r = sqrt(x);
  3.    r = r0 = r-floor(r);
  4.    p= 0.00000001 ;
  5.    rt= s = 0;
  6.    while(abs(r0 -rt) > p , s++ ;r = 1/r ;rt = r - floor(r);r = rt );

  7.    return (s % 2);
  8. }

  9. for(i=2,10^4,if(ispower(i,2)==0 && f(i)==1,cnt++);print(i ,":" ,cnt))
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-3-13 10:10:06 | 显示全部楼层
求$sqrt(n)$的连分数展开可参阅wiki 词条 Methods of computing square roots 中的Continued fraction expansion 一节
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-3-13 10:18:18 | 显示全部楼层
以下的内容是摘自我的一个研究报告,未发表,转载请注明出处。
记 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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-3-13 10:27:41 | 显示全部楼层
厉害,连私房菜都端上来了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-3-13 10:41:51 | 显示全部楼层
猜想1: 好像只要含有4k+3的质因子, 然后周期就是偶数,不含有4k+3的质因子,周期就是奇数(完全平方数除外)
猜想2: $T(a^2+b^2)$是偶数,否则就是奇数。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-3-13 11:26:36 | 显示全部楼层
contfrac(sqrt(163))计算根号163的连分数!  我说的是用pari/gp
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-3-13 12:25:52 | 显示全部楼层
猜想2的第一个反例是3*5=15
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-3-13 12:39:43 | 显示全部楼层
对于非平方整数:
如果含有了4k+3的质数因子,那么肯定是偶数,
如果不含有4k+3的质数因子,那么是不是就是奇数了呢?这个我还不知道!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-3-13 15:05:38 | 显示全部楼层
这个问题比较难的,我上面的回答只是正确了一小部分,离正确答案还有些远
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2023-2-8 12:53 , Processed in 0.070198 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表