مسائل Project Euler من 1 إلى 5: حلول بالرياضيات و Python

ملخص

تعلم مشكلات Project Euler من 1 إلى 5 مفاهيم خوارزمية ورياضية أساسية: قواعد القابلية للقسمة، توليد المتتاليات، التحليل إلى عوامل أولية، ونظرية الأعداد. سنقوم بحل كل منها باستخدام أساليب القوة الغاشمة (brute-force) أولاً، ثم التحسين باستخدام رؤى رياضية مثل صيغ المتسلسلات الحسابية وغربال إراتوستينس.

يعد Project Euler مجموعة أسطورية من المشكلات الرياضية الحسابية التي تربط بين الرياضيات البحتة والبرمجة العملية. المشكلات المبكرة (1-5) بسيطة بشكل مخادع: فهي تبدو كتمارين مدرسية ولكنها تخفي دروساً خوارزمية عميقة. تعلمك حلولها بكفاءة تقنيات التحسين — مثل التخزين المؤقت (memoization)، والاختصارات الرياضية، والتفكير الخوارزمي — التي تتوسع لتشمل مشكلات أصعب.

في هذا الدليل، سنعمل على حل المشكلات من 1 إلى 5، مع عرض كل من حل القوة الغاشمة الساذج والنسخة المحسنة رياضياً لكل منها. سترى كيف يمكن لفهم الرياضيات الكامنة وراء المشكلة أن يقلل من وقت التشغيل من O(n) إلى O(1)، ولماذا يظل Project Euler مهماً في عام 2026 كساحة تدريب للتحضير للمقابلات وحل المشكلات الخوارزمية.

المشكلة 1: مجموع المضاعفات

المشكلة: أوجد مجموع كل مضاعفات 3 أو 5 الأقل من 1000.

هذه مسألة قابلية قسمة بحتة: قم بالمرور عبر الأرقام من 1 إلى 999، وتحقق مما إذا كان كل رقم يقبل القسمة بالتساوي على 3 أو 5، ثم اجمع الأرقام المطابقة.

حل القوة الغاشمة:

def sum_multiples_bruteforce(limit: int) -> int:
    """O(n) solution: iterate and check divisibility."""
    total = 0
    for i in range(limit):
        if i % 3 == 0 or i % 5 == 0:
            total += i
    return total

result = sum_multiples_bruteforce(1000)
print(result)  # 233168

الوقت: O(n)، المساحة: O(1). بسيط وصحيح، ولكنه بطيء للحدود الكبيرة.

الحل المحسن (المتسلسلة الحسابية):

البصيرة الرئيسية: مضاعفات 3 الأقل من 1000 تشكل متتالية حسابية (3، 6، 9، ...، 999). مجموع المتتالية الحسابية هو n * (first + last) / 2، حيث n هو العدد.

• مضاعفات 3: العدد = ⌊999/3⌋ = 333، المجموع = 333 * (3 + 999) / 2 = 166833
• مضاعفات 5: العدد = ⌊999/5⌋ = 199، المجموع = 199 * (5 + 995) / 2 = 99500
• مضاعفات 15 (التداخل): العدد = ⌊999/15⌋ = 66، المجموع = 66 * (15 + 990) / 2 = 33165

def sum_multiples_optimized(limit: int) -> int:
    """O(1) solution using arithmetic series."""
    def arithmetic_sum(divisor: int, ceiling: int) -> int:
        """Sum of multiples of divisor below ceiling."""
        n = (ceiling - 1) // divisor
        first = divisor
        last = n * divisor
        return n * (first + last) // 2

    sum_3 = arithmetic_sum(3, limit)
    sum_5 = arithmetic_sum(5, limit)
    sum_15 = arithmetic_sum(15, limit)

    return sum_3 + sum_5 - sum_15

result = sum_multiples_optimized(1000)
print(result)  # 233168

التعقيد: O(1) مقابل O(n). بالنسبة للحد 1,000,000، يقوم حل القوة الغاشمة بمليون تكرار؛ بينما يقوم الحل المحسن بـ 6 عمليات حسابية.

---

المشكلة 2: مجموع أعداد فيبوناتشي الزوجية

المشكلة: أوجد مجموع كل أعداد فيبوناتشي الزوجية الأقل من 4 ملايين.

تنتج متتالية فيبوناتشي (1، 1، 2، 3، 5، 8، 13، 21، ...) رقماً زوجياً في كل ثالث رقم (2، 8، 34، ...). نحن بحاجة إلى مجموعها.

حل القوة الغاشمة:

def even_fibonacci_sum_bruteforce(limit: int) -> int:
    """O(log limit) solution: generate Fibs (which grow exponentially), filter evens, sum."""
    a, b = 1, 1
    total = 0

    while b < limit:
        if b % 2 == 0:
            total += b
        a, b = b, a + b

    return total

result = even_fibonacci_sum_bruteforce(4_000_000)
print(result)  # 4613732

الوقت: O(log limit) — تنمو أعداد فيبوناتشي بشكل أسي، لذا فإن عدد أعداد فيبوناتشي الأقل من limit هو لوغاريتمي. المساحة: O(1).

الحل المحسن (كل ثالث رقم فيبوناتشي):

خاصية رياضية: كل ثالث رقم في متتالية فيبوناتشي هو رقم زوجي. إذا كان F(n) يمثل رقم فيبوناتشي النوني، فإن F(3k) يكون دائماً زوجياً.

لذا بدلاً من توليد كل أعداد فيبوناتشي وتصفيتها، قم بتوليد كل ثالث رقم مباشرة:

• E(n) = رقم فيبوناتشي الزوجي النوني
• E(1) = 2، E(2) = 8، E(3) = 34
• العلاقة التكرارية: E(n) = 4 * E(n-1) + E(n-2)

def even_fibonacci_sum_optimized(limit: int) -> int:
    """Skip to every third Fibonacci directly."""
    a, b = 2, 8  # First two even Fibs
    total = a

    while b < limit:
        total += b
        a, b = b, 4 * b + a  # Recurrence for even Fibs

    return total

result = even_fibonacci_sum_optimized(4_000_000)
print(result)  # 4613732

التعقيد: نفس O(log limit) للتكرار، ولكن تكرارات أقل بـ 3 مرات تقريباً (كل ثالث رقم بدلاً من كل رقم فيبوناتشي). التحسين هو معامل ثابت، وليس تقاربياً، ولكنه عملي للحد 4M.

---

المشكلة 3: أكبر عامل أولي

المشكلة: ما هو أكبر عامل أولي للعدد 600851475143؟

التحليل إلى عوامل أولية: تفكيك الرقم إلى قواسمه الأولية. نهج القوة الغاشمة يقسم على العوامل المرشحة؛ بينما يتحقق النهج المحسن فقط حتى √n ويستخدم القسمة التجريبية بكفاءة.

حل القوة الغاشمة:

def largest_prime_factor_bruteforce(n: int) -> int:
    """O(n) worst case: trial division by every integer up to n."""
    largest = 1
    for i in range(2, n + 1):
        while n % i == 0:
            largest = i
            n //= i
        if n == 1:
            break
    return largest

result = largest_prime_factor_bruteforce(600851475143)
print(result)  # 6857

الوقت: O(n) في أسوأ الحالات (عندما يكون n أولياً)، المساحة: O(1). هذا يعمل ولكنه بطيء جداً للمدخلات الكبيرة — بالنسبة لـ n ≈ 6×10^11 سيقوم بمئات المليارات من التكرارات قبل الانتهاء.

الحل المحسن (القسمة التجريبية حتى √n):

البصيرة الرئيسية: إذا كان لـ n عامل أكبر من √n، فإنه يمتلك على الأكثر عاملاً واحداً من هذا القبيل (مقترناً بعامل أقل من √n). لذا نحتاج فقط للقسمة التجريبية حتى √n. كما نتخطى الأعداد الزوجية بعد التعامل مع الرقم 2 صراحة.

def largest_prime_factor_optimized(n: int) -> int:
    """Optimized trial division up to sqrt(n)."""
    largest = -1

    # Check factor 2
    while n % 2 == 0:
        largest = 2
        n //= 2

    # Check odd factors from 3 onwards
    i = 3
    while i * i <= n:
        while n % i == 0:
            largest = i
            n //= i
        i += 2

    # Remaining n (if > 1) is prime
    if n > 1:
        largest = n

    return largest

result = largest_prime_factor_optimized(600851475143)
print(result)  # 6857

التعقيد: O(√n) مقابل O(n) للقوة الغاشمة. بالنسبة لـ n=600851475143، √n ≈ 775,146، لذا فإن النسخة المحسنة تكرر حوالي 390 ألف مرة (مع تخطي الأعداد الزوجية) بدلاً من القسمة التجريبية عبر حوالي 6×10^11 مرشحاً.

---

المشكلة 4: أكبر ناتج ضرب متناظر

المشكلة: أوجد أكبر عدد متناظر (palindrome) ناتج عن ضرب عددين يتكون كل منهما من 3 أرقام.

العدد المتناظر يقرأ بنفس الطريقة من الأمام والخلف (121، 1331، 12321). نحتاج إلى أكبر عدد يتكون من ضرب رقمين من 100-999.

حل القوة الغاشمة:

def is_palindrome(n: int) -> bool:
    """Check if n reads the same forwards and backwards."""
    s = str(n)
    return s == s[::-1]

def largest_palindrome_bruteforce() -> int:
    """O(n²): try all pairs, check palindrome for each."""
    largest = 0

    for i in range(100, 1000):
        for j in range(i, 1000):  # j >= i to avoid duplicates
            product = i * j
            if is_palindrome(product) and product > largest:
                largest = product

    return largest

result = largest_palindrome_bruteforce()
print(result)  # 906609

الوقت: O(n²) حيث n=900 (نطاق الأعداد المكونة من 3 أرقام)، أي حوالي 810,000 تكرار. المساحة: O(1).

الحل المحسن (تكرار عامل واحد تنازلياً):

البصيرة الرئيسية: بدلاً من التحقق من جميع النواتج، قم بتكرار عامل واحد تنازلياً من 999، وحساب النواتج، وتتبع أكبر عدد متناظر تم العثور عليه. هذا يتخطى العديد من الأزواج دون الحاجة للتحقق منها.

def largest_palindrome_optimized() -> int:
    """O(n²) but with early termination: iterate outer factor down."""

    def is_palindrome(n: int) -> bool:
        s = str(n)
        return s == s[::-1]

    max_palindrome = 0

    # Iterate i from 999 downward; once i*999 < max, stop
    for i in range(999, 99, -1):
        if i * 999 < max_palindrome:
            break
        for j in range(999, i - 1, -1):
            product = i * j
            if product < max_palindrome:
                break
            if is_palindrome(product):
                max_palindrome = product

    return max_palindrome

result = largest_palindrome_optimized()
print(result)  # 906609

التعقيد: لا يزال O(n²) في أسوأ الحالات، ولكن مع الإنهاء المبكر عندما تنخفض النواتج عن الحد الأقصى المعروف للعدد المتناظر. بالنسبة لهذه المشكلة، يكون التسريع حوالي 2-3 مرات بسبب التقليم (pruning).

---

المشكلة 5: أصغر عدد يقبل القسمة على 1-20

المشكلة: ما هو أصغر عدد موجب يقبل القسمة على جميع الأعداد الصحيحة من 1 إلى 20؟

هذا هو المضاعف المشترك الأصغر (LCM). تزيد القوة الغاشمة الرقم حتى تجد عدداً يقبل القسمة على الجميع؛ بينما يستخدم الحل المحسن التحليل إلى عوامل أولية وصيغة LCM.

حل القوة الغاشمة:

def smallest_divisible_bruteforce() -> int:
    """O(n * m): iterate n, check divisibility by 1-20."""
    n = 1

    while True:
        if all(n % i == 0 for i in range(1, 21)):
            return n
        n += 1

result = smallest_divisible_bruteforce()
print(result)  # 232792560

الوقت: O(k * lcm(1..20)) حيث k=20 (القواسم التي يتم التحقق منها لكل مرشح) — ما يقرب من 4.6 مليار عملية على هذا المدخل. بطيء جداً. المساحة: O(1).

الحل المحسن (التحليل إلى عوامل أولية + LCM):

المضاعف المشترك الأصغر هو حاصل ضرب أعلى القوى الأولية في التحليلات:

• LCM(1..20) = 2⁴ × 3² × 5 × 7 × 11 × 13 × 17 × 19
• = 16 × 9 × 5 × 7 × 11 × 13 × 17 × 19 = 232,792,560

from math import gcd

def lcm(a: int, b: int) -> int:
    """Least common multiple: lcm(a,b) = a*b / gcd(a,b)."""
    return (a * b) // gcd(a, b)

def smallest_divisible_optimized() -> int:
    """O(n log n): compute LCM of 1-20."""
    result = 1
    for i in range(1, 21):
        result = lcm(result, i)
    return result

result = smallest_divisible_optimized()
print(result)  # 232792560

بديل (التحليل المباشر إلى عوامل أولية):

def smallest_divisible_primes() -> int:
    """O(1): hardcode highest prime powers up to 20."""
    # Prime factorizations:
    # 2: 2^4 (from 16)
    # 3: 3^2 (from 9)
    # 5: 5^1
    # 7: 7^1
    # 11: 11^1
    # 13: 13^1
    # 17: 17^1
    # 19: 19^1
    return 2**4 * 3**2 * 5 * 7 * 11 * 13 * 17 * 19

result = smallest_divisible_primes()
print(result)  # 232792560

التعقيد: الحل المحسن هو O(n log n) حيث n=20 (كل gcd هي O(log result) والنتيجة تنمو إلى حوالي 232 مليون)، وهو أسرع بكثير من القوة الغاشمة O(k · lcm) ≈ 4.6 مليار عملية.

---

أهم النقاط المستفادة

1. الخصائص الحسابية تقلل التعقيد: تنخفض المشكلة 1 من O(n) إلى O(1) باستخدام صيغ المتسلسلات الحسابية.
2. التعرف على الأنماط: نمط "كل ثالث رقم فيبوناتشي" في المشكلة 2 يوفر تسريعاً بمقدار 3 أضعاف.
3. خدع الجذور التربيعية: تستفيد المشكلة 3 من حدود التحليل إلى عوامل √n.
4. العمل العكسي للتحسين: تنزل المشكلة 4 من الحد الأقصى للعثور على الإجابة بشكل أسرع.
5. استخدام نظرية الأعداد: تحل صيغة LCM في المشكلة 5 المسألة في أجزاء من الثانية بدلاً من ثوانٍ.

تضع هذه المشكلات المبكرة الأساس لتحديات أصعب. ومع تقدمك في Project Euler، تصبح هذه التقنيات — القابلية للقسمة، التحليل إلى عوامل، المتتاليات، والحساب المعياري — أدوات قياسية.

الخلاصة

تعد مشكلات Project Euler من 1 إلى 5 بوابة للتفكير الحسابي. إنها مباشرة بما يكفي ليتم حلها بشكل ساذج، ولكنها غنية بما يكفي لتعليم مبادئ تحسين دائمة. سواء كنت تتدرب للمقابلات، أو تعزز أساسياتك الرياضية، أو تستمتع ببساطة بالألغاز الخوارزمية، فإن هذه المشكلات تكافئ كلاً من إصرار القوة الغاشمة والبصيرة الرياضية.

يعكس الانتقال من القوة الغاشمة إلى الحلول المحسنة رحلة التحول إلى مبرمج أفضل: التعرف على الهيكل، تطبيق النظرية، والتعبير عن الأناقة في الكود. ابدأ بالمشكلات من 1 إلى 5، ثم انطلق للأمام بثقة.