Mersennovo prvočíslo

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie

Mersennovo prvočíslo alebo Mersennovo číslo je prvočíslo ktoré sa dá zapísať v tvare M_{n}=2^{n}-1, kde n je prirodzené číslo. Príkladom Mersenovho prvočísla je číslo 3 pretože je to prvočíslo a navyše 3=2^{2}-1. Prvých 10 Mersennovych prvočísel tvorí postupnosť:

3, 7, 31, 127, 8191, 131071, 524287, 2147483647, 2305843009213693951, 618970019642690137449562111...

V súčasnosti je známych 48 Mersennových prvočísel. Zatiaľ najväčšie známe Mersennovo prvočíslo má 17 miliónov cifier a bolo objavené v roku 2013.

Obsah

Prípustné hodnoty n [upraviť]

Nutnou podmienkou k tomu, aby bolo M_{n} prvočíslom je prvočíselnosť samotného n. Totiž, ak je n zložené číslo, dá sa vyjadriť v tvare n=a.b kde a,b sú prirodzené čísla rôzne od 1. Navyše platí vzťah

M_{n}=M_{ab}=2^{ab}-1=(2^a-1)\cdot \left(1+2^a+2^{2a}+2^{3a}+\dots+2^{(b-1)a}\right)

z ktorého vyplýva, že M_{n} je tiež zložené číslo. Preto môže byť M_{n} prvočíslom len v tom prípade, ak je prvočíslom aj n.

To ale neznamená, že ak je n prvočíslom, je ním aj M_{n}. Najmenším príkladom je M_{11}=2047=23.89.

Zoznam Mersennových prvočísel [upraviť]

# p Mp Cifry v Mp Dátum objavu Objaviteľ
1 2 3 1 500 pred Kr.[1] starí Gréci
2 3 7 1 500 pred Kr.[1] starí Gréci
3 5 31 2 275 pred Kr.[1] starí Gréci
4 7 127 3 275 pred Kr.[1] starí Gréci
5 13 8191 4 1456 anonym [2]
6 17 131071 6 1588 Cataldi
7 19 524287 6 1588 Cataldi
8 31 2147483647 10 1772 Euler
9 61 2305843009213693951 19 1883 Ivan 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. január 1952 Robinson pomocou SWAC
14 607 531137992…031728127 183 30. január 1952 Robinson
15 1 279 104079321…168729087 386 25. jún 1952 Robinson
16 2 203 147597991…697771007 664 7. október 1952 Robinson
17 2 281 446087557…132836351 687 9. október 1952 Robinson
18 3 217 259117086…909315071 969 8. september 1957 Riesel pomocou BESK
19 4 253 190797007…350484991 1 281 3. november 1961 Hurwitz using IBM 7090
20 4 423 285542542…608580607 1 332 3. november 1961 Hurwitz
21 9 689 478220278…225754111 2 917 11. máj 1963 Gillies using ILLIAC II
22 9 941 346088282…789463551 2 993 16. máj 1963 Gillies
23 11 213 281411201…696392191 3 376 2. jún 1963 Gillies
24 19 937 431542479…968041471 6 002 4. marec 1971 Tuckerman using IBM 360/91
25 21 701 448679166…511882751 6 533 30. október 1978 Noll & Nickel pomocou CDC Cyber 174
26 23 209 402874115…779264511 6 987 9. február 1979 Noll
27 44 497 854509824…011228671 13 395 8. apríl 1979 Nelson & Slowinski
28 86 243 536927995…433438207 25 962 25. september 1982 Slowinski
29 110 503 521928313…465515007 33 265 28. január 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. február 1992 Slowinski & Gage na Harwell Lab Cray-2[4]
33 859 433 129498125…500142591 258 716 4. január 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. august 1997 GIMPS / Gordon Spence[8]
37 3 021 377 127411683…024694271 909 526 27. január 1998 GIMPS / Roland Clarkson[9]
38 6 972 593 437075744…924193791 2 098 960 1. jún 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. máj 2004 GIMPS / Josh Findley[13]
42[*] 25 964 951 122164630…577077247 7 816 230 18. február 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. apríl 2009 GIMPS / Odd M. Strindmo
47[*] 43 112 609 316470269…697152511 12 978 189 23. august 2008 GIMPS / Edson Smith[17]

* Zatiaľ nie je známe, či medzi 40. a 47. existujú niektoré doposiaľ neobjavené Mersennove prvočísla, číslovanie je preto iba predbežné.

Referencie [upraviť]

  1. ↑ a b c d e f 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. ↑ a b Titanic Primes Raced to Win $100 000 Research Award. Retrieved on 2008-09-16.

Pozri aj [upraviť]

Externé zdroje [upraviť]

  • A000043 Zoznam tých prirodzených čísel n pre ktoré je M_{n} prvočíslom. Odkazy na literatúru.
  • Tlačová správa o objavení 45 a 46 Merseenového prvočísla
Zdroj: „http://sk.wikipedia.org/w/index.php?title=Mersennovo_prvočíslo&oldid=5242065“