Project Euler المسائل ١-٥: حلول باستخدام الرياضيات و 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(n) solution: generate all Fibs, 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 n) لتوليد أعداد فيبوناتشي (نمو أسي)، المساحة: 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 n) للتكرار، ولكن تكرارات أقل بـ 3 مرات تقريباً (كل ثالث عدد بدلاً من كل عدد فيبوناتشي). التحسين هو معامل ثابت، وليس تقاربياً، ولكنه عملي للحد 4M.

---

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

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

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

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

def largest_prime_factor_bruteforce(n: int) -> int:
    """O(n) worst case: trial division by all candidates."""
    factor = n

    # Remove factor 2
    while n % 2 == 0:
        factor = 2
        n //= 2

    # Try odd candidates up to n
    i = 3
    while i * i <= n:
        while n % i == 0:
            factor = i
            n //= i
        i += 2

    # If n > 1, then n itself is prime
    if n > 1:
        factor = n

    return factor

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

الوقت: O(√n)، المساحة: O(1). نكرر فقط حتى √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). الفرق في المعاملات الثابتة: النسخة المحسنة تتخطى الأعداد الزوجية. بالنسبة لـ n=600851475143، √n ≈ 775,146، لذا نكرر حوالي 390 ألف مرة بدلاً من 775 ألفاً.

---

المشكلة 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(lcm(1..20)) = O(232,792,560)، بطيء جداً. المساحة: 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(232M).

---

ما ستتعلمه

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، ثم انطلق للأمام بثقة.