Natural number impostors

by David Radcliffe

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

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 = 9 to = 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
Advertisements