A positive integers sequence is defined such that, for all , is the greatest prime divisor of . Find:

This is indeed a charming little problem. As it is a little convoluted in character, I wish to make it a little more straightforward by setting . The general setting with arbitrary starting values leads to "essentially" the same problem, but restricting those values to 1 helps to avoid unnecessary variables.

For convenience, I set , so that will be the biggest prime divisor of . In order to gain some familiarity with the situation, the following table provides the relevant values for :


3 2 2 2/3
4 4 2 1/2
5 6 3 3/5
6 9 3 1/2
7 12 3 3/7
8 15 5 5/8
9 20 5 5/9
10 25 5 1/2
11 30 5 5/11
12 35 7 7/12
13 42 7 7/13
14 49 7 1/2
15 56 7 7/15
16 63 7 7/16
17 70 7 7/17
18 77 11 11/18
19 88 11 11/19
20 99 11 11/20
21 110 11 11/21
22 121 11 1/2
23 132 11 11/23
24 143 13 13/24
25 156 13 13/25
26 169 13 1/2
27 182 13 13/27
28 195 13 13/28
29 208 13 13/29
30 221 17 17/30


With respect to this table, we will refer to the first column as the index or line number, to the second column as the -column, to the third column as the -column, and to the respective entries as -values and -values.

The table suggests to some extent that the limit of is , and we will now examine that hypothesis.

When we take a look at our table, we see that it consists of sections of constant values for . In lines 12 to 17, for example, we consistently have the value 7 in the -column. We will now investigate these sections a little closer, focussing on the values of and . For that purpose, we define to be the -th prime number (in their natural increasing order), i.e. , etc.

We start our investigation in line 5 which marks the beginning of the section of the value 3 for . We observe that the -value and the -value, that is 6 and 3, can be written as and for . Plainly speaking, the -value is the product of the corresponding prime in the -column and the previous prime. We will show that this is no coincidence for the first line of such a section.

We make a sketch of an inductive argument: By inspection, we see that, at the beginning of the section with the -value 3, we do indeed have and in those two columns. By definition of , the value in the -column in the next line is which is the same as . If the value in the -column of that line does not change, is added to the -value in the following line once again, resulting in the value there, and as long as nothing changes in the -column, the values in the -column will be of the form , in the following lines.

The value in the -column will change once we reach the smallest such that has a prime factor larger than . As two different prime numbers are always relatively prime, this is equivalent to the fact that divides . We start with , when is smaller than and also smaller than any candidate prime number (which must even be greater than ). Clearly, the first such that has a prime divisor greater than is the one with , so that our new prime number will be , which then does not only divide , but will be equal to it.

This shows that the length of the section under investigation is lines (as that was the crucial value of which initiated a change in the -column). The last line of that section will have the value in the -column and in the -column, and the new section will therefore begin with a line that has in the -column and in the -column. In particular, this shows that the values in the -column run through all the prime numbers in a monotonously increasing way.

So far, we have described the values in the -column in terms of the sequence . Now we have to consider them as actual elements of the sequence , which, loosely speaking, means that we have to find a relation between those values and the line number.

The crucial insight of our work so far is now that, in the -column, the prime number prevails for exactly lines. Thus the prime number , which appears for the first time in line 5, is succeeded by in line . By induction, the prime number (for some integer ) will appear in the -column for the first time in line
and this telescoping sum is the same as

This means nothing less than
and therefore
As the -value does not change within a section (by definition of a section), we can conclude that, at the end of the section, which comes lines later, we have
Within a section, the values of are clearly strictly decreasing, as it is only the index which changes. Therefore, to establish the limit of , which is the ultimate objective of this text, it suffices to focus on the values of at the beginning and at the end of each section. If the values of the subsequence at the beginning, i.e.
and at the end, i.e.
converge to the same limit, the entire sequence will converge to that same limit by the squeezing theorem. There is the (still open) conjecture that there are infinitely many twin primes. If we assume that the conjecture is true, this would easily show that the only possible limit of our two subsequences from above, and therefore the whole sequence, is indeed .

To actually prove that limit statement, some sophisticated approximation of is needed. I am somewhat hesitant to proceed here, however, as I feel that this is beyond what is reasonable for a problem from a Math olympiad. To me, the attraction of this problem lies in uncovering the more elementary results from above. If others can produce an elementary proof of the limit statement, though, I am very interested in hearing about it.