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

ملخص

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

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

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

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

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

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

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

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 ≈ 34 مليون فحص قابلية قسمة (أقل في الممارسة العملية — المرشحون الفرديون فقط، ونتوقف عند أول قاسم)
• الغربال: حوالي 130,000 × log(log(130,000)) ≈ 320 ألف عملية

في الممارسة العملية، يعمل الغربال أسرع بمراحل من القسمة التجريبية لهذا الحجم ويتوسع بشكل أفضل بكثير مع نمو 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

# The full 1000-digit number is given in the problem statement on
# projecteuler.net. Paste it here as a single string with no whitespace.
digits = "..."  # 1000 digits, e.g. "7316717653133062491922511967..."
result = largest_product_bruteforce(digits, 13)
print(result)  # 23514624000 when the full 1000-digit string is supplied

الوقت: 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

# Same 1000-digit string as above.
digits = "..."  # 1000 digits from the problem statement
result = largest_product_optimized(digits, 13)
print(result)  # 23514624000

التعقيد: 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³) — مع a < b < c و n=1000، هذا يمثل تقريبًا n³/6 ≈ 167 مليون ثلاثية مرشحة في أسوأ الحالات. لا يزال بطيئًا، لكن الخوارزمية تخرج بمجرد العثور على الحل الفريد، لذا تعتمد التكلفة الزمنية الفعلية على مكان وجود الحل.

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

القيد: 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 مليون

المشكلة: أوجد مجموع كل الأعداد الأولية أقل من 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 — هذا يعني حوالي 2 مليون مرشح × ما يصل إلى حوالي 1,414 قسمة تجريبية لكل منهم، بإجمالي مليارات العمليات. غير عملي.

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

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

متغير محسن الذاكرة (الغربال المجزأ):

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

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 ملايين عملية، يكتمل في أقل من ثانية على الأجهزة الحديثة.
• الغربال المجزأ: نفس تعقيد الوقت، ولكن بجزء بسيط من الذاكرة — فقط الأعداد الأولية الأساسية (~√n) بالإضافة إلى جزء واحد بحجم ~100 ألف عنصر في المرة الواحدة، بدلاً من مصفوفة تحتوي على 2 مليون عنصر.

---

أفضل الممارسات

1. الصيغ ذات الشكل المغلق (المشكلة 6): استخدم الرياضيات لإلغاء الحلقات التكرارية. O(1) يتفوق على O(n) في كل مرة.
2. غربال إراتوستينس (المشكلتان 7 و10): الخوارزمية القياسية المعتمدة لتوليد جميع الأعداد الأولية تحت حد معين. O(n

   ترسخ المسائل من 6 إلى 10 في Project Euler الأساسيات: فالرؤية الرياضية تتفوق على الـ brute force، وفهم هيكل بياناتك (الأعداد الأولية، النوافذ، القيود) يكشف عن فرص الـ optimization. سواء كنت تستعد للمقابلات التقنية أو تبني أساساً في الرياضيات الحسابية، فإن هذه المسائل الخمس ضرورية. قم بتنفيذها، واحسب وقت تشغيلها، واشعر بالفرق الهائل بين المناهج الساذجة والمحسنة (optimized).