[轉貼]辛達拉姆篩法

[轉貼]辛達拉姆篩法

J+W 於 星期三 八月 24, 2005 12:14 pm


令人詫異的是:到目前爲止,“篩法”最好的應是一個印度學生辛達拉姆(Sundaram)於1934年發明的辛達拉姆篩法(詳見李維超著《辛達拉姆篩法的推廣》,《數學通報》2001年第3期,中國數學會、北京師範大學編輯)。辛達拉姆的篩法是:構建數陣——辛達拉姆表。表的第一行和第一列都是首項爲4,公差爲3的等差數列。從第二行開始,以後各行也是等差數列,公差分別爲5,7,9,11,13……。其結論是:若自然數N+出現在數陣勢中,則2n+1不是素數;若自然數N+不出現在數陣中,則2n+1必是素數。數陣通項爲am=(2m+1)n+m,n 爲行數,m爲列數。
辛答拉姆的證明相當精彩。首先,他寫出了第n行的第一個數4+(n-1)×3=3n+1
注意到該行是公差爲2n+1的等差數列,所以此行第m列的數是:
(3n+1)+(m-1)(2n+1)=2(m+1)n+m
現在設N是表中的第n行第m列的數,則N=(2m+1)n+m
於是
2N+1=2[(2m+1)n+m]+1
=(2m+3)(2n+1)
所以是個合數。
再設N不在上表中。要想正面證明2N+1不是質數,是相當困難的。如果換成證明等價的逆否命題,即證“若2N+1不是質數,則N必在表中”似乎要容易得多。事實上,若
2N+1=x·y,(x、y爲整數)
則因2N+1爲奇數,x、y也必爲奇數。不妨設:
x=2p+1;y=2q+1
從而
2N+l=(2p+1)(2q+1)=2p(2q+1)+(2q+1)N是表中第p行第q列的數。
綜合上述,我們證明瞭辛答拉姆篩法的正確性。例如18不在表中,則2×18+1=37是質數。相反,71在表中,則2×71+1=143是合數,它有因數11和13。

J+W
版 主
版 主
 
文章: 2165
註冊時間: 2003-12-30






數學文章