מספר מרסן

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

מספרי מרסן (Mersenne numbers) הם מספרים שהם חזקה של 2 פחות 1, כלומר מן הצורה, \ M_n=2^n-1.

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

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

ב-4 בספטמבר 2006 התגלה מספר מרסן ה-44, שהוא המספר הראשוני הגדול ביותר הידוע כיום: \ 2^{32,582,657}-1. למספר זה 9,808,358 ספרות עשרוניות; כאחדים מקודמיו, מספר זה התגלה באמצעות חישוב מבוזר קהילתי. למגלי המספר הראשוני הראשון שלו עשרה מליון ספרות ממתין פרס בן $100,000 מטעם ה- Electronic Frontier Foundation.

[עריכה] ראו גם

[עריכה] קישורים חיצוניים