מספר מרסן

מספרי מרסן, הנקראים על שם המתמטיקאי האב מרן מרסן, הם מספרים שהם חזקה של שתיים פחות 1, כלומר, בתבנית: <math>\ M_n=2^n-1</math>. חמשת מספרי מרסן הטבעיים הראשונים הם 1, 3, 7, 15 ו-31.

בתצוגה בינארית, מספר מרסן הוא יחידה חוזרת המורכבת מ-n מופעים של הספרה 1. לדוגמה: המספר 31, השווה ל-<math>\ 2^5-1</math>, מוצג בבסיס בינארי כמספר 11111.

למספרי מרסן ראשוניים יש קשר הדוק למספרים משוכללים, שהם מספרים השווים לסכום מחלקיהם. מבחינה היסטורית, המחקר על מספרי מרסן בא מקשר זה: אוקלידס הראה במאה ה-4 לפנה"ס שאם <math>\ M_n</math> הוא מספר מרסן ראשוני אז <math>\frac{M_n(M_n+1)}{2}=2^{n-1}(2^n-1)</math> הוא מספר משוכלל. כעבור כאלפיים שנה, במאה ה-18, הראה אוילר שכל המספרים המשוכללים הזוגיים הם בתבנית זו. לא ידוע האם יש אינסוף מספרי מרסן ראשוניים. הפירוק <math>(2^a-1)\cdot (1+2^a+2^{2a}+2^{3a}+\dots+2^{(b-1)a})=2^{ab}-1</math> מראה ש-<math>\ M_n</math> יכול להיות ראשוני רק אם <math>\ n</math> עצמו ראשוני, מה שמקל במידה ניכרת על חיפוש מספרי מרסן ראשוניים. אך ההפך אינו נכון: <math>\ M_n</math> יכול להיות פריק כאשר <math>\ n</math> ראשוני. לדוגמה, <math>\ 2^{11}-1=23\cdot 89</math>.

נכון ל-2019 מספר מרסן הראשוני הגדול ביותר שהתגלה הוא מספר מרסן הראשוני ה-51, <math>\ 2^{82,589,933}-1</math>. למספר זה 24,862,048 ספרות עשרוניות והוא התגלה על ידי מיזם GIMPS.
==החיפוש אחר מספרי מרסן ראשוניים==
קיימים אלגוריתמים מהירים למציאת מספרי מרסן ראשוניים (כמו מבחן לוקאס-להמר למספרי מרסן), וכתוצאה מכך המספרים הראשוניים הגדולים ביותר הידועים היום הם מספרי מרסן.

החל מסוף המאה ה-20 התפתח מאוד התחום של חישוב מבוזר קהילתי. מציאת מספר ראשוני גדול כרוכה בפעולות חישוביות רבות, אך ניתן לחלק את כלל המספרים לבדיקה בין משתמשים רבים כך שכל אחד בודק מספר אחר, ובדרך כלל יוקצה מספר זהה לשני בודקים שונים. בדרך זו גדלים הסיכויים למצוא מספרים אלה, אם כי בהחלט ייתכן שמספר גדול יותר יימצא לפני מספרים קטנים ממנו. למעשה, נכון ליוני 2021, נבדקו כל מספרי מרסן ברצף עד המספר <math>\ 2^{102,887,301}-1</math> לפחות פעם אחת.

המיזם שנטל על עצמו את ניהול המספרים, הקצאתם לבדיקה ובדיקת התוצאות החוזרות הוא GIMPS. גוף זה גם מכריז על מספרי מרסן ראשוניים חדשים שנתגלו, מעת לעת.
* ב-23 באוגוסט 2008 התגלה מספר מרסן הראשוני ה-47, <math>\ 2^{43,112,609}-1</math>. מספר זה, שהתגלה במחלקה למתמטיקה של אוניברסיטת קליפורניה בלוס אנג'לס, הוא בן 12,978,189 ספרות עשרוניות. מספר זה הוכרז כמנצח הפרס בן $100,000 מטעם קרן החזית האלקטרונית.
* ב-6 בספטמבר 2008 התגלה מספר מרסן הראשוני ה-45, <math>\ 2^{37,156,667}-1</math>. למספר זה 11,185,272 ספרות עשרוניות והוא התגלה על ידי משתמש גרמני מעיר ליד קלן בגרמניה. זה היה מספר מרסן הראשוני הראשון שנתגלה באופן בלתי רציף מאז 1988.
* ב-17 בספטמבר 2015 נשלחה ממחשבו של קורטיס קופר הודעה לשרת מיזם GIMPS על גילוי מספר מרסן הראשוני ה-49. אולם, בגלל באג תוכנתי, ההודעה לא התקבלה. כך נשאר מספר זה עלום עד עבודות התחזוקה השוטפות של השרת, כשלושה חודשים וחצי לאחר מכן. ב-7 בינואר 2016 הוכרז המספר באופן רשמי אך, תאריך הגילוי הקובע הוא היום בו נשלחה לראשונה (17 בספטמבר 2015) ההודעה לשרת. קביעה זו באה בעקבות המקרה שאירע ב-3 בנובמבר 1961. ביום זה קרא אלכסנדר הורביץ את תדפיס המחשב שלו מהסוף להתחלה (מאחר שזו הדרך שבה נערם. בדומה למדפסת המפיקה דו"ח מההתחלה לסוף כך שהדף הראשון של הדו"ח יימצא בתחתית הערמה) והבחין במספר מרסן הראשוני ה-20, <math>\ 2^{4,423}-1</math> מספר שניות לפני מספר מרסן הראשוני ה-19, <math>\ 2^{4,253}-1</math>, אף על פי שהמספר הקטן התגלה מוקדם יותר. מכאן ש-<math>\ 2^{4,253}-1</math> נחשב ל"מספר מרסן הראשוני שמעולם לא היה הגדול ביותר" כשהתגלה.

GIMPS העניקו $50,000 למחלקה למתמטיקה של אוניברסיטת קליפורניה בלוס אנג'לס, $25,000 מיועדים לצדקה ורוב שאר הכסף יועבר למגלים של ששת מספרי מרסן הראשוניים האחרונים.

למגלי המספר הראשוני הראשון שלו מאה מיליון ספרות ממתין פרס בן $150,000 מטעם קרן החזית האלקטרונית.

==רשימת מספרי מרסן ראשוניים==

{| class="wikitable"
|-
! #
! חזקה
! מספר מרסן
! מספר ספרות
! תאריך גילוי
! מגלה
! שיטה
|-
| style="text-align:right;"| 1
| style="text-align:right;"| 2
| style="text-align:right;"| 3
| style="text-align:right;"| 1
| 430 לפנה"ס
| מתמטיקאים יווניים
| חלוקה נסיונית
|-
| style="text-align:right;"| 2
| style="text-align:right;"| 3
| style="text-align:right;"| 7
| style="text-align:right;"| 1
| 430 לפנה"ס
| מתמטיקאים יווניים
| חלוקה נסיונית
|-
| style="text-align:right;"| 3
| style="text-align:right;"| 5
| style="text-align:right;"| 31
| style="text-align:right;"| 2
| 300 לפנה"ס
| מתמטיקאים יווניים
| חלוקה נסיונית
|-
| style="text-align:right;"| 4
| style="text-align:right;"| 7
| style="text-align:right;"| 127
| style="text-align:right;"| 3
| 300 לפנה"ס
| מתמטיקאים יווניים
| חלוקה נסיונית
|-
| style="text-align:right;"| 5
| style="text-align:right;"| 13
| style="text-align:right;"| 8191
| style="text-align:right;"| 4
| 1456
| אלמוני
| חלוקה נסיונית
|-
| style="text-align:right;"| 6
| style="text-align:right;"| 17
| style="text-align:right;"| 131071
| style="text-align:right;"| 6
| 1588
| פייטרו קטלדי
| חלוקה נסיונית
|-
| style="text-align:right;"| 7
| style="text-align:right;"| 19
| style="text-align:right;"| 524287
| style="text-align:right;"| 6
| 1588
| פייטרו קטלדי
| חלוקה נסיונית
|-
| style="text-align:right;"| 8
| style="text-align:right;"| 31
| style="text-align:right;"| 2147483647
| style="text-align:right;"| 10
| 1772
| לאונרד אוילר
| חלוקה נסיונית מתקדמת
|-
| style="text-align:right;"| 9
| style="text-align:right;"| 61
| style="text-align:right;"| 2305843009213693951
| style="text-align:right;"| 19
| נובמבר 1883
| איבן פרוושין
| סדרת לוקאס
|-
| style="text-align:right;"| 10
| style="text-align:right;"| 89
| style="text-align:right;"| 618970019642…137449562111
| style="text-align:right;"| 27
| יוני 1911
| ראלף פאוורס
| סדרת לוקאס
|-
| style="text-align:right;"| 11
| style="text-align:right;"| 107
| style="text-align:right;"| 162259276829…578010288127
| style="text-align:right;"| 33
| 1 ביוני 1914
| ראלף פאוורס
| סדרת לוקאס
|-
| style="text-align:right;"| 12
| style="text-align:right;"| 127
| style="text-align:right;"| 170141183460…715884105727
| style="text-align:right;"| 39
| 10 בינואר 1876
| אדואר לוקאס
| סדרת לוקאס
|-
| style="text-align:right;"| 13
| style="text-align:right;"| 521
| style="text-align:right;"| 686479766013…291115057151
| style="text-align:right;"| 157
| 30 בינואר 1952
| רפאל רובינזון
| מבחן לוקאס-להמר למספרי מרסן / מחשב SWAC
|-
| style="text-align:right;"| 14
| style="text-align:right;"| 607
| style="text-align:right;"| 531137992816…219031728127
| style="text-align:right;"| 183
| 30 בינואר 1952
| רפאל רובינזון
| מבחן לוקאס-להמר למספרי מרסן / מחשב SWAC
|-
| style="text-align:right;"| 15
| style="text-align:right;"| 1,279
| style="text-align:right;"| 104079321946…703168729087
| style="text-align:right;"| 386
| 25 ביוני 1952
| רפאל רובינזון
| מבחן לוקאס-להמר למספרי מרסן / מחשב SWAC
|-
| style="text-align:right;"| 16
| style="text-align:right;"| 2,203
| style="text-align:right;"| 147597991521…686697771007
| style="text-align:right;"| 664
| 7 באוקטובר 1952
| רפאל רובינזון
| מבחן לוקאס-להמר למספרי מרסן / מחשב SWAC
|-
| style="text-align:right;"| 17
| style="text-align:right;"| 2,281
| style="text-align:right;"| 446087557183…418132836351
| style="text-align:right;"| 687
| 9 באוקטובר 1952
| רפאל רובינזון
| מבחן לוקאס-להמר למספרי מרסן / מחשב SWAC
|-
| style="text-align:right;"| 18
| style="text-align:right;"| 3,217
| style="text-align:right;"| 259117086013…362909315071
| style="text-align:right;"| 969
| 8 בספטמבר 1957
| האנס רייזל
| מבחן לוקאס-להמר למספרי מרסן / מחשב BESK
|-
| style="text-align:right;"| 19
| style="text-align:right;"| 4,253
| style="text-align:right;"| 190797007524…815350484991
| style="text-align:right;"| 1,281
| 3 בנובמבר 1961
| אלכסנדר הורביץ
| מבחן לוקאס-להמר למספרי מרסן / מחשב IBM 7090
|-
| style="text-align:right;"| 20
| style="text-align:right;"| 4,423
| style="text-align:right;"| 285542542228…902608580607
| style="text-align:right;"| 1,332
| 3 בנובמבר 1961
| אלכסנדר הורביץ
| מבחן לוקאס-להמר למספרי מרסן / מחשב IBM 7090
|-
| style="text-align:right;"| 21
| style="text-align:right;"| 9,689
| style="text-align:right;"| 478220278805…826225754111
| style="text-align:right;"| 2,917
| 11 במאי 1963
| דונלד גיליס
| מבחן לוקאס-להמר למספרי מרסן / מחשב ILLIAC II
|-
| style="text-align:right;"| 22
| style="text-align:right;"| 9,941
| style="text-align:right;"| 346088282490…883789463551
| style="text-align:right;"| 2,993
| 16 במאי 1963
| דונלד גיליס
| מבחן לוקאס-להמר למספרי מרסן / מחשב ILLIAC II
|-
| style="text-align:right;"| 23
| style="text-align:right;"| 11,213
| style="text-align:right;"| 281411201369…087696392191
| style="text-align:right;"| 3,376
| 2 ביוני 1963
| דונלד גיליס
| מבחן לוקאס-להמר למספרי מרסן / מחשב ILLIAC II
|-
| style="text-align:right;"| 24
| style="text-align:right;"| 19,937
| style="text-align:right;"| 431542479738…030968041471
| style="text-align:right;"| 6,002
| 4 במרץ 1971
| בריינט טקרמן
| מבחן לוקאס-להמר למספרי מרסן / מחשב IBM 360/91
|-
| style="text-align:right;"| 25
| style="text-align:right;"| 21,701
| style="text-align:right;"| 448679166119…353511882751
| style="text-align:right;"| 6,533
| 30 באוקטובר 1978
| לנדון נול ולורה ניקל
| מבחן לוקאס-להמר למספרי מרסן / מחשב CDC Cyber 174
|-
| style="text-align:right;"| 26
| style="text-align:right;"| 23,209
| style="text-align:right;"| 402874115778…523779264511
| style="text-align:right;"| 6,987
| 9 בפברואר 1979
| לנדון נול
| מבחן לוקאס-להמר למספרי מרסן / מחשב CDC Cyber 174
|-
| style="text-align:right;"| 27
| style="text-align:right;"| 44,497
| style="text-align:right;"| 854509824303…961011228671
| style="text-align:right;"| 13,395
| 8 באפריל 1979
| הארי נלסון ודייוויד סלווינסקי
| מבחן לוקאס-להמר למספרי מרסן / מחשב Cray 1
|-
| style="text-align:right;"| 28
| style="text-align:right;"| 86,243
| style="text-align:right;"| 536927995502…209433438207
| style="text-align:right;"| 25,962
| 25 בספטמבר 1982
| דייוויד סלווינסקי
| מבחן לוקאס-להמר למספרי מרסן / מחשב Cray 1
|-
| style="text-align:right;"| 29
| style="text-align:right;"| 110,503
| style="text-align:right;"| 521928313341…083465515007
| style="text-align:right;"| 33,265
| 29 בינואר 1988
| וולטר קולקוויט ולוק וולש
| מבחן לוקאס-להמר למספרי מרסן / מחשב NEC SX-2
|-
| style="text-align:right;"| 30
| style="text-align:right;"| 132,049
| style="text-align:right;"| 512740276269…455730061311
| style="text-align:right;"| 39,751
| 19 בספטמבר 1983
| דייוויד סלווינסקי
| מבחן לוקאס-להמר למספרי מרסן / מחשב Cray X-MP
|-
| style="text-align:right;"| 31
| style="text-align:right;"| 216,091
| style="text-align:right;"| 746093103064…103815528447
| style="text-align:right;"| 65,050
| 1 בספטמבר 1985
| דייוויד סלווינסקי
| מבחן לוקאס-להמר למספרי מרסן / מחשב Cray X-MP/24
|-
| style="text-align:right;"| 32
| style="text-align:right;"| 756,839
| style="text-align:right;"| 174135906820…328544677887
| style="text-align:right;"| 227,832
| 17 בפברואר 1992
| דייוויד סלווינסקי ופול גייג'
| מבחן לוקאס-להמר למספרי מרסן. מחשב Cray-2
|-
| style="text-align:right;"| 33
| style="text-align:right;"| 859,433
| style="text-align:right;"| 129498125604…243500142591
| style="text-align:right;"| 258,716
| 4 בינואר 1994
| דייוויד סלווינסקי ופול גייג'
| מבחן לוקאס-להמר למספרי מרסן / מחשב Cray C90
|-
| style="text-align:right;"| 34
| style="text-align:right;"| 1,257,787
| style="text-align:right;"| 412245773621…976089366527
| style="text-align:right;"| 378,632
| 3 בספטמבר 1996
| דייוויד סלווינסקי ופול גייג'
| מבחן לוקאס-להמר למספרי מרסן / מחשב Cray T94
|-
| style="text-align:right;"| 35
| style="text-align:right;"| 1,398,269
| style="text-align:right;"| 814717564412…868451315711
| style="text-align:right;"| 420,921
| 13 בנובמבר 1996
| GIMPS / ג'ואל ארמנגאוד
| מבחן לוקאס-להמר למספרי מרסן / תוכנת Prime95 / מחשב מגהרץ 90 Pentium
|-
| style="text-align:right;"| 36
| style="text-align:right;"| 2,976,221
| style="text-align:right;"| 623340076248…743729201151
| style="text-align:right;"| 895,932
| 24 באוגוסט 1997
| GIMPS / גורדון ספנסר
| מבחן לוקאס-להמר למספרי מרסן / תוכנת Prime95 /מחשב מגהרץ 100 Pentium
|-
| style="text-align:right;"| 37
| style="text-align:right;"| 3,021,377
| style="text-align:right;"| 127411683030…973024694271
| style="text-align:right;"| 909,526
| 27 בינואר 1998
| GIMPS / רולנד קלרקסון
| מבחן לוקאס-להמר למספרי מרסן / תוכנת Prime95 / מחשב מגהרץ 200 Pentium
|-
| style="text-align:right;"| 38
| style="text-align:right;"| 6,972,593
| style="text-align:right;"| 437075744127…142924193791
| style="text-align:right;"| 2,098,960
| 1 ביוני 1999
| GIMPS / נאיאן הג'ראטוולא
| מבחן לוקאס-להמר למספרי מרסן / תוכנת Prime95 / מחשב מגהרץ 350 Pentium 2
|-
| style="text-align:right;"| 39
| style="text-align:right;"| 13,466,917
| style="text-align:right;"| 924947738006…470256259071
| style="text-align:right;"| 4,053,946
| 14 בנובמבר 2001
| GIMPS / מייקל קמרון
| מבחן לוקאס-להמר למספרי מרסן / תוכנת Prime95 / מחשב מגהרץ 800 Athlon T-Bird
|-
| style="text-align:right;"| 40
| style="text-align:right;"| 20,996,011
| style="text-align:right;"| 125976895450…762855682047
| style="text-align:right;"| 6,320,430
| 17 בנובמבר 2003
| GIMPS / מייקל שאפר
| מבחן לוקאס-להמר למספרי מרסן / תוכנת Prime95 /מחשב 2 גיגה-הרץ Dell Dimension
|-
| style="text-align:right;"| 41
| style="text-align:right;"| 24,036,583
| style="text-align:right;"| 299410429404…882733969407
| style="text-align:right;"| 7,235,733
| 15 במאי 2004
| GIMPS / ג'וש פינדלי
| מבחן לוקאס-להמר למספרי מרסן / תוכנת Prime95 / מחשב 2.4 גיגה-הרץ Pentium 4
|-
| style="text-align:right;"| 42
| style="text-align:right;"| 25,964,951
| style="text-align:right;"| 122164630061…280577077247
| style="text-align:right;"| 7,816,230
| 18 בפברואר 2005
| GIMPS / מרטין נובאק
| מבחן לוקאס-להמר למספרי מרסן / תוכנת Prime95 / מחשב 2.4 גיגה-הרץ Pentium 4
|-
| style="text-align:right;"| 43
| style="text-align:right;"| 30,402,457
| style="text-align:right;"| 315416475618…411652943871
| style="text-align:right;"| 9,152,052
| 15 בדצמבר 2005
| GIMPS / קורטיס קופר
| מבחן לוקאס-להמר למספרי מרסן / תוכנת Prime95 / מחשב 2 גיגה-הרץ Pentium 4
|-
| style="text-align:right;"| 44
| style="text-align:right;"| 32,582,657
| style="text-align:right;"| 124575026015…154053967871
| style="text-align:right;"| 9,808,358
| 4 בספטמבר 2006
| GIMPS / קורטיס קופר וסטיבן בון
| מבחן לוקאס-להמר למספרי מרסן / תוכנת Prime95 / מחשב 3 גיגה-הרץ Pentium 4
|-
| style="text-align:right;"| 45
| style="text-align:right;"| 37,156,667
| style="text-align:right;"| 202254406890…022308220927
| style="text-align:right;"| 11,185,272
| 6 בספטמבר 2008
| GIMPS / האנס-מייקל אלוניץ'
| מבחן לוקאס-להמר למספרי מרסן / תוכנת Prime95 / מחשב 2.83 גיגה-הרץ Core 2 Duo
|-
| style="text-align:right;"| 46
| style="text-align:right;"| 42,643,801
| style="text-align:right;"| 169873516452…765562314751
| style="text-align:right;"| 12,837,064
| 12 באפריל 2009
| GIMPS / אוד סטרינדמו
| מבחן לוקאס-להמר למספרי מרסן / תוכנת Prime95 / מחשב 3 גיגה-הרץ Core 2 Duo
|-
| style="text-align:right;"| 47
| style="text-align:right;"| 43,112,609
| style="text-align:right;"| 316470269330…166697152511
| style="text-align:right;"| 12,978,189
| 23 באוגוסט 2008
| GIMPS / אדסון סמית'
| מבחן לוקאס-להמר למספרי מרסן / תוכנת Prime95 / מחשב 745 מגהרץ Dell Optiplex
|-
| style="text-align:right;"| 48
| style="text-align:right;"| 57,885,161
| style="text-align:right;"| 581887266232…071724285951
| style="text-align:right;"| 17,425,170
| 25 בינואר 2013
| GIMPS / קורטיס קופר
| מבחן לוקאס-להמר למספרי מרסן / תוכנת Prime95 /מחשב 3 גיגה-הרץ Core 2 Duo
|-
| style="text-align:right;"| 49
| style="text-align:right;"| 74,207,281
| style="text-align:right;"| 300376418084…287190498687
| style="text-align:right;"| 22,338,618
| 17 בספטמבר 2015
| GIMPS / קורטיס קופר
| מבחן לוקאס-להמר למספרי מרסן / תוכנת Prime95 Intel i7-4790 @ 3.60GHz
|-
| style="text-align:right;"| 50
| style="text-align:right;"| 77,232,917
| style="text-align:right;"| 467333183359…069762179071
| style="text-align:right;"| 23,249,425
| 26 בדצמבר 2017
| GIMPS / ג'ונתן פייס
| מבחן לוקאס-להמר למספרי מרסן / תוכנת Prime95 Intel i5-6600 @ 3.30GHz
|-
| style="text-align:right;"| 51
| style="text-align:right;"| 82,589,933
| style="text-align:right;"| 325217902591…148894445742 
| style="text-align:right;"| 24,862,048
| 7 בדצמבר 2018
| GIMPS / פטריק לארוץ'
| מבחן לוקאס-להמר למספרי מרסן / תוכנת Prime95 Intel i5-4590T @ 2.0GHz
|}

==ראו גם==
*קבוע ארדש-בורוויין
*מרסן (אסטרואיד)
*פרנק נלסון קול
*מספר פרמה

==קישורים חיצוניים ==

* [http://www.mersenne.org אתר GIMPS] - המרכז את החיפוש אחר מספרי מרסן חדשים.
* [https://web.archive.org/web/20120430081231/http://kaye7.school.org.il/number_types.htm#%D7%9E%D7%A1%D7%A4%D7%A8%D7%99_%D7%9E%D7%A8%D7%A1%D7%9F מספרי מרסן/טיפוסי מספרים בתורת המספרים באתר של המרכז לתכנון לימודים במכללת קיי, באר-שבע]
* 
* 
* 

== הערות שוליים ==

קטגוריה:תורת המספרים
קטגוריה:חישוב מבוזר קהילתי
קטגוריה:בעיות פתוחות בתורת המספרים
קטגוריה:מספרים ראשוניים