Case Study · Math · Algorithms
Project Euler, Annotated
The idea
Project Euler is a collection of problems that look like programming exercises and are really mathematics in disguise. Every one can be brute-forced, and almost every one has a second solution, quicker by orders of magnitude, that you find only by understanding the structure instead of enumerating it. The gap between those two solutions is the whole point, and the site enforces it with a soft rule of thumb: if your program takes more than a minute, you have the wrong solution. This page annotates a few of my favorites, showing both roads, because the lesson is never the answer. It is the distance between the two ways of getting it.
The most visual of these problems is number 14, the longest Collatz chain, so its plate opens the page; play with it first, then read the four problems in order below.
The plate below is the picture the number theory hides. The jagged skyline is not noise: it is a genuinely chaotic function that no formula predicts, riding on a conjecture no one has proved, and yet every bar is finite because every number tested, into the quintillions, does eventually reach 1.
111 steps to 1, peak 9232.
27 → 82 → 41 → 124 → 62 → 31 → 94 → 47 → 142 → 71 → 214 → 107 → 322 → 161 → 484 → 242 → 121 → 364 → 182 → 91 → 274 → 137 → 412 → 206 → 103 → 310 → 155 → 466 → 233 → 700 → 350 → 175 → 526 → 263 → 790 → 395 → 1186 → 593 → 1780 → 890 → 445 → 1336 → 668 → 334 → 167 → 502 → 251 → 754 → 377 → 1132 → 566 → 283 → 850 → 425 → 1276 → 638 → 319 → 958 → 479 → 1438 → 719 → 2158 → 1079 → 3238 → 1619 → 4858 → 2429 → 7288 → 3644 → 1822 → 911 → 2734 → 1367 → 4102 → 2051 → 6154 → 3077 → 9232 → 4616 → 2308 → 1154 → 577 → 1732 → 866 → 433 → 1300 → 650 → 325 → 976 → 488 → 244 → 122 → 61 → 184 → 92 → 46 → 23 → 70 → 35 → 106 → 53 → 160 → 80 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
Problem 1: multiples of 3 or 5
Sum the numbers below 1000 divisible by 3 or 5. The loop is one line and finishes instantly, so this problem’s whole purpose is to teach that you did not need the loop. By inclusion-exclusion, the sum of multiples of 3 plus the sum of multiples of 5 double-counts the multiples of 15, so subtract them once. Each piece is an arithmetic series: the multiples of below are with , summing to .
That is in constant time, no loop at all, and the same closed form gives the answer for where the loop would never finish. Inclusion-exclusion and the Gauss series are both here in the very first problem, which is Project Euler telling you what kind of place it is.
Problem 2: even Fibonacci numbers
Sum the even Fibonacci numbers below four million. The obvious loop generates Fibonacci numbers and tests parity, but the parities are not random: the sequence runs odd, odd, even, odd, odd, even, forever, because the sum of two odds is even and the sum of an odd and an even is odd. So every third Fibonacci number is even, and those even terms satisfy their own recurrence, , which you can derive by composing the Fibonacci rule three times. You never generate the odd terms at all. Seeing the period-3 parity pattern is the difference between knowing the Fibonacci numbers and knowing the Fibonacci numbers.
Problem 3: the largest prime factor
Find the largest prime factor of . The trap is to look for primes and test each as a divisor. The insight inverts it: divide the number by 2 until it is odd, then by 3, then by 5, and so on, and every divisor you pull out is automatically prime, because you have already removed all its smaller factors by the time you reach it. You never test primality once. And you never search past , because after stripping the small factors, whatever remains above one is the largest prime factor itself: a number has at most one prime factor greater than its own square root. Trial division sounds slow and is, at this size, instant, once you stop looking for primes and start peeling them off.
Problem 14: the longest Collatz chain
Take any positive integer; if it is even, halve it, and if it is odd, triple it and add one. Repeat. The Collatz conjecture says you always reach 1, and it is unproven, one of the famous open problems that a child can state and no one can solve. Problem 14 asks which starting number under a million takes the longest to fall to 1. The plain brute force computes the chain for each start, but chains overlap enormously: once a chain drops into a value you have already seen, its remaining length is known, so memoizing the stopping times turns a million independent walks into one shared computation, each number visited about once.
The ones worth drawing next
Problem 14 earned its plate because its shape is the argument, and a few others would too, for the same reason: the picture carries a truth the prose only asserts. Problem 28’s number spiral turns the diagonals into a literal geometric object, so the pattern in their sum becomes something you can watch wind out from the center. Problem 15’s lattice paths are Pascal’s triangle rotated into a grid, where every route across is the same two moves in a different order. The figurate numbers of Problem 45, triangular against pentagonal against hexagonal, are three families of dots whose rare coincidences are easier to believe once you see the shapes line up. Each of those is low-numbered or long-famous, so naming it here gives nothing away; the drawing, as always, would be the part that does the teaching.
When the insight earns its keep
That constraint on which problems appear here is Project Euler’s own. The site has a stated etiquette (do not publish solutions to the higher-numbered problems, so the puzzle survives for the next person), and this page respects it: the four problems above are all low-numbered starters whose insights are textbook, chosen precisely because spoiling them spoils nothing. The genre’s real risk is that the clever closed form becomes the point. Problem 1’s Gauss trick is beautiful and also completely unnecessary at , where the loop is instant and clearer to read; the discipline is knowing when the insight earns its complexity, which is exactly when the brute force stops finishing, and not one problem sooner. The best thing Project Euler taught me is not any single trick. It is the reflex to ask, after the loop already works, what the loop was secretly computing.