森德拉姆篩法

又一個篩。森德拉姆 (Sundaram) 其人不過是東印度 (即現孟加拉國,在未獨立前為印度管治) 的窮苦學生。時 1934 年,他創了一個富有特式的森德拉姆篩法 (Sieve of Sundaram) 了。

方法如下

4
7
10
13
16
19
22
25
28
......
7
12
17
22
27
32
37
42
47
......
10
17
24
31
38
45
52
59
66
......
13
22
31
40
49
58
67
76
85
......
16
27
38
49
60
71
82
93
104
......
19
32
45
58
71
84
97
110
123
......
22
37
52
67
82
97
112
127
142
......
25
42
59
76
93
110
127
144
161
......
28
47
66
85
104
123
142
161
180
......
......
......
......
......
......
......
......
......
......
......

 

建立如上表的森德拉姆對稱矩陣 (Matrix):

矩陣第一行為首項 4,公差 3 的算術數列 (Arithmetic Sequence)。

矩陣第二行為首項 7,公差 5 的算術數列。

矩陣第三行為首項 10,公差 7 的算術數列。

這樣下去,下一行的首項是上一行的 +3 ,而公差則是上一行的 +2。

這矩陣奇妙之處在於:如果一自然數 N 在表中某處出現,則 2N+1 不是素數; N 在表中找不到,則 2N+1 是素數。

不妨看看實例吧:表是從 4 開始,略過了 1、2、3,這 2*1+1=3 、2*2+1=5 和 2*3+1=7 都是素數。

 

現已證明,這篩子是可信的,不會有反例  (Counterexample)。

原因很簡單,我們不難發現,表中第一行所有數字均屬 3k+1 類,而表中第二行所有數字均屬 5k+2 類,表中第二行所有數字均屬 7k+3 類:如此類推,表中第 n 行的所有數字均屬 (2n+1) * k + n 類別。當然,這些算術級數亦包括所有比 (2n+1) 大的數值。那麼,把屬於第一行的數字乘 2 加 1 以後便是 3 的倍數,把屬於第二行的數字乘 2 加 1 以後便是 5 的倍數,把屬於第三行的數字乘 2 加 1 以後便是 7 的倍數,把第 n 行的數字乘 2 加 1 以後便是 (2n+1) 的倍數。試想像一數不在表中出現是什麼意思,即它的「兩倍添一」是一奇數,但不是任何比它一半少的奇數的倍數:這樣的奇數不是素數才怪。

雖云森德拉姆篩法可信,但使用時不見得比埃拉托斯特尼篩法 (Sieve of Eratosthenes) 方便。而森德拉姆篩法不會把所有素數列出,這和埃拉托斯特尼篩法沒有遺漏的把所有素數找出來不同:例如惟一的偶素數 2 ,在森德拉姆的篩法下便無法找到了。