Project Euler مسائل 6-10: الأعداد الأولية، المربعات والمتتاليات

ملخص

تقدم المشكلات من 6 إلى 10 نظرية الأعداد الخوارزمية: حساب المجاميع والمربعات (المشكلة 6)، توليد الأعداد الأولية عبر غربال إراتوستينس (المشكلتان 7 و10)، معالجة الأرقام (المشكلة 8)، وثلاثيات فيثاغورس (المشكلة 9). تقفز الحلول من O(n) إلى O(n log log n) باستخدام الغرابيل والتحفيظ (memoization).

تمثل مشكلات Project Euler من 6 إلى 10 خطوة كبيرة في الصعوبة مقارنة بالمشكلات من 1 إلى 5. ستنتقل من القابلية البسيطة للقسمة إلى غرابيل الأعداد الأولية، خوارزميات النافذة المنزلقة (sliding-window)، ومعادلات ديوفانتوس. تعلمك هذه المشكلات تقنيات أساسية تتوسع لتشمل مجموعة الـ 100 مشكلة كاملة: غربال إراتوستينس هو حجر الأساس لأي عمل رياضي حاسوبي، وفهم ثلاثيات فيثاغورس يفتح الأبواب لحل مشكلات التوافيق.

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

المشكلة 6: الفرق بين مجموع المربعات ومربع المجموع

المشكلة: لأول 100 عدد طبيعي، أوجد الفرق بين مربع المجموع ومجموع المربعات. أي، احسب (1+2+...+100)² - (1²+2²+...+100²).

تختبر هذه المشكلة فهم الصيغ الرياضية مقابل الحساب الغاشم (brute computation).

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

def sum_square_difference_bruteforce(n: int) -> int:
    """O(n): compute both sums via iteration."""
    sum_of_squares = sum(i**2 for i in range(1, n + 1))
    square_of_sum = sum(range(1, n + 1)) ** 2
    return square_of_sum - sum_of_squares

result = sum_square_difference_bruteforce(100)
print(result)  # 25164150

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

الحل المحسن (الصيغ الرياضية المغلقة):

باستخدام الصيغ المعروفة:

• المجموع: 1+2+...+n = n(n+1)/2
• مجموع المربعات: 1²+2²+...+n² = n(n+1)(2n+1)/6

def sum_square_difference_optimized(n: int) -> int:
    """O(1): use closed-form formulas."""
    sum_n = n * (n + 1) // 2
    sum_of_squares = n * (n + 1) * (2 * n + 1) // 6

    square_of_sum = sum_n ** 2

    return square_of_sum - sum_of_squares

result = sum_square_difference_optimized(100)
print(result)  # 25164150

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

---

المشكلة 7: العدد الأولي رقم 10001

المشكلة: ما هو العدد الأولي رقم 10,001؟

يتطلب إيجاد العدد الأولي رقم n إما القسمة التجريبية (بطيئة) أو غربال إراتوستينس (سريع). هذا هو الدافع الكلاسيكي لتعلم الغرابيل.

حل القوة الغاشمة (القسمة التجريبية):

def is_prime_trial(n: int) -> bool:
    """Check primality via trial division up to sqrt(n)."""
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for i in range(3, int(n**0.5) + 1, 2):
        if n % i == 0:
            return False
    return True

def nth_prime_bruteforce(n: int) -> int:
    """O(n sqrt(n)): find nth prime by trial division."""
    count = 0
    candidate = 2

    while count < n:
        if is_prime_trial(candidate):
            count += 1
            if count == n:
                return candidate
        candidate += 1

result = nth_prime_bruteforce(10001)
print(result)  # 104743

الوقت: O(n√p) حيث p هو العدد الأولي رقم n (حوالي 104,743). هذا بطيء جدًا بالنسبة لـ n الكبيرة.

الحل المحسن (غربال إراتوستينس):

يقوم الغربال ببناء مصفوفة منطقية (boolean array) تحدد جميع الأعداد الأولية حتى حد معين، مع استبعاد الأعداد المركبة عن طريق تحديد مضاعفات كل عدد أولي.

def sieve_of_eratosthenes(limit: int) -> list[int]:
    """O(n log log n): sieve all primes up to limit."""
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False

    for i in range(2, int(limit**0.5) + 1):
        if is_prime[i]:
            # Mark all multiples of i as composite
            for j in range(i * i, limit + 1, i):
                is_prime[j] = False

    return [i for i in range(2, limit + 1) if is_prime[i]]

def nth_prime_optimized(n: int) -> int:
    """O(limit log log limit): use sieve to find nth prime."""
    # Approximate upper bound: nth prime ~ n * ln(n) for large n
    limit = max(15, int(n * (__import__('math').log(n + 1) + 2)))

    while True:
        primes = sieve_of_eratosthenes(limit)
        if len(primes) >= n:
            return primes[n - 1]
        limit *= 2

result = nth_prime_optimized(10001)
print(result)  # 104743

التعقيد: الغربال هو O(n log log n) مقابل القسمة التجريبية O(n√n). بالنسبة للعدد الأولي رقم 10,001:

• القسمة التجريبية: ~104,743 مرشح × √104,743 ≈ 10 مليون عملية
• الغربال: ~130,000 حد × log(log(130,000)) ≈ 2 مليون عملية

الغربال أسرع بـ 5-10 مرات ويتعامل بسهولة مع قيم n الأكبر.

---

المشكلة 8: أكبر حاصل ضرب لـ 13 رقمًا متتاليًا

المشكلة: بالنظر إلى رقم مكون من 1000 خانة (موجود في نص المشكلة)، أوجد الـ 13 رقمًا متتاليًا التي يكون حاصل ضربها هو الأكبر.

هذه مشكلة نافذة منزلقة (sliding-window): حافظ على نافذة من 13 رقمًا، وقم بتحريكها عبر السلسلة، واحسب نواتج الضرب، وتتبع الحد الأقصى.

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

def largest_product_bruteforce(digits_str: str, window_size: int) -> int:
    """O(n*k): check all windows of size k."""
    max_product = 0

    for i in range(len(digits_str) - window_size + 1):
        window = digits_str[i:i + window_size]
        product = 1
        for digit in window:
            product *= int(digit)
        max_product = max(max_product, product)

    return max_product

# Example (using first 100 digits of the 1000-digit number)
digits = "73167176531330624919225119674151088626142863460141595621011573228220635045648233182332206999"
result = largest_product_bruteforce(digits, 13)

الوقت: O(n × k) حيث n=1000، k=13، أي حوالي 13,000 عملية. المساحة: O(1).

الحل المحسن (نافذة منزلقة مع إعادة حساب ذكية):

التحسين الرئيسي: عند تحريك النافذة، يمكن حساب حاصل الضرب الجديد كـ (old_product / left_digit) × new_right_digit. ومع ذلك، يتطلب هذا القسمة، والتي تفشل إذا كانت هناك أصفار في النافذة. النهج الأفضل: تخطي النوافذ التي تحتوي على 0 (حاصل الضرب سيكون 0 على أي حال).

def largest_product_optimized(digits_str: str, window_size: int) -> int:
    """O(n): sliding window with zero-skipping."""
    max_product = 0

    i = 0
    while i <= len(digits_str) - window_size:
        window = digits_str[i:i + window_size]

        # If window contains 0, skip to after the 0
        if '0' in window:
            i += window.index('0') + 1
            continue

        # Compute product for this window
        product = 1
        for digit in window:
            product *= int(digit)

        max_product = max(max_product, product)
        i += 1

    return max_product

digits = "73167176531330624919225119674151088626142863460141595621011573228220635045648233182332206999"
result = largest_product_optimized(digits, 13)

التعقيد: O(n) مستهلك (amortized). في أسوأ الحالات (لا توجد أصفار)، يتم فحص كل موضع مرة واحدة. مع وجود الأصفار، يتم تخطي النوافذ، مما يقلل التكرارات. حساب حاصل الضرب الداخلي هو O(k)، ولكن k ثابت (13)، لذا التعقيد الإجمالي هو O(n).

---

المشكلة 9: ثلاثية فيثاغورس الخاصة

المشكلة: ثلاثية فيثاغورس (a, b, c) تحقق a² + b² = c². أوجد الثلاثية الفريدة التي تحقق a + b + c = 1000، وأرجع حاصل ضرب a × b × c.

يتضمن ذلك حل معادلة ديوفانتوس: أوجد (a, b, c) بحيث a² + b² = c² و a + b + c = 1000.

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

def special_pythagorean_triplet_bruteforce() -> int:
    """O(n³): triple nested loop."""
    for a in range(1, 1000):
        for b in range(a + 1, 1000):
            for c in range(b + 1, 1000):
                if a + b + c == 1000 and a**2 + b**2 == c**2:
                    return a * b * c
    return 0

result = special_pythagorean_triplet_bruteforce()
print(result)  # 31875000

الوقت: O(n³) مع n=1000، أي حوالي مليار تكرار. بطيء جدًا.

الحل المحسن (الاختزال إلى حلقة مزدوجة):

القيد: a + b + c = 1000. إذن c = 1000 - a - b. قيد فيثاغورس: a² + b² = c² = (1000 - a - b)².

بالتوسيع: a² + b² = 1000² - 2×1000(a+b) + (a+b)² بالتبسيط: a² + b² = 1,000,000 - 2000(a+b) + a² + 2ab + b² بإعادة الترتيب: 0 = 1,000,000 - 2000(a+b) + 2ab بالحل: 2ab - 2000(a+b) = -1,000,000 ab - 1000(a+b) = -500,000 ab - 1000a - 1000b = -500,000 a(b - 1000) = 1000b - 500,000 a = (1000b - 500,000) / (b - 1000)

def special_pythagorean_triplet_optimized() -> int:
    """O(n²): derive c from a,b; compute algebraically."""
    for a in range(1, 500):
        for b in range(a + 1, 1000 - a):
            c = 1000 - a - b
            if a**2 + b**2 == c**2:
                return a * b * c
    return 0

result = special_pythagorean_triplet_optimized()
print(result)  # 31875000

مزيد من التحسين باستخدام الجبر:

def special_pythagorean_triplet_algebraic() -> int:
    """O(n): use derived formula."""
    # From: a(b - 1000) = 1000b - 500,000
    # We iterate b and solve for a
    for b in range(2, 500):
        numerator = 1000 * b - 500_000
        denominator = b - 1000
        if numerator % denominator == 0:  # a must be integer
            a = numerator // denominator
            if a > 0 and a < b:
                c = 1000 - a - b
                if a**2 + b**2 == c**2:
                    return a * b * c
    return 0

result = special_pythagorean_triplet_algebraic()
print(result)  # 31875000

التعقيد: O(n²) المحسن مقابل O(n³) للقوة الغاشمة. تقترب النسخة الجبرية من O(n) ولكنها تتضمن عبء القسمة. التسريع العملي: ~100 مرة لـ n=1000.

---

المشكلة 10: مجموع الأعداد الأولية تحت المليونين

المشكلة: أوجد مجموع كل الأعداد الأولية تحت 2,000,000.

هذا تطبيق خالص للغربال: قم بتوليد جميع الأعداد الأولية تحت 2 مليون، ثم اجمعها.

حل القوة الغاشمة (القسمة التجريبية):

def is_prime_trial(n: int) -> bool:
    """Trial division primality test."""
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for i in range(3, int(n**0.5) + 1, 2):
        if n % i == 0:
            return False
    return True

def sum_primes_bruteforce(limit: int) -> int:
    """O(n sqrt(n)): trial division on each candidate."""
    total = 0
    for i in range(2, limit):
        if is_prime_trial(i):
            total += i
    return total

result = sum_primes_bruteforce(2_000_000)
# Very slow: ~2M candidates × √2M ≈ billions of operations

الوقت: O(n√n) مع n=2M، أي ملايين العمليات لكل مرشح. غير عملي.

الحل المحسن (غربال إراتوستينس):

def sieve_of_eratosthenes_sum(limit: int) -> int:
    """O(n log log n): sieve + sum."""
    is_prime = [True] * limit
    is_prime[0] = is_prime[1] = False

    for i in range(2, int(limit**0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, limit, i):
                is_prime[j] = False

    return sum(i for i in range(2, limit) if is_prime[i])

result = sieve_of_eratosthenes_sum(2_000_000)
print(result)  # 142913828922

البديل المحسن للذاكرة (الغربال المجزأ - Segmented Sieve):

بالنسبة للحدود الكبيرة جدًا، يستخدم الغربال الكامل مساحة O(n) من الذاكرة. يقوم الغربال المجزأ بتقسيم النطاق إلى أجزاء، مع غربلة كل جزء مع الحفاظ على ثبات استهلاك الذاكرة.

def simple_sieve(limit: int) -> list[int]:
    """Generate primes up to sqrt(limit)."""
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(limit**0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, limit + 1, i):
                is_prime[j] = False
    return [i for i in range(2, limit + 1) if is_prime[i]]

def sum_primes_segmented(limit: int) -> int:
    """O(n log log n) time, O(sqrt(n)) space."""
    sqrt_limit = int(limit**0.5) + 1
    base_primes = simple_sieve(sqrt_limit)

    # Sieve all numbers up to sqrt(limit)
    total = sum(base_primes)

    # Segmented sieve for [sqrt+1, limit)
    low = sqrt_limit + 1
    high = min(low + 100_000, limit)

    while low < limit:
        is_prime = [True] * (high - low + 1)

        for p in base_primes:
            start = max(p * p, ((low + p - 1) // p) * p)
            for j in range(start, high + 1, p):
                is_prime[j - low] = False

        for i in range(len(is_prime)):
            if is_prime[i]:
                total += low + i

        low = high + 1
        high = min(low + 100_000, limit)

    return total

result = sum_primes_segmented(2_000_000)
print(result)  # 142913828922

التعقيد: الغربال القياسي: O(n log log n) وقت، O(n) مساحة. الغربال المجزأ: O(n log log n) وقت، O(√n) مساحة.

بالنسبة لـ n=2M:

• القسمة التجريبية: مليارات العمليات، غير عملية.
• الغربال: ~8 مليون عملية، يكتمل في أقل من ثانية واحدة.
• الغربال المجزأ: نفس التعقيد الزمني، مع 1/100 من استهلاك الذاكرة.

---

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

1. الصيغ الرياضية المغلقة (المشكلة 6): استخدم الرياضيات لإلغاء الحلقات التكرارية. O(1) يتفوق دائمًا على O(n).
2. غربال إراتوستينس (المشكلتان 7 و10): المعيار الذهبي لإيجاد الأعداد الأولية. O(n log log n) يتفوق على القسمة التجريبية بمراحل.
3. تحسين النافذة المنزلقة (المشكلة 8): التكرار الذكي (تخطي الأصفار) يقلل من الحسابات الزائدة.
4. التبسيط الجبري (المشكلة 9): قلل أبعاد مساحة البحث الخاصة بك باستخدام القيود. O(n³) ← O(n).
5. المفاضلة بين الذاكرة والسرعة (المشكلة 10): تتيح لك الغرابيل المجزأة التعامل مع حدود ضخمة بكفاءة.

تشكل هذه التقنيات العمود الفقري لحل المشكلات الخوارزمية. تمثل المشكلات من 6 إلى 10 الانتقال من "البرمجة الأساسية" إلى "التفكير الخوارزمي" — أتقن هذه المشكلات، وستصبح المشكلات من 11 إلى 20 في متناول يدك.

الخاتمة

تثبت مشكلات Project Euler من 6 إلى 10 الأساسيات: الرؤية الرياضية تتفوق على القوة الغاشمة، وفهم هيكل بياناتك (الأعداد الأولية، النوافذ، القيود) يكشف عن فرص التح