Sequence of integers $S_n$ where all elements that $n$ divides increment by one

Question

Let $S_1$ denote the sequence of positive integers ${1,2,3,4,5,6,cdots}$ and define the sequence $S_{n+1}$ in terms of $S_n$ by adding 1 to those integers in $S_n$ which are divisible by $n$. Thus, for example, $S_2$ is ${2,3,4,5,6,7,cdots}$ , $S_3$ is ${3,3,5,5,7,7,cdots}$ Determine those integers $n$ with the property that the first $n-1$ integers in $S_n$ are $n$.
This problem is from quite an old source with no solution or presence on the internet. I have a lengthy paragraph which I believe shows that the property exists if and only if $n$ is a prime or 1. The argument is clear from inspecting $S_3$, any element $n$ between two primes must join the set of monotonically increasing elements at the beginning of the sequence due to the existence of $S_n$. Since no $n$ divides the primes other than the prime and one, all preceding elements must equal the prime at this point and there are $n-1$ of them.
How can I prove this with a rigorous argument? Preferably without induction because I think we understand the problem better without it.

Calvin Lin · Answer

This approach does use induction, in part because the sets are defined inductively. I'm guessing it's similar to your solution.
Let the sequence be $ S_n = { S_{n,1} , S_{n,2 } , ldots }$.
Hint: Show that if $ a leq b$, then $ S_{n, a } leq S_{ n, b }$.
Hint: Show that $ S_{n,1 } = n $.
Hint: Hence conclude that if $n$ is prime, then $n = S_{n, 1} leq S_{n,2} leq ldots leq S_{n, n - 1 } = n$, so the condition is satisfied.
Hint: Show that if $ n$ is not prime, then $ S_{1, n-1 } = n$ and $  n+1 = S_{2, n-1} leq S_{n, n-1}$.
Hence conclude that if $n$ is not prime, then the condition isn't satisfied.

We can guess these facts by looking at the initial cases:
$ S_1 = { 1, 2, 3, 4, 5, 6, 7 , 8,  ....    }$
$ S_2 = {2, 3, 4, 5, 6, 7, 8, 9, ...    }$
$ S_3 = {3, 3, 5, 5, 7, 7, 9, 9, ...   }$
$ S_4 = {4, 4, 5, 5, 7, 7, 10, 10, ...   }$
$ S_5 = {5, 5, 5, 5, 7, 7, 10, 10, ....   }$
$ S_6 = {6, 6, 6, 6, 7, 7, 11, 11, ...      }$
$ S_7 = {7, 7, 7, 7, 7, 7, 11, 11, ...   }$

Sequence of integers $S_n$ where all elements that $n$ divides increment by one

One Answer

Add your own answers!

Ask a Question