Bad news: your worst enemies are at the gate. For your fledgling kingdom guards the world’s only herd of tiny dino creatures. To you, they’re sacred. To everyone else, they’re food. The three closest nation-states have all teamed up in what they call an alliance of the hungry to smash open your walls and devour the herd.
Your fortifications will hold off their armies for now. But when their siege weapons arrive tomorrow, you won’t stand a chance. Luckily, you have a wall fabricator: if you run it all night, you may be able to reinforce your border before the weapons arrive. However, it can only create wall segments of a specific, whole number size that you must determine ahead of time.
Your engineers have been in close consultation with your spymaster. Each rival kingdom has wall-busters that come in one specific size. The clowns’ are all 6 meters, the royals’ are 9, and the redheads’ are 20. Each wall-buster can level a wall segment of the matching size. And they can be combined as well; two 6′s can take out a 12 meter wall and a 6 and a 9 could break one that’s 15 meters. But a 7 meter wall would hold fast against any of them. Meanwhile, large walls aren't necessarily protected. Here’s how they could take down 70, 71, and 72 meters.
Your fabricator takes the same amount of time to produce a wall segment no matter its length, and it’s not particularly fast. So to finish the wall in time, you need the longest segment that can’t be destroyed by any combination of the siege weapons, which your enemies have hundreds of.
What wall length will save your kingdom?
Pause here to figure it out yourself. Answer in 3
Answer in 2
Answer in 1
It's possible to solve this problem by trial and error. But there’s also a remarkably quick and elegant solution inspired by an idea that’s thousands of years old: the sieve of Eratosthenes. Eratosthenes of Cyrene was a 3rd century BCE mathematician from ancient Greece interested in prime numbers, that is numbers only divisible by 1 and themselves. Presumably he grew bored of manually checking whether a given number was prime, so he came up with the following technique.
Make a giant list of numbers. X out all of the multiples of 2, except 2 itself. Now do the same with multiples of 3. The even multiples have already been eliminated, and the odd multiples can all be found in this column. 4 was already accounted for when you did multiples of 2, so move on to 5. The multiples of 5 and 7 show up conveniently in diagonals. This method eliminates all possible composite numbers, leaving only primes behind. We've already identified every prime less than 121, and it’s easy to go higher and higher this way.
We can use a similar technique with our wall problem to eliminate entire groups of numbers at once. A first, critical step is to be deliberate about the number of columns. If we use 6 again, the numbers in each column will be exactly 6 apart. What that means is that if we identify a number vulnerable to the wall-busters, then all the rest of the column below it would also fall. In other words, because your enemies can make 9, they can make 15, 21, 27, and so on by adding the clowns’ 6-meter machines. So right away this eliminates 6, 9 and 20, and everything under them.
We’ve accounted for the 6′s with the columns, so we can focus on combinations of 20′s and 9′s to eliminate more options. Your rivals can easily make 20 plus 9 and 20 plus 20 and everything below. Using this approach, we could have eliminated the 70, 71, and 72, and infinitely many other options without having to do any calculations.
In the remaining column there are no multiples of 9 or 20, but 49 jumps out, as 2 times 20 plus 9. There's no way to make 43, so that must be the largest wall segment that your enemies can’t destroy.
And there you have it. You plug 43 into the wall fabricator, and after a tense night, the sun rises on your now impregnable fortress and a herd that won’t become unhappy meals.
