### Natural number impostors

#### by David Radcliffe

Dave Gale (@reflectivemaths) asked the following question on Twitter:

What comes next: 1 2 3 4 5 6 7 8 9 ? #mathchat

— Dave Gale (@reflectivemaths) July 25, 2012

The obvious answer is 10, but Dave’s answer was 11 because he had in mind the sequence of palindromes in base 10.

There are infinitely many ways to continue any given sequence, so the question has infinitely many “correct” answers. I looked up the sequence *1,2,3,4,5,6,7,8,9* in the On-Line Encyclopedia of Integer Sequences (OEIS), which is an enormous database containing over 200,000 integer sequences. This search returned 1825 sequences, among which were A000027 (the natural numbers) and A002113 (palindromes in base 10).

I wondered how many of these sequences continued to 10, so I looked up the sequence

*1,2,3,4,5,6,7,8,9,10*. This search returned only 1088 sequences. Based on this result, I predicted that there was a 60% chance that the next number in Gale’s sequence was 10. (1088/1825 = 0.596.) Alas, my guess was incorrect.

This raises the following question. How many of the sequences in the OEIS are “natural number impostors”? That is, if a sequence contains the first *n* positive integers consecutively, then what is the probability that the next term is *n*+1? Having formulated this question, which has no importance whatsoever, I was nevertheless driven to find an answer. The results are shown below.

The abrupt decrease from *n *= 9 to *n *= 10 is probably explained by the fact that many of the sequences in the OEIS are defined in terms of their base-10 representations. My raw data is listed below.

n a(n) 1 133108 2 56891 3 16940 4 6931 5 4239 6 3084 7 2467 8 2090 9 1825 10 1088 11 761 12 615 13 498 14 437 15 386 16 320 17 286 18 264 19 249 20 230 21 207 22 198 23 188 24 180 25 169 26 164 27 159 28 154 29 140 30 132 31 125 32 117 33 110 34 105 35 103 36 100 37 93 38 91 39 89 40 85

So now you need to compute b(n)=a(n+1)/a(n).