What comes next in this sequence?

Aside: To comment on my recent Gresham College lectures please go to this blog entry. My most recent Gresham College lecture was on Monday 15 April.  I talked about proof, by human and by computer.  The lectures can be viewed on the Gresham College website.

*******************

Here's something which I found (presented in a different way) in a nice book by Anany and Maria Levitin, Algorithmic Puzzles (Oxford University Press, 2011).

Answers to all puzzles appear at the foot of the blog.

What is the next number in this sequence?

Puzzle 1: 

 1, 2, 3, 5, 7, 11, ... ?

The answer will come at the foot of this post, but think about it first!

What makes puzzles like this interesting?  They occur in IQ tests and psychometric tests which supposedly measure one's aptitude for a job.  But they are problematic.  If I were to ask a twelve-year old, "What comes next in the sequence 1, 2, 4, 8, ...?" I would expect the answer 16 - these are powers of 2.  If I were to ask a class of maths undergraduates, that answer would be too obvious - why would I be asking such a simple question - so they might deduce that something else was expected.  

Puzzle 2:

1, 2, 4, 8, ...?

So it is unlikely that the answer to Puzzle 1 is simply 13, as if I was listing the primes and forgot that 1 is not a prime.

Here's another one, but don;t waste time on this one:

0, 4, 4, 8, 10, 9, 11, 15, ?

Well, even the wonderful On-Line Encyclopedia of Integer Sequences can't solve this one!  In fact these were the waiting times in minutes listed on the electronic display for the arrivals of the next ten buses when I arrived at my local bus stop yesterday evening.  The next two numbers were 18 and 18.  But this sequence was essentially random and it has no interest as a puzzle.

When I learned at school that you can fit any set of n data points by a polynomial of degree n-1, it seemed to make sequence questions trivial.  A natural answer for a mathematician would be simply to fit the polynomial of least degree so that, for example, to find the next term in the sequence "1, 2, 4, 8 ..." I would just find the quadratic equation that goes through the points (1,1), (2,2) and (3,4) .  It is (1/2)s^2 - (1/2)x + 1, which gives us 7 for the fourth term in the sequence.

But this has no predictive power whatsoever, because for any possible numerical value of the next term, there is a polynomial equation that fits it.  If, at the beginning of next season, I record the number of goals scored by my football team in their first 5 matches as 0, 0, 0, 0 and 0 (which is not unlikely), I might take comfort from the fact that the formula (n-5)(n-4)(n-3)(n-2)(n-1) has successfully predicted the goals in the first five matches and that therefore I can expect my team to score 120 in their sixth match.  But the existence of the formula is proof only of the power of mathematics in representing data.

So if there are formulae which can represent any sequence and suggest any term I like for the next one, what is the interest in these questions?  In "intelligence" tests, I would argue that they are often testing simply testing your understanding of the context: any answer can be justified but the "correct" answer is the one that the setter had in mind, and your task is to work out what kind of answer is expected.  A mathematically over-sophisticated answer fails the test, which is about your ability to fit in as much as it is about mathematics.

But as a puzzle, if I ask a colleague or a student for the answer to Puzzle 1 or Puzzle 2, the whole point is that the answer is not the most obvious one (primes or powers of two).  It's a sort of mathematical joke: the recipient is not expected to get the answer, but will be amused when they hear it.  The joke is that the same initial sequences arise in very different contexts.  Before I give solutions, here's one more, which is based on what I was once told is Whitfield' Diffie's favourite sequence puzzle.

Puzzle 3: What comes next in this sequence:

138, 125, 116, 110, 103, 97, 86, 77, 68, 59, 51, ?

The Encyclopedia of Integer Sequences won't help with this one either.

Solutions follow:

***************************************************************************************

SOLUTIONS

Solution to Puzzle 1: There are no more numbers in this sequence. These are related to McNugget Numbers - McDonalds' Chicken McNuggets are sold in boxes of 4, 6, 9 and 20.  You can order any number of McNuggets by choosing suitable combinations of boxes, except for 1, 2, 3, 5, 7, 9 and 11.   (Wikipedia's discussion of McNugget Numbers excludes boxes of 4, which are perhaps only available in the UK.  As a vegetarian, I do not have first-hand knowledge here.)

Solution to Puzzle 2: 15.  The number of ways you can cut a cake with n cuts (in three dimensions,without rearranging the pieces between cuts, and assuming, rather unrealistically, that the cuts are perfect and don;t create extra pieces in the form of crumbs) goes 1, 2, 4, 8, 15, 26, 42, 64, ... (See the Encyclopedia of Integer Sequences)

Solution to Puzzle 3: Grand Central Station.  The terms of the sequence are consecutive stops on the New York Subway, Line Four (Check here!).