Numărul Mersenne

Numărul Mersenne este un număr de formă , unde este un număr natural ; astfel de numere sunt remarcabile prin faptul că unele dintre ele sunt prime pentru valori mari ale . Ele sunt numite după matematicianul francez Marin Mersenne , care le-a studiat proprietățile în secolul al XVII-lea. $M_{n}=2^{n}-1$ $n$ $n$

Primele numere Mersenne [1] :

1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, …

Proprietăți

Pentru toate , următorul lucru este adevărat: dacă este compus, atunci este și compozit, ceea ce decurge din expansiune: $M_{n}$ $n$ $n=kl,k,l>1$ $M_{n}$

2^{n}-1=2^{kl}-1=(2^{k}-1)(2^{k(l-1)}+2^{k(l-2)} +\puncte +1),

De aici rezultă imediat: un număr este prim numai dacă numărul este și prim. Afirmația inversă nu este adevărată în cazul general, cel mai mic contraexemplu este . $M_{n}$ $n$ $M_{{11}}=2047=23\cdot 89$

Orice divizor al unui număr compus pentru un număr prim are forma , unde este un număr natural (aceasta este o consecință a micii teoreme a lui Fermat ). $M_{p}$ $p$ $2\cdot p\cdot k+1$ $k$

Primele Mersenne sunt strâns legate de numerele perfecte . Euclid a arătat că un număr de forma , unde numărul Mersenne este prim, este perfect. Euler a demonstrat că toate numerele par perfecte sunt epuizate prin această formulă. (În ceea ce privește numerele perfecte impare, până acum nu se știe nimic despre existența lor.) ${\tfrac {M_{p}(M_{p}+1)}{2}}=2^{{p-1}}(2^{p}-1)$ $M_{p}$

Primele Mersenne

Pentru toate numerele prime de formă, exponentul este întotdeauna un număr prim, astfel încât numerele Mersenne cu exponent prim [2] sunt studiate în special (în unele lucrări, doar astfel de numere sunt considerate numere Mersenne). Secvența primelor Mersenne începe astfel [3] : $2^{n}-1$ $n$ $M_{p}=2^{p}-1$ $p$

3 , 7 , 31 , 127 , 8191, 131 071, 524 287, 2 147 483 647 , 2 305 843 009 213 693 951 , 618 970 019 642 690 137 449 562 111 , 162 259 276 829 213 363 391 578 010 288 127 127 , 170 141 183 460 469 231 731 687 303 715 884 105 727 …

Exponenții primelor Mersenne cunoscute formează o secvență [4] [5] : $p$

2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9141 , 9141 , 9141 , 914,13 , 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 , 32 582 657 , 37 156 667 , 42 643 801 , 43 112 801 , 43 112 801 , 43 112 801 , 43 112 801 , 43 112 801 , 43 112 801 , 43 112 801 , 7 7 112 801

Numerele Mersenne au câștigat faimă în legătură cu un algoritm eficient pentru verificarea simplității numerelor Mersenne - testul Luc-Lehmer . Prin urmare, numerele prime Mersenne au deținut de multă vreme conducerea ca cele mai mari numere prime cunoscute [6] . De asemenea, numerele prime Mersenne sunt folosite pentru a construi generatoare de numere pseudoaleatoare cu perioade mari [7] , cum ar fi vortexul Mersenne .

Găsirea numerelor prime Mersenne

Cel mai mare număr prim cunoscut (din ianuarie 2019) este numărul Mersenne , găsit pe 7 decembrie 2018 de Patrick Laroche, ca parte a proiectului de calcul voluntar GIMPS . Notația zecimală a unui număr conține 24.862.048 de cifre [8] . $M_{82589933}=2^{82589933}-1$ $M_{82589933}$

În total, din decembrie 2018, sunt cunoscute 51 de numere prime Mersenne, în timp ce numerele de serie sunt stabilite în mod fiabil doar pentru primele 48 [9] numere. În special, nu se știe dacă există alte numere prime Mersenne mai mici decât cea cunoscută. În special, al 45-lea prim Mersenne a fost găsit cu două săptămâni mai târziu decât al 47-lea prim Mersenne cunoscut , în timp ce al 46-lea prim Mersenne cunoscut nu a fost găsit decât un an mai târziu. $M_{37156667}$ $M_{{43112609}}$ $M_{42643801}$

În 2009, proiectul GIMPS a primit un premiu de 100.000 USD de la Electronic Frontier Foundation pentru găsirea unui număr prim Mersenne pentru găsirea unui număr prim a cărui notație zecimală conține cel puțin 10 milioane de cifre [10] . $M_{{43112609}}$

Variații și generalizări

Numărul dublu Mersenne este un număr de forma. Din ianuarie 2021, sunt cunoscute doar 4 numere prime de acest fel (pentru). $M_{M_{n}}=2^{2^{n}-1}-1$ $n=2,3,5,7$

Numerele catalan-mersenne sunt membri ai unei secvențe de numere care încep cu 2 și sunt construite prin aplicarea unei funcțiimembrului anterior; primele elemente[11]: $2^{n}-1$ $n$

2, 3, 7, 127 , 170141183460469231731687303715884105727 …

Catalan a presupus că aceste numere sunt prime „până la o anumită limită”.

Numărul Mersenne generalizat este un număr de forma:

h^{0}+h^{1}+h^{2}+\dots +h^{n-1}={\frac {h^{n}-1}{h-1)} =M_{h,n}

O astfel de generalizare se datorează a ceea ce poate fi reprezentat ca suma primilor termeni ai unei progresii geometrice crescătoare : $2^{n}-1$ $n$

2^{n}-1=2^{0}+2^{1}+2^{2}+\dots +2^{n-1}={\frac {2^{n}- 1}{2-1}}

cu alte cuvinte, numerele Mersenne sunt un caz special de numere Mersenne generalizate pentru . Pentru unele valori și numerele Mersenne generalizate sunt simple, de exemplu, , , , , , , și o serie de altele. $h=2$ $h$ $n$ $M_{3,3}$ $M_{3,7}$ $M_{3,13}$ $M_{3,71}$ $M_{5,3}$ $M_{5,7}$ $M_{5,47}$

Probleme deschise

Nu se știe dacă mulțimea numerelor prime Mersenne este finită sau infinită, iar densitatea distribuției lor în mulțimea numerelor naturale este necunoscută.

Nu se știe dacă numere prime duble Mersenne există pentru . $n>7$

Note

↑ Secvența OEIS A000225 _
↑ Secvența OEIS A001348 _
↑ Secvența OEIS A000668 _
↑ Secvența OEIS A000043 _
↑ Lista numerelor prime Mersenne cunoscute . Excelent Internet Mersenne Prime Search . Preluat: 9 decembrie 2016.
↑ Cele mai mari prime cunoscute--Un rezumat . The Prime Pages (26 decembrie 2018). Preluat: 28 decembrie 2018.
↑ R. P. Brent, P. Zimmermann. Generatoare de numere aleatorii cu perioadă divizibilă cu un prim Mersenne // Note de curs în informatică. - 2003. - T. 2667 . - S. 1-10 .
↑ Elizabeth Ivtushok. Cel mai mare număr prim a fost mărit cu un milion și jumătate de caractere . nplus1.ru. Preluat: 23 decembrie 2018. (Rusă)
↑ GIMPS Milestones . www.mersenne.org . Preluat: 5 aprilie 2022. (nedefinit)
↑ Numărul prim record de 12 milioane de cifre aduce premiu de 100.000 USD
↑ Secvența OEIS A007013 _

Link -uri

Weisstein, Eric W. Mersenne Prime (engleză) pe site-ul web Wolfram MathWorld .
Weisstein, Eric W. Mersenne Number (engleză) pe site-ul web Wolfram MathWorld .
Weisstein, Eric W. Double Mersenne Numbers (engleză) pe site-ul Wolfram MathWorld .
Andrei Konyaev . Nicăieri mai ușor. Am găsit un număr prim cinci romane lungi „Război și pace” // lenta.ru. — 12 februarie 2013.
Proiectul Mersenne Prime Search (GIMPS ) .
Proiect pentru căutarea divizorilor numerelor Mersenne duble MM31, MM61, MM89, MM107, MM127 (ing.) .