• 汇集公众科学智慧交流科学思想见解
  • 点燃科学智慧火花构建互动交流平台
科学智慧火花
发表评论  4                

钱德拉筛及其推广

投稿时间:2014-06-11 11:08 投稿人:周密 【字号: 访问量:

1934年,东印度(现孟加拉国)的钱德拉提出一个正方形筛子:

第1行是首项为4, 公差为3的等差数列4, 7, 10, …, 4+3(n-1), …

第2行是首项为7, 公差为5的等差数列7, 12, 17, …, 7+5(n-1), …

第3行是首项为10, 公差为7的等差数列10, 17, 24, …, 10+7(n-1), …

第4行是首项为13, 公差为9的等差数列13, 22, 31, …, 13+9(n-1), …

第m行是首项为3m+1, 公差为2m+1的等差数列3m+1, 5m+2, 7m+3, …, 它的第n项为 3m+1+(n-1)(2m+1)=2mn+m+n, …

写成以下的阵列:

 

第1列

第2列

第3列

第4列

第5列

第n列

第1行

4

7

10

13

16

4+3(n-1)

第2行

7

12

17

22

27

7+5(n-1)

第3行

10

17

24

31

38

10+7(n-1)

第4行

13

22

31

40

49

13+9(n-1)

第5行

16

27

38

49

60

16+11(n-1)

第m行

3m+1

5m+2

7m+3

9m+4

11m+5

2mn+m+n

这个方筛的奥妙在于:如果某个自然数N出现在表中,那么2N+1肯定不是素数;如果N在表中不出现,那么2N+1肯定是素数。

事实上,如果N=2mn+m+n,则2N+1=2(2mn+m+n)+1=4mn+2m+2n+1=(2m+1)(2n+1),它不是素数。反之,设N在表中不出现,如果2N+1不是素数,则2N+1必定是两个奇数之积,写2N+1=(2m+1)(2n+1)=4mn+2m+2n+1,得到N=2mn+m+n,它出现在表中,与假设矛盾。所以当N不出现在矩阵中时2N+1必为质数。

我据此做出了几个类似矩阵(简化一些): 

5 8 11 14 17 20,,,,,,, 

8 13 18 23 28 33,,,。,, 

11 18 25 32 39 46,,,,, 

,,,,,,,,,,,,,, 

在此矩阵中若干自然数N出现在此矩阵中则2N—1肯定不是质数,若不出现则2N—1必然为质数,因为第一个矩阵5 不出现,第二个矩阵6不出现而2*5+1=2*6—1,所以成立。 

同理,再列出一个矩阵: 

6 9 12 15 18,,,,, 

9 14 19 24 29,,,, 

12 19 26 33 40,,,, 

,,,,,,, 

可得出若自然数N出现在此矩阵中则2*N—3肯定不是质数,若不出现则2N—3必为质数,道理同上。 

还可列出: 

4+x, 7+x 10+x 13+x,,,,,, 

7+x 12+x 17+x 22+x ,,,,,, 

10+x 17+x 24+x 31+x ,,,,, 

,,,,,, 

可得出若自然数N出现在矩阵中则2*N—(2x—1)肯定不是质数,若不出现则2*N—(2x—1)肯定是质数。

还可以继续列出:

3   6    9   12 15   18,,,,,,

6 11    16   21 26   31,,,,,

9   16   23   30   37   44,,,,

,,,,,,,,,,

在这个矩阵中若自然数N出现在其中则2N+3必为合数,若不出现则2N+3必为质数,因为在以4开头的矩阵中6不出现,以3 开头的矩阵中5不出现,而2*6+1=2*5+3,所以成立。

再列一个矩阵:

2   5   8   11   14   17,,,,,,

5   10   15   20   25   30,,,,

8   15    22   29   36   43,,,,,

,,,,,,,,,,

再次矩阵中若自然数N出现则2*N+5必为合数,否则必为质数,道理同上。再找出一个通式,如下:

4—x     7—x   10—x    13—x    16—x,,,,,,,

7—x     12—x   17—x    22—x    27—x,,,,,

10—x    17—x    24—x   31—x    38—x,,,,,,

,,,,,,,,

在此矩阵中若自然数N出现在其中则2N+(2x+1)必为合数,若不出现则2N+(2x+1)必为质数。