חידות - מספרים ענקיים

מספרים ענקיים

בדיקת נכונותו של המשפט האחרון של פרמה באמצעות מחשב התקדמה בקצב גובר הולך. אבני דרך אחדות:
בשנת 1937 נמצא המשפט נכון לכל החזקות עד 617, בשנת 1955 הוגבה הרף ל-4,001, בשנת 1976 ל-125,000, ובשנת 1992 הוכחה נכונות המשפט לכל חזקה עד ארבעה מיליון!
שילוב תוצאה זו עם הוכחה אליה הגיעה סופי ז'רמן הוביל למסקנה שאם יש דוגמה נגדית למשפ פרמה, הרי כרוך בה חישוב של מספר גדול מארבעה מיליון בחזקת ארבעה מיליון. לעומת מספר זה מתגמד גם מספר החלקיקים ביקום כולו, כך שלא קל למצוא דוגמא נגדית כזו.
גם בחידות הבאות נגיע למספרים ענקיים, החורגים מגבולות הדמיון.

האם יאבד ביל גייטס את כל הונו?

הונו של ביל גייטס, המוחזק במניות של חברת "מיקרוסופט", נאמד כעת ב-72 מיליארד דולר. על-פי תחזיות אופטימיות של האנליסטים, יגיע הון זה בשנת 2005 לסך טריליון ( 10¹²) דולר. נמשיך מכאן בתחזית פחות אופטימית, בדיונית לחלוטין.

בשנת 2005 הכריז ביל גייטס על מערכת ההפעלה החדשה "חלונות 2005". בהכרזה הטלביזיונית, שבה צפו בהתרגשות כל 7 מיליארד תושבי כדור הארץ, אמר גייטס:

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

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

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

תרומותיו של ביל גייטס גדלות בטור הנדסי. לאחר n באגים מגיע סכומו של טור זה ל- 2ⁿ-1 דולר. חרף הסכומים הצנועים המופיעים באיבריו הראשונים של הטור, הרי כבר לאחר 40 באגים יעבור סכום הטור את הונו ההתחלתי של ביל גייטס, כלומר סכום הטור יהיה גדול מטריליון דולר. קל להגיע לתוצאה זו גם בחישוב מהיר בעל-פה, ללא הסתייעות במחשבון, שהרי, כידוע, 2¹⁰ = 1024 > 10³, ולכן 2⁴⁰ > 10¹².

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

מגדלי האנוי

"במקדש הגדול בבנרס שלושה מוטות יהלום, עליהם מונחות 64 דיסקיות זהב בגדלים שונים. עם בריאת העולם, הניח האל ברהמה את כל הדיסקיות על אחד המוטות, מסודרות לפי גודלן, כך שהדיסקית בעלת הקוטר הגדול ביותר נמצאת בתחתית, והדיסקית העליונה היא הקטנה ביותר. על הנזירים שבמקדש מוטלת החובה להעביר את מגדל הדיסקיות מהמוט המקורי לאחד משני המוטות האחרים, והם ממלאים את חובתם זו ללא הרף. העברת הדיסקיות נעשית לפי הכללים הבאים:
בכל פעם מותר להעביר דיסקית אחת בלבד;
לעולם אין לשים דיסקית על דיסקית קטנה ממנה.
כאשר ישלימו הנזירים את משימתם, יקיץ הקץ על העולם".

אגדה מיתולוגית זו אינה כה עתיקה כפי שניתן לשער מקריאתה. האגדה חוברה בשנת 1883 על-ידי המתמטיקאי הצרפתי אדוארד לוקאס (Edouard Lucas), ופורסמה תחת השם הבדוי "פרופ' קלאוס", שהוא אנגרם של השם המקורי. יחד עם האגדה הופץ בצרפת צעצוע בשם "מגדלי האנוי", שהיווה מודל מצומצם של האגדה, הן מבחינת מספר הדיסקיות (שמונה בלבד) והן מבחינת מחיר חומר הגלם. מאז נפוץ משחק זה בצורות מגוונות. ניתן ליצור במהירות עותק של המשחק באמצעות שמונה קלפים ממוספרים מ-1 ועד 8. הנה דוגמה של התהליך במגדל שגובהו 4 דיסקיות בלבד (אל דאגה, מגדל כה נמוך אינו משפיע על גורל העולם).

בהנחה שהנזירים היעילים והמסורים מעבירים בכל שניה דיסקית אחת ממוט למוט, מתי יקיץ הקץ על העולם?

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

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

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

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

מתיאור האלגוריתם נובע שאם להעברת מגדל בן 1-n דיסקיות נחוצות M העברות, הרי להעברת מגדל בן n דיסקיות נחוצות 2·M+1 העברות. להעברת מגדל שבו יש רק דיסקית אחת נחוצה העברה אחת, ולכן להעברת מגדל בן n דיסקיות נחוצות 2ⁿ-1 העברות.

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

.1+2¹+2²+2³+...+2^n-1 = 2ⁿ-1

במגדל שבהאנוי יש 64 דיסקיות, שלהעברתן נחוצות 2⁶⁴-1 העברות. הנזירים היעילים והמסורים מעבירים בכל שנייה דיסקית אחת ממוט למוט, ולכן יקיץ הקץ על העולם בעוד יותר מ- 580,000,000,000 שנים.

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

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

נמספר את הדיסקיות החל מ-1 לדיסקית העליונה ועד n לדיסקית התחתונה, ונמספר את כל הצעדים הנחוצים להשלמת המשימה במספרים בינאריים, החל מ-1 וכלה ב- 2ⁿ-1.
הייצוג הבינארי של המספר 2ⁿ-1 פשוט ביותר: זהו מספר שבו n ספרות שכולן 1. מספר הספרות במספר הבינארי שווה, אם כן, למספר הדיסקיות. בכל צעד, המיקום, החל מהקצה הימני של המספר, של הסיפרה 1 הימנית ביותר במספרו הבינארי של הצעד הוא מספרה של הדיסקית שאותה יש להזיז כעת. סיפרה זו היא הסיפרה היחידה שהשתנתה מ-0 ל-1 במעבר מהמספר הבינארי הקודם למספר הבינארי הנוכחי.

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

החידה של מגדלי האנוי מעלה עוד שאלות אחדות, שיוצגו כאן ללא פתרון:

כאשר אנו נמצאים בהעברה ה-k מתוך 2ⁿ-1 ההעברות הנחוצות להשלמת המשימה, מה מצב הדיסקיות, כלומר על איזה מוט מונחת כל דיסקית?
לכאורה ניתן לענות על שאלה זו באמצעות ביצוע k הצעדים, אך כבר התברר לנו שההמתנה עלולה להיות ממושכת מדי, ולכן יש לענות על השאלה באמצעות נוסחה שתיתן את מצב הדיסקיות ישירות על פי מספרה הסידורי של ההעברה.

השאלה ההפוכה: כאשר אנו רואים את הדיסקיות במצב נתון, מה מספרה הסידורי של ההעברה הנוכחית?

כאשר נתונים שלושה מוטות ומגדל של n דיסקיות, נחוצות 2ⁿ-1 העברות. אם נגדיל את מספר המוטות ל- n+1 די יהיה ב- 2n-1 העברות. כמה העברות נחוצות כאשר יש j מוטות, 3<j<n+1 ?

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

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

מספרי מרסן

בחידה של מגדלי האנוי, להעברת מגדל בן n דיסקיות נחוצות 2ⁿ-1 העברות. כאשר n אינו ראשוני, גם המספר 2ⁿ-1 אינו ראשוני (אם n=uv אז 2^uv-1 מתחלק ב-2^u-1). כאשר n הוא ראשוני, ייתכן שגם המספר 2ⁿ-1 הוא ראשוני. בשנת 1644 פרסם מרן מרסן (Marin Mersenne), ידידו של פרמה, טענה לפיה המספר 2^p-1 הוא ראשוני כאשר p=2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257 ואינו ראשוני לכל p אחר שקטן מ-257. מרסן, בדומה לפרמה, לא נתן הוכחה לטענתו זו.

בשנת 1772 הוכיח אוילר שהמספר 2³¹-1 הוא ראשוני. כמאה שנה אחר כך פיתח אדוארד לוקאס שיטה יעילה לבדיקת ראשוניותו של מספר מרסן. באמצעות שיטה זו, שהתבססה על סדרת פיבונאצ'י הראה לוקאס שהמספר 2¹²⁷-1 הוא ראשוני, ובמשך 75 שנה היה זה המספר הגדול ביותר הידוע כראשוני. כ-240 שנה לאחר פרסומה התגלה פגם ראשון בטענתו של מרסן: המספר 2⁶¹-1 , שאינו מופיע ברשימתו של מרסן, התגלה כראשוני.

בשנת 1903 הראה המתמטיקאי האמריקאי פרנק נלסון קול שהמספר 2⁶⁷-1, המופיע ברשימתו של מרסן, אינו ראשוני. אריק טמפל בל, היסטוריון של המתמטיקה בעל נטייה לדרמטיזציה, מתאר כיצד הציג קול את תגליתו בכנס של החברה המתמטית האמריקאית:

"קול, שתמיד היה ידוע כמי שממעט במילים, עלה לבמה, ובלי לומר מלה חישב על הלוח את המספר 2⁶⁷. מהתוצאה הפחית בזהירות 1, וקיבל מספר ובו 21 ספרות: 147,573,952,589,676,412,927. קול עבר לצדו האחר של הלוח וחישב את המכפלה 193,707,721 X 761,838,257,287. תוצאות שני החישובים נמצאו זהות. קהל המאזינים פרץ, לראשונה בתולדות מוסד זה, במחיאות כפיים סוערות. קול חזר למקומו בלי להוציא הגה מפיו. לאיש בקהל לא היו שאלות."

בהמשך התגלו עוד שני מספרים שחסרים ברשימתו של מרסן, והתברר שגם המספר 2²⁵⁷-1, המופיע ברשימתו של מרסן, אינו ראשוני. חרף חמש הטעויות שנתגלו בטענתו של מרסן, מספרים מהצורה 2ⁿ-1 קרויים מספרי מרסן, ואנו מגלים עניין מיוחד בראשוניים שבהם. בדיקת ראשוניות של מספרים גדולים, כמו אלה שמופיעים בטענתו של מרסן, מצריכה חישובים רבים, ולכן רק בשנת 1947 הסתיימה בדיקת הטענה, כלומר בדיקתם של כל מספרי מרסן שבהם p < 257. שלוש מאות שנה חלפו, אם כן, מיום שהעלה מרסן את טענתו ועד שנסתיימה בדיקתה, אך זמן זה קצר לעומת תחזיתו של מרסן, שאמר: "כדי לקבוע האם מספר בן 15 או 20 ספרות הוא ראשוני, לא יספיק כל הזמן שבעולם".

למירוץ אחר מספרי מרסן ראשוניים נרתם המחשב, וכעת ידועים 39 מספרי מרסן ראשוניים. האם יש אינסוף מספרי מרסן ראשוניים? האם יש אינסוף מספרי מרסן שאינם ראשוניים? התשובות לשאלות אלה אינן ידועות עדיין.

ככל שנוספו איברים ברשימת מספרי מרסן הראשוניים, כן גדלה עוצמת החישוב הנדרשת לגילוי איברים נוספים. עד לסוף המאה העשרים שימשו מחשבי-על להשגת עוצמת החישוב הנדרשת. לגילוי המספר ה-27 ברשימה, למשל, שימש, בשנת 1979, מחשב-על מסוג Cray-I. התפתחותה של רשת האינטרנט איפשרה להשיג את עוצמת החישוב הנדרשת באמצעות הפעלתם של אלפי מחשבים אישיים לביצוע המשימה.

המספר ה-36 ברשימה, שהתגלה בשנת ,1997 הוא 2^2976221-1. מגלה המספר, גורדון ספנס, אמריקאי בן 38, הסתפק במחשב פנטיום 100 שעבד במשך 15 יום על משימה זו. מספר מרסן ה-37, 2^3021377-1, התגלה על-ידי רולאנד קלארקסון, סטודנט בן 19 מקליפורניה.

מספר מרסן ה-38, 2^6972593-1, התגלה ב-1 ביוני 1999 על-ידי נאיאן חאג'רטוואלה. במספר זה יש יותר משני מיליון ספרות עשרוניות, והוא מזכה את מוצאו בפרס של 50,000 דולר שהובטח לראשון שימצא מספר ראשוני שבו יותר ממיליון ספרות עשרוניות. מה אתה מבזבז את זמננו בסיפורים על פרסים שכבר חולקו, אתם מתלוננים? יש במסגרת זו גם פרסים גדולים יותר שעדיין מחכים לזוכים.

מספר מרסן ה-41, 2^24036583-1, התגלה ב-15 במאי 2004 על-ידי ג'וש פינדלי מסיאטל. מאז התגלו עוד עשרה מספרי מרסן גדולים יותר, והגדול שבהם, 2^82,589,933-1, התגלה ב-7 בדצמבר 2018 על ידי פטריק לרוש.

חידתנו כאן היא, כמובן, מהו המספר הבא ברשימת מספרי מרסן הראשוניים? בפתרון החידה אינכם לבד. אתם מוזמנים להצטרף למירוץ האינטרנט הגדול אחר מספרי מרסן, שבו התגלו שלושת מספרי מרסן האחרונים עד כה, באמצעות ניצול הזמן הפנוי של אלפי מחשבים המשתתפים במשימה זו. התוכנית המשמשת למטרה זו מתבססת על שיטתו אדוארד לוקאס לבדיקת ראשוניותו של מספר מרסן, כפי ששוכללה בשנת 1930 בידי ד.ה. למר (D.H. Lehmer).

המשך לחידה הבאה

לרשימת החידות