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 ، لكن لا يوجد برهان يثبت استحالة وجودها. يجب أن تعمل دالتك انطلاقًا من التعريف، لا من افتراض أن المدخل زوجي.

مبتدئرياضيات ومحاكاة

+10

القاسم الحقيقي للعدد n هو قاسم موجب أصغر من n نفسه. العدد الكامل يساوي مجموع قواسمه الحقيقية: 6 = 1 + 2 + 3. يُعطى لك عدد صحيح موجب n. أعد true إذا كان n عددًا كاملًا، وfalse خلاف ذلك.

الدالة

isPerfect(n: integer) → boolean

ninteger: العدد الصحيح الموجب المراد اختباره
تُرجعboolean: صحيح إذا كان n يساوي مجموع قواسمه الحقيقية، وخطأ خلاف ذلك

القيود

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.

سؤال إضافي

كل عدد كامل زوجي يكون على الصورة 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 مرة واحدة لا مرتين، لأن 6 × 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 ضمن الأعداد الصحيحة، ولا يواجه هذه المشكلة مطلقًا.

أسئلة شائعة3

ما التعقيد الزمني للتحقق مما إذا كان العدد كاملًا؟

يستغرق جمع أزواج القواسم حتى √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، لكن لا يوجد برهان يثبت استحالة وجودها. يجب أن تعمل دالتك انطلاقًا من التعريف، لا من افتراض أن المدخل زوجي.

def isPerfect(n):
    # اكتب الكود هنا

اختبار #1

اختبار #2

اختبار #3

وسيط

n = 28

الإخراج المتوقع

true