The next number is 9. This is Golomb’s sequence, a non-decreasing sequence of integers in which an is the number of times that n occurs in the sequence. We’re given a1 = 1 to start with, and this indicates that the number 1 appears only once in the whole sequence. That means that a2 is greater than 1. Setting a2 to 2 immediately tells us that 2 appears twice in the sequence, so a3 also must be 2. That tells us that 3 occurs twice in the sequence, and so on. In this way each number in the sequence is uniquely determined.