魔方吧·中文魔方俱乐部

标题: 一个奇特的素数筛选的矩阵 [打印本页]

作者: 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/)