1  Which Ones?

Later in this book we will ask how many. How many ways to make a dollar; how many handshakes in a room of thirty. Those questions have a number for an answer, and we will build some real machinery to get it.

This chapter asks a different question: which ones?

Which lockers are left open. Which postage amounts you simply cannot make. Which numbers are equal to the sum of their own divisors. Which number every four-digit number secretly falls into.

That change of question changes the shape of the answer. “How many” hands you back a single number. “Which ones” hands you back a list — and a list is also the first real data structure you’ll learn in Python. The two fit together so naturally that you will barely notice you’re learning one while chasing the other.

All four puzzles here share a method, too, and it is one you’ll use forever:

Test every candidate. Keep the ones that pass.

Everything in this chapter can be checked with paper and pencil. That’s on purpose. You should never be in the position of believing a number only because a computer printed it.

Note

The code cells in this chapter are live. You can edit them and press Run Code to run them right in your browser. (Nothing is sent anywhere. The first cell on a page takes a few seconds to load Python.) The cells share one session and are meant to be run top to bottom, like a notebook.

1.1 Kaprekar’s constant

Capstone: Take any four-digit number whose digits are not all the same. Rearrange its digits to make the biggest number you can, and the smallest, and subtract. Repeat with the answer. Where do you end up?

You will need a pencil for this one. It’s worth it.

1.1.1 Do it by hand first

Take 3524.

Its digits are 3, 5, 2, 4. The biggest number you can build from them is 5432. The smallest is 2345. Subtract:

5432 − 2345 = 3087

Now do the same thing to 3087. Biggest: 8730. Smallest: 0378. Subtract:

8730 − 0378 = 8352

Again, on 8352. Biggest: 8532. Smallest: 2358.

8532 − 2358 = 6174

And once more, on 6174. Biggest: 7641. Smallest: 1467.

7641 − 1467 = 6174

It didn’t move. We’re stuck — permanently.

Note

Pause and try. Pick your own four-digit number. Not 1111 or 7777 — the digits must not all be the same. Run it through the process on paper. How many steps before you stop moving? Where did you land?

If you did that honestly, you landed on 6174. Everyone does. That’s the puzzle: why does every four-digit number fall into the same hole?

Tip

Who was Kaprekar? Dattatreya Ramchandra Kaprekar (1905–1986) was a schoolteacher in Devlali, a small town in Maharashtra, India. He held no research post and published much of his work in obscure journals, sometimes at his own expense; professional mathematicians in India largely ignored him during his lifetime. He spent decades playing with ordinary numbers and noticing things nobody had noticed before.

The 6174 result is the one that carries his name — he announced it at a mathematical conference in Madras in 1949 — but it wasn’t his only find. A Kaprekar number is one whose square can be cut into two pieces that add back to the original: 45 squared is 2025, and 20 + 25 = 45. So is 9 (81, and 8 + 1 = 9), and 297 (88209, and 88 + 209 = 297).

The puzzle is named after him for the ordinary reason: he found it. It is worth knowing that a result this striking came from a provincial schoolteacher armed with nothing but patience and a pencil, roughly the equipment you have right now. Discovering something in mathematics does not require permission.

We’ll answer it. But first we need Python to do the grinding, and to do that we have to talk about something we’ve been able to ignore until now.

1.1.2 Numbers and text are not the same thing

Look again at what we did by hand. We took 3524 — a number — and did something to it that has nothing to do with its size: we rearranged its digits. Sorting digits isn’t arithmetic. You cannot add, subtract, multiply or divide your way to “5432 from 3524.”

Rearranging is something you do to text.

Python keeps these two ideas strictly separate, and it will tell you so:

They print identically. They are not the same:

3524
3524
<class 'int'>
<class 'str'>

int is Python’s name for a whole number. str is short for string — a string of characters, which is what programmers call text. The quotation marks in "3524" are not decoration; they are the entire difference.

Note

Puzzles and quick checks. After each example in this chapter comes a puzzle: a cell with several small tasks. Replace every ______, press Run Code, and the puzzle checks each task and tells you the first one that still needs work. A puzzle runs on its own, apart from the chapter’s other cells, so anything it needs is already inside it. The quick checks are multiple choice: pick an answer and you’ll see why it is right or wrong.

Puzzles and quick checks need an obooks account. Sign in with the person icon at the top of the page (or create an account there) to unlock them. Your progress is then saved, and each puzzle shows a ✓ once you’ve solved it.

Puzzle. Make a number and a piece of text, then ask Python what types they are.

Quotes make text; no quotes makes a number. type(x) gives the type of x.

Why it matters:

3525
35241

The same + sign does two different jobs. On numbers it adds. On strings it glues them end to end. Python isn’t confused — it is doing exactly what you asked, and what you asked depended on the type.

Tip

Types are not bureaucracy. Every value in Python has a type, and the type decides what the operations mean. Most beginner bugs are a value being a string when you thought it was a number, or the reverse. When something baffling happens, print(type(x)) is the first question to ask.

Puzzle. One more trick for the last task: a string times a whole number repeats the string, so "ab" * 3 is "ababab".

For Task 4, write "-" * 20.

What does print("7" + "7") show?

• 14
  • That is what print(7 + 7) shows. The quotes make these two strings.
• 77
  • On strings, + glues end to end.
• "77"
  • Close, but print doesn’t show quotes. They are how you write a string, not part of the text.
• An error
  • Gluing two strings is fine. Mixing types, as in "7" + 7, is what gives an error.

Happily, you can convert:

str(...) turns a number into text. int(...) turns text into a number. Our whole puzzle is going to live on that round trip: become text to rearrange, become a number to subtract.

Exercise 1: Predict the type

Fill in each blank with either int or str — what type is each value? Run it and see whether Python agrees with you.

Puzzle. len(...) counts the characters in a string: len("cat") is 3. You’ll need it for the last task.

int(year_text) + 1 is the number. str(...) turns it back into text.

What does int("0042") give?

• "0042"
  • int(...) always gives back a number, never text.
• 42
  • As a number, leading zeros carry no value, so they are dropped. Remember this one: it comes back to bite us later in this section.
• 0042
  • A number has nowhere to keep leading zeros. Only text can hold them.
• An error
  • Leading zeros are allowed in the text. int reads straight past them.

1.1.3 Taking a number apart

To rearrange the digits, first we need them separately. Turn the number into a string, and Python will hand you its characters:

['2', '3', '4', '5']

Two new things just arrived at once.

sorted(...) put the characters in order, smallest first. And look at how it gave them back: square brackets, commas between. That is a list — the structure this whole chapter is built on. A list is an ordered row of values, and here it holds four one-character strings.

Notice the quotes inside. '2' is the character 2, not the number 2. We’re still in text-land, which is exactly where we want to be.

Puzzle. sorted works on any string, not only on digits.

sorted(str(90210)). A number has to become a string before sorted can take it apart.

Sorting the other direction takes one extra instruction:

['5', '4', '3', '2']

There are our two arrangements: the smallest and the biggest.

Puzzle. sorted isn’t only for characters. Give it a list of numbers and it sorts those, by size.

sorted(..., reverse=True) sorts biggest first, for characters and numbers alike.

1.1.4 Putting it back together

A list of characters isn’t a number yet. We need to glue the characters into one string, then convert that string to an int.

Gluing is "".join(...) — read it as “join these pieces together, with nothing in between”:

5432
2345
3087

3087 — the same answer we got with a pencil. Read that middle line from the inside out, because it is the whole trick in one line:

1. sorted(digits) — a list of characters, in order
2. "".join(...) — those characters glued into one string
3. int(...) — that string read as a number

Number → text → list → text → number. Each conversion exists because the next step can only be done to that type.

Puzzle. The string in front of .join goes between the pieces. "" puts nothing between them; "-" would put a dash.

Read int("".join(sorted(digits))) from the inside out, as in the example above.

What is "".join(sorted("3087"))?

• 378
  • That’s what you’d get from int(...) around it. Without int, the result is still a string.
• "0378"
  • sorted gives the list ['0', '3', '7', '8'], and join glues it into one string. The zero survives because it is still text.
• ['0', '3', '7', '8']
  • That’s sorted("3087") on its own. join turns the list into one string.
• "8730"
  • That’s the reverse=True order. Plain sorted puts the smallest first.

1.1.5 One step, as a function

We’re going to do that repeatedly, so let’s name it:

3087
8352
6174
6174

Exactly the four lines we worked out on paper, including the last one that refuses to move.

Puzzle. Split the Kaprekar step into three small functions of your own.

Each function works on str(number). biggest sorts with reverse=True; both finish with int(...).

1.1.6 Round and round

Rather than calling it by hand, let it run:

1 --> 3087
2 --> 8352
3 --> 6174
4 --> 6174
5 --> 6174
6 --> 6174
7 --> 6174
8 --> 6174

Three steps to arrive, and then it sits there forever.

That line number = kaprekar_step(number) is worth a second look. It takes the current value, runs it through, and stores the result back under the same name. The number we’re holding gets replaced each time round. That is how a loop makes progress.

Exercise 2: Try your own

Put your own four-digit number in the blank — any one, as long as its digits aren’t all identical — and count how many steps it takes.

Puzzle. Each loop below replaces a value with a new one each time round, as number = kaprekar_step(number) did. This puzzle already has kaprekar_step; it is set up for you.

The pattern is always name = (something made from name).

After these lines run, what is x?

x = 1
for attempt in range(0, 3):
    x = x + x

• 2
  • That’s after one time round. The loop runs three times.
• 3
  • The loop does run three times, but x isn’t counting the passes. It doubles on each one.
• 6
  • That would be adding 2 each time. x + x doubles whatever x is now.
• 8
  • 1, then 2, then 4, then 8. Each pass replaces x with double its current value.

1.1.7 The bug: when four digits become three

Try 2111 and something goes wrong:

1 --> 999
2 --> 0
3 --> 0
4 --> 0
5 --> 0
6 --> 0

Zero, forever. And zero is certainly not 6174.

The first line is right: 2111 − 1112 = 999. The damage is done on the second step. Ask what kaprekar_step(999) does. str(999) is "999" — three characters. Sorted up it’s "999", sorted down it’s "999", and 999 − 999 is 0.

By hand you would never have made this mistake. You’d have written 999 as 0999, four digits with a leading zero, because you know we’re playing a four-digit game. Biggest: 9990. Smallest: 0999. And 9990 − 999 = 8991, which is very much alive.

Python dropped the leading zero because as a number, 0999 and 999 are the same thing. Leading zeros carry no value. But this puzzle isn’t about value, it’s about digits — and as text, "0999" and "999" are different.

Puzzle. Follow the zero through the round trip yourself. The first, buggy kaprekar_step is set up for you.

int(...) reads text as a number, str(...) turns a number into text, and len(...) counts characters.

The fix is to insist on four characters:

1 --> 999
2 --> 8991
3 --> 8082
4 --> 8532
5 --> 6174
6 --> 6174

.zfill(4) means “pad with zeros on the left until this is 4 characters long.” Five steps, and 2111 gets home after all.

Tip

The lesson worth keeping. This wasn’t a typo, it was a type bug — the most common kind there is. The value was right and the representation was wrong. Whenever you move between numbers and text, ask what got lost in the crossing. Here it was a zero that a number has no room to remember.

Puzzle. .zfill works on any string. Use it four ways.

str(7).zfill(3). For the clock, glue three strings: hours, ":", minutes.

Why did the first kaprekar_step send 2111 to 0?

• The subtraction came out wrong
  • 2111 − 1112 = 999 is correct. The trouble starts on the next step.
• str(999) has only three characters, so the missing zero was never sorted
  • The step then compared "999" with "999" and got 0. Padded to "0999", it gives 9990 − 0999 = 8991.
• sorted can’t sort digits that are all the same
  • It can: sorted("999") is ['9', '9', '9']. The problem is that the text should have been "0999".
• 2111 is a repdigit
  • A repdigit has all its digits the same, like 1111. 2111 isn’t one, and it reaches 6174 once the bug is fixed.

1.1.8 Why it ends where it does

Now the mathematics. Why does this always end, and why always at 6174? Those are two different questions, and only the first has a quick answer.

Why every trail settles into a loop. There are only so many four-digit numbers — 9,000 of them, from 1000 to 9999. Each one, fed to our step, produces exactly one output. So follow any starting number and you get a trail: one value, then the next, then the next, forever.

Think of the numbers as rooms, and the step as a one-way door out of each room. A never-ending trail through a finite set of rooms has no choice: sooner or later it must walk into a room it has already been in. From there it has nothing new to do — each room always leads through the same door — so it goes round the same circuit again, and again, forever.

So every trail ends in a loop. But notice what that argument does not say: how long the loop is. It could be a single room whose door leads straight back into itself. That’s 6174, because 7641 − 1467 = 6174. Or it could be a ring of several rooms that the trail circles without ever stopping anywhere.

Could it have been a ring? Yes — and in other versions of this game, it is. Play it with two-digit numbers, padding to two digits the way we padded to four. Start at 21:

21 − 12 = 09, then 90 − 09 = 81, then 81 − 18 = 63, then 63 − 36 = 27, then 72 − 27 = 45, then 54 − 45 = 09

Back at 09, and round we go again. Every two-digit start ends up on that ring, and no two-digit number stays put. With five digits, no number stays put either, and there are three different rings for a trail to fall into.

So the room argument guarantees a loop, but it can’t tell us whether the loop is one room or many, or whether every trail finds the same one. Four-digit numbers all ending at one number isn’t a law of nature. It’s a fact about four digits, and to learn it we have to look.

Looking is less work than it sounds. Write any four-digit number’s digits in order from largest to smallest, and call them a ≥ b ≥ c ≥ d. The biggest arrangement is abcd and the smallest is dcba, so one step gives

\[(1000a + 100b + 10c + d) - (1000d + 100c + 10b + a) \;=\; 999(a - d) + 90(b - c)\]

The answer depends on just two gaps: between the largest and smallest digits, and between the middle two. The first gap runs from 1 to 9 (it is only 0 for 1111, 2222 and the rest). The second can be anything from 0 up to the first. That’s 2 + 3 + … + 10 = 54 combinations. After one step, all 8,991 starting numbers have been funnelled into just 54 rooms.

Tracing 54 trails would take an afternoon by hand. For Python it’s no work at all — so we might as well skip the shortcut and test every starting number:

8991

The if line runs the line indented under it only when its test is true; you’ll see a lot more of it in the next section. Here it counts the starts that are sitting on 6174 after seven steps. That’s 8,991 — every one of the 9,000 except the nine repdigits 1111, 2222, …, 9999, which collapse straight to 0.

That cell is the answer to “why 6174?” There’s no single clever reason behind it. Proofs of this result come down to checking cases, and the 54-room funnel is what makes the check small enough to do. It is this chapter’s method once again: test every candidate, keep the ones that pass.

Kaprekar published the result in 1949: every four-digit number whose digits aren’t all equal reaches 6174, in at most seven steps. You have just checked both halves of it yourself.

Tip

“Finitely many states, so it must repeat” is a tool, not a one-off trick. Any process that keeps applying the same rule to values drawn from a finite collection must eventually cycle. You will meet the argument again in pseudo-random number generators, in card shuffles, and anywhere a machine with finite memory runs forever.

Puzzle. != means “is not equal to”, the opposite of ==. The fixed kaprekar_step is set up for you.

Task 2 is a loop that makes progress, like number = kaprekar_step(number). steps goes up by one each time.

1.1.9 Stretch problems

The seven-step worst case

Kaprekar’s bound is seven steps. Find a starting number that actually needs all seven. (Hint: try several starting numbers and count. Modify the loop so it stops reporting once it hits 6174.)

Three digits

Play the same game with three-digit numbers instead of four — use .zfill(3) and think about what “biggest” and “smallest” mean now. There is a constant here too. What is it?

Five digits

Switch to .zfill(5) and run a few five-digit numbers for twenty steps each. No five-digit number stays put. What does each trail do instead? How many different rings can you find?

The repdigits

Why does 1111 collapse to 0 in a single step? Why is that true of every number whose digits are all the same, without checking them one by one?

1.2 Perfect numbers

Capstone: A number is perfect if its divisors — not counting itself — add up to the number. 6 is perfect, because 1 + 2 + 3 = 6. Which numbers under 10,000 are perfect?

Guess how many there are before reading on. Dozens? Hundreds?

1.2.1 Do it by hand first

The divisors of 6, leaving 6 itself out, are 1, 2 and 3. Add them: 1 + 2 + 3 = 6. Perfect.

The divisors of 28, leaving out 28, are 1, 2, 4, 7 and 14.

1 + 2 + 4 + 7 + 14 = 28

Perfect again.

Note

Pause and try. Do the same for 8 and for 12. List the divisors of each (not counting the number itself), add them, and compare the total to the number you started with. Are either of them perfect? Is the total bigger or smaller?

For 8 the divisors are 1, 2, 4, adding to 7 — just short. For 12 they are 1, 2, 3, 4, 6, adding to 16 — over. So numbers come in three kinds, and perfection is the knife-edge between falling short and overshooting.

Mathematicians name all three: 8 is deficient, 12 is abundant, and 6 and 28 are perfect.

1.2.2 Asking Python whether one number divides another

To find divisors we need one new operator: %, said “mod” or “remainder”. It divides and reports what’s left over.

0
2

4 goes into 12 exactly, so the remainder is 0. 5 doesn’t, so 2 is left over. That gives us our test: number % d == 0 means d divides number.

Puzzle. % has a partner, //, which divides and throws the remainder away. 135 minutes is 135 // 60 = 2 hours, with 135 % 60 = 15 minutes left over.

a // b is how many whole times b fits into a; a % b is what’s left.

Note the double equals. A single = assigns a value; a double == asks whether two things are equal and answers True or False:

True
False

True and False are values just like 3524 and "3524" are, and they have their own type — bool, after George Boole. They will run the next two sections.

Puzzle. Each answer here is True or False, but get Python to work it out: don’t type True or False yourself.

== asks a question and answers True or False. % gives a remainder.

Which of these asks a question, and answers True or False?

• d = 4
  • A single = stores 4 under the name d. It doesn’t ask anything.
• d == 4
  • The double == asks whether d equals 4.
• d % 4
  • That’s a remainder: a number, not True or False.
• d = d % 4
  • This works out a remainder and stores it back in d.

1.2.3 Collecting divisors into a list

Now we can find every divisor of 28 by testing each candidate in turn and keeping the ones that pass — the chapter’s pattern, in its plainest form:

[1, 2, 4, 7, 14]
28

Three things to notice.

divisors = [] makes an empty list — a container with nothing in it yet. .append(d) puts one more value on the end. And sum(...) adds up everything a list contains, which saves us keeping a running total by hand.

This is the list doing its second job. In the Kaprekar section a list was something sorted handed us. Here it’s something we build up ourselves, one passing candidate at a time.

range(1, 28) stops at 27, so 28 is never tested against itself. That’s not an accident — the puzzle says to leave the number itself out.

Puzzle. Start each list empty and .append the values that pass. Some blanks need two lines: an if, then the append indented under it.

Test every candidate, keep the ones that pass: for, then if, then .append.

Which numbers does for d in range(1, 6): go through?

• 1, 2, 3, 4, 5, 6
  • range stops before its second number, so 6 isn’t included.
• 1, 2, 3, 4, 5
  • It starts at the first number and stops just before the second.
• 0, 1, 2, 3, 4, 5
  • It starts at the first number you give it, 1. Only range(6) starts at 0.
• 2, 3, 4, 5, 6
  • It starts at 1, not after it.

Let’s name it:

6
7
16
28

All four match what we worked out on paper: 6 and 28 land on themselves, 8 falls short, 12 overshoots.

Exercise 1: Find the abundant numbers

A number is abundant when its divisors add up to more than the number. Fill in the blank with the right comparison — <, > or ==.

(You should find five of them, and the smallest is 12.)

Puzzle. divisor_sum is set up for you. Write three more functions in the same style.

A function can return a question: return divisor_sum(number) == number hands back True or False.

1.2.4 The search

Now sweep a range and keep the survivors:

[6, 28, 496]

Three, in the first thousand numbers. Not dozens. Three.

You may be wondering why we stopped at 1,000 when the capstone asked about 10,000. Because this search is expensive: divisor_sum(candidate) walks every number below its argument, so checking everything up to 10,000 means roughly fifty million divisions. It would finish, eventually, and you would sit there watching it.

So let’s do what this book always does when brute force starts to hurt: think.

Puzzle. divisor_sum is set up for you. The last task may take a few seconds.

Task 3 needs two lines in the blank: an if testing divisor_sum(candidate) > candidate, and an append under it.

Which of these numbers is abundant?

• 8
  • Its divisors 1, 2, 4 add up to 7, just short: 8 is deficient.
• 28
  • 1 + 2 + 4 + 7 + 14 = 28 exactly: 28 is perfect.
• 18
  • 1 + 2 + 3 + 6 + 9 = 21, which is more than 18.
• 13
  • 13 is prime, so its only smaller divisor is 1. Very deficient.

1.2.5 Euclid’s shortcut

Look at what we found, in binary-flavoured pieces:

6 = 2 × 3 28 = 4 × 7 496 = 16 × 31

The left factors are 2, 4, 16 — powers of two. The right factors are 3, 7, 31 — each one less than the next power of two: 3 = 4 − 1, 7 = 8 − 1, 31 = 32 − 1. And each right factor is prime.

Euclid noticed this more than two thousand years ago and proved the rule:

If 2^p − 1 is prime, then 2^p−1 × (2^p − 1) is a perfect number.

Try it:

2 3 6
3 7 28
5 31 496
7 127 8128

(** is Python’s “to the power of”. 2**7 is 128.)

Puzzle. Build three lists with **, and turn Euclid’s rule into a function.

2**p is 2 to the power p. Brackets matter: 2**(p - 1) is not 2**p - 1.

For p = 4, Euclid’s rule gives 2³ × (2⁴ − 1) = 8 × 15 = 120. Why isn’t 120 perfect?

• 2⁴ − 1 = 15 is not prime
  • 15 = 3 × 5. The rule only promises a perfect number when 2^p − 1 is prime.
• 4 is even
  • p = 2 is even too, and it gives 6. What matters is whether 2^p − 1 is prime.
• 120 is too big
  • Size has nothing to do with it: 8128 is perfect.
• 15 is odd
  • 3, 7 and 31 are odd as well, and they all work.

There is our fourth perfect number: 8128. We didn’t search for it, we predicted it — and we can check that prediction cheaply, testing one number instead of ten thousand:

8128

So the answer to the capstone is 6, 28, 496, 8128 — four numbers under 10,000, three found by searching and the fourth found by thinking.

Tip

Why they’re so rare. The rule needs 2^p − 1 to be prime, and that is a demanding condition. p = 11 looks promising but 2¹¹ − 1 = 2047 = 23 × 89, not prime, so it yields nothing. The next p that works is 13, and it produces 33,550,336 — which is why the list stops at 8128 for a very long time.

Numbers of the form 2^p − 1 are called Mersenne primes. Only 52 are known. Finding new ones is an ongoing worldwide computing project, and each discovery hands mathematics one more perfect number. Whether any odd perfect number exists is unknown — an open question more than two millennia old.

Puzzle. A prime is a number above 1 whose only divisors are 1 and itself. In the language of divisor_sum (set up for you), its divisors other than itself add up to exactly 1.

return divisor_sum(number) == 1. What does that give for 1, whose divisor sum is 0?

1.2.6 Stretch problems

Stop searching so hard

divisor_sum(10000) tests 9,999 candidates, but divisors come in pairs: if 4 divides 100, so does 25. You never need to look past the square root. Rewrite divisor_sum to check only up to the square root of the number, adding both members of each pair. Then the search to 10,000 becomes quick.

Amicable numbers

220 and 284 are amicable: the divisors of each add up to the other. Check it with divisor_sum, then hunt for the next such pair below 1,500.

How close can you get?

Some numbers miss perfection by exactly one. Find the numbers under 100 whose divisor sum is one less than themselves. What do they all have in common?

1.3 The stamp problem

Capstone: You have an unlimited supply of 3-cent and 5-cent stamps, and no others. Which postage amounts can you not make?

1.3.1 Do it by hand first

Walk up from 1 and try:

Amount	Possible?	How
1	no
2	no
3	yes	3
4	no
5	yes	5
6	yes	3 + 3
7	no
8	yes	3 + 5
9	yes	3 + 3 + 3
10	yes	5 + 5
11	yes	3 + 3 + 5

Note

Pause and try. Keep going: 12, 13, 14, 15. Can you make all of them? Do you think you will ever hit another impossible amount?

Four failures so far — 1, 2, 4 and 7 — and then nothing but successes. It begins to look as though 7 is the last one ever. Let’s check that with code, and then prove it.

1.3.2 A list of yes and no

We want to record, for every amount, whether it can be made. That’s one True or False per amount — so a list of booleans, one slot per amount:

51
False

[False] * 51 builds a list of 51 copies of False. We’ll treat slot number n as the answer to “can I make n cents?”, so we start by assuming nothing is possible and switch slots on as we discover otherwise.

len(...) reports how many values a list holds. reachable[0] reads the value in slot 0. Positions count from zero, so a 51-slot list has positions 0 through 50 — which is exactly what we want, since we care about amounts 0 through 50.

Puzzle. Make lists with *, read a slot by its position, and change a slot by storing into it.

flags[0] = False stores into slot 0. A five-slot list ends at position 4.

After reachable = [False] * 51, which of these reads the last value?

• reachable[51]
  • 51 slots means positions 0 to 50. Position 51 doesn’t exist, and Python stops with an IndexError.
• reachable[50]
  • Counting from zero, the 51st slot is at position 50.
• reachable[len(reachable)]
  • len(reachable) is 51, so this is the same mistake as reachable[51]. reachable[len(reachable) - 1] would work.
• reachable[0]
  • That’s the first slot.

Now switch on every amount we can actually build. Try every combination of some 3s and some 5s:

False
True

Seven cannot be made; eight can. That matches the table.

This is our first nested loop — one for inside another — and all it means is “try every pairing.” The outer loop fixes a number of 3-cent stamps, and for each of those the inner loop runs through every number of 5-cent stamps. (17 threes is 51 cents and 10 fives is 50, so going further is pointless.) Chapter 2 is built almost entirely out of this idea.

Puzzle. Three nested loops. Each blank sits inside both loops, so it runs once for every pairing.

Task 3 is the stamp program from above with 2 and 7 in place of 3 and 5.

1.3.3 The search

Now collect the failures:

[1, 2, 4, 7]

Four impossible amounts in the first fifty, and nothing after 7.

not flips a boolean: not False is True. So if not reachable[amount] reads as “if this amount is not reachable” — which is precisely the question the puzzle asks.

Exercise 2: A different pair of stamps

Change the stamps to 4 cents and 7 cents and find the impossible amounts. Fill in the three blanks.

(For the last blank, remember a list’s final value is at position len(...) - 1. Compare your largest impossible amount with 4 × 7 − 4 − 7.)

Puzzle. The 3-cent and 5-cent reachable list from above is set up for you.

Task 3 has two parts: mark every reachable amount, then loop over range(1, 61) and count the slots still False.

1.3.4 Why it stops — and stays stopped

Here is the proof, and it is short enough to keep in your head.

We can make 8, 9 and 10 — three amounts in a row. Now notice: if you can make an amount, you can make three cents more, by adding one more 3-cent stamp.

So from 8 we get 11, 14, 17, … From 9 we get 12, 15, 18, … From 10 we get 13, 16, 19, …

Every whole number above 7 is 8, 9 or 10 plus some multiple of 3 — because those three cover all three possible remainders when you divide by 3. So every amount from 8 upward is reachable, forever, and 7 is the largest impossible amount.

Tip

Three in a row is the whole trick. Once you can make three consecutive amounts using 3-cent stamps as one of your coins, you can make everything above them. With stamps worth a and b cents that share no common factor, the largest unreachable amount is always

a × b − a − b

For 3 and 5 that’s 15 − 3 − 5 = 7, exactly what we found. It’s called the Frobenius number, and you may also meet it as the “Chicken McNugget theorem,” after the puzzle of which nugget quantities you can order.

The “no common factor” condition matters. With 4-cent and 6-cent stamps every total is even, so every odd amount is impossible forever and there is no largest one.

With 5-cent and 8-cent stamps, what is the largest amount you cannot make?

• 27
  • 5 × 8 − 5 − 8 = 27.
• 40
  • 40 is five 8s, so you can make it.
• 13
  • 13 is one 5 plus one 8.
• There isn’t one
  • That only happens when the stamps share a common factor, like 4 and 6. 5 and 8 share none.

1.3.5 Stretch problems

The nugget question

McDonald’s once sold nuggets in boxes of 6, 9 and 20. What is the largest number of nuggets you cannot buy exactly? (Adapt the search to three stamp sizes with a third nested loop.)

Check the formula

Try several pairs of stamp values with no common factor — 5 and 7, 3 and 8, 7 and 11 — and compare your largest impossible amount with a × b − a − b each time.

Count them

How many amounts are impossible with 3-cent and 5-cent stamps? Count the length of the impossible list. Then try 5 and 7. Can you guess the rule? (Compare your counts with (a − 1)(b − 1) / 2.)

1.4 The locker problem

Capstone: A school has 100 lockers, all closed, and 100 students. Student 1 flips every locker. Student 2 flips every 2nd locker. Student 3 flips every 3rd locker, and so on through student 100. “Flip” means open it if it’s closed, close it if it’s open. When everyone is done, which lockers are open?

This is the chapter’s capstone, and the answer is one of the most satisfying in elementary mathematics.

1.4.1 Do it by hand first

Take just ten lockers and ten students, and track them on paper. Write . for closed and O for open.

Start: all ten closed. Student 1 flips every one, so they all open. Student 2 flips lockers 2, 4, 6, 8, 10, closing them. Student 3 flips 3, 6, 9. Student 4 flips 4 and 8. And so on.

Note

Pause and try. Do it. Ten columns, ten rows, one row per student. It takes about five minutes and it is the difference between reading this section and understanding it. Which lockers are open at the end?

You should end with lockers 1, 4 and 9 open, and every other one closed.

1, 4, 9. Hold that thought.

1.4.2 Think about a single locker

Before coding anything, ask a smaller question: how many times does locker 12 get flipped?

Student 1 flips it, because 1 divides 12. Student 2 flips it. Student 3, 4, 6 and 12 flip it. Student 5 does not — student 5 touches lockers 5, 10, 15, and 12 isn’t among them.

So locker 12 is flipped exactly once by each of its divisors: 1, 2, 3, 4, 6, 12. That’s six flips. Starting closed and flipping an even number of times brings it back to closed.

Now locker 16. Its divisors are 1, 2, 4, 8, 16 — five of them. Five flips, an odd number, so locker 16 ends open.

That is the whole puzzle, restated:

A locker ends open exactly when it has an odd number of divisors.

We met divisors two sections ago, when we added them up. Here we only need to count them — and the parity of that count decides everything.

1.4.3 A list you change as you go

For the code we need to remember 100 lockers, each open or closed. A list of booleans again, exactly like the stamps — but used differently. There we switched slots on and left them on. Here we’ll be flipping them back and forth, and the list will carry the state of the whole school as the students go by.

101

101 slots so that positions 1 through 100 are real lockers; slot 0 goes unused, which keeps locker numbers and list positions identical and saves a great deal of confusion.

Puzzle. A list can count its own values: .count(True) says how many slots hold True.

doors[3] = not doors[3]: read the slot, flip it, store it back.

Now the students. Student k visits lockers k, 2k, 3k, … and range takes a third argument for exactly this — the size of the step:

[3, 6, 9, 12, 15, 18]

range(3, 21, 3) counts from 3 up to (not including) 21, in steps of 3 — precisely the lockers student 3 touches.

Puzzle. A negative step counts down: range(10, 0, -1) runs 10, 9, …, 1, and stops before 0.

range(start, stop, step): the stop is never included.

What does list(range(4, 20, 4)) give?

• [4, 8, 12, 16]
  • It starts at 4, steps by 4, and stops before 20.
• [4, 8, 12, 16, 20]
  • The stop value is never included. range(4, 21, 4) would reach 20.
• [0, 4, 8, 12, 16]
  • It starts at the first number, 4.
• [4, 5, 6, ..., 19]
  • The third number is the step, so it counts in fours.

Now let’s send all 100 students through:

[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

The perfect squares. 1, 4, 9, 16, 25, 36, 49, 64, 81, 100 — and our ten-locker experiment on paper gave 1, 4, 9, which is the same answer cut short.

The line doing the real work is:

lockers[locker] = not lockers[locker]

Read it as: take what’s in this slot, flip it, put it back. This is the list’s third and most important job. In Kaprekar a list was handed to us by sorted. In perfect numbers we built one up by appending. Here the list is state — a record of how things stand, edited in place as the program runs.

Exercise 3: Count the flips

Instead of flipping, count how many students touch each locker. Fill in the blanks so that flips[locker] ends up holding the number of divisors of locker.

Look at which lockers got an odd number of flips, and compare with the answer above. Do you see why _____ had to be what it was?

Puzzle. Run the corridor with different rules and collect the open lockers.

Task 2 is Task 1 again, with one change to the outer loop.

1.4.4 Why perfect squares

Now the mathematics, and it is lovely.

Divisors come in pairs. If d divides n, then so does n ÷ d, and those two multiply back to n. For 12: 1 pairs with 12, 2 pairs with 6, 3 pairs with 4. Six divisors, three pairs.

Pairing up is what makes the count even — and that’s the usual case.

But a pair can collapse. If d and n ÷ d are the same number, it only gets counted once. That happens exactly when d × d = n, which is to say when n is a perfect square.

For 16: 1 pairs with 16, 2 pairs with 8, and then 4 pairs with… 4. Itself. Two full pairs plus one lonely 4 makes five divisors — odd.

So:

odd number of divisors ⇔ some divisor is its own partner ⇔ n is a perfect square ⇔ locker n ends open

Nothing about lockers, students or flipping survives into that argument. The puzzle was a question about the parity of divisor counts wearing a disguise, and the answer was always going to be the squares.

Tip

Why this is the chapter’s capstone. It’s the only puzzle here where the code alone would leave you unsatisfied. Seeing [1, 4, 9, 16, ...] print out provokes the question rather than answering it: why those? You can run the program a thousand times and never learn why. Ten lines of reasoning about divisor pairs settles it completely, for 100 lockers or a million.

That’s the trade this whole book is about. The computer tells you what. Mathematics tells you why.

With 1000 lockers and 1000 students, which of these lockers ends open?

• 500
  • 500 isn’t a perfect square: its divisors pair up (1 with 500, 2 with 250, …), so it is flipped an even number of times.
• 961
  • 961 = 31 × 31. Its divisor 31 has no partner, so it’s flipped an odd number of times.
• 999
  • 999 = 27 × 37 isn’t a square. Even number of flips: closed.
• 1000
  • The square root of 1000 is about 31.6, not a whole number, so it is not a square.

1.4.5 Stretch problems

A thousand lockers

Change 100 to 1000 and predict the answer before running. How many lockers are open? (You should be able to say the number without any code at all.)

Only the first fifty students

Suppose only students 1 through 50 walk the corridor, but there are still 100 lockers. Which lockers are open now? Predict first — which lockers had a divisor bigger than 50, and what did losing that student do to their parity?

Twice around

What if every student goes down the corridor twice? What if the students are numbered 2 through 100, with student 1 staying home?

1.5 What all four had in common

Four puzzles, four answers, and every single answer was a list:

Puzzle	Which ones?
Kaprekar	6174
Perfect numbers	6, 28, 496, 8128
Stamps	1, 2, 4, 7
Lockers	1, 4, 9, 16, 25, 36, 49, 64, 81, 100

And every one was found the same way: test every candidate, keep the ones that pass. Lay the four programs side by side and you’ll see the same skeleton each time — a loop over candidates, a test, and a list collecting the survivors.

The list did three different jobs along the way, and they’re worth naming because you’ll use all three forever:

1. A list you’re handed. sorted(digits) gave us one.
2. A list you build up. divisors.append(d), one passing candidate at a time.
3. A list that holds state. lockers[locker] = not lockers[locker], edited in place as the program runs.

In the stamp program, which job is impossible doing?

• A list you’re handed
  • Nothing hands it over ready-made. It starts as [].
• A list you build up
  • It starts empty and each failing amount is appended.
• A list that holds state
  • That’s reachable, whose slots get switched on as amounts are found.

On the mathematics, each puzzle ended somewhere the code could not take us. Kaprekar had to stop because there are only finitely many four-digit numbers. Perfect numbers are rare because Mersenne primes are rare. Stamps run out of failures once three consecutive amounts are reachable. Lockers open exactly on the squares because only a square has a divisor that partners with itself.

In every case the program found the answer and the mathematics explained it.

Next chapter, the question changes. Instead of which ones, we ask how many — how many ways to make a dollar in coins, how many handshakes in a room, how many ways to climb a staircase. The answers stop being lists and become counts, and that single change will demand a different set of tools.