对于野花质数等差数列的分析

显示全部楼层 · 2012-5-21 10:19:41

对于野花质数等差数列的分析
--当时做第一题时就觉得有规律，不过现在才有点想明白
问题1：
跨度为10，长度为3的数列
设第一个数为3n+b，（n>=1,0<=b<=2)
那么第2个数3n+b+10=3(n+3)+(b+1)
而第3个数3n+b+20=3(n+6)+(b+2)
根据抽屉原则,b,b+1,b+2三个数必定有一个是3的倍数，
也就是说这3个候选质数中必有1个是3的倍数，而符合条件的质数只有一个：3
由题意，3是三个数最小的，因此，答案是： 3 13 23
问题2：
虽然没有给出跨度k，但显然k必须是一个偶数，否则x+k,x+2k中必有一个为大于2的偶数，它是合数，不符合题意。
对这个偶数还有其他的要求。
比如，它不能为4=3+1，
不然x x+4 x+8 x+12 x+16 x+20 x+24
即 x x+3+1 x+3*2+2 x+3*4 x+3*5+1 x+3*6+2 x+3*8
这7个数必有2个是3的倍数
同理，k也不能为8=3*2+2
所以合理推论，这个偶数应该能被几个不同的质数整除，比如2*3*5=30
这样无论它的n倍，除以 2 3 5 后的余数都是0，而不会出现不同的余数，因此x+kn中不会出现 2 3 5的倍数，才符合质数的条件
但30不能被7整除，它=7*4+2，它的n倍中除以7会有不同的余数，比如2 4 6 1（8）3（10）5（12）0（14），所以当长度为8时，
还是会出现合数。所以，这个偶数还必须被7整除，
回到问题2
首先要求长度为7，我们有2种选择，
选择1：第一个数为7，偶数不需要能被7整除，可以尝试30 60 90 120 150等
选择2：第一个数不为7，偶数能被7整除，可以尝试210 420 630 840等
再猜想，如果长度要求N
那么这个跨度必须具有“所有”小于或等于N的质因数
长度=8：质因数2 3 5 7
长度=9：质因数2 3 5 7
长度=10：质因数2 3 5 7
长度=11：质因数2 3 5 7 11
长度=12：质因数2 3 5 7 11
长度=13：质因数2 3 5 7 11 13
问题3，实际上也部分得到了解决
newkid的结论验证了这一点，step=60060 len=13
60060=2（2*3*5*7*11*13）
剩下就是怎么用程序实现，应该可以按此规律减少尝试的次数
问题4，
显然这个跨度必须是3的倍数，同时它是个偶数，而第一个质数必须是3，那么从最大的跨度开始尝试即可
我也提出一个问题
问题5：
第一个长度为15的等差数列的首数和跨度分别是什么？

千问 · 2012-5-21 10:19:41

厉害，OO分析的这么透彻！

千问 · 2012-5-21 10:19:41

原帖链接还是我给吧： http://www.itpub.net/thread-1559255-1-1.html
bs下〇〇，嘿嘿

千问 · 2012-5-21 10:19:41

用NUMBER可以表示126个BIT,筛子可以做大一点，就是计算复杂一点。

千问 · 2012-5-21 10:19:41

newkid 发表于 2012-1-1 05:35
用NUMBER可以表示126个BIT,筛子可以做大一点，就是计算复杂一点。
针对第5问？

千问 · 2012-5-21 10:19:41

newkid 发表于 2012-1-1 05:35
用NUMBER可以表示126个BIT,筛子可以做大一点，就是计算复杂一点。
number的长度是22字节，按理说能表示160bit

千问 · 2012-5-21 10:19:41

OO这个分析收藏了！

千问 · 2012-5-21 10:19:41

〇〇发表于 2012-1-5 14:05
number的长度是22字节，按理说能表示160bit
我是按38位来打算的：
SELECT LOG(2,LPAD(9,38,9)) FROM DUAL;
LOG(2,LPAD(9,38,9))
-------------------
126.233268
实际上可以到40位，132 BIT:
select to_char(power(2,132)) from dual;
TO_CHAR(POWER(2,132))
----------------------------------------
5444517870735015415413993718908291383296
超过132就不行了：
select to_char(power(2,133)) from dual;
TO_CHAR(POWER(2,133))
----------------------------------------
1.0889035741470030830827987437816583E+40
我也写了个二进制的筛法，但是ORACLE对NUMBER型的计算太慢了，一百万内素数也要花4秒。