A055874

What's the next number in this sequence?
1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 4, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1...
A quick look at the Online Encyclopedia of Integer Sequences (you have it bookmarked, don't you?) reveals this sequence to be A055874, "a(n) = largest m such that 1, 2, ..., m divide n." Take, for example, the sixth number in the list, 3. Then, think about the numbers that evenly divide into 6: 1, 2, 3, and 6. The first three divisors start a pattern of counting up from 1, by 1: 1, 2, 3. That patten is broken after the 3, so 3 is the largest number such that all of the positive integers from 1 to that number (i.e., 1, 2, and 3) divide evenly into 6. After the 3 is 1, the seventh number in the list. That means that, when counting up from 1 by 1's, the only numbers that divide evenly into 7 are 1. For 8, the list is 1 and 2, so the eighth number in the list is 2.

So, what is the next number in the list? There are already 23, so the next number is the largest positive integer in the list, starting from 1 and counting by 1's, that divides evenly into 24, or 4.

What else can we tell about this sequence? It contains the numbers 1 - 4; will all positive integers eventually show up? Specifically, when will 5 be seen? For 5 to be in the sequence, then there has to be a number x such that, 1, 2, 3, 4, and 5 all evenly divide into x, but 6 does not (because the numbers in this sequence are the largest in the list from 1). But, if 2 and 3 divide evenly into x, then 6 (2 × 3) will, too, so 6 will be in the list, meaning that 5 won't be the largest. Will 7 make it in the sequence? Yes, it first shows up in spot #420, and 8 in the 840th place. What about 9? In order for 9 to be there, 2 and 5 have to be there first, so 10 (2 × 5) will be in the list of divisors, so 9 won't be the largest. What other numbers are missing?

Every second number in the sequence is 1, because every second positive integer is odd, and for odd numbers, the list of incrementing divisors ends at 1. About one-third of the entries are 2. For two to be there, the product number must be even (2 is a divisor) and must not be a multiple of 3 (or else, 2 wouldn't be the largest in the list). So, the second and fourth entries are 2, but not the sixth or twelfth. In the first 10,000 elements of this sequence, 4 shows up about 1 time in 15, 6 one time in 70, and 7 only shows up 12 times. Can you figure out why? We know why 9 isn't there; how often should 10 occur?