连续自然数构成的素数

mathe

将前N个自然数连续写成一行，构成一个大数，请问能否找到一些N使得这个数是素数， 如: 1234567891011121314151617 转自http://tieba.baidu.com/f?kz=360842437

mathe

我已经用HugeCalc计算到N=1600都没有素数。

无心人

N=3k+2应该不行

mathe

如何得出这个结论？

无心人

1+2=3 1+2+3+4+5=12 ... 注意到两位以上数字，三个相加只和末位数字相关 所以可证明

mathe

嗯，那就是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. }

复制代码

mathe

已经搜索到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%

zgg___

可以给出程序在检测N=8053、10279和36583这3个特殊值时的运行时间么？

mathe

这三个数有什么特殊的？好像都挺慢 8053素性判断需要8.1分钟,10279需要16.3分钟,36583还没有运行出来，到出来再看吧

zgg___

呵呵，也没什么特殊的，就是慢，想比较一下mathe机器的计算能力。