Perfect Number

Q: מהי סיבוכיות הזמן של בדיקת מספר מושלם?

איסוף זוגות מחלקים עד √n דורש זמן של O(√n) ומקום של O(1) . עבור n = 10^8 , מדובר בכ־ 10^4 צעדים. בדיקת כל מועמד עד n / 2 דורשת זמן של O(n) , כלומר כ־ 5 × 10^7 צעדים עבור אותו קלט.

Q: כמה מספרים מושלמים יש מתחת ל־10^8?

חמישה: 6 , 28 , 496 , 8128 ו־ 33550336 . הם נעשים נדירים במהירות. הבא בתור, 8589869056 , אפילו לא נכנס למספר שלם בן 32 סיביות.

Q: האם קיימים מספרים מושלמים אי־זוגיים?

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

Q: מה ההבדל בין מספרים מושלמים, שופעים וחסרים?

השוו את סכום המחלקים האמיתיים למספר. אם הם שווים, המספר מושלם, כמו 28 . אם הסכום גדול יותר, המספר שופע, כמו 12 , שסכום המחלקים שלו הוא 16 . אם הסכום קטן יותר, המספר חסר, כמו כל מספר ראשוני, שהמחלק האמיתי היחיד שלו הוא 1 .

מתחיליםמתמטיקה וסימולציה

+10

מחלק ראוי של n הוא מחלק חיובי שקטן מ־n עצמו. מספר מושלם שווה לסכום המחלקים הראויים שלו: 6 = 1 + 2 + 3. נתון לך מספר שלם חיובי n. החזר true אם n מושלם, ו־false אחרת.

פונקציה

isPerfect(n: integer) → boolean

ninteger: המספר השלם החיובי לבדיקה
מחזירהboolean: true אם n שווה לסכום המחלקים האמיתיים שלו, אחרת false

אילוצים

1 ≤ n ≤ 10⁸

דוגמאות

קלט: n = 28
פלט: true
הסבר: המחלקים הראויים של 28 הם 1, 2, 4, 7 ו־14. סכומם הוא 28, ולכן 28 הוא מספר מושלם.

קלט: n = 12
פלט: false
הסבר: המחלקים האמיתיים של 12 הם 1, 2, 3, 4 ו-6. סכומם הוא 16, שעולה על 12.

קלט: n = 1
פלט: false
הסבר: ל־1 אין כלל מחלקים ראויים, לכן הסכום הוא 0, ולא 1.

+16 בדיקות נסתרות בשליחה

שאלת המשך

לכל מספר מושלם זוגי יש את הצורה 2^(p-1) × (2^p-1) כאשר 2^p-1 הוא ראשוני. האם תוכל לרשום את כל המספרים המושלמים הקטנים מ־10^8 באמצעות הנוסחה הזאת, בלי לבדוק כל מספר?

רמזים

פתחו אותם אחד אחד. כל רמז חושף קצת יותר.

נפתחו 0 מתוך 3

פתרון

ההגדרה מבקשת סכום של מחלקים, והלולאה המתבקשת בודקת כל מועמד עד n / 2. עבור n = 10^8 מדובר ב־5 × 10^7 פעולות חילוק. מחלקים מופיעים בזוגות שמכפלתם היא n, כך שאפשר לאסוף את שני האיברים בכל זוג ובמקביל לחפש רק עד √n, בערך 10^4 צעדים.

חבר כל מחלק אמיתי

נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר

האינטואיציה

פעלו לפי ההגדרה. בדקו כל d החל מ־1 כלפי מעלה, וכאשר n % d == 0, הוסיפו את d לסכום מצטבר. בסוף השוו את הסכום ל־n. עבור 28, הלולאה אוספת את 1, 2, 4, 7 ואת 14, ו־1 + 2 + 4 + 7 + 14 = 28.

אפשר לעצור ב־n / 2. מחלק שאינו n משאיר מנה של לפחות 2, ולכן הוא לעולם אינו גדול ממחצית n. הגבול מתאים גם ל־n = 1: הלולאה רצה אפס פעמים, הסכום נשאר 0, והתשובה היא false.

חלוקת הטווח לשניים אינה משנה את קצב הגידול. עבור n = 10^8, הלולאה עדיין רצה 5 × 10^7 פעמים, והיא עושה זאת עבור כל קלט בגודל הזה, בין אם הוא מחלק ובין אם לא.

אלגוריתם

הגדר את total ל־0.
עבור עם d מ־1 עד n / 2.
אם n % d == 0, הוסף את d ל־total.
החזר האם total == n.

def isPerfect(n):
    total = 0
    # No proper divisor of n is larger than n / 2.
    for d in range(1, n // 2 + 1):
        if n % d == 0:
            total += d
    return total == n

איסוף זוגות מחלקים עד השורש הריבועי

האינטואיציה

כש־d מחלק את n, גם n / d מחלק אותו. עבור 28 הזוגות הם 1 × 28, 2 × 14 ו־4 × 7. בכל זוג אחד מהאיברים קטן או שווה ל־√n, כי מכפלה של שני מספרים שגדולים מ־√n גדולה מ־n. לכן חיפוש עד √n מוצא כל זוג פעם אחת, ומוסיפים את שני האיברים תוך כדי החיפוש.

יש שני איברים שדורשים תשומת לב. הזוג 1 × n כולל את n עצמו, שאינו מחלק אמיתי: מתחילים את הסכום ב־1 ואת החיפוש ב־2. נקודת התחלה זו שגויה עבור n = 1, שהמחלק היחיד שלו הוא עצמו, ולכן מחזירים עבורו תחילה false. וכאשר n הוא ריבוע, השורש מופיע בזוג עם עצמו: עבור 36, צריך להוסיף את 6 פעם אחת ולא פעמיים.

כותבים את הגבול כך: d * d ≤ n, וכך נשארים במספרים שלמים. עבור n = 10^8 הלולאה נעצרת ב־d = 10^4, ולכן היא רצה בערך 10^4 פעמים במקום 5 × 10^7.

אלגוריתם

אם n == 1, יש להחזיר false.
יש להגדיר את total כ-1 ואת d כ-2.
כל עוד d * d ≤ n: אם d מחלק את n, יש להוסיף את d, ולהוסיף גם את n / d כאשר הוא שונה מ-d.
יש לעבור ל-d הבא.
יש להחזיר האם total == n.

def isPerfect(n):
    if n == 1:
        return False
    total = 1  # 1 divides every n > 1; n itself does not count
    d = 2
    while d * d <= n:
        if n % d == 0:
            total += d
            partner = n // d
            if partner != d:  # a square root pairs with itself: add it once
                total += partner
        d += 1
    return total == n

מלכודות ומקרי קצה

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

סופרים גם את n עצמו. הזוג 1 × n מוסיף את n, ואז נראה שלכל מספר יש סכום גדול מ-n. מתחילים את הסכום ב-1 ואת החיפוש ב-2.
קובעים ש-1 הוא מספר מושלם. כשהסכום מתחיל ב-1, עבור הקלט 1 מתקבלת ההשוואה 1 == 1. סכום המחלקים האמיתיים שלו הוא 0, לכן צריך לטפל בו לפני הלולאה.
מוסיפים את השורש הריבועי פעמיים. עבור 16, המחלקים האמיתיים הם 1, 2, 4 ו-8, וסכומם 15. הוספת 4 פעמיים נותנת 19.
עוצרים בתנאי d * d < n. כך מדלגים על השורש הריבועי כולו, ולכן 4 של 16 לעולם לא נספר.
קובעים את הגבול לפי שורש ריבועי בנקודה צפה. בדיוק יחיד, או מעל 2^53 בדיוק כפול, תוצאת השורש של ריבוע מושלם עלולה להיות קטנה באחד ולגרום להשמטת מחלק. הבדיקה d * d ≤ n נשארת במספרים שלמים, ולכן הבעיה הזאת לעולם לא מתרחשת.

שאלות נפוצות4

מהי סיבוכיות הזמן של בדיקת מספר מושלם?

איסוף זוגות מחלקים עד √n דורש זמן של O(√n) ומקום של O(1). עבור n = 10^8, מדובר בכ־10^4 צעדים. בדיקת כל מועמד עד n / 2 דורשת זמן של O(n), כלומר כ־5 × 10^7 צעדים עבור אותו קלט.

כמה מספרים מושלמים יש מתחת ל־10^8?

חמישה: 6, 28, 496, 8128 ו־33550336. הם נעשים נדירים במהירות. הבא בתור, 8589869056, אפילו לא נכנס למספר שלם בן 32 סיביות.

האם קיימים מספרים מושלמים אי־זוגיים?

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

מה ההבדל בין מספרים מושלמים, שופעים וחסרים?

השוו את סכום המחלקים האמיתיים למספר. אם הם שווים, המספר מושלם, כמו 28. אם הסכום גדול יותר, המספר שופע, כמו 12, שסכום המחלקים שלו הוא 16. אם הסכום קטן יותר, המספר חסר, כמו כל מספר ראשוני, שהמחלק האמיתי היחיד שלו הוא 1.

Python

def isPerfect(n):
    # כתבו כאן קוד

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

n = 28

צפוי

true