魔方吧·中文魔方俱乐部
标题:
一个奇特的素数筛选的矩阵
[打印本页]
作者:
ggglgq
时间:
2005-1-6 09:08:45
标题:
一个奇特的素数筛选的矩阵
一个奇特的素数筛选的矩阵
请大家看看下面的这个对称矩阵:
4 7 10 13 16 19 22 ......
7 12 17 22 27 32 37 ......
10 17 24 31 38 45 52 ......
13 22 31 40 49 58 67 ......
16 27 38 49 60 71 82 ......
... ... ... ... ... ... ... ...
规律是显然的:第一行公差为 3 ;第二行公差为 5 ,...
这个对称矩阵有什么用呢?
这就是森德拉姆(Sundaram,1934)素数筛法矩阵,如果一个自然数 N
出现在矩阵当中,那么 2*N+1 是合数;反之若 N 不在表中出现,则 2*N+1
肯定是素数!
这么神奇的矩阵,奥妙在哪里呢 ?
[
本帖最后由 ggglgq 于 2009-6-29 11:15 编辑
]
作者:
ggglgq
时间:
2005-1-7 11:47:47
其实原理很简单!
让我们来分析一下:显然,矩阵的第i行、第j列的通项为
2(i-1)(j-1)+3(i-1)+3(j-1)+4
因此若N在表中的i行j列出现,则
2*N+1=2(2(i-1)(j-1)+3(i-1)+3(j-1)+4)+1
=(2(i-1)+3)(2(j-1)+3)
显然是一个合数。
假设2*N+1是合数,那么肯定存在奇数m,n满足2*N+1=m*n,并且
m>=3,n>=3, 那么,
N=(m*n-1)/2=((2*((m-3)/2)+3)(2*((n-3)/2)+3)-1)/2
根据通项公式,N应该出现在矩阵的(m-3)/2+1行,(n-3)/2+1列。
因此若N在表中不出现,则2*N+1必为素数!
[
本帖最后由 ggglgq 于 2009-6-29 11:17 编辑
]
作者:
cube_master
时间:
2005-1-7 14:02:39
好,顶一下[em23]
作者:
lok
时间:
2005-3-1 19:17:36
看來大家還是數學高手!
作者:
Cielo
时间:
2005-6-29 11:50:26
估计是高中竞赛题,强
欢迎光临 魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)
Powered by Discuz! X2