圣诞新年小娱乐——寻找等差素数数列

〇〇

发表于 2011-12-24 13:00:43 |只看该作者 |倒序浏览 3/5/7 这是一组等差为2长度为3的最小的也是唯一的素数数列
11/17/23/29 这是一组等差为6长度为4的一组最小的素数数列

而事实上：

陶哲轩，数学界的莫扎特。于2006年获菲尔兹奖，主要是证明了一令人惊讶的素数定理：存在任意长的素数等差数列。例如数列11,17,23,29是含4个素数的间距为6的素数等差数列。尽管目前能找到的最长的素数等差数列的长度仅是25（数已经长过了18 位），但陶能证明任意长度的存在！显然，25的长度是太难了，那我们来做一些简单的尝试，找出一些素数数列（所谓数列，至少要三个数）：

1.找出第一组等差为10的素数数列，并给出其长度
2.找出第一组长度分别为7/8/9的等差素数数列
3.找出1000000以内，等差最大的素数数列，并给出其长度
4.找出1000000以内，长度最长的等差数列，并给出其等差

风云剑

一眼看出
1)3,13,23
其他的还没计算。

wayne

2# 风云剑
既然是数列，那么至少是3个元素，等差为10 的话，那么三个中至少有一个是3的倍数，又因为是素数，所以，3,13,23 是仅有的一组

〇〇

寻求高效的算法

wayne

4# 〇〇
如果序列长度为7，或者是8，9，10，序列的第一个元素
是2，则无解
是3，则公差只能是70的倍数，
是5，则公差只能是42的倍数，
是7，则公差只能是30的倍数，
大于7，则公差只能是2*3*5*7=210 的倍数

〇〇

问题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，实际上也部分得到了解决
剩下就是怎么用程序实现，应该可以按此规律减少尝试的次数

geslon

11/17/23/29 这是一组等差为6长度为4的一组最小的素数数列

楼主这个论述可搞笑了，这个前面可以加上5的。

5、11、17、23、29
等差为6，长度为5.

geslon

7,157,307,457,607,757,907

似乎是一组长度为7的，公差150的素数数列？

geslon

4# 〇〇
如果序列长度为7，或者是8，9，10，序列的第一个元素
是2，则无解
是3，则公差只能是70的倍数，
是5，则公差只能是42的倍数，
是7，则公差只能是30的倍数，
大于7，则公差只能是2*3*5*7=210 的倍数
wayne 发表于 2011-12-31 14:07

首项是2,3,5那是不可能的。我们假设公差为k，比如首项为5，则5+5k就不是素数了。

容易知道，序列长度为7，首项至少是7。
同理，序列长度为8,9,10，首项至少是11.（也就是说首项a至少是不小于长度L的素数）

公差必须包含所有小于长度L的素因子。

即：要求出一个长度为L的素数等差数列，假设其首项为a，公差为k。
则 a为不小于L的素数，且k为包含所有不小于l的质因子，是必要而不充分条件。

LZC_314

这位朋友问的问题和我差不多~我也想知道怎么弄呢