Kominers's Conundrums: What Comes Next in the Sequence?

Scott Duke Kominers

29 Jun 2020, 11:32 AM IST

(Bloomberg Opinion) -- Numbers are everywhere: in grocery prices, our transit routes, the Bloomberg Terminal (of course). We have a tendency to try to find order in all of them. Often, that’s a futile exercise — most numbers in our lives are pretty random. But sometimes, the patterns are real.

Numerical patterns are the foundation of what — as far as I can remember — is the first type of puzzle I ever solved: sequence problems.

These puzzles are deceptively simple to state. We’re given just a list of numbers, and the question is What comes next? But that minimalism hides surprising complexity; unlike our story or wordplay puzzles, numerical sequences don’t come with much in the way of clues.

For example, suppose I gave you this sequence:

4, 6, 10, 18, 34, 66, 130, 258, 514 …

How would you start thinking about what the next element is?

First, you might look for properties of the numbers and notice that they’re all even and grow pretty quickly. That suggests that the next element is probably going to be even as well — and it will probably be big.

That narrows the problem down, but unfortunately not that much. To get more insight, it’s often a good idea to look at the larger numbers in the sequence. Those tend to be less common, which might point to a pattern we can extrapolate. Here, the large numbers might actually look more familiar: 258 and 514, for example, are each 2 more than standard computer memory sizes (256 GB and 512 GB, respectively).

But of course the sequence isn’t about computer memory. Memory just happens to come in sizes that are powers of 2, because that’s the number of addresses you can encode with a given number of binary digits. And indeed, powers of 2 are the key: The sequence is obtained by adding 2 to each power of 2, so the next element is 1024 + 2 = 1026.

Sometimes a sequence is “self-referential,” in the sense that the next element depends on previous ones. For example, you might know the Fibonacci sequence, which appears throughout mathematics and nature (and apparently the stock market):

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 …

After the initial 1s, each element of the sequence is constructed by adding the previous two elements together (1 + 1 = 2; 2 + 1 = 3; 3 + 2 = 5; and so forth).

Other times, a sequence may count something. For example,

2, 4, 7, 11, 16, 22, 29, 37, 46 …

colloquially known as the lazy caterer's sequence, counts the maximum number of pieces you can cut a pizza into using a given number of cuts straight across the pie, starting at “2” for a single cut.

Alternatively, a numerical sequence might be something entirely different. When the numbers jump around in no clear pattern, we might start wondering whether the sequence is really about numbers at all. For example,

10, 6, 13, 1, 13, 10, 10, 1, 19 …

looks totally mysterious. Why so many 10s and 1s? Why do the numbers go up and down?

The trick here is to translate the numbers into letters, treating “1” as “A,” “2” as “B” and so forth. Then we get

J, F, M, A, M, J, J, A, S …

Still mysterious? Not so much: Those are the first letters of the names of each month (January, February, March …). “S” stands for “September,” so the next is “O” for “October.” That’s the 15th letter in the alphabet, so “15” comes next in our original sequence.

We’re off next weekend for the July 4 holiday, so here are four sequences that you get almost two weeks to figure out (you don't have to solve all of them to submit your answers):

1, 3, 6, 10, 15, 21, 28, 36, 45, 55 … ?
1, 1, 2, 4, 7, 13, 24, 44, 81 … ?
73, 97, 1012, 1111, 1126 … ?
3, 13, 1113, 3113, 132113, 1113122113 ... ?

What comes next in each?

If you figure out any of them — or even make partial progress — please let me know at skpuzzles@bloomberg.net before midnight New York time on Wednesday, July 8. (If you get stuck, there’ll be hints announced in Bloomberg Opinion Today. Sign up here.)

Last Week’s Conundrum

We met a kaleidoscope of 38 secondary-colored chameleons hanging out in pairs. Whenever two chameleons of different colors met, they would both change to the third color. Starting off with 19 purple, 12 green and 7 orange, we asked whether at the end of the summer all of them could be purple — or green.

All green, it turns out, is possible: If four purple chameleons meet four green (in pairs, of course, to respect lizard social-distancing guidelines), then we end up with 15 purple, 8 green and 15 orange. Then having purple and orange chameleons meet up repeatedly eventually leads to all the chameleons being green.

That said, no matter what order the chameleons meet up in, they’ll never all be purple. To see this, we have to notice a surprising chameleon-count curiosity: No matter how the chameleons meet up, the difference between the number of green and orange chameleons always has the same remainder when divided by 3. (Wait, really?)

It’s true: At the start, there are 12 green and 7 orange, and 12 – 7 = 5 is 2 more than a multiple of 3. If a green and orange chameleon meet, then those two chameleons turn purple, leaving the green-orange difference unchanged (11 – 6 is still 5). And if instead, say, a green and purple chameleon meet, then the number of green chameleons decreases by 1 but the number of orange chameleons increases by 2. Now the difference is 11 – 9 = 2. This pattern continues no matter which chameleon meetings happen. Whenever two chameleons meet, the total adjustment between the green and orange counts is either 0 or 3, so the remainder when the difference is divided by 3 is unchanged.

If all the chameleons were purple, then we would have 0 green and 0 orange. But that would mean a difference between the two counts of 0, which can’t happen because the difference always has to leave a remainder of 2 when divided by 3.

Noam Elkies figured this out first, beating out Benjamin Phillabaum by just minutes. Others among the 14 solvers included Michael Branicky, Anna Collins, Benjamin Mathias Clark, Alex Jarzebowicz, Kevin Ke and Ajay Kumar K S.

The Bonus Round

Tour the Winchester Mystery House from home, or tune into pro marble racing (hat tip: Elizabeth Sibert). “Hamilton: The Online Jigsaw Puzzle”; 3-D printing Damascus steel; “Street-Fighting Mathematics”; from psychology Ph.D. to poker champ; turning clouds into adorable animals. And inquiring minds want to know: How can we tell if two words are anagrams of each other?

Even well-known sequences like the Fibonacci numbers can be made unfamiliar by making slight changes: 5, 3, 8, 11, 19, 30, 49 ..., for example, is like a Fibonacci sequence but starting with 5, 3 instead of 1, 1.

This puzzle is a classic that appears in Peter Winkler’s “Mathematical Mind-Benders”; there, Winkler reports that it appeared in the International Mathematics Tournament of the Towns in 1984.

In fact, the difference between every pair of counts has a fixed remainder when divided by 3; this is just the most relevant for our problem.

This column does not necessarily reflect the opinion of the editorial board or Bloomberg LP and its owners.

Scott Duke Kominers is the MBA Class of 1960 Associate Professor of Business Administration at Harvard Business School, and a faculty affiliate of the Harvard Department of Economics. Previously, he was a junior fellow at the Harvard Society of Fellows and the inaugural research scholar at the Becker Friedman Institute for Research in Economics at the University of Chicago.