【数论的简介】

opaque

【数论的简介】

数论被誉为数学的皇后,他的研究对象是我们大家经常接触的整数的性质,例如求一个数的最大公约数和最小公倍数,
求一个正整数的素因子分解,辗转相除法,求方程的整数解等等各种问题都是数论要研究的东西. 只有1和数本身作为因数的数叫做素数.
例如 2,3,5,7,3021377等等.素数就像整数世界里的原子,整个整数世界都是由这些原子组成的,比如15等于3X5,121等于11X11等等.
  那么素数到底有多少个呢?早在2000多年前的古希腊,欧几里德就用反证法解决了这个问题,
在他的不朽名著<几何原本>的第四卷命题20中是这样叙述的:\"预先给定几个素数,则有比他们更多的素数.\"他是这样证明的:
设a,b,c是给定的素数,构造一个数:t:t=a*b*c+1,则已有的素数a,b,c均不能整除t,所以要么t本身就是素数,此时t不等于a,b,c中任意一个数;
要么他能被不同于a,b,c的某个素数整除,因此必然存在一个素数p不同于已有素数a,b,c.例如:2X3X5+1=31,3X5X7+1=106=2X53.
一般地,有了n个素数,就可以构造出n+1个素数,因此素数有无穷多.
素数的分布也很不均匀,下表是到目前为止所知的小于x的素数的个数pi(x)

            x          pi(x)
----------------------------  -------------------------
            10             4
           100             25
           1,000            168
          10,000            1,229
          100,000            9,592
        1,000,000          78,498
        10,000,000          664,579
        100,000,000         5,761,455
       1,000,000,000         50,847,534
       10,000,000,000         455,052,511
      100,000,000,000        4,118,054,813
      1,000,000,000,000        37,607,912,018
    10,000,000,000,000      346,065,536,839
    100,000,000,000,000      3,204,941,750,802
   1,000,000,000,000,000     29,844,570,422,669
   10,000,000,000,000,000     279,238,341,033,925
   100,000,000,000,000,000    2,623,557,157,654,233
  1,000,000,000,000,000,000    24,739,954,287,740,860
  10,000,000,000,000,000,000    234,057,667,276,344,607
100,000,000,000,000,000,000  2,220,819,602,560,918,840
------------------------------ -----------------------------


【最大的素数】


--------------------------------------------------------------------------------

26972593-1

  这是到目前为止人类所发现的最大素数,它是由纳杨,沃特曼,库洛夫斯基三人在1999年6月1日发现的,这是一个梅森素数,有2098960位数字,是用Primes95这个软件找到的,该软件由沃特曼和库洛夫斯基共同编写的,是一个分布在因特网上的应用软件,现在已经有大约6万人在共同使用这个软件来寻找这种被称为梅森素数的类型的素数.纳扬是这6万人中之一,在1998年1月28日,美国加利福尼亚大学的大学生克拉克也是利用这个软件发现了第37个梅森素数,我现在也参加到这个行列中,现在已经检验完三个指数了,结果都不是素数,每检验一个指数,大约需要60天,当然指数越大时间越长.这个软件的客户端是一个后台运行的程序,只要你一开机,它就自动运行在后台,对于你的正常工作毫不影响.现在这个软件已经到了第9版.有兴趣的可以到如下站点去下载:ftp://entropia.com/gimps/prime95.zip

.下表列出了从1961年以来所发现的全部梅森素数.摘自http://www.utm.edu/research/primes/

序号 素数 位数 发现人 时间 注释
1 26972593-1 2098960 Nayan, Woltman, Kurowski 1999 Mersenne 38
2 23021377-1 909526 Clarkson, Woltman, Kurowski 1998 Mersenne 37
3 22976221-1 895932 Spence, Woltman 1997 Mersenne 36
4 21398269-1 420921 Armengaud, Woltman 1996 Mersenne 35
5 21257787-1 378632 Slowinski & Gage 1996 Mersenne 34
6 2859433-1 258716 Slowinski & Gage 1994 Mersenne 33  
7 2756839-1 227832 Slowinski & Gage 1992 Mersenne 32
8 2216091-1 65050 David Slowinski 1985 Mersenne 31  
9 2132049-1 39751 David Slowinski 1983 Mersenne 30  
10 2110503-1 33265 Welsh & Colquitt 1988 Mersenne 29
11 286243-1 25962 David Slowinski 1982 Mersenne 28
12 244497-1 13395 Slowinski & Nelson 1979 Mersenne 27  
13 223209-1 6987 L. Curt Noll 1979 Mersenne 26  
14 221701-1 6533 Nickel & Noll 1978 Mersenne 25
15 219937-1 6002 Bryant Tuckerman 1971 Mersenne 24
16 211213-1 3376 Donald B. Gillies 1963 Mersenne 23
17 29941-1 2993 Donald B. Gillies 1963 Mersenne 22
18 29689-1 2917 Donald B. Gillies 1963 Mersenne 21
19 24423-1 1332 Alexander Hurwitz 1961 Mersenne 20
20 24253-1 1281 Alexander Hurwitz 1961 Mersenne 19


--------------------------------------------------------------------------------

【最完美的数】


--------------------------------------------------------------------------------

完美数又称为完全数,最初是由毕达哥拉斯(Pythagoras)的信徒发现的,他们注意到,数6有一个特性,它等于它自己的因子(不包括它自身)的和:
      6=1+2+3,下一个具有同样性质的数是28,28=1+2+4+7+14
  接着是496和8128.他们称这类数为完美数.欧几里德在大约公元前350-300年间证明了:若2^n-1是素数,则数2^(n-1)[2^n-1]是完全数.两千年后,欧拉证明每个偶完全数都具有这种形式.这就在完全数与梅森数之间建立了紧密的联系,到1998年1月27日为止,共发现了37个梅森素数,这就是说已发现了37个完全数.
  完全数是非常奇特的数,它们有一些特殊性质,例如每个完全数都是三角形数,即都能写成n(n+1)/2.把它们(6除外)的各位数字相加,直到变成一位数,那么这个一位数一定是1;它们都是连续奇数的立方和(6除外),除了因子1之外,每个完全数的所有因子(包括自身)的到数和等于1,比如:
       1/2+1/3+1/6=1
完全数都是以6或8结尾的,看看它们的二进制表达式吧:
110
11100
111110000
1111111000000
  注意以上谈到的完全数都是偶完全数,至今仍然不知道有没有奇完全数,有人证明如果存在的话,将大于10^100.


注意以上谈到的完全数都是偶完全数,至今仍然不知道有没有奇完全数,有人证明如果存在的话,将大于10^100.


　

　

完全数Pp ##  p Mp的位数 Pp的位数 年代 发现者
6 1 2 1 1 ---- ----
28 2 3 1 2 ---- ----
496 3 5 2 3 ---- ----
8128 4 7 3 4 ---- ----
33550336 5 13 4 8 1456 anonymous
8589869056 6 17 6 10 1588 Cataldi
137438691328 7 19 6 12 1588 Cataldi
2305843008139952128 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

【素数的分类】


--------------------------------------------------------------------------------

素数从理论上来说只能分成两类,即偶素数和奇素数,由于历史和人为习惯的原因, 人们又对素数进行了各种各样的分类,这些分类中最著名的有两种,一种就是前面提到过的梅森素数,另一种是叫做费马素数.其他的类型的素数不太被人们所熟悉,比如普罗斯素数.还有另外一种分类法既是按素数本身的形态来区分的,比如说回文素数,下表列出了最近发现的最大的十个回文素数:

742950290870000078092059247, 742950290871010178092059247,
742950290872020278092059247, 742950290873030378092059247,
742950290874040478092059247, 742950290875050578092059247,
742950290876060678092059247, 742950290877070778092059247,
742950290878080878092059247, 742950290879090978092059247

另一种非常重要的是神秘的素数对,或成为孪生素数,孪生素数是指如果p是素数且p+2也是素数,则称p和p+2为一对孪生素数,比如5,7;11,13等等.下表是目前所发现的最大的前二十个孪生素数:

rank prime digits who when comment
1 361700055.239020±1 11755 Henri Lifchitz 1999 Twin
2 835335.239014±1 11751 Ballinger & Gallot 1998 Twin
3 242206083.238880±1 11713 Jarai & Indlekofer 1995 Twin
4 40883037.223456±1 7069 Lifchitz & Gallot 1998 Twin
5 843753.222222±1 6696 Rivera & Gallot 1997 Twin
6 7485.220023±1 6032 Buddenhagen & Gallot 1998 Twin
7 8182815.217838±1 5377 Smith & Gallot 1998 Twin
8 570918348.105120±1 5129 Harvey Dubner 1995 Twin [Ribenboim95, p263]
9 22687485.216557±1 4992 Hanson & Gallot 1999 twin
10 697053813.216352±1 4932 Jarai & Indlekofer 1995 Twin [IJ96]
11 37442007.215440±1 4656 Hanson & Gallot 1999 Twin
12 6797727.215328±1 4622 Tony Forbes 1995 Twin [Forbes97]
13 1692923232.104020±1 4030 Harvey Dubner 1993 Twin [Peterson93]
14 3981.213153±1 3964 Walker & Gallot 1999 Twin
15 245630385.212937±1 3903 Brennen & Gallot 1998 Twin
16 915.211455±1 3452 Ballinger & Gallot 1998 Twin
17 4655478828.103429±1 3439 Harvey Dubner 1993 Twin [IJ96]
18 1706595.211235±1 3389 Brown, Noll, Parady, Smith_G, Smith_J & Zarantonello 1989 Twin [PSZ90]
19 10941.210601±1 3196 Hanson & Gallot 1998 Twin
20 12110457.210006±1 3020 Lifchitz & Gallot 1998 Twin

【因数的分解】


--------------------------------------------------------------------------------

  数的素性检验方法问题在近几年得到了飞速的发展,过去,要检验一个数 n 是否是素数,最简单的方法是用试除法,用小于n的平方根以下的所有素数去除n,若都除不尽,则n就是素数,否则为合数.这对于比较小的数来说还适用,若用计算机编成程序,对于10位数,几乎瞬间即可完成,对于一个20位数,则需要2个小时,对于一个50位数就需要一百亿年,令人吃惊的是,要检验一个一百位数,需要的时间就猛增到10^36年.到了1980年,这种困难的情况得到了改观,阿德曼(Adleman),鲁梅利(Rumely),科恩(Cohen),和伦斯特拉(Lenstra)研究出一种非常复杂的技巧,现在以他们的名字的首字母命名的ARCL检验法,检验一个20位数只消10秒钟,对于一个50位数用15秒钟,100位数用40秒钟,如果要他检验一个1000位数,只要用一个星期也就够了.但是大部分的素性检验法都不能分解出因数来,只能回答一个数是否是素数.
  那么,如何去找合数的因子呢?试除法显然不适用于大数的因数分解,但实际上,目前所有用于素性检验和因数分解的方法中又都少不了试除法.一般在开始时它的运算并不慢,比如先用前一百万个素数去试除,如果找到一个因数,那么素性和因数分解问题就都解决了.若未找到,这时他如果是合数,就只有极大的因数,费马曾经找到了一种极其简单的对付这种情况的方法,以下就是这种方法的简单说明:
  设n=uv,u和v都是大的奇数,不妨设u<=v令x=(u+v)/2,y=(v-u)/2.于是,0<=y<x<=n,且v=x+y,u=x-y故n=uv=(x+y)(x-y)=x*x-y*y或者    y*y=x*x-n,若能找到两个数x,y满足前式,则 n=(x+y)(x-y),即得出了n 的因数分解.费马本人就是用此方法找到了2027651281=44021X46061.可以这样进行,找出k>=√n 然后从x=k 开始,依次检验x=k+1,x=k+2...这些数是否能使x*x-n成为平方数,一旦找到这样的x,当然分解工作就完成了.倘若n有两个大小相近的因数,则其中之一能很快找到.你可以用此方法试着分解一下10379.另外,在判断x*x-n是否是平方数时,可以排除个位数是2,3,7,8的情况,因为没有一个平方数是以2,3,7,8结尾的.


　

　


--------------------------------------------------------------------------------

【最大的数表】


--------------------------------------------------------------------------------

  自然数列:1,2,3,....可以按他们各自的素因子的多少而分成两大类,除1以外,若某个自然数的素因子只有1和其自身,则称其为素数,否则成为合数.因此,按这种性质,自然数只有两种状态,要么是素数,要么是合数,如果用0代表素数,用1代表合数,那么整个自然数列将被替换成:
  1,2,3,4,5,6,7,8,9,...
  1,0,0,1,0,1,0,1,1,...
  将此0,1序列每八位组成一个字节,在限定的范围内,做成一个&#39;素数库&#39;,这就是我长期以来所要完成的目标.
  但是,我们看到,以上序列中包含了所有的偶数,我们知道,除了2以外,所有的偶数都是合数,因此没有必要保存他们,将他们通通都划掉,而且由于2是已经知道的素数,也不必保存他,则剩下的只是奇数了,显然也包含了所有的奇素数,该数列的通项公式为:
            P=2N+1 (N=0,1,2,3,...)
            N=(P-1)/2
  在这里,P将被称为预选数,其中既有素数,也有合数,N称为数P的序号.现在我们正在逐步缩小包围圈,从自然数范围缩小到奇数范围,我们还能进一步缩小包围圈吗?答案是肯定的.为了更好的理解,我们需要引入数论中的一个概念,即剩余类的概念.任给一个自然数K,则所有自然数除以K所得余数只能是:
          0,1,2,3,....K-1
这K种类型,即所有自然数可以分成K类:
          KN+0,KN+1,KN+2,...KN+(K-1)
这K种类型的数系被称为数K的剩余系,前面我们已经讨论过的就是2的剩余系:
          2N,2N+1
我们保留了其中的一类2N+1,将此数列用0或1按是否素数一一替换,即可做成一个以2为基的&#39;素数库&#39;,要从库中检索某个数是否是素数,只要看看库中的第N位是否是0即可.
  要想继续缩小包围圈,大家可以猜到下一步将要划去3的倍数,这样也将6的倍数划去了,因此我们进一步考虑的是6的剩余系:
          6N,6N+1,6N+2,6N+3,6N+4,6N+5
其中只有6N+1,6N+5才包含了大于3的所有素数,其他的4类显然都是合数,我们将6N+1,6N+5保留下来,并统一成如下的一对公式:
          P=3N+5-(N mod 2) (N=0,1,2,3,...)
          N=[14P-15-(P mod 6)]/12
  利用这一对公式可以造出一个素数库,显然这个库所存储的数只占自然数的三分之一,这就是以6为基的&#39;素数库&#39;.在进一步将要划去5的倍数,也将2X3X5=30的倍数划去了,因此下一步是以30为基的&#39;素数库&#39;,只剩下如下八种剩余类:
          30N+1,30N+7,30N+11,30N+13,30N+17,30N+19,30N+23,30N+29
  也可以统一成如下的一对公式:
          P=30XINT(N/8)+U(N mod 8)  (N=0,1,2,3,....)
          N=8XINT(P/30)+V(P mod 30)
  其中U(0)=1,U(1)=7,U(2)=11,U(3)=13,U(4)=17,U(5)=19,U(6)=23,U(7)=29
   V(1)=0,V(7)=1,V(11)=2,V(13)=3,V(17)=4,V(19)=5,V(23)=6,V(29)=7
  用这个公式编制一个&#39;素数库&#39;,所保存的数只占自然数的十五分之四,我目前所使用的就是这个公式,已经做好的最大的素数库有640M字节,他把200亿以下的所有素数全部存储进去了.下一步将要做一个3200M字节的素数库,这个素数库可以把一千亿以下的所有素数存储进去.如果继续缩小包围圈,那将是以2X3X5X7=210为基,它将剩下48个有用的剩余类,所保存的数只占自然数的三十五分之八,再下去就是以 2X3X5X7X11=2310为基,它有480个有用的剩余类,一般地,当基B=2X3X5X7...XP 时,有用的剩余类(简化剩余类)实际上就等于B的欧拉函数的值,所谓的欧拉函数φ(B)是指小于B且与B互素的数的个数.存储效率即指φ(B)/B,下表所列的就是我所做的素数库的前八个字节的内容:

字节地址 字位序号 0 1 2 3 4 5 6 7 保存的数
0 0 1 7 11 13 17 19 23 29 01H
1 8 31 37 41 43 47 49 53 59 20H
2 16 61 67 71 73 77 79 83 89 10H
3 24 91 97 101 103 107 109 113 119 81H
4 32 121 127 131 133 137 139 143 149 49H
5 40 151 157 161 163 167 169 173 179 24H
6 48 181 187 191 193 197 199 203 209 C2H
7 56 211 217 221 223 227 229 233 239 06H
一.柯召素数问题

有一些素数的数字之和仍为素数,例如11,23,29,47,67等等.由于这种素数首先有我国四川大学的柯召教授研究过,不妨称之为柯召素数.请问柯召素数是否有无限多个?


--------------------------------------------------------------------------------

二.分解2101-1

人们早就知道2101-1是由两个素数的积组成的,但是至今还没有人能够分解出这两个素数来,你能做到吗?

  这个难题现在已经由陈研用Mathematic4在很短的时间内解决了:
2101-1=7432339208719 * 341117531003194129=2,535,301,200,456,456,458,802,993,406,410,751
我用 factor.exe 验证了右边那个31位数,确实是合数,并且是前面那两个素数的乘积,感谢陈研的工作.


--------------------------------------------------------------------------------

三.回归数

有许多数具有这样一种有趣的性质:它的十进制表示的各位数字,按照原来的顺序进行某种数学运算,又可以重新得到该数,这就是回归数,例如:

24=23+42 2427=21+42+23+74  81=(8+1)2 145=1!+4!+5!

英国数学家哈代(G.H.Hardy 1877-1947)曾经发现过另一种形式的回归数:

153=13+53+33 371=33+73+13  370=33+73+03 407=43+03+73

他们都是三位数且等于各位数字的三次幂之和,这种巧合不能不令人感到惊讶.更为称奇的是,一位读者看过哈代的有趣发现后,竟然构造出其值等于各位数字四(五,六)次幂之和的四(五,六)位数:

1634=14+64+34+44 54748=55+45+75+45+85  548834=56+46+86+86+36+46

像这种其值等于各位数字的 n 次幂之和的 n 位数,称为 n 位 n 次幂回归数.本文只讨论这种回归数,故简称为回归数,人们自然要问:对于什么样的自然数 n 有回归数?这样的 n 是有限个还是无穷多个?对于已经给定的 n ,如果有回归数,那么有多少个回归数?
1986年美国的一位数学教师安东尼.迪拉那(Anthony Diluna)巧妙地证明了使 n 位数成为回归数的 n 只有有限个.
设 An 是这样的回归数,即:

  An=a1a2a3...an=a1n+a2n+...+ann (其中 0<=a1,a2,...an<=9)

  从而 10n-1<=An<=n9n 即 n 必须满足 n9n>10n-1 也就是 (10/9)n<10n    ⑴

  随着自然数 n 的不断增大,(10/9)n 值的增加越来越快,很快就会使得 ⑴ 式不成立,因此,满足⑴的 n 不能无限增大,即 n 只能取有限多个.进一步的计算表明:

  (10/9)60=556.4798...<10*60=600    (10/9)61=618.3109...>10*61=610

  对于 n>=61,便有 (10/9)n>10n

由此可知,使⑴式成立的自然数 n<=60.故这种回归数最多是60位数.迪拉那说,他的学生们早在1975年借助于哥伦比亚大学的计算机得到下列回归数:

  一位回归数:1,2,3,4,5,6,7,8,9
  二位回归数:不存在
  三位回归数:153,370,371,407
  四位回归数:1634,8208,9474
  五位回归数:54748,92727,93084
  六位回归数:548834
  七位回归数:1741725,4210818,9800817
  八位回归数:24678050,24678051
但是此后对于哪一个自然数 n (<=60)还有回归数?对于已经给定的 n ,能有多少个回归数?最大的回归数是多少?


--------------------------------------------------------------------------------

三.我的关于数学黑洞的猜想:数学黑洞是指自然数经过某种数学运算之后陷入了一种循环的境况.例如,自然数的数字的平方和会陷入两个死循环:1和4.自然数的数字的立方和会陷入几组死循环:
  1;
  37,73,307,370,703,730;
  47,74,407,470,704,740;
  153,135,315,351,513,531;
  137,173,317,371,713,731;
  55,250,133;
136,244
  160,217,352;
  919,1459;
  自然数的数字四次方和有多少组死循环?
  自然数的数字五次方和有多少组死循环?
  ......


--------------------------------------------------------------------------------

四.不定方程:X2+Y3=Z3非常有意思,我求出了它的两种类型的解:
    X=(a√a)*S2K/2    (a>=0 k=0,1,2,...)
    Y=a*(T2k-1)/2
    Z=a*(T2k+1)/2
  其中:S0=2,T0=1,Sn+1=2Sn+3Tn,Tn+1=Sn+2Tn
  另一种解为:
    X=m3(S3-1)2    (m>=0 S=0,1,2...)
    Y=m2(S3-1)
    Z=m2S(S3-1)
  谁能找到全部解,你能帮我解决吗?

opaque

【数论的简介】

数论被誉为数学的皇后,他的研究对象是我们大家经常接触的整数的性质,例如求一个数的最大公约数和最小公倍数,
求一个正整数的素因子分解,辗转相除法,求方程的整数解等等各种问题都是数论要研究的东西. 只有1和数本身作为因数的数叫做素数.
例如 2,3,5,7,3021377等等.素数就像整数世界里的原子,整个整数世界都是由这些原子组成的,比如15等于3X5,121等于11X11等等.
  那么素数到底有多少个呢?早在2000多年前的古希腊,欧几里德就用反证法解决了这个问题,
在他的不朽名著<几何原本>的第四卷命题20中是这样叙述的:\"预先给定几个素数,则有比他们更多的素数.\"他是这样证明的:
设a,b,c是给定的素数,构造一个数:t:t=a*b*c+1,则已有的素数a,b,c均不能整除t,所以要么t本身就是素数,此时t不等于a,b,c中任意一个数;
要么他能被不同于a,b,c的某个素数整除,因此必然存在一个素数p不同于已有素数a,b,c.例如:2X3X5+1=31,3X5X7+1=106=2X53.
一般地,有了n个素数,就可以构造出n+1个素数,因此素数有无穷多.
素数的分布也很不均匀,下表是到目前为止所知的小于x的素数的个数pi(x)

            x          pi(x)
----------------------------  -------------------------
            10             4
           100             25
           1,000            168
          10,000            1,229
          100,000            9,592
        1,000,000          78,498
        10,000,000          664,579
        100,000,000         5,761,455
       1,000,000,000         50,847,534
       10,000,000,000         455,052,511
      100,000,000,000        4,118,054,813
      1,000,000,000,000        37,607,912,018
    10,000,000,000,000      346,065,536,839
    100,000,000,000,000      3,204,941,750,802
   1,000,000,000,000,000     29,844,570,422,669
   10,000,000,000,000,000     279,238,341,033,925
   100,000,000,000,000,000    2,623,557,157,654,233
  1,000,000,000,000,000,000    24,739,954,287,740,860
  10,000,000,000,000,000,000    234,057,667,276,344,607
100,000,000,000,000,000,000  2,220,819,602,560,918,840
------------------------------ -----------------------------


【最大的素数】


--------------------------------------------------------------------------------

26972593-1

  这是到目前为止人类所发现的最大素数,它是由纳杨,沃特曼,库洛夫斯基三人在1999年6月1日发现的,这是一个梅森素数,有2098960位数字,是用Primes95这个软件找到的,该软件由沃特曼和库洛夫斯基共同编写的,是一个分布在因特网上的应用软件,现在已经有大约6万人在共同使用这个软件来寻找这种被称为梅森素数的类型的素数.纳扬是这6万人中之一,在1998年1月28日,美国加利福尼亚大学的大学生克拉克也是利用这个软件发现了第37个梅森素数,我现在也参加到这个行列中,现在已经检验完三个指数了,结果都不是素数,每检验一个指数,大约需要60天,当然指数越大时间越长.这个软件的客户端是一个后台运行的程序,只要你一开机,它就自动运行在后台,对于你的正常工作毫不影响.现在这个软件已经到了第9版.有兴趣的可以到如下站点去下载:ftp://entropia.com/gimps/prime95.zip

.下表列出了从1961年以来所发现的全部梅森素数.摘自http://www.utm.edu/research/primes/

序号 素数 位数 发现人 时间 注释
1 26972593-1 2098960 Nayan, Woltman, Kurowski 1999 Mersenne 38
2 23021377-1 909526 Clarkson, Woltman, Kurowski 1998 Mersenne 37
3 22976221-1 895932 Spence, Woltman 1997 Mersenne 36
4 21398269-1 420921 Armengaud, Woltman 1996 Mersenne 35
5 21257787-1 378632 Slowinski & Gage 1996 Mersenne 34
6 2859433-1 258716 Slowinski & Gage 1994 Mersenne 33  
7 2756839-1 227832 Slowinski & Gage 1992 Mersenne 32
8 2216091-1 65050 David Slowinski 1985 Mersenne 31  
9 2132049-1 39751 David Slowinski 1983 Mersenne 30  
10 2110503-1 33265 Welsh & Colquitt 1988 Mersenne 29
11 286243-1 25962 David Slowinski 1982 Mersenne 28
12 244497-1 13395 Slowinski & Nelson 1979 Mersenne 27  
13 223209-1 6987 L. Curt Noll 1979 Mersenne 26  
14 221701-1 6533 Nickel & Noll 1978 Mersenne 25
15 219937-1 6002 Bryant Tuckerman 1971 Mersenne 24
16 211213-1 3376 Donald B. Gillies 1963 Mersenne 23
17 29941-1 2993 Donald B. Gillies 1963 Mersenne 22
18 29689-1 2917 Donald B. Gillies 1963 Mersenne 21
19 24423-1 1332 Alexander Hurwitz 1961 Mersenne 20
20 24253-1 1281 Alexander Hurwitz 1961 Mersenne 19


--------------------------------------------------------------------------------

【最完美的数】


--------------------------------------------------------------------------------

完美数又称为完全数,最初是由毕达哥拉斯(Pythagoras)的信徒发现的,他们注意到,数6有一个特性,它等于它自己的因子(不包括它自身)的和:
      6=1+2+3,下一个具有同样性质的数是28,28=1+2+4+7+14
  接着是496和8128.他们称这类数为完美数.欧几里德在大约公元前350-300年间证明了:若2^n-1是素数,则数2^(n-1)[2^n-1]是完全数.两千年后,欧拉证明每个偶完全数都具有这种形式.这就在完全数与梅森数之间建立了紧密的联系,到1998年1月27日为止,共发现了37个梅森素数,这就是说已发现了37个完全数.
  完全数是非常奇特的数,它们有一些特殊性质,例如每个完全数都是三角形数,即都能写成n(n+1)/2.把它们(6除外)的各位数字相加,直到变成一位数,那么这个一位数一定是1;它们都是连续奇数的立方和(6除外),除了因子1之外,每个完全数的所有因子(包括自身)的到数和等于1,比如:
       1/2+1/3+1/6=1
完全数都是以6或8结尾的,看看它们的二进制表达式吧:
110
11100
111110000
1111111000000
  注意以上谈到的完全数都是偶完全数,至今仍然不知道有没有奇完全数,有人证明如果存在的话,将大于10^100.


注意以上谈到的完全数都是偶完全数,至今仍然不知道有没有奇完全数,有人证明如果存在的话,将大于10^100.


　

　

完全数Pp ##  p Mp的位数 Pp的位数 年代 发现者
6 1 2 1 1 ---- ----
28 2 3 1 2 ---- ----
496 3 5 2 3 ---- ----
8128 4 7 3 4 ---- ----
33550336 5 13 4 8 1456 anonymous
8589869056 6 17 6 10 1588 Cataldi
137438691328 7 19 6 12 1588 Cataldi
2305843008139952128 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

【素数的分类】


--------------------------------------------------------------------------------

素数从理论上来说只能分成两类,即偶素数和奇素数,由于历史和人为习惯的原因, 人们又对素数进行了各种各样的分类,这些分类中最著名的有两种,一种就是前面提到过的梅森素数,另一种是叫做费马素数.其他的类型的素数不太被人们所熟悉,比如普罗斯素数.还有另外一种分类法既是按素数本身的形态来区分的,比如说回文素数,下表列出了最近发现的最大的十个回文素数:

742950290870000078092059247, 742950290871010178092059247,
742950290872020278092059247, 742950290873030378092059247,
742950290874040478092059247, 742950290875050578092059247,
742950290876060678092059247, 742950290877070778092059247,
742950290878080878092059247, 742950290879090978092059247

另一种非常重要的是神秘的素数对,或成为孪生素数,孪生素数是指如果p是素数且p+2也是素数,则称p和p+2为一对孪生素数,比如5,7;11,13等等.下表是目前所发现的最大的前二十个孪生素数:

rank prime digits who when comment
1 361700055.239020±1 11755 Henri Lifchitz 1999 Twin
2 835335.239014±1 11751 Ballinger & Gallot 1998 Twin
3 242206083.238880±1 11713 Jarai & Indlekofer 1995 Twin
4 40883037.223456±1 7069 Lifchitz & Gallot 1998 Twin
5 843753.222222±1 6696 Rivera & Gallot 1997 Twin
6 7485.220023±1 6032 Buddenhagen & Gallot 1998 Twin
7 8182815.217838±1 5377 Smith & Gallot 1998 Twin
8 570918348.105120±1 5129 Harvey Dubner 1995 Twin [Ribenboim95, p263]
9 22687485.216557±1 4992 Hanson & Gallot 1999 twin
10 697053813.216352±1 4932 Jarai & Indlekofer 1995 Twin [IJ96]
11 37442007.215440±1 4656 Hanson & Gallot 1999 Twin
12 6797727.215328±1 4622 Tony Forbes 1995 Twin [Forbes97]
13 1692923232.104020±1 4030 Harvey Dubner 1993 Twin [Peterson93]
14 3981.213153±1 3964 Walker & Gallot 1999 Twin
15 245630385.212937±1 3903 Brennen & Gallot 1998 Twin
16 915.211455±1 3452 Ballinger & Gallot 1998 Twin
17 4655478828.103429±1 3439 Harvey Dubner 1993 Twin [IJ96]
18 1706595.211235±1 3389 Brown, Noll, Parady, Smith_G, Smith_J & Zarantonello 1989 Twin [PSZ90]
19 10941.210601±1 3196 Hanson & Gallot 1998 Twin
20 12110457.210006±1 3020 Lifchitz & Gallot 1998 Twin

【因数的分解】


--------------------------------------------------------------------------------

  数的素性检验方法问题在近几年得到了飞速的发展,过去,要检验一个数 n 是否是素数,最简单的方法是用试除法,用小于n的平方根以下的所有素数去除n,若都除不尽,则n就是素数,否则为合数.这对于比较小的数来说还适用,若用计算机编成程序,对于10位数,几乎瞬间即可完成,对于一个20位数,则需要2个小时,对于一个50位数就需要一百亿年,令人吃惊的是,要检验一个一百位数,需要的时间就猛增到10^36年.到了1980年,这种困难的情况得到了改观,阿德曼(Adleman),鲁梅利(Rumely),科恩(Cohen),和伦斯特拉(Lenstra)研究出一种非常复杂的技巧,现在以他们的名字的首字母命名的ARCL检验法,检验一个20位数只消10秒钟,对于一个50位数用15秒钟,100位数用40秒钟,如果要他检验一个1000位数,只要用一个星期也就够了.但是大部分的素性检验法都不能分解出因数来,只能回答一个数是否是素数.
  那么,如何去找合数的因子呢?试除法显然不适用于大数的因数分解,但实际上,目前所有用于素性检验和因数分解的方法中又都少不了试除法.一般在开始时它的运算并不慢,比如先用前一百万个素数去试除,如果找到一个因数,那么素性和因数分解问题就都解决了.若未找到,这时他如果是合数,就只有极大的因数,费马曾经找到了一种极其简单的对付这种情况的方法,以下就是这种方法的简单说明:
  设n=uv,u和v都是大的奇数,不妨设u<=v令x=(u+v)/2,y=(v-u)/2.于是,0<=y<x<=n,且v=x+y,u=x-y故n=uv=(x+y)(x-y)=x*x-y*y或者    y*y=x*x-n,若能找到两个数x,y满足前式,则 n=(x+y)(x-y),即得出了n 的因数分解.费马本人就是用此方法找到了2027651281=44021X46061.可以这样进行,找出k>=√n 然后从x=k 开始,依次检验x=k+1,x=k+2...这些数是否能使x*x-n成为平方数,一旦找到这样的x,当然分解工作就完成了.倘若n有两个大小相近的因数,则其中之一能很快找到.你可以用此方法试着分解一下10379.另外,在判断x*x-n是否是平方数时,可以排除个位数是2,3,7,8的情况,因为没有一个平方数是以2,3,7,8结尾的.


　

　


--------------------------------------------------------------------------------

【最大的数表】


--------------------------------------------------------------------------------

  自然数列:1,2,3,....可以按他们各自的素因子的多少而分成两大类,除1以外,若某个自然数的素因子只有1和其自身,则称其为素数,否则成为合数.因此,按这种性质,自然数只有两种状态,要么是素数,要么是合数,如果用0代表素数,用1代表合数,那么整个自然数列将被替换成:
  1,2,3,4,5,6,7,8,9,...
  1,0,0,1,0,1,0,1,1,...
  将此0,1序列每八位组成一个字节,在限定的范围内,做成一个&#39;素数库&#39;,这就是我长期以来所要完成的目标.
  但是,我们看到,以上序列中包含了所有的偶数,我们知道,除了2以外,所有的偶数都是合数,因此没有必要保存他们,将他们通通都划掉,而且由于2是已经知道的素数,也不必保存他,则剩下的只是奇数了,显然也包含了所有的奇素数,该数列的通项公式为:
            P=2N+1 (N=0,1,2,3,...)
            N=(P-1)/2
  在这里,P将被称为预选数,其中既有素数,也有合数,N称为数P的序号.现在我们正在逐步缩小包围圈,从自然数范围缩小到奇数范围,我们还能进一步缩小包围圈吗?答案是肯定的.为了更好的理解,我们需要引入数论中的一个概念,即剩余类的概念.任给一个自然数K,则所有自然数除以K所得余数只能是:
          0,1,2,3,....K-1
这K种类型,即所有自然数可以分成K类:
          KN+0,KN+1,KN+2,...KN+(K-1)
这K种类型的数系被称为数K的剩余系,前面我们已经讨论过的就是2的剩余系:
          2N,2N+1
我们保留了其中的一类2N+1,将此数列用0或1按是否素数一一替换,即可做成一个以2为基的&#39;素数库&#39;,要从库中检索某个数是否是素数,只要看看库中的第N位是否是0即可.
  要想继续缩小包围圈,大家可以猜到下一步将要划去3的倍数,这样也将6的倍数划去了,因此我们进一步考虑的是6的剩余系:
          6N,6N+1,6N+2,6N+3,6N+4,6N+5
其中只有6N+1,6N+5才包含了大于3的所有素数,其他的4类显然都是合数,我们将6N+1,6N+5保留下来,并统一成如下的一对公式:
          P=3N+5-(N mod 2) (N=0,1,2,3,...)
          N=[14P-15-(P mod 6)]/12
  利用这一对公式可以造出一个素数库,显然这个库所存储的数只占自然数的三分之一,这就是以6为基的&#39;素数库&#39;.在进一步将要划去5的倍数,也将2X3X5=30的倍数划去了,因此下一步是以30为基的&#39;素数库&#39;,只剩下如下八种剩余类:
          30N+1,30N+7,30N+11,30N+13,30N+17,30N+19,30N+23,30N+29
  也可以统一成如下的一对公式:
          P=30XINT(N/8)+U(N mod 8)  (N=0,1,2,3,....)
          N=8XINT(P/30)+V(P mod 30)
  其中U(0)=1,U(1)=7,U(2)=11,U(3)=13,U(4)=17,U(5)=19,U(6)=23,U(7)=29
   V(1)=0,V(7)=1,V(11)=2,V(13)=3,V(17)=4,V(19)=5,V(23)=6,V(29)=7
  用这个公式编制一个&#39;素数库&#39;,所保存的数只占自然数的十五分之四,我目前所使用的就是这个公式,已经做好的最大的素数库有640M字节,他把200亿以下的所有素数全部存储进去了.下一步将要做一个3200M字节的素数库,这个素数库可以把一千亿以下的所有素数存储进去.如果继续缩小包围圈,那将是以2X3X5X7=210为基,它将剩下48个有用的剩余类,所保存的数只占自然数的三十五分之八,再下去就是以 2X3X5X7X11=2310为基,它有480个有用的剩余类,一般地,当基B=2X3X5X7...XP 时,有用的剩余类(简化剩余类)实际上就等于B的欧拉函数的值,所谓的欧拉函数φ(B)是指小于B且与B互素的数的个数.存储效率即指φ(B)/B,下表所列的就是我所做的素数库的前八个字节的内容:

字节地址 字位序号 0 1 2 3 4 5 6 7 保存的数
0 0 1 7 11 13 17 19 23 29 01H
1 8 31 37 41 43 47 49 53 59 20H
2 16 61 67 71 73 77 79 83 89 10H
3 24 91 97 101 103 107 109 113 119 81H
4 32 121 127 131 133 137 139 143 149 49H
5 40 151 157 161 163 167 169 173 179 24H
6 48 181 187 191 193 197 199 203 209 C2H
7 56 211 217 221 223 227 229 233 239 06H
一.柯召素数问题

有一些素数的数字之和仍为素数,例如11,23,29,47,67等等.由于这种素数首先有我国四川大学的柯召教授研究过,不妨称之为柯召素数.请问柯召素数是否有无限多个?


--------------------------------------------------------------------------------

二.分解2101-1

人们早就知道2101-1是由两个素数的积组成的,但是至今还没有人能够分解出这两个素数来,你能做到吗?

  这个难题现在已经由陈研用Mathematic4在很短的时间内解决了:
2101-1=7432339208719 * 341117531003194129=2,535,301,200,456,456,458,802,993,406,410,751
我用 factor.exe 验证了右边那个31位数,确实是合数,并且是前面那两个素数的乘积,感谢陈研的工作.


--------------------------------------------------------------------------------

三.回归数

有许多数具有这样一种有趣的性质:它的十进制表示的各位数字,按照原来的顺序进行某种数学运算,又可以重新得到该数,这就是回归数,例如:

24=23+42 2427=21+42+23+74  81=(8+1)2 145=1!+4!+5!

英国数学家哈代(G.H.Hardy 1877-1947)曾经发现过另一种形式的回归数:

153=13+53+33 371=33+73+13  370=33+73+03 407=43+03+73

他们都是三位数且等于各位数字的三次幂之和,这种巧合不能不令人感到惊讶.更为称奇的是,一位读者看过哈代的有趣发现后,竟然构造出其值等于各位数字四(五,六)次幂之和的四(五,六)位数:

1634=14+64+34+44 54748=55+45+75+45+85  548834=56+46+86+86+36+46

像这种其值等于各位数字的 n 次幂之和的 n 位数,称为 n 位 n 次幂回归数.本文只讨论这种回归数,故简称为回归数,人们自然要问:对于什么样的自然数 n 有回归数?这样的 n 是有限个还是无穷多个?对于已经给定的 n ,如果有回归数,那么有多少个回归数?
1986年美国的一位数学教师安东尼.迪拉那(Anthony Diluna)巧妙地证明了使 n 位数成为回归数的 n 只有有限个.
设 An 是这样的回归数,即:

  An=a1a2a3...an=a1n+a2n+...+ann (其中 0<=a1,a2,...an<=9)

  从而 10n-1<=An<=n9n 即 n 必须满足 n9n>10n-1 也就是 (10/9)n<10n    ⑴

  随着自然数 n 的不断增大,(10/9)n 值的增加越来越快,很快就会使得 ⑴ 式不成立,因此,满足⑴的 n 不能无限增大,即 n 只能取有限多个.进一步的计算表明:

  (10/9)60=556.4798...<10*60=600    (10/9)61=618.3109...>10*61=610

  对于 n>=61,便有 (10/9)n>10n

由此可知,使⑴式成立的自然数 n<=60.故这种回归数最多是60位数.迪拉那说,他的学生们早在1975年借助于哥伦比亚大学的计算机得到下列回归数:

  一位回归数:1,2,3,4,5,6,7,8,9
  二位回归数:不存在
  三位回归数:153,370,371,407
  四位回归数:1634,8208,9474
  五位回归数:54748,92727,93084
  六位回归数:548834
  七位回归数:1741725,4210818,9800817
  八位回归数:24678050,24678051
但是此后对于哪一个自然数 n (<=60)还有回归数?对于已经给定的 n ,能有多少个回归数?最大的回归数是多少?


--------------------------------------------------------------------------------

三.我的关于数学黑洞的猜想:数学黑洞是指自然数经过某种数学运算之后陷入了一种循环的境况.例如,自然数的数字的平方和会陷入两个死循环:1和4.自然数的数字的立方和会陷入几组死循环:
  1;
  37,73,307,370,703,730;
  47,74,407,470,704,740;
  153,135,315,351,513,531;
  137,173,317,371,713,731;
  55,250,133;
136,244
  160,217,352;
  919,1459;
  自然数的数字四次方和有多少组死循环?
  自然数的数字五次方和有多少组死循环?
  ......


--------------------------------------------------------------------------------

四.不定方程:X2+Y3=Z3非常有意思,我求出了它的两种类型的解:
    X=(a√a)*S2K/2    (a>=0 k=0,1,2,...)
    Y=a*(T2k-1)/2
    Z=a*(T2k+1)/2
  其中:S0=2,T0=1,Sn+1=2Sn+3Tn,Tn+1=Sn+2Tn
  另一种解为:
    X=m3(S3-1)2    (m>=0 S=0,1,2...)
    Y=m2(S3-1)
    Z=m2S(S3-1)
  谁能找到全部解,你能帮我解决吗?

木木鱼

相当牛逼

无影人

顶了。