数学研发论坛

 找回密码
 欢迎注册
查看: 13985|回复: 31

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

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

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

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

x
各位好,我想求$\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$=int(sqrt(n)), 即平方根向下取整。
2. 逐次求出$a_1,a_2,a_3,a_4...$等,边求边检查ai的值,如果$a_i=2xxa_0$,则其连分数的周期是i.
如sqrt(13)=<3,1,1,1,1,6>, $a_0=3, a_5=2xxa_0$,故其周期为5
如sqrt(61)=<7,1,4,3,1,2,2,1,3,4,1,14>, $a_0=7, a_11=2xxa_0$,故其周期为11
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-3-13 10:10:06 | 显示全部楼层
至于求sqrt(n)的连分数展开,即楼上的<a0,a1,a2...> 可参阅wiki 词条 Methods of computing square roots 中的Continued fraction expansion 一节
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-3-13 10:18:18 | 显示全部楼层
以下的内容是摘自我的一个研究报告,未发表,转载请注明出处。
文献[1]给出的一个初略的周期的上界O(ln(D)*sqrt(D)) .而我的实验表明,√D的连分数的周期不超过c√D,c的取值和D有关,随着D的增加而缓慢增长。下表给出对于不同的D,其平方根的连分数周期的上界。
D        C(近似值)        备注
7        1.51        7是第1个其平方根连分数周期大于1.5倍平方根的数。以下将“平方根连分数的周期”简称为周期
1726        2.12        1726是第1个周期大于2倍平方根的数
111094        2.50        111094是第1个其周期大于2.5倍平方根的数
289111        2.60        289111是第1个其周期大于2.6倍平方根的数
969406        2.71        969406是第1个其周期大于2.7倍平方根的数
2237134        2.82        2237134是第1个其周期大于2.8倍平方根的数
10393111        2.90        10393111是第1个其周期大于2.9倍平方根的数
39803611        3.01        39803611是第1个其周期大于3倍平方根的数
可以看出, c增长率越来越慢,实际上,满足其平方根连分数的周期>3.0√D的D非常的少,1亿以内的数共有9个,他们是39803611, 40781911, 55839694, 78986779, 83808631, 85181539,86156599,91358446和97544899,其连分数周期与√D的最大比约为3.0319.另外,我亦发现,如果一个数的平方根的连分数的周期很大,那个这个数也往往包含很少的素因子。上表中,这些数或者是一个素数,或者是2和一个素数的乘积。周期很大和很小的数都不太常见,若D=n^2 +1,则√D的连分数的周期仅为1.

[1] Weisstein, Eric W,”Periodic continued Fraction” from MathWorld
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-3-13 10:27:41 | 显示全部楼层
厉害,连私房菜都端上来了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-3-13 10:41:51 | 显示全部楼层
好像只要含有4k+3的质因子, 然后周期就是偶数,不含有4k+3的质因子,周期就是奇数(排除完全平方数)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-3-13 10:48:40 | 显示全部楼层
好像只要含有4k+3的质因子, 然后周期就是偶数,不含有4k+3的质因子,周期就是奇数(排除完全平方数) .我凭借我的数学直觉来回答这个问题.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-3-13 11:09:50 | 显示全部楼层
kronecker(a,b)计算lengdre和jacobi符号
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-3-13 11:26:36 | 显示全部楼层
contfrac(sqrt(163))计算根号163的连分数!  我说的是用pari/gp
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-3-13 11:59:55 | 显示全部楼层
如果一个整数能表示成两个非负整数的平方和,那么它的连分数的展开周期是偶数,如果不能表示成两个非负整数的平方和,那么它的连分数的周期是奇数,很显然,完全平方数等于他自己与零的平方的和,完全平方数的周期是零,也是偶数............

这个只是我的猜测
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2021-9-26 15:28 , Processed in 0.062578 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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