בבלוג 65 הצבנו בפניכם שיטה לצמצום טווח החיפוש אחר המספר הראשוני הבא אחרי האחרון הידוע, כשלרשותנו כלי חיפוש "יווניים": אנו מחלקים את סדרת הראשוניים לשתי תת-קבוצות זרות ויוצרים מספר M השווה להפרש מכפלות הקבוצות. M לא יוכל להתחלק בראשוני כלשהו מהקבוצה כולה, כי הראשוני הזה כלול רק בתת-קבוצה אחת ונעדר מהשנייה ולכן לא יכול לחלק את הפרשן. מאחר שיש חלוקות רבות לשתי תת-קבוצות, השאלה היא כיצד נמצא את החלוקה הנותנת את ההפרש הקטן ביותר?
לשאלה הזאת יש תשובה פשוטה: ניצור את כל החלוקות והסכומים, נשווה ונמצא את החלוקה שהפרשה הוא הקטן ביותר. לדוגמה, עבור 2, 3, ו-5 יש בדיוק שלוש חלוקות:
2*3-5=1, 2*5-3=7, 3*5-2=13.
ברור ש-1 הוא הקטן ביותר, אך הוא אינו ראשוני ואינו מתחלק בשום מספר ראשוני. איך הוא השתרבב לתוצאות? פשוט מאוד – קבענו רק שהתוצאה לא תתחלק בשום מספר ראשוני, ו-1 עומד בתנאי הזה! התוצאה המפתיעה הזו אינה חד-פעמית. הנה עוד שתי דוגמאות:
M=(5*11*13)-(2*3*7*17)=715-714 = 1 :עבור 17
עבור 7: M=3*5-2*7=1
ןמכאן, עלינו לחפש את ההפרש הקטן ביותר השונה מ-1.
אם נעשה זאת בחישוב ידני - ניתקל בקושי: יש המון אפשרויות! כל תת-קבוצה מתוך n איברים ניתנת לבחירה על ידי ייחוס הספרה 1 לאיבר שנבחר ו-0 לאיבר שאינו כלול בה, כלומר: לכל איבר קיימות שתי אפשרויות, ולכן ישנן 2n תת-קבוצות, כולל הקבוצה כולה והקבוצה הריקה. מאחר שכל חלוקה כוללת שתי תת-קבוצות – הנבחרת והמשלימה – יש 2n-1 חלוקות.
מאחר שמכפלת הקבוצה כולה פחות הקבוצה הריקה הוא הההפרש המקסימלי, נשמיט אותו ולכן יהיה עלינו לבדוק "רק" 2n-1-1. אבל לגבי 21 המספרים הראשוניים הראשונים – פירושו של דבר יותר ממיליון חלוקות שונות, ואם נעבור לראשוניים גדולים יותר נקבל מספר חלוקות אסטרונומי אך יותר. האם יש דרך לצמצם את החיפוש להפרש הקטן ביותר או לפחות למצוא הפרש קטן יחסית, אם לא הקטן ביותר?
ננסה להבין מה אנו מחפשים: נסמן את מכפלת כל n הראשונים ברשימה ב-M, ואת מכפלת כל תת-קבוצה בחלוקה כלשהי ב-x.y, כך ש: y-x יהיה קטן ככל האפשר. בעיקרון, המספר הקטן ביותר מתקבל כאשר x ו-,y יהיו שורשי M, ואז ההפרש יהיה 0 – אך במקרה שלנו זה לא ייתכן, כי השניים שונים מאחר שהם זרים. לכן עלינו לחפש תת-קבוצה שמכפלתה קרובה ככל האפשר לשורש .M
ננתח דוגמה שכבר נתקלנו בה: קבוצת שבעת המספרים הראשונים עד 17. מספר החלוקות האפשרויות הוא 26-1=63. אם נכפול את כל שבעת המספרים הראשוניים נקבל 510,510=M. השורש נמצא בין 714 ל-715, ואכן קיבלנו לעיל את הפתרון x,y=714,715, אך הפרשם הוא 1. לכן נחפש פתרון נוסף שבו ה-x או ה-y יהיה המספר השני הכי קרוב לשורש, ונגלה שהפתרון הוא 107=770-663=(17*13*3)-(11*7*5*2) – כלומר, את הראשוני הבא עלינו לחפש בין 17 ל-107.
זה חסם פחות טוב מ: 34=17*2 לפי המשפט המופיע בבלוג 65 (חסם של 2n), אך הוא הרבה יותר טוב מהתוצאה "היוונית" – 510,509, ולא נזקקנו לשם כך ל"מתמטיקה גבוהה".
אמנון ז'קוב
הערה לגולשים
אם אתם חושבים שההסברים אינם ברורים מספיק או אם יש לכם שאלות הקשורות לנושא, אתם מוזמנים לכתוב על כך בפורום. אנו נתייחס להערותיכם. הצעות לשיפור וביקורת בונה יתקבלו תמיד בברכה.
