מספר מרסן

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

לא ידוע האם קיים מספר משוכלל אי-זוגי. נימוקים היוריסטיים מראים שהתשובה ככל הנראה שלילית.

החיפוש אחר מספרי מרסן ראשוניים[עריכת קוד מקור | עריכה]

קיימים אלגוריתמים מהירים למציאת מספרי מרסן ראשוניים (כמו מבחן לוקאס-להמר למספרי מרסן), וכתוצאה מכך המספרים הראשוניים הגדולים ביותר הידועים היום הם מספרי מרסן.

החל מתחילת המאה ה-21 התפתח מאוד התחום של חישוב מבוזר קהילתי. מציאת מספר ראשוני כרוכה בפעולות חישוביות רבות, אך ניתן לחלק את כלל המספרים לבדיקה בין משתמשים רבים כך שכל אחד בודק מספר אחר, ובדרך כלל יוקצה מספר זהה לשני בודקים שונים. בדרך זו גדלים הסיכויים למצוא מספרים אלה, אם כי בהחלט ייתכן שמספר גדול יותר יימצא לפני מספרים קטנים ממנו. למעשה, נכון לנובמבר 2009, נבדקו כל מספרי מרסן ברצף רק עד המספר \ 2^{27,506,209}-1.

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

  • ב-23 באוגוסט 2008 התגלה מספר מרסן הראשוני ה-47, \ 2^{43,112,609}-1. מספר זה, שהתגלה במחלקה למתמטיקה של אוניברסיטת קליפורניה בלוס אנג'לס, הוא בן 12,978,189 ספרות עשרוניות. מספר זה הוכרז כמנצח הפרס בן $100,000 מטעם קרן החזית האלקטרונית.
  • ב-6 בספטמבר 2008 התגלה מספר מרסן הראשוני ה-45, \ 2^{37,156,667}-1. למספר זה 11,185,272 ספרות עשרוניות והוא התגלה על ידי משתמש גרמני מעיר ליד קלן בגרמניה. זה היה מספר מרסן הראשוני הראשון שנתגלה באופן בלתי רציף מאז 1988. בשל שיטת החישוב המבוזר, ייתכן שיש מספרי מרסן קטנים ממנו.

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

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

רשימת מספרי מרסן ראשוניים[עריכת קוד מקור | עריכה]

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

ראו גם[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]