Mersennovo število

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje

Mersennovo število (tudi Evklid-Mersennovo število) je naravno število oblike:

 M_{n} \equiv 2^{n} - 1, \qquad ( 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 (avgust 2015) je po vrsti znanih 44 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, 20.996.011, 24.036.583, 25.964.951, 30.402.457 in 32.582.657.

in še 4 Mersennova praštevila za n enak:

37.156.667, 42.643.801, 43.112.609 in 57.885.161.

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

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.

Značilnosti[uredi | uredi kodo]

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, ...

Vsota neskončne vrste obratnih vrednosti Mersennovih praštevil konvergira in je enaka konstanti:

 \begin{align}
\sum_{n=1}^{\infty} \frac{1}{M_{n}} &= \frac{1}{3} + \frac{1}{7} + \frac{1}{31} + \frac{1}{127} + \frac{1}{8191} + \frac{1}{131071} + \frac{1}{524287} + \frac{1}{2147483647} + \frac{1}{2305843009213693951} + \ldots \\
&= 0{,}5164541789407 \ldots \!\, , \end{align} (OEIS A173898).

Za prvih 100 števk konstante zadostuje prvih enajst Mersennovih praštevil.

Seznam znanih Mersennovih praštevil[uredi | uredi kodo]

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

# n\, M_{n}\, št. števk v M_{n}\, datum odkritja odkritelj metoda
1 2 3 1 okoli 430 pr. n. št. starogrški matematiki[1]  
2 3 7 1 okoli 430 pr. n. št. starogrški matematiki[1]  
3 5 31 2 okoli 300 pr. n. št. starogrški matematiki[2]  
4 7 127 3 okoli 300 pr. n. št. starogrški matematiki[2]  
5 13 8191 4 1456 neznani [3] poskusno deljenje
6 17 131071 6 1588 Cataldi poskusno deljenje[4]
7 19 524287 6 1588 Cataldi poskusno deljenje[5]
8 31 2147483647 10 1772 Euler[6][7] izboljšano poskusno deljenje[8]
9 61 2305843009213693951 19 november 1883[9] Pervušin Lucasova zaporedja
10 89 618970019642...137449562111 27 junij 1911[10] Powers Lucasova zaporedja
11 107 162259276829...578010288127 33 1. junij 1914[11][12][13] Powers[14] Lucasova zaporedja
12 127 170141183460...715884105727 39 10. januar 1876[15] Lucas Lucasova zaporedja
13 521 686479766013...291115057151 157 30. januar 1952[16] Robinson LLT / računalnik SWAC
14 607 531137992816...219031728127 183 30. januar 1952[16] Robinson LLT / SWAC
15 1279 104079321946...703168729087 386 25. junij 1952[17] Robinson LLT / SWAC
16 2203 147597991521...686697771007 664 7. oktober 1952[18] Robinson LLT / SWAC
17 2281 446087557183...418132836351 687 9. oktober 1952[18] Robinson LLT / SWAC
18 3217 259117086013...362909315071 969 8. september 1957[19] Riesel LLT / računalnik BESK
19 4253 190797007524...815350484991 1281 3. november 1961[20][21] Hurwitz LLT / računalnik IBM 7090
20 4423 285542542228...902608580607 1332 3. november 1961[20][21] Hurwitz LLT / IBM 7090
21 9689 478220278805...826225754111 2917 11. maj 1963[22] Gillies LLT / superračunalnik ILLIAC II
22 9941 346088282490...883789463551 2993 16. maj 1963[22] Gillies LLT / ILLIAC II
23 11.213 281411201369...087696392191 3376 2. junij 1963[22] Gillies LLT / ILLIAC II
24 19.937 431542479738...030968041471 6002 4. marec 1971[23] Tuckerman LLT / računalnik IBM 360/91
25 21.701 448679166119...353511882751 6533 30. oktober 1978[24] Noll, Nickel LLT / superračunalnik CDC Cyber 174
26 23.209 402874115778...523779264511 6987 9. februar 1979[25] Noll LLT / CDC Cyber 174
27 44.497 854509824303...961011228671 13.395 8. april 1979[26][27] Nelson, Slowinski LLT / superračunalnik Cray 1
28 86.243 536927995502...709433438207 25.962 25. september 1982 Slowinski LLT / Cray 1
29 110.503 521928313341...083465515007 33.265 28. januar 1988[28][29] Colquitt, Welsh LLT / superračunalnik NEC SX-2[30]
30 132.049 512740276269...455730061311 39.751 19. september 1983[1][31] Slowinski LLT / superračunalnik Cray X-MP
31 216.091 746093103064...103815528447 65.050 1. september 1985[1][32][33] Slowinski LLT / Cray X-MP/24
32 756.839 174135906820...328544677887 227.832 19. februar 1992 Slowinski, Gage superračunalnik Cray-2 v Harwell Lab[34]
33 859.433 129498125604...243500142591 258.716 4. januar 1994[35][36][37] Slowinski, Gage LLT / superračunalnik Cray C90
34 1.257.787 412245773621...976089366527 378.632 3. september 1996[38] Slowinski, Gage[39] LLT / superračunalnik Cray T94
35 1.398.269 814717564412...868451315711 420.921 13. november 1996 GIMPS / Joel Armengaud[40] LLT / progam Prime95 – 90 MHz Pentium PC
36 2.976.221 623340076248...743729201151 895.932 24. avgust 1997 GIMPS / Gordon Spence[41] LLT / Prime95 – 100 MHz Pentium PC
37 3.021.377 127411683030...973024694271 909.526 27. januar 1998 GIMPS / Roland Clarkson[42] LLT / Prime95 – 200 MHz Pentium PC
38 6.972.593 437075744127...142924193791 2.098.960 1. junij 1999 GIMPS / Nayan Hajratwala[43] LLT / Prime95 – 350 MHz Pentium II IBM Aptiva
39 13.466.917 924947738006...470256259071 4.053.946 14. november 2001 GIMPS / Michael Cameron[44] LLT / Prime95 – 800 MHz Athlon T-Bird
40 20.996.011 125976895450...762855682047 6.320.430 17. november 2003 GIMPS / Michael Shafer[45] LLT / Prime95 – 2 GHz Dell Dimension
41 24.036.583 299410429404...882733969407 7.235.733 15. maj 2004 GIMPS / Josh Findley[46] LLT / Prime95 – 2.4 GHz Pentium 4 PC
42 25.964.951 122164630061...280577077247 7.816.230 18. februar 2005 GIMPS / Martin Nowak[47] LLT / Prime95 – 2.4 GHz Pentium 4 PC
43 30.402.457 315416475618...411652943871 9.152.052 15. december 2005 GIMPS / Cooper, Boone[48] LLT / Prime95 – 2 GHz Pentium 4 PC
44 32.582.657 124575026015...154053967871 9.808.358 4. september 2006 GIMPS / Cooper, Boone[49] LLT / Prime95 – 3 GHz Pentium 4 PC
45[*] 37.156.667 202254406890...022308220927 11.185.272 6. september 2008 GIMPS / Hans-Michael Elvenich[50] LLT / Prime95 – 2.83 GHz Core 2 Duo PC
46[*] 42.643.801 169873516452...765562314751 12.837.064 12. april 2009[**] GIMPS / Odd Magnar Strindmo[51] LLT / Prime95 – 3 GHz Core 2 PC
47[*] 43.112.609 316470269330...166697152511 12.978.189 23. avgust 2008 GIMPS / Edson Smith[50] LLT / Prime95 – Dell Optiplex 745
48[*] 57.885.161 581887266232...071724285951 17.425.170 25. januar 2013 GIMPS / Cooper[52] LLT / Prime95 – 3 GHz Intel Core2 Duo E8400[53]
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 44. (M32.582.657) in 48. (M57.885.161) v tej razpredelnici. Zato so zadnje štiri zaporedne številke le začasne. Vsa Mersennova števila manjša od 47-ega (M43.112.609) so bila preverjena vsaj enkrat, nekatera pa niso bila preverjena dvakrat. Nekatera Mersennova števila manjša od 48-ega niso bila preverjena.[54] Praštevila ne odkrijejo vedno v naraščajočem vrstnem redu. 29. Mersennovo praštevilo je bilo na primer odkrito za 30. in 31. Prav tako je bilo 45. odkrito štirinajst dni za 47., ter 46. slabih sedem mesecev za 47.

^ ** Število M42,643,801 je bilo prvič odktito na stroju 12. aprila 2009. Vendar nihče ni bil pozoren na to dejstvo vse do 4. junija. Tako se lahko oba datuma, 12. april ali 4. junij, štejeta za datum 'odkritja'. Odktitelj Strindmo je verjetno uporabil nadimek Stig M. Valstad.

Število M43.112.609 je prvo odkrito praštevilo z več kot 10 milijoni desetiških števk. 48. znano Mersennovo praštevilo bi se zapisalo na 4647. straneh v desetiškem sistemu po 75 števk v vrstici in 50 vrstic na stran. Največje znano Mersennovo praštevilo (257,885,161 − 1) je hkrati tudi trenutno največje znano praštevilo.[52]

2305843009213693951[uredi | uredi kodo]

Š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 [[Édouard Lucas|Lucas

Neskončni verižni ulomek[uredi | uredi kodo]

Konstanta neskončnega verižnega ulomka Mersennovih praštevil je:[55]

 u_{\mathcal{M}} = [0; 3, 7, 31, 127, 8191, 131071, 524287, 2147483647, 2305843009213693951, \ldots] = 0,318248158405 \ldots \!\, . (OEIS A242072).

Glej tudi[uredi | uredi kodo]

Sklici[uredi | uredi kodo]

  1. ^ 1,0 1,1 1,2 1,3 Noll, Landon Curt. "Mersenne Prime Digits and Names" (v angleščini). 
  2. ^ 2,0 2,1 "Euclid's Elements, knjiga IX, propozicija 36" (v angleščini). 
  3. ^ The Prime Pages, Mersenne Primes: History, Theorems and Lists.
  4. ^ str. 13–18 v Trattato de' nvumeri perfetti Di Pietro Antonio Cataldo 1603. http://fermi.imss.fi.it/rd/bdv?/bdviewer@selid=1373775#
  5. ^ str. 13–18 v Trattato de' nvumeri perfetti Di Pietro Antonio Cataldo 1603. http://fermi.imss.fi.it/rd/bdv?/bdviewer@selid=1373775#
  6. ^ Euler (1772).
  7. ^ http://primes.utm.edu/notes/by_year.html#31 Datum in leto odkritja nista točno znana. Možni so datumi med letoma 1752 in 1772.
  8. ^ Caldwell, Chris K. "Modular restrictions on Mersenne divisors" (v angleščini). Primes.utm.edu. Pridobljeno dne 2011-05-21. 
  9. ^ “En novembre de l’année 1883, dans la correspondance de notre Académie se trouve une communication qui contient l’assertion que le nombre 261 − 1 = 2305843009213693951 est un nombre premier. /…/ Le tome XLVIII des Mémoires Russes de l’Académie /…/ contient le compte-rendu de la séance du 20 décembre 1883, dans lequel l’objet de la communication du père Pervouchine est indiqué avec précision.” Bulletin de l'Académie Impériale des Sciences de St.-Pétersbourg, s. 3, v. 31, 1887, cols. 532–533. http://www.biodiversitylibrary.org/item/107789#page/277/mode/1up [pridobljeno dne 2012-09-17] Glej tudi Mélanges mathématiques et astronomiques tirés du Bulletin de l’Académie impériale des sciences de St.-Pétersbourg v. 6 (1881–1888), str. 553–554. Glej tudi Mémoires de l'Académie impériale des sciences de St.-Pétersbourg: Sciences mathématiques, physiques et naturelles, vol. 48
  10. ^ Powers (1911).
  11. ^ "M. E. Fauquenbergue a trouvé ses résultats depuis Février, et j’en ai reçu communication le 7 Juin; M. Powers a envoyé le 1er Juin un cablógramme à M. Bromwich [secretary of London Mathematical Society] pour M107. Sur ma demande, ces deux auteurs m’ont adressé leurs remarquables résultats, et je m’empresse de les publier dans nos colonnes, avec nos felicitations." str. 103, André Gérardin, Nombres de Mersenne str. 85, 103–108 v Sphinx-Œdipe. [Journal mensuel de la curiosité, de concours & de mathématiques.] v. 9, No. 1, 1914.
  12. ^ "Power's cable announcing this same result was sent to the London Math. So. on 1 June 1914." Mersenne's Numbers, Scripta Mathematica, v. 3, 1935, str. 112–119 http://primes.utm.edu/mersenne/LukeMirror/lit/lit_008s.htm [pridobljeno dne 2012-10-13]
  13. ^ Powers (1914).
  14. ^ "M107: Fauquembergue or Powers?" (v angleščini). The Prime Pages. .
  15. ^ Lucas (1876).
  16. ^ 16,0 16,1 Lehmer (1952a). »S pomočjo standardnega testa za Mersennova praštevil s programom, ki ga je izdelal R. M. Robinson, je SWAC odkril praštevili 2521 − 1 in 2607 − 1 30. januarja 1951. To je vodilo do 13. in 14. popolnega števila.«
  17. ^ Lehmer (1952b). »Program opisan v opombi 131 (c) je našel 15-o Mersennovo praštevilo 21279 − 1 25. junija. SWAC je preveril to število v 13-ih minutah in 25-ih sekundah.«
  18. ^ 18,0 18,1 Lehmer (1952c). »Dve novi Mersennovi praštevili, 22203 − 1 in 22281 − 1, je odkril računalnik SWAC 7. in 9. oktobra 1952.«
  19. ^ Riesel (1958). »8. septembra 1957 je švedski elektronski računalnik BESK našel, da je Mersennovo število M3217 = 23217 − 1 praštevilo.«
  20. ^ 20,0 20,1 Hurwitz; Selfridge (1961).
  21. ^ 21,0 21,1 Hurwitz (1962). »Če je p praštevilo se Mp = 2p − 1 imenuje Mersennovo število. Praštevili M4253 in M4423 sta bili odkriti s programiranjem Lucas-Lehmerjevega testa za raačunalnik IBM 7090.«
  22. ^ 22,0 22,1 22,2 Gillies (1964). »Praštevila M9689, M9941 in M11213, ki so sedaj največja znana praštevila, so bila odkrita z računalnikom Illiac II v Laboratoriju digitalnih računalnikov Univerze Illinoisa.«
  23. ^ Tuckerman (1971). »Zvečer 4. marca 1971 je bil odkrit ničelni Lucas-Lehmerjev ostanek za p = p24 = 19937, zato je število M19937 24-o Mersennovo praštevilo.«
  24. ^ Noll; Nickel (1980). »30. oktobra 1978 ob 9:40 sva odkrila, da je število M21701 praštevilo. Procesorki čas z ta test je bil 7:40:20. Tuckerman in Lehmer sta kasneje priskrbela potrditev tega rezultata.«
  25. ^ Noll; Nickel (1980). »Od preostalih števil Mp je bilo najdeno, da je le število M23209 praštevilo. Test se je zaključil 9. februarja 1979 ob 4:06 po izvedenem procesorskem času 8:39:37. Lehmer in McGrogan sta kasneje potrdila rezultat.«
  26. ^ Slowinski (1978/79).
  27. ^ Slowinski (1982). »27. Mersennovo praštevilo. Ima 13395 števk in je enako 244497 – 1. [...] Njegova praštevilskost je bila odkrita 8. aprila 1979 s pomočjo Lucas-Lehmerjevega testa. Test sta sprogramirala na računalniku CRAY-1 David Slowinski in Harry Nelson.« (str. 15) »Rezultat je bil, da je po uporabi Lucas-Lehmerjevega testa na približno tisoč števil koda v nedeljo 8. aprila ugotovila, da je število 244497 − 1 dejansko 27. Mersennovo praštevilo.« (str. 17).
  28. ^ Colquitt; Welsh (1991). »Program s FFT, ki je vseboval 8192 kompleksnih elementov, kar je bila najmanjša zahtevana velikost za preverjanje števila M110503, je tekel približno 11 minut na računalniku SX-2. Odkritje števila M110503 (29. januar 1988) je bilo potrjeno.«
  29. ^ Peterson (1988). »Taa teden sta dva računalniška strokovnjaka našla 31. Mersennovo praštevilo. Na njihovo začudenje novo okdrito praštevilo pade med dve predhodno znani Mersennovi praštevili. Število se pojavi pri p = 110,503, kar pomeni, da je tretje največje znano Mersennovo praštevilo.«
  30. ^ "Mersenne Prime Numbers" (v angleščini). Omes.uni-bielefeld.de. 2011-01-05. Pridobljeno dne 2011-05-21. 
  31. ^ Higgins (1983a), Higgins (1983b). »Slowinski, računalniški inženir za Cray Research Inc. v Chipppewa Fallsu, je odkril število v nedeljo ob 11:36 [to je 19. septembra 1983].«
  32. ^ Peterson (1985).
  33. ^ Sallee (1985).
  34. ^ "The finding of the 32nd Mersenne". The Prime Pages (v angleščini). 
  35. ^ Caldwell, Chris K. "The Largest Known Primes" (v angleščini). 
  36. ^ Crays press release
  37. ^ Elektronska pošta Slowinskega
  38. ^ Silicon Graphics' press release http://web.archive.org/web/19970606011821/http://www.sgi.com/Headlines/1996/September/prime.html [Retrieved 2012-09-20]
  39. ^ "A Prime of Record Size! 21257787-1". The Prime Pages (v angleščini). 
  40. ^ GIMPS Discovers 35th Mersenne Prime.
  41. ^ GIMPS Discovers 36th Known Mersenne Prime.
  42. ^ GIMPS Discovers 37th Known Mersenne Prime.
  43. ^ GIMPS Finds First Million-Digit Prime, Stakes Claim to $50,000 EFF Award.
  44. ^ GIMPS, Researchers Discover Largest Multi-Million-Digit Prime Using Entropia Distributed Computing Grid.
  45. ^ GIMPS, Mersenne Project Discovers Largest Known Prime Number on World-Wide Volunteer Computer Grid.
  46. ^ GIMPS, Mersenne.org Project Discovers New Largest Known Prime Number, 224,036,583-1.
  47. ^ GIMPS, Mersenne.org Project Discovers New Largest Known Prime Number, 225,964,951-1.
  48. ^ GIMPS, Mersenne.org Project Discovers New Largest Known Prime Number, 230,402,457-1.
  49. ^ GIMPS, Mersenne.org Project Discovers Largest Known Prime Number, 232,582,657-1.
  50. ^ 50,0 50,1 "Titanic Primes Raced to Win $100,000 Research Award" (v angleščini). Pridobljeno dne 2008-09-16. 
  51. ^ "The List of Largest Known Primes Home Page" (v angleščini). Pridobljeno dne 2012-09-18. 
  52. ^ 52,0 52,1 "GIMPS Project Discovers Largest Known Prime Number, 257,885,161 − 1" (v angleščini). Great Internet Mersenne Prime Search. Pridobljeno dne 2013-02-05. 
  53. ^ "List of known Mersenne prime numbers" (v angleščini). Pridobljeno dne 2014-11-29. 
  54. ^ "GIMPS Milestones Report" (v angleščini). Pridobljeno dne 2015-05-23. 
  55. ^ Wolf (2010).

Viri[uredi | uredi kodo]

Zunanje povezave[uredi | uredi kodo]

  • Domača stran projekta GIMPS, ki se ukvarja z iskanjem Mersennovih števil. (v angleščini)