Project Euler: Mathematical Coding Challenges

Here is a question that looks harmless: find the sum of all multiples of 3 or 5 below 1000. A calculator cannot do this in one step. Pen and paper would take an evening of careful listing and a high chance of an arithmetic slip somewhere around the 400s. But eight lines of code can hand you the exact answer, correctly, in a fraction of a second. That gap — between "a human grinding through arithmetic" and "a short program that never gets tired or careless" — is exactly what Project Euler is built to make you feel, over and over, on problems that get progressively harder. This chapter teaches you how to think in that gap: how to turn a math statement into working code, and how to notice when your code is doing something needlessly slow.

What Project Euler Actually Is

Project Euler is a website (projecteuler.net) hosting a long, numbered series of problems, each one demanding both a mathematical insight and a program to carry it out at scale. It is named after Leonhard Euler, the 18th-century mathematician whose work touches an enormous range of topics — number theory, geometry, calculus — because the problems on the site span a similarly wide range of mathematical ideas. It was created in 2001 by a British teacher, Colin Hughes, originally as a set of extra problems for his own students, and it has since grown into an archive with hundreds of numbered problems, each submitted with a single exact numeric answer that the site checks instantly. Problem 1 is deliberately gentle. By problem 50 or so, you typically need real algorithmic thinking, not just a longer loop. By problem 200, most solvers are professional programmers or mathematicians.

The important thing to understand before you write a single line of code is what kind of skill this is training. It is not the same skill as "memorize this formula" and it is not the same skill as "type code that compiles." It sits in between: read a precise mathematical statement, decide what a computer needs to compute to answer it, write that computation correctly, and then — this is the part beginners skip — check whether there is a smarter way to compute it before your program runs for longer than the age of the universe. Every one of those four steps shows up in this chapter.

Step One: Turning Words Into Code (Multiples of 3 or 5)

Take the multiples-of-3-or-5 problem, but shrink it first. Find the sum of all multiples of 3 or 5 below 10. Small enough to do by hand: the multiples of 3 below 10 are 3, 6, 9; the multiples of 5 below 10 are 5. Combined and added: 3 + 5 + 6 + 9 = 23. Notice we do not double-count 15 — it does not appear here because 15 is not below 10, but in general a number that is a multiple of both 3 and 5 (like 15) should only be added once, not twice. Keep that rule in mind; it becomes important in a moment.

Now the translation into code. A computer cannot "notice" multiples the way your eye can scan a short list — it has to be told, explicitly, to check every candidate number one at a time. That mechanical checking is exactly what a loop is for:

def sum_multiples(limit):
    total = 0
    for n in range(1, limit):
        if n % 3 == 0 or n % 5 == 0:
            total += n
    return total

print(sum_multiples(10))

Trace it exactly as Python would, to build the habit of never trusting code you have not walked through by hand. range(1, 10) produces 1, 2, 3, 4, 5, 6, 7, 8, 9. For each n, the condition n % 3 == 0 or n % 5 == 0 asks "does 3 divide n with no remainder, OR does 5 divide n with no remainder?" — the or is exactly what stops us double-counting 15-type numbers, because it is a yes/no test, not two separate additions. Walking through: n=1 no, n=2 no, n=3 yes (total=3), n=4 no, n=5 yes (total=8), n=6 yes (total=14), n=7 no, n=8 no, n=9 yes (total=23). Final answer: 23, matching the hand count exactly. Now the same function, unmodified, answers the real problem:

print(sum_multiples(1000))   # 233168

233168 is the correct, verified answer to Project Euler Problem 1. Nothing about the code changed between the 10-case and the 1000-case — only the input. That is the first big idea this chapter wants you to internalize: a correctly written loop does not care whether it runs 9 times or 999 times. The work of getting the logic right happens once, on a small case you can check by hand; the work of scaling up is free.

Step Two: Building a Sequence as You Go (Even Fibonacci Numbers)

Not every Project Euler problem hands you a ready-made list to filter, the way "check every number from 1 to 999" did. Many ask you to generate a sequence first. The Fibonacci sequence is the classic example: each term is the sum of the two terms before it. Project Euler's version starts 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... The real problem asks: by considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Shrink it first, as always. Below 100, the Fibonacci terms are 1, 2, 3, 5, 8, 13, 21, 34, 55, 89. The even ones among these are 2, 8, and 34. Their sum is 2 + 8 + 34 = 44. Hold onto that number; it is what your code must reproduce before you trust it on the real four-million case.

The coding idea here is different from Step One. Instead of looping over numbers that already exist (1 through 999), you build the sequence one term at a time, using two variables that constantly get updated to "slide forward" along the sequence:

def even_fib_sum(limit):
    a, b = 1, 2
    total = 0
    while a < limit:
        if a % 2 == 0:
            total += a
        a, b = b, a + b
    return total

print(even_fib_sum(100))

Trace it. Start: a=1, b=2, total=0. Loop condition a < 100 is true throughout until a reaches 144, so let's follow a: a=1 (odd, skip) → a,b become 2,3. a=2 (even, total=2) → a,b become 3,5. a=3 (odd) → a,b become 5,8. a=5 (odd) → a,b become 8,13. a=8 (even, total=10) → a,b become 13,21. a=13 (odd) → a,b become 21,34. a=21 (odd) → a,b become 34,55. a=34 (even, total=44) → a,b become 55,89. a=55 (odd) → a,b become 89,144. a=89 (odd) → a,b become 144,233. Now a=144, and the loop condition a < 100 is false, so the loop stops. Final total: 44 — exactly matching the hand count. The line a, b = b, a + b is doing two jobs simultaneously: it moves the "current term" forward to what used to be the "next term," and it computes a fresh "next term" as their sum. This simultaneous-assignment trick is worth noticing carefully, because it is the standard Python idiom for walking forward through any sequence defined by "the next thing depends on the last two things."

Once the logic is verified on the small case, scaling up costs nothing again:

print(even_fib_sum(4000000))   # 4613732

4613732 is the verified correct answer to Project Euler Problem 2. The even Fibonacci terms below four million are 2, 8, 34, 144, 610, 2584, 10946, 46368, 196418, 832040, and 3524578 — eleven terms, adding to 4613732.

The Misconception: "A Loop That Checks Everything Always Works"

Here is where most beginners get a rude surprise, and where Project Euler starts teaching something Khan-Academy-style "learn loops" tutorials rarely emphasize: a loop that is logically correct can still be practically useless, because it takes too long to finish. Consider Project Euler Problem 3: the prime factors of 13195 are 5, 7, 13 and 29 — what is the largest prime factor of the number 600851475143?

The tempting first instinct, based on everything in Steps One and Two, is: loop a candidate divisor from 2 up to n, and whenever it divides evenly, it is a factor. That instinct is not wrong about correctness — it is wrong about speed. To check every number up to 600,851,475,143 one at a time, even at an optimistic hundred million checks per second, would take well over an hour, and this is a comparatively small Project Euler number — later problems use numbers that would make this approach take centuries. The misconception to correct explicitly is this: "loop through everything" is not the same skill as "solve the problem." Project Euler is specifically designed so that the brute-force loop works on the small example (13195, done in a blink) but becomes infeasible on the real one (600851475143). You are being tested on whether you notice the difference before you run out of patience waiting for an answer that will arrive next year.

The fix relies on a genuine mathematical fact, not a programming trick: if a number d divides n evenly, then n/d also divides n evenly, and the two divisors d and n/d always sit on opposite sides of the square root of n (or exactly at it, if n is a perfect square). This means you never need to test divisors past √n — anything larger than √n is guaranteed to already have shown up, paired with something smaller than √n, earlier in your search.

Translated into code, the trial-division loop simply stops climbing once the candidate divisor's square passes n — and crucially, every time a divisor is found, it is divided out of n repeatedly, which shrinks n and therefore shrinks the square-root ceiling as the search goes on:

def largest_prime_factor(n):
    factor = 2
    while factor * factor <= n:
        while n % factor == 0:
            n //= factor
        factor += 1
    return n

print(largest_prime_factor(13195))

Trace the outer loop briefly. factor=2: 2×2=4 ≤ 13195, but 13195 is odd, so nothing divides out; factor becomes 3. factor=3: 13195's digit sum is 1+3+1+9+5=19, not a multiple of 3, so nothing divides out; factor becomes 4, then 5. factor=5: 13195 ends in 5, so it divides evenly — n becomes 13195 ÷ 5 = 2639, and dividing again fails (2639 doesn't end in 0 or 5), so factor becomes 6, 7. factor=7: 2639 ÷ 7 = 377 exactly, so n becomes 377. factor climbs to 13 (skipping non-divisors): 377 ÷ 13 = 29 exactly, so n becomes 29. Now factor increments to 14, and the loop checks 14×14=196 ≤ 29 — false, since n has shrunk all the way down to 29. The loop exits and returns 29. That matches the problem statement's own worked example (13195 = 5 × 7 × 13 × 29, largest factor 29) exactly. Run the same function on 600851475143 and it returns 6857 — the verified answer to Problem 3 — in a small fraction of a second, because the search ceiling shrinks every time a factor is divided out, rather than crawling through hundreds of billions of candidates.

A Second Kind of Speed-Up: Replacing a Loop With Algebra

The square-root trick sped up a loop by shrinking how far it has to run. Sometimes you can do better still: skip the loop entirely, because middle-school algebra already computed the answer in closed form. Project Euler Problem 6 asks: the sum of the squares of the first ten natural numbers is 1²+2²+...+10² = 385. The square of the sum is (1+2+...+10)² = 55² = 3025. Find the absolute difference between the sum of the squares and the square of the sum, for the first one hundred natural numbers.

Check the small case by hand exactly as given: sum of squares 1 through 10 is 1+4+9+16+25+36+49+64+81+100 = 385. Sum 1 through 10 is 55, and 55² = 3025. Difference: 3025 − 385 = 2640. A direct, loop-based program reproduces this immediately:

def sum_square_difference(n):
    sum_of_squares = sum(i * i for i in range(1, n + 1))
    square_of_sum = sum(range(1, n + 1)) ** 2
    return square_of_sum - sum_of_squares

print(sum_square_difference(10))    # 2640
print(sum_square_difference(100))   # 25164150

25164150 is the correct, verified answer for n=100. This program works fine — but notice it still has to loop, twice, generating every one of the 100 (or however many) terms to add them up. Middle-school algebra gives you two exact formulas that make the looping unnecessary altogether: the sum of the first n natural numbers is n(n+1)/2, and the sum of their squares is n(n+1)(2n+1)/6. Substituting n=100: the sum is 100×101/2 = 5050, so the square of the sum is 5050² = 25502500. The sum of squares is 100×101×201/6 = 2030100/6 = 338350. The difference: 25502500 − 338350 = 25164150 — identical to the loop's answer, computed with three multiplications and two divisions instead of two hundred additions:

def sum_square_difference_fast(n):
    s = n * (n + 1) // 2
    sq = n * (n + 1) * (2 * n + 1) // 6
    return s * s - sq

print(sum_square_difference_fast(100))   # 25164150

For n=100 the difference between the two approaches is invisible — both finish instantly. But the lesson is the one Project Euler is designed to drill into you: as n grows into the millions or billions, a loop that does one unit of work per number takes proportionally longer, while a formula that does a fixed handful of operations regardless of n stays instant. Recognizing "there's a formula for this" is just as much a Project Euler skill as writing the loop in the first place — and it is exactly the kind of algebra-to-code bridge that CBSE's Computer Science and Informatics Practices syllabus is building toward when it pairs programming constructs with mathematical reasoning.

How This Connects to What You're Already Learning

Every tool used in this chapter — for loops, while loops, the modulus operator %, conditionals with and/or, functions with return values, and simultaneous variable assignment — is standard material in a Grade 8 Python-based computer science course. Project Euler does not require anything beyond that toolkit; what it adds is the discipline of checking your program against a small hand-computed case before trusting it on a large one, and the habit of asking "how many operations is this actually going to run?" before you click submit. Indian students preparing for programming contests often meet this same discipline on platforms like CodeChef (built by the Indian company Directi) or in school-level Informatics Olympiad training — Project Euler is a quieter, unpressured place to build the same instincts first, one verified small example at a time, with no clock running.

Practice: Test Yourself Before You Look Up the Answer

• Modify sum_multiples to find the sum of all multiples of 7 or 11 below 500. Hand-check it first on "below 20" (multiples of 7: 7,14; multiples of 11: 11 — sum should be 32) before trusting the larger run.
• In even_fib_sum, what would happen to the answer if the condition were changed from a % 2 == 0 to a % 2 != 0? Trace the first six terms by hand to predict the new total below 100 before running any code.
• Explain in one sentence why largest_prime_factor is allowed to stop checking once factor * factor exceeds the current value of n, even though n keeps shrinking as the function runs.
• Using the two closed-form algebra formulas from this chapter, compute the sum-square-difference for n=20 by hand, then verify it against sum_square_difference_fast(20).
• A classmate says: "My loop checking every number up to n always gives the right answer, so it's a good solution." Identify precisely what is missing from that claim.

Summary

• Project Euler pairs a mathematical statement with a requirement to compute an exact numeric answer for large inputs — correctness alone is not enough; the code must also finish in reasonable time.
• The reliable workflow is: shrink the problem to a size you can verify by hand, write code, trace it line by line against your hand answer, then scale up to the real input unchanged.
• Sequences that build on previous terms (like Fibonacci) are generated with running variables updated together, using patterns like a, b = b, a + b, rather than looked up from a pre-made list.
• A logically correct brute-force loop can still be the wrong solution if it takes too long — Problem 3 (largest prime factor) shows this directly, since checking every number up to 600,851,475,143 is infeasible.
• The square-root trial-division optimization works because any divisor pair (d, n/d) always straddles √n, so nothing past √n needs to be tested — and dividing out factors as you find them shrinks n, shrinking the ceiling further as you go.
• Sometimes the fastest optimization is not a smarter loop but no loop at all: closed-form algebraic formulas (like n(n+1)/2 for a running sum) replace repeated addition with a fixed number of operations.

Think About It

Think about this: How would you explain project euler: mathematical coding challenges to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.