2004-3-8 23:12
全世界的计算机联合起来！--- 十万美元的悬赏(zt)
文章来源: abc1230 于 2004-03-08 02:18:05
一、价值五万美元的素数
2000年4月6日，住在美国密歇根州普利茅茨的那扬·哈吉拉特瓦拉(Nayan Hajratwala)先生得到了一笔五万美元的数学奖金，因为他找到了迄今为止已知的最大素数，这是一个梅森素数：
26972593-1。
这也是我们知道的第一个位数超过一百万位的素数。精确地讲，如果把这个素数写成我们熟悉的十进制形式的话，它共有两百零九万八千九百六十位数字，如果把它以这个形式写下来，大约需要150到200篇本文的篇幅。
可是哈吉拉特瓦拉先生并不是一个数学家，他甚至很可能对寻找素数的数学理论一无所知——虽然这使他赢得了这笔奖金。他所做的一切，就是从互联网上下载了一个程序。这个程序在他不使用他的奔腾II350型计算机时悄悄地运行。在经过111天的计算后，上面所说的这个素数被发现了。
二、梅森素数
我们把一个大于1的自然数叫作素数，如果只有1和它本身可以整除它。如果一个比1大的自然数不是素数，我们就叫它合数。1既不是素数，也不是合数。
比如说，你很容易就可以验证7是一个素数；而15是一个合数，因为除了1和15外，3和5都可以整除15。根据定义，2是一个素数，它是唯一的偶素数。早在公元前三百年的古希腊时代，伟大的数学家欧几里德就证明了存在着无穷多个素数。
关于素数，有许多既简单又美丽，但是极为困难的，到现在还没有答案的问题。其中有著名的哥德巴赫猜想，它是说任何一个大于6的偶数，都能表示为两个奇素数之和。还有孪生素数问题。象5和7，41和43这样相差2的素数对，被称为孪生素数。孪生素数问题是说：是不是有无穷多对孪生素数？这里要顺便提一下的是，这些看起来很简单的数学问题，它们的解决方法将一定是极其复杂的，需要最先进的数学工具。如果你不是狂妄到认为几百甚至几千年来所有在这些问题上耗费了无数聪明才智的数学家（有许多是非常伟大的）和数学爱好者加起来都不如你聪明，就不要试图用初等方法去解决这些问题，徒费时间和精力。
古希腊人还对另一种数感兴趣。他们将它称为完美数。一个大于1的自然数叫完美数，如果它的所有因子（包括1，但不包括本身）之和等于它本身。比如说6=1+2+3就是最小的完美数，古希腊人把它看作维纳斯也就是爱情的象征。28=1+2+4+7+14是另一个完美数。欧几里德证明了：一个偶数是完美数，当且仅当它具有如下形式：
2p-1（2p-1）
其中2p-1是素数。上面的6和28对应着p=2和3的情况。我们只要找到了一个形如2p-1的素数，也就知道了一个偶完美数；我们只要找到所有形如2p-1的素数，也就找到了所有偶完美数。所以哈吉拉特瓦拉先生不但找到了世界上已知的最大的素数，还找到了世界上已知的最大的偶完美数。嗯，你要问，关于奇完美数又是怎么样的情况？回答是：我们现在连一个奇完美数也没有找到过，我们甚至根本不知道是不是有奇完美数存在。我们只知道，要是有奇完美数存在的话，它一定是非常非常大的！奇完美数是否存在这个问题，也是一个上面所说的既简单又美丽，但是极为困难的著名数学问题。
有很长一段时间人们以为对于所有素数p，
M_p=2p-1
都是素数（注意到要使2p-1是一个素数，p本身必须是一个素数，想一想为什么？）但是在1536年雷吉乌斯(Hudalricus Regius)指出，M_11=211-1=2047=23*89不是素数。
皮特罗·卡塔尔迪(Pietro Cataldi)首先对这类数进行了系统的研究。他在1603年宣布的结果中说，对于p=17，19，23，29，31和37，2p-1是素数。但是1640年费尔马使用著名的费尔马小定理（不要和那个费尔马大定理混淆起来）证明了卡塔尔迪关于p=23和37的结果是错误的，欧拉在1738年证明了p=29的结果也是错的，过后他又证明了关于p=31的结论是正确的。值得指出的是，卡塔尔迪是用手工一个一个验算取得他的结论的；而费尔马和欧拉则是使用了在他们那时最先进的数学知识，避免了许多复杂的计算和因此可能造成的错误。
法国神父梅森(Marin Mersenne)在1644年他发表了他的成果。他宣称对于p=2，3，5，7，13，17，19，31，67，127和257，2p-1都是素数，而对于其它小于257的素数p，2p-1都是合数。今天我们把形如M_p=2p-1的素数叫做梅森素数，M_p中的M就是梅森姓氏的第一个字母。
用手工来判断一个很大的数是否素数是相当困难的，梅森神父自己也承认他的计算并不一定准确。一直要等到一个世纪以后，在1750年，欧拉宣布说找到了梅森神父的错误：M_41和M_47也是素数。可是伟大如欧拉也会犯计算错误——事实上M_41和M_47都不是素数。不过这可不是说梅森神父的结果就是对的。要等到1883年，也就是梅森神父的结果宣布了两百多年后，第一个错误才被发现：M_61是一个素数。然后其它四个错误也被找了出来：M_67和M_257不是素数，而M_89和M_107是素数。直到1947年，对于p<=257的梅森素数M_p的正确结果才被确定，也就是当p=2，3，5，7，13，17，19，31，61，89，107和127时，M_p是素数。现在这个表已经被反复验证，一定不会有错误了。
下面是我们现在知道的所有梅森素数的列表：（我们注意到梅森神父的名字不在上面——这种素数已经由他的名字命名了，就把荣誉分给最后确认者吧。）
序号 p M_p的位数 相对应的 确认 确认人
完美数的 年代
位数
1 2 1 1 ---- ----
2 3 1 2 ---- ----
3 5 2 3 ---- ----
4 7 3 4 ---- ----
5 13 4 8 1456 佚名
6 17 6 10 1588 Cataldi
7 19 6 12 1588 Cataldi
8 31 10 19 1772 Euler
9 61 19 37 1883 Pervushin
10 89 27 54 1911 Powers
11 107 33 65 1914 Powers
12 127 39 77 1876 Lucas
13 521 157 314 1952 Robinson
14 607 183 366 1952 Robinson
15 1279 386 770 1952 Robinson
16 2203 664 1327 1952 Robinson
17 2281 687 1373 1952 Robinson
18 3217 969 1937 1957 Riesel
19 4253 1281 2561 1961 Hurwitz
20 4423 1332 2663 1961 Hurwitz
21 9689 2917 5834 1963 Gillies
22 9941 2993 5985 1963 Gillies
23 11213 3376 6751 1963 Gillies
24 19937 6002 12003 1971 Tuckerman
25 21701 6533 13066 1978 Noll & Nickel
26 23209 6987 13973 1979 Noll
27 44497 13395 26790 1979 Nelson & Slowinski
28 86243 25962 51924 1982 Slowinski
29 110503 33265 66530 1988 Colquitt & Welsh
30 132049 39751 79502 1983 Slowinski
31 216091 65050 130100 1985 Slowinski
32 756839 227832 455663 1992 Slowinski & Gage
33 859433 258716 517430 1994 Slowinski & Gage
34 1257787 378632 757263 1996 Slowinski & Gage
35 1398269 420921 841842 1996 GIMPS
36 2976221 895932 1791864 1997 GIMPS
37 3021377 909526 1819050 1998 GIMPS
?? 6972593 2098960 4197919 1999 GIMPS
是不是有无穷多个梅森素数呢？数学家们目前还无法回答这个问题。
文章来源: abc1230 于 2004-03-08 02:18:05
一、价值五万美元的素数
2000年4月6日，住在美国密歇根州普利茅茨的那扬·哈吉拉特瓦拉(Nayan Hajratwala)先生得到了一笔五万美元的数学奖金，因为他找到了迄今为止已知的最大素数，这是一个梅森素数：
26972593-1。
这也是我们知道的第一个位数超过一百万位的素数。精确地讲，如果把这个素数写成我们熟悉的十进制形式的话，它共有两百零九万八千九百六十位数字，如果把它以这个形式写下来，大约需要150到200篇本文的篇幅。
可是哈吉拉特瓦拉先生并不是一个数学家，他甚至很可能对寻找素数的数学理论一无所知——虽然这使他赢得了这笔奖金。他所做的一切，就是从互联网上下载了一个程序。这个程序在他不使用他的奔腾II350型计算机时悄悄地运行。在经过111天的计算后，上面所说的这个素数被发现了。
二、梅森素数
我们把一个大于1的自然数叫作素数，如果只有1和它本身可以整除它。如果一个比1大的自然数不是素数，我们就叫它合数。1既不是素数，也不是合数。
比如说，你很容易就可以验证7是一个素数；而15是一个合数，因为除了1和15外，3和5都可以整除15。根据定义，2是一个素数，它是唯一的偶素数。早在公元前三百年的古希腊时代，伟大的数学家欧几里德就证明了存在着无穷多个素数。
关于素数，有许多既简单又美丽，但是极为困难的，到现在还没有答案的问题。其中有著名的哥德巴赫猜想，它是说任何一个大于6的偶数，都能表示为两个奇素数之和。还有孪生素数问题。象5和7，41和43这样相差2的素数对，被称为孪生素数。孪生素数问题是说：是不是有无穷多对孪生素数？这里要顺便提一下的是，这些看起来很简单的数学问题，它们的解决方法将一定是极其复杂的，需要最先进的数学工具。如果你不是狂妄到认为几百甚至几千年来所有在这些问题上耗费了无数聪明才智的数学家（有许多是非常伟大的）和数学爱好者加起来都不如你聪明，就不要试图用初等方法去解决这些问题，徒费时间和精力。
古希腊人还对另一种数感兴趣。他们将它称为完美数。一个大于1的自然数叫完美数，如果它的所有因子（包括1，但不包括本身）之和等于它本身。比如说6=1+2+3就是最小的完美数，古希腊人把它看作维纳斯也就是爱情的象征。28=1+2+4+7+14是另一个完美数。欧几里德证明了：一个偶数是完美数，当且仅当它具有如下形式：
2p-1（2p-1）
其中2p-1是素数。上面的6和28对应着p=2和3的情况。我们只要找到了一个形如2p-1的素数，也就知道了一个偶完美数；我们只要找到所有形如2p-1的素数，也就找到了所有偶完美数。所以哈吉拉特瓦拉先生不但找到了世界上已知的最大的素数，还找到了世界上已知的最大的偶完美数。嗯，你要问，关于奇完美数又是怎么样的情况？回答是：我们现在连一个奇完美数也没有找到过，我们甚至根本不知道是不是有奇完美数存在。我们只知道，要是有奇完美数存在的话，它一定是非常非常大的！奇完美数是否存在这个问题，也是一个上面所说的既简单又美丽，但是极为困难的著名数学问题。
有很长一段时间人们以为对于所有素数p，
M_p=2p-1
都是素数（注意到要使2p-1是一个素数，p本身必须是一个素数，想一想为什么？）但是在1536年雷吉乌斯(Hudalricus Regius)指出，M_11=211-1=2047=23*89不是素数。
皮特罗·卡塔尔迪(Pietro Cataldi)首先对这类数进行了系统的研究。他在1603年宣布的结果中说，对于p=17，19，23，29，31和37，2p-1是素数。但是1640年费尔马使用著名的费尔马小定理（不要和那个费尔马大定理混淆起来）证明了卡塔尔迪关于p=23和37的结果是错误的，欧拉在1738年证明了p=29的结果也是错的，过后他又证明了关于p=31的结论是正确的。值得指出的是，卡塔尔迪是用手工一个一个验算取得他的结论的；而费尔马和欧拉则是使用了在他们那时最先进的数学知识，避免了许多复杂的计算和因此可能造成的错误。
法国神父梅森(Marin Mersenne)在1644年他发表了他的成果。他宣称对于p=2，3，5，7，13，17，19，31，67，127和257，2p-1都是素数，而对于其它小于257的素数p，2p-1都是合数。今天我们把形如M_p=2p-1的素数叫做梅森素数，M_p中的M就是梅森姓氏的第一个字母。
用手工来判断一个很大的数是否素数是相当困难的，梅森神父自己也承认他的计算并不一定准确。一直要等到一个世纪以后，在1750年，欧拉宣布说找到了梅森神父的错误：M_41和M_47也是素数。可是伟大如欧拉也会犯计算错误——事实上M_41和M_47都不是素数。不过这可不是说梅森神父的结果就是对的。要等到1883年，也就是梅森神父的结果宣布了两百多年后，第一个错误才被发现：M_61是一个素数。然后其它四个错误也被找了出来：M_67和M_257不是素数，而M_89和M_107是素数。直到1947年，对于p<=257的梅森素数M_p的正确结果才被确定，也就是当p=2，3，5，7，13，17，19，31，61，89，107和127时，M_p是素数。现在这个表已经被反复验证，一定不会有错误了。
下面是我们现在知道的所有梅森素数的列表：（我们注意到梅森神父的名字不在上面——这种素数已经由他的名字命名了，就把荣誉分给最后确认者吧。）
序号 p M_p的位数 相对应的 确认 确认人
完美数的 年代
位数
1 2 1 1 ---- ----
2 3 1 2 ---- ----
3 5 2 3 ---- ----
4 7 3 4 ---- ----
5 13 4 8 1456 佚名
6 17 6 10 1588 Cataldi
7 19 6 12 1588 Cataldi
8 31 10 19 1772 Euler
9 61 19 37 1883 Pervushin
10 89 27 54 1911 Powers
11 107 33 65 1914 Powers
12 127 39 77 1876 Lucas
13 521 157 314 1952 Robinson
14 607 183 366 1952 Robinson
15 1279 386 770 1952 Robinson
16 2203 664 1327 1952 Robinson
17 2281 687 1373 1952 Robinson
18 3217 969 1937 1957 Riesel
19 4253 1281 2561 1961 Hurwitz
20 4423 1332 2663 1961 Hurwitz
21 9689 2917 5834 1963 Gillies
22 9941 2993 5985 1963 Gillies
23 11213 3376 6751 1963 Gillies
24 19937 6002 12003 1971 Tuckerman
25 21701 6533 13066 1978 Noll & Nickel
26 23209 6987 13973 1979 Noll
27 44497 13395 26790 1979 Nelson & Slowinski
28 86243 25962 51924 1982 Slowinski
29 110503 33265 66530 1988 Colquitt & Welsh
30 132049 39751 79502 1983 Slowinski
31 216091 65050 130100 1985 Slowinski
32 756839 227832 455663 1992 Slowinski & Gage
33 859433 258716 517430 1994 Slowinski & Gage
34 1257787 378632 757263 1996 Slowinski & Gage
35 1398269 420921 841842 1996 GIMPS
36 2976221 895932 1791864 1997 GIMPS
37 3021377 909526 1819050 1998 GIMPS
?? 6972593 2098960 4197919 1999 GIMPS
是不是有无穷多个梅森素数呢？数学家们目前还无法回答这个问题。