Mersennovo število

Iz Wikipedije, proste enciklopedije
(Preusmerjeno s strani Mersennovo praštevilo)
Skoči na: navigacija, iskanje

Mersennovo število je naravno število oblike:

M_{n} \equiv 2^{n} - 1; \quad n > 0 \!\, .

Mersenne je poskušal odkriti, katera števila takšne oblike so praštevila. Mersennova praštevila so v tesni povezavi s popolnimi števili. Trenutno (maj 2013) je po vrsti znanih 40 Mersennovih praštevil za n enak (OEIS A000043):

2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11.213, 19.937, 21.701, 23.209, 44.497, 86.243, 110.503, 132.049, 216.091, 756.839, 859.433, 1.257.787, 1.398.269, 2.976.221, 3.021.377, 6.972.593, 13.466.917 in 20.996.011.

in še 7 Mersennovih praštevil za n enak:

24.036.583, 25.964.951, 30.402.457, 32,582,657, 37.156.667, 42.643.801 in 43.112.609.

Ni pa znano ali obstaja še kakšno Mersennovo praštevilo, ki je manjše od 41., oziroma med zadnjimi sedmimi.

Velja domnevna ocena za gostoto porazdelitve Mersennovih praštevil z eksponentom p < x:

e^{\gamma} \log (\log x) / \log 2 \!\, ,

kjer je γ Euler-Mascheronijeva konstanta.

Vsebina

Značilnosti [uredi]

Enakost:

2^{ab}-1=(2^a-1) \left(1+2^a+2^{2a}+2^{3a}+\cdots+2^{(b-1)a}\right) \!\,

kaže, da je M_{n} lahko praštevilo le, če je tudi n praštevilo. Praštevilskost n je nujen, ne pa tudi zadosten pogoj, da je M_{n} praštevilo. To dejstvo zelo poenostavlja iskanje Mersennovih praštevil. Obratna izjava, da je M_{n} nujno praštevilo, če je n praštevilo, pa ne velja. Najmanjši protiprimer je 2^{11}-1=2047=23 \cdot 89, ki je sestavljeno število. Prva druga praštevila, za katera M_{n} ni praštevilo, so (OEIS A054723):

11, 23, 29, 37, 41, 43, 47, 53, 59, 67, 71, 73, 79, 83, 97, 101, 103, 109, 113, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, ...

Ni znano ali je takšnih števil neskončno mnogo. Ta praštevila si sledijo po vrsti, (11 je peto praštevilo, 23 deveto, itd.): (OEIS A135980):

5, 9, 10, 12, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 25, 26, 27, 29, 30, 32, 33, 34, 35, 36, 37, 38, 39, 40, ...

Seznam znanih Mersennovih praštevil [uredi]

Razpredelnica podaja vsa do sedaj znana Mersennova praštevila (OEIS A000668):

# n Mn št. števk v Mn datum odkritja odkritelj
1 2 3 1 5. stoletje pr. n. št.[1] starogrški matematiki
2 3 7 1 5. stoletje pr. n. št.[1] starogrški matematiki
3 5 31 2 3. stoletje pr. n. št.[1] starogrški matematiki
4 7 127 3 3. stoletje pr. n. št.[1] starogrški matematiki
5 13 8191 4 1456 neznani [2]
6 17 131071 6 1588 Cataldi
7 19 524287 6 1588 Cataldi
8 31 2147483647 10 1772 Euler
9 61 2305843009213693951 19 1883 Pervušin
10 89 618970019…449562111 27 1911 Powers
11 107 162259276…010288127 33 1914 Powers[3]
12 127 170141183…884105727 39 1876 Lucas
13 521 686479766…115057151 157 30. januar 1952 Robinson, računalnik SWAC
14 607 531137992…031728127 183 30. januar 1952 Robinson
15 1279 104079321…168729087 386 25. junij 1952 Robinson
16 2203 147597991…697771007 664 7. oktober 1952 Robinson
17 2281 446087557…132836351 687 9. oktober 1952 Robinson
18 3217 259117086…909315071 969 8. september 1957 Riesel, računalnik BESK
19 4253 190797007…350484991 1281 3. november 1961 Hurwitz, računalnik IBM 7090
20 4423 285542542…608580607 1332 3. november 1961 Hurwitz
21 9689 478220278…225754111 2917 11. maj 1963 Gillies, superračunalnik ILLIAC II
22 9941 346088282…789463551 2993 16. maj 1963 Gillies
23 11.213 281411201…696392191 3376 2. junij 1963 Gillies
24 19.937 431542479…968041471 6002 4. marec 1971 Tuckerman, računalnik IBM 360/91
25 21.701 448679166…511882751 6533 30. oktober 1978 Noll, Nickel, superračunalnik CDC Cyber 174
26 23.209 402874115…779264511 6987 9. februar 1979 Noll
27 44.497 854509824…011228671 13.395 8. april 1979 Nelson, Slowinski
28 86.243 536927995…433438207 25.962 25. september 1982 Slowinski
29 110.503 521928313…465515007 33.265 28. januar 1988 Colquitt, Welsh
30 132.049 512740276…730061311 39.751 19. september 1983[1] Slowinski
31 216.091 746093103…815528447 65.050 1. september 1985[1] Slowinski
32 756.839 174135906…544677887 227.832 19. februar 1992 Slowinski, Gage, superračunalnik Cray-2 v Harwell Lab[4]
33 859.433 129498125…500142591 258.716 4. januar 1994[5] Slowinski, Gage
34 1.257.787 412245773…089366527 378.632 3. september 1996 Slowinski, Gage[6]
35 1.398.269 814717564…451315711 420.921 13. november 1996 GIMPS / Joel Armengaud[7]
36 2.976.221 623340076…729201151 895.932 24. avgust 1997 GIMPS / Gordon Spence[8]
37 3.021.377 127411683…024694271 909.526 27. januar 1998 GIMPS / Roland Clarkson[9]
38 6.972.593 437075744…924193791 2.098.960 1. junij 1999 GIMPS / Nayan Hajratwala[10]
39 13.466.917 924947738…256259071 4.053.946 14. november 2001 GIMPS / Michael Cameron[11]
40 20.996.011 125976895…855682047 6.320.430 17. november 2003 GIMPS / Michael Shafer[12]
41[*] 24.036.583 299410429…733969407 7.235.733 15. maj 2004 GIMPS / Josh Findley[13]
42[*] 25.964.951 122164630…577077247 7.816.230 18. februar 2005 GIMPS / Martin Nowak[14]
43[*] 30.402.457 315416475…652943871 9.152.052 15. december 2005 GIMPS / Curtis Cooper, Steven Boone[15]
44[*] 32.582.657 124575026…053967871 9.808.358 4. september 2006 GIMPS / Curtis Cooper & Steven Boone[16]
45[*] 37.156.667 202254406…308220927 11.185.272 6. september 2008 GIMPS / Hans-Michael Elvenich[17]
46[*] 42.643.801 169873516…562314751 12.837.064 12. april 2009[**] GIMPS / Odd M. Strindmo
47[*] 43.112.609 316470269…697152511 12.978.189 23. avgust 2008 GIMPS / Edson Smith[17]
Graf števila števk v največjem znanem Mersennovem praštevilu po letu v elektronski dobi. Navpično merilo, število števk, je dvojno logaritmično merilo vrednosti praštevila.

 * Ni znano ali obstaja kakšno Mersennovo praštevilo med 40. (M20.996.011) in 47. (M43.112.609) v tej razpredelnici. Zato je zadnjih sedem zaporednih številk le začasnih. 29. Mersennovo praštevilo je bilo odkrito za 30. in 31. Prav tako je bilo 45. odkrito štirinajst dni za 47., trenutno največjim znanim praštevilom, ter 46. slabih sedem mesecev za 47.

47. znano Mersennovo praštevilo bi zapisali na 3461. straneh v desetiškem sistemu po 75 števk v vrstici in 50 vrstic na stran. [1]

2305843009213693951 [uredi]

Število 2305843009213693951 je deveto Mersennovo praštevilo in je enako 2^{61}-1. Leta 1883 je Pervušin pokazal, da je praštevilo, in ga zato včasih imenujejo Pervušinovo število. Do leta 1911 je ostalo drugo največje znano praštevilo za številom 2^{127}-1, katerega praštevilskost je že sedem let prej dokazal Lucas.

Glej tudi [uredi]

Opombe in sklici [uredi]

  1. ^ 1,0 1,1 1,2 1,3 1,4 1,5 1,6 Landon Curt Noll, Mersenne Prime Digits and Names.
  2. ^ The Prime Pages, Mersenne Primes: History, Theorems and Lists.
  3. ^ The Prime Pages, M107: Fauquembergue or Powers?.
  4. ^ The Prime Pages, The finding of the 32nd Mersenne.
  5. ^ Chris Caldwell, The Largest Known Primes.
  6. ^ The Prime Pages, A Prime of Record Size! 21257787-1.
  7. ^ GIMPS Discovers 35th Mersenne Prime.
  8. ^ GIMPS Discovers 36th Known Mersenne Prime.
  9. ^ GIMPS Discovers 37th Known Mersenne Prime.
  10. ^ GIMPS Finds First Million-Digit Prime, Stakes Claim to $50,000 EFF Award.
  11. ^ GIMPS, Researchers Discover Largest Multi-Million-Digit Prime Using Entropia Distributed Computing Grid.
  12. ^ GIMPS, Mersenne Project Discovers Largest Known Prime Number on World-Wide Volunteer Computer Grid.
  13. ^ GIMPS, Mersenne.org Project Discovers New Largest Known Prime Number, 224,036,583-1.
  14. ^ GIMPS, Mersenne.org Project Discovers New Largest Known Prime Number, 225,964,951-1.
  15. ^ GIMPS, Mersenne.org Project Discovers New Largest Known Prime Number, 230,402,457-1.
  16. ^ GIMPS, Mersenne.org Project Discovers Largest Known Prime Number, 232,582,657-1.
  17. ^ 17,0 17,1 Titanic Primes Raced to Win $100,000 Research Award (v angleščini). Pridobljeno dne 2008-09-16.

Viri [uredi]

Zunanje povezave [uredi]

  • Domača stran projekta GIMPS, ki se ukvarja z iskanjem Mersennovih števil. (v angleščini)
Vzpostavljeno iz »http://sl.wikipedia.org/w/index.php?title=Mersennovo_število&oldid=3945198«