论文部分内容阅读
翻阅日历，品玩数字。灵感，有时就诞生于这无聊，却成就于认真。
众所周知，一个大于1的整数，如果除了它本身和1以外，不能被其他正整数所整除，这个整数就是质数（也称素数），如2，3，5，7，11等都是质数。在自然数列中，因为限定前提和特征的缘故，质数显得稀少且特别。古往今来，许多数学家都致力于寻找质数，其方法可谓多种多样。
“埃拉托斯特尼筛”
公元前3世纪，古希腊学者埃拉托斯特尼提出的著名“筛法”就非常具有代表性。他在一块涂蜡的板上依次写上自然数列的数字，将蜡板固定在一个框上，把其中的1及合数一个个挖去，就得到一个像筛子一样有许多小孔的东西，其中留下的数就是质数，这张数表被称为“埃拉托斯特尼筛”。埃拉托斯特尼是怎样“筛”质数的呢？他的具体做法如下：
把n个自然数按次序排列起来;
1不是质数，也不是合数，要划去;
2是质数，留下来，而把2后面所有2的倍数都划去;
2后面第一个没划去的数是3，把3留下，再把3后面所有3的倍数都划去;
3后面第一个没划去的数是5，把5留下，再把5后面所有5的倍数都划去;
……
这样一直做下去，就会把不超过n的全部合数都筛掉，留下的就是不超过n的全部质数。
例如：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
用“埃拉托斯特尼筛”可以找出不超过30的质数有：2，3，5，7，11，13，17，19，23，29，共10个。
有人统计过：在1到1000之间，有168个质数;在1000到2000之间，有135个质数;在2000到3000之间，有127个质数;而在3000到4000之间，就只有120个质数了。总之，越往后质数就越稀少。这种方法是世界上最古老的求质数的方法。它原理简单，运用起来很方便。现在，凭借经过改进后的“埃拉托斯特尼筛”，数学家们已经把10亿以内的质数都筛出来了。
“辛答拉姆筛法”
4 7 10 13 16 19 …
7 12 17 22 27 32 …
10 17 24 31 38 45 …
13 22 31 40 49 58 …
16 27 38 49 60 71 …
……
1934年，也就是“埃拉托斯特尼筛”问世两千多年后，一位年轻的印度学生辛答拉姆创造了上表，表中数的排列规律是：第一行（最上层横着数）和第一列（最左边竖着数）的数是相同的，在这一行（列）中，从第二个数起，每一個数与前一个数相差3，例如7-4 = 10-7 = 13-10 = 16-13 = … = 3;在第二行（列）中，从第二个数起，每一个数与前一个数相差5;在第三行（列）中，从第二个数起，每一个数与前一个数相差7;在第四行（列）中，从第二个数起，每一个数与前一个数相差9;在第五行（列）中，从第二个数起，每一个数与前一个数相差11。3，5，7，9，11，13……相信你根据这样的规律也能接着写出第六行、第七行……
不过，辛答拉姆的发现远比此深刻，并且其数学意义重大。他从中发现并证实了一个极为奇特有趣的现象：在这个表中，随便找一个自然数M，那么2M+1一定不是质数。
例如：M = 4，2M+1 = 2 × 4+1 = 9，9不是质数;M = 31，2M+1 = 2 × 31+1 = 63，63也不是质数;如此等等。反过来，随便找一个表中没有的自然数M，则2M+1一定是质数。
例如：M = 11，11不在表中，2M+1 = 2 × 11+1 = 23，23的确是质数; M = 23，23不在表中，2M+1 = 2 × 23+1 = 47，47也是质数;如此等等。
辛答拉姆猜想：若自然数M出现在这个表中，则2M+1不是质数;若自然数M不出现在这个表中，则2M+1是质数。辛答拉姆极为精彩地证明了这个猜想。
他写出第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 = 4mn + 2n + 2m + 1 = 2m（2n + 1） + （2n + 1） = （2m+1）（2n+1），显然它是个合数。再设N不在上表中，现在必须2N+1是质数。辛答立姆采用反证法，即证明“若2N+1不是质数，则N必在表中”，这与原命题等价，并且最重要的是证明起来相对要容易得多。事实上，若2N+1不是质数，则有2N + 1 = x·y（x，y为整数），因为2N+1为奇数，则可推知x，y也必为奇数。不妨设x = 2p+1，y = 2q + 1，从而有2N+l = （2p+1）（2q+1），对照上面“N是表中的第n行第m列的数，则2N+1 = （2m+1）（2n+1）”的结论，可确定这里的N表示的是表中第p行第q列的数。由此，人们确信这是寻找质数的又一个独特而有效的方法，它被称为“辛答拉姆筛法”。
这两种“质数筛”都从一个侧面反映出：研究质数在自然数列中的分布一直是数论最重要和最有吸引力的中心问题之一。
众所周知，一个大于1的整数，如果除了它本身和1以外，不能被其他正整数所整除，这个整数就是质数（也称素数），如2，3，5，7，11等都是质数。在自然数列中，因为限定前提和特征的缘故，质数显得稀少且特别。古往今来，许多数学家都致力于寻找质数，其方法可谓多种多样。
“埃拉托斯特尼筛”
公元前3世纪，古希腊学者埃拉托斯特尼提出的著名“筛法”就非常具有代表性。他在一块涂蜡的板上依次写上自然数列的数字，将蜡板固定在一个框上，把其中的1及合数一个个挖去，就得到一个像筛子一样有许多小孔的东西，其中留下的数就是质数，这张数表被称为“埃拉托斯特尼筛”。埃拉托斯特尼是怎样“筛”质数的呢？他的具体做法如下：
把n个自然数按次序排列起来;
1不是质数，也不是合数，要划去;
2是质数，留下来，而把2后面所有2的倍数都划去;
2后面第一个没划去的数是3，把3留下，再把3后面所有3的倍数都划去;
3后面第一个没划去的数是5，把5留下，再把5后面所有5的倍数都划去;
……
这样一直做下去，就会把不超过n的全部合数都筛掉，留下的就是不超过n的全部质数。
例如：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
用“埃拉托斯特尼筛”可以找出不超过30的质数有：2，3，5，7，11，13，17，19，23，29，共10个。
有人统计过：在1到1000之间，有168个质数;在1000到2000之间，有135个质数;在2000到3000之间，有127个质数;而在3000到4000之间，就只有120个质数了。总之，越往后质数就越稀少。这种方法是世界上最古老的求质数的方法。它原理简单，运用起来很方便。现在，凭借经过改进后的“埃拉托斯特尼筛”，数学家们已经把10亿以内的质数都筛出来了。
“辛答拉姆筛法”
4 7 10 13 16 19 …
7 12 17 22 27 32 …
10 17 24 31 38 45 …
13 22 31 40 49 58 …
16 27 38 49 60 71 …
……
1934年，也就是“埃拉托斯特尼筛”问世两千多年后，一位年轻的印度学生辛答拉姆创造了上表，表中数的排列规律是：第一行（最上层横着数）和第一列（最左边竖着数）的数是相同的，在这一行（列）中，从第二个数起，每一個数与前一个数相差3，例如7-4 = 10-7 = 13-10 = 16-13 = … = 3;在第二行（列）中，从第二个数起，每一个数与前一个数相差5;在第三行（列）中，从第二个数起，每一个数与前一个数相差7;在第四行（列）中，从第二个数起，每一个数与前一个数相差9;在第五行（列）中，从第二个数起，每一个数与前一个数相差11。3，5，7，9，11，13……相信你根据这样的规律也能接着写出第六行、第七行……
不过，辛答拉姆的发现远比此深刻，并且其数学意义重大。他从中发现并证实了一个极为奇特有趣的现象：在这个表中，随便找一个自然数M，那么2M+1一定不是质数。
例如：M = 4，2M+1 = 2 × 4+1 = 9，9不是质数;M = 31，2M+1 = 2 × 31+1 = 63，63也不是质数;如此等等。反过来，随便找一个表中没有的自然数M，则2M+1一定是质数。
例如：M = 11，11不在表中，2M+1 = 2 × 11+1 = 23，23的确是质数; M = 23，23不在表中，2M+1 = 2 × 23+1 = 47，47也是质数;如此等等。
辛答拉姆猜想：若自然数M出现在这个表中，则2M+1不是质数;若自然数M不出现在这个表中，则2M+1是质数。辛答拉姆极为精彩地证明了这个猜想。
他写出第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 = 4mn + 2n + 2m + 1 = 2m（2n + 1） + （2n + 1） = （2m+1）（2n+1），显然它是个合数。再设N不在上表中，现在必须2N+1是质数。辛答立姆采用反证法，即证明“若2N+1不是质数，则N必在表中”，这与原命题等价，并且最重要的是证明起来相对要容易得多。事实上，若2N+1不是质数，则有2N + 1 = x·y（x，y为整数），因为2N+1为奇数，则可推知x，y也必为奇数。不妨设x = 2p+1，y = 2q + 1，从而有2N+l = （2p+1）（2q+1），对照上面“N是表中的第n行第m列的数，则2N+1 = （2m+1）（2n+1）”的结论，可确定这里的N表示的是表中第p行第q列的数。由此，人们确信这是寻找质数的又一个独特而有效的方法，它被称为“辛答拉姆筛法”。
这两种“质数筛”都从一个侧面反映出：研究质数在自然数列中的分布一直是数论最重要和最有吸引力的中心问题之一。