The next number in the sequence

We'll start today's post with what I think is a relatively easy set of puzzles. What is the next number in each of the following sequences?

a. 1 2 3 4 5 6 7 8 9 10 11 12

b. 1 1 2 3 5 8 13 21

c. 8 8,000,000,000 8,000,000,008

d. 31 28 31 30 31 30 31 31 30 31

e. 3 1 4 1 5

f. 1 11 21 1112 3112 211312 312213 212223

g. 1 1 4 1 9 2 16 3 25 5 36 8 49 13

My Answers:

a. 13

b. 34

c. 8,000,000,080

d. 30

e. 9

f. 114213

g. 64

My reasons:

a. They are the natural numbers in increasing order.

b. They are fibonacci numbers.

c. They are the numbers in alphabetical order (in English).

d. They are the number of days in the months of the year.

e. They are the (decimal) digits of pi. 

f. Each term describes the contents of the previous term. ie - the first term contains one 1, the second two 1s, the third one one and one two..

g. The odd terms are successive squares, the even terms successive fibonacci numbers.

We've recently been having an argument in the office about whether puzzles like this make sense. There is one sense in which they don't - there is some degree 13 polynomial which evaluates to 1 at 1, 2 at 2, 3 at 3 and 8,000,000,080 at 13, so arguably, that would be a valid answer to my sequence a. However, I think everyone can agree that that's just silly. The interesting question is *why* can we all agree that it's just silly? 

When we were discussing this in the pub, Nev suggested that 16,000,000,008 was an equally valid answer to sequence c., presumably on the grounds that we have a fibonacci sequence which happens to begin 8, 8,000,000,000. This, however, feels fundamentally unsatisfactory - why choose those two numbers in particular to seed the sequence?

Another sequence with an alternative answer is e. You could argue that 1 is a valid continuation, with the sequence being, in fact, two interlocking sequences, one arithmetic sequence, one constant sequence - in fact, this was exactly the sort of description I claimed was right for problem g! However, this feels unsatisfactory here - why choose to start your arithmetic sequence at 3? Why choose the constant sequence 1? 

I believe that the reason for our intuition that these are the "correct" answers to these sequence puzzles can be formalised, and it requires the notion of Kolmogorov Complexity. In essence, the "right" sequence is the one that can be expressed with the smallest description. Note that for certain definitions of "smallest", this does indeed make "the numbers in alphabetical order" a better answer than "a fibonacci-type sequence starting with 8, 8,000,000,000", and it does so for precisely the reason we would hope. To specify the starting numbers 8 and 8 billion you need to give 60 extra bits of information.

Another way to think about this is that the probability of picking this particular example given that the sequence is "a fibonacci-type sequence" is something like 1 in 16 quintillion. On the other hand, the probability of picking this particular sequence given that it is an "alphabetical order"-type sequene is pretty close to 1 - so unless "alphabetical order-type" sequences are somehow fundamentally 16 quintillion times more complicated than 'fibonacci-type" sequences, the given explanation is more satisfactory.

One problem with the notion of Kolmogorov Complexity is that it depends fairly heavily on which language (language meant in the formal sense here, although it applies in the less formal sense too) you use to encode the sequences. So, for example, for someone who has never spoken a word of English, the 'fibonacci' answer to sequence c. is likely to be the most parsimonious, and if we didn't use the decimal system, so had only ever seen pi written as 11.0010010000111111011010101, then "1" would probably seem like a good answer to sequence e.

So, I agree, these questions are fundamentally subjective - if I'd written this post in French, for examlpe, then sequence c. would read 100, 105, 150, 155, 152, 151, etc... However this doesn't mean that there isn't a 'right answer' for whatever encoding system we happen to be working in at the moment - and I think we generally do agree on which encoding system is sensible, especially if we happen to all be speaking the same language and all be competent mathematicians.

Finally, I'll leave you with a classic:

What is the next number in this sequence?

4, 2, 3, 4, 6, 2, 4, ?