找回密码
 欢迎注册
查看: 28043|回复: 34

[擂台] 连续自然数构成的素数

[复制链接]
发表于 2008-4-22 11:09:06 | 显示全部楼层 |阅读模式

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

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

×
将前N个自然数连续写成一行,构成一个大数,请问能否找到一些N使得这个数是素数,
如:
1234567891011121314151617
转自http://tieba.baidu.com/f?kz=360842437
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-22 11:09:32 | 显示全部楼层
我已经用HugeCalc计算到N=1600都没有素数。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-22 11:43:53 | 显示全部楼层


N=3k+2应该不行
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-22 12:41:00 | 显示全部楼层
如何得出这个结论?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-22 19:11:42 | 显示全部楼层
1+2=3
1+2+3+4+5=12
...
注意到两位以上数字,三个相加只和末位数字相关
所以可证明
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-23 08:23:19 | 显示全部楼层
嗯,那就是3k+2和3k+3都不行。
我用HugeCalc写了个简单的代码搜索,找到9801了还没有结果:
  1.     int i,j;
  2.     integer v(1);
  3.     int count=0;
  4.     int k=10;
  5.         int c=HugeCalc::GetPrimeCount(2,100000);
  6.         unsigned *pb=new unsigned[c];
  7.         unsigned *buff=new unsigned[1000000];
  8.         memset(buff,0,sizeof(unsigned)*1000000);
  9.         HugeCalc::GetPrimeList(pb,c,2,100000);
  10.         int fc=0;
  11.         for(i=0;i<c;i++){
  12.                 int p=pb[i];
  13.                 long long s=123456789%p;
  14.                 int t;
  15.                 k=10;
  16.                 for(t=2;t<=6;t++){
  17.                         for(j=k;j<10*k;j++){
  18.                                 s*=k*10;
  19.                                 s+=j;
  20.                                 s%=p;
  21.                                 if(s==0&&buff[j]==0){
  22.                                         buff[j]=1;
  23.                                         fc++;
  24.                                 }
  25.                         }
  26.                         k*=10;
  27.                 }
  28.         }
  29.         fprintf(stderr,"Filtered %d\n",fc);
  30.         k=10;
  31.     integer x("123456789");
  32.     for(i=2;i<=6;i++){
  33.         for(j=k;j<10*k;j++){
  34.             x*=k*10;
  35.             x+=j;
  36.             if((!buff[j])&&x.IsPrime()){
  37.                 printf("Found: %s\n",x.GetStr());
  38.                 count++;
  39.             }
  40.             if(j%100==1){
  41.                 fprintf(stderr,"Reach %d,found %d\n",j,count);
  42.             }
  43.         }
  44.         k*=10;
  45.     }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-23 10:40:49 | 显示全部楼层
已经搜索到10000以外都没有解了(花了半天多的机器时间)。
看来这个题目很难找到可行的解了。
根据百度贴吧链接中KeyTo9のFans给出的一个估计公式,我们可以知道到N为止素数数目的估计值大概在
$log(log(N))+C$,如果考虑到前1000个数中都没有找到数值,那么我们对于能够找到一个素数的N的一个大概范围可以估计为使得$log(log(N))-log(log(1000))>=1$的最小N,这个N大概为$1.4xx10^8$
如果再结合无心人上面的分析,那么这个序列中素数的概率应该本通常完全随机挑选的序列还要低一倍,也就是估计公式应该再加上一个系数$1/2$,所以我们期望的N应该改为使得$log(log(N))-log(log(1000))>=2$的最小N,这个值大概为$1.5xx10^22$,所以按上面程序的速度,很难有这么好的运气找到一个解了。
如果我让程序再运行上2个月左右,估计能够搜索到100000的范围(大概$N^2$的复杂度?所以100倍的时间),而这个范围能够找出一个素数的概率大概在11%
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-23 11:35:25 | 显示全部楼层
可以给出程序在检测N=8053、10279和36583这3个特殊值时的运行时间么?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-23 12:18:58 | 显示全部楼层
这三个数有什么特殊的?好像都挺慢
8053素性判断需要8.1分钟,10279需要16.3分钟,36583还没有运行出来,到出来再看吧
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-23 13:03:44 | 显示全部楼层
呵呵,也没什么特殊的,就是慢,想比较一下mathe机器的计算能力。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-3-29 02:06 , Processed in 0.045498 second(s), 16 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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