מספר מרסן

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

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

למספרי מרסן ראשוניים יש קשר הדוק למספרים משוכללים, שהם מספרים השווים לסכום מחלקיהם. מבחינה היסטורית, המחקר על מספרי מרסן בא מקשר זה: אוקלידס הראה במאה ה-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$ .

נכון ל-2019 מספר מרסן הראשוני הגדול ביותר שהתגלה הוא מספר מרסן הראשוני ה-51, $\ 2^{82,589,933}-1$ . למספר זה 24,862,048 ספרות עשרוניות והוא התגלה על ידי מיזם GIMPS.^[1]

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

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

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

המיזם שנטל על עצמו את ניהול המספרים, הקצאתם לבדיקה ובדיקת התוצאות החוזרות הוא 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.
ב-17 בספטמבר 2015 נשלחה ממחשבו של קורטיס קופר הודעה לשרת מיזם GIMPS על גילוי מספר מרסן הראשוני ה-49. אולם, בגלל באג תוכנתי, ההודעה לא התקבלה. כך נשאר מספר זה עלום עד עבודות התחזוקה השוטפות של השרת, כשלושה חודשים וחצי לאחר מכן. ב-7 בינואר 2016 הוכרז המספר באופן רשמי אך, תאריך הגילוי הקובע הוא היום בו נשלחה לראשונה (17 בספטמבר 2015) ההודעה לשרת. קביעה זו באה בעקבות המקרה שאירע ב-3 בנובמבר 1961. ביום זה קרא אלכסנדר הורביץ את תדפיס המחשב שלו מהסוף להתחלה (מאחר שזו הדרך שבה נערם. בדומה למדפסת המפיקה דו"ח מההתחלה לסוף כך שהדף הראשון של הדו"ח יימצא בתחתית הערמה) והבחין במספר מרסן הראשוני ה-20, $\ 2^{4,423}-1$ מספר שניות לפני מספר מרסן הראשוני ה-19, $\ 2^{4,253}-1$ , אף על פי שהמספר הקטן התגלה מוקדם יותר. מכאן ש- $\ 2^{4,253}-1$ נחשב ל"מספר מרסן הראשוני שמעולם לא היה הגדול ביותר" כשהתגלה.^[3]

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

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

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

#	חזקה	מספר מרסן	מספר ספרות	תאריך גילוי	מגלה	שיטה
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
49	74,207,281	300376418084…287190498687	22,338,618	17 בספטמבר 2015	GIMPS / קורטיס קופר	מבחן לוקאס-להמר למספרי מרסן / תוכנת Prime95‏ Intel i7-4790 @ 3.60GHz
50	77,232,917	467333183359…069762179071	23,249,425	26 בדצמבר 2017	GIMPS / ג'ונתן פייס	מבחן לוקאס-להמר למספרי מרסן / תוכנת Prime95‏ Intel i5-6600 @ 3.30GHz^[5]
51	82,589,933	325217902591…148894445742	24,862,048	7 בדצמבר 2018	GIMPS / פטריק לארוץ'	מבחן לוקאס-להמר למספרי מרסן / תוכנת Prime95‏ Intel i5-4590T @ 2.0GHz