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

Mathematics Asked by twentyyears on July 31, 2020

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.

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, ... }$$

Answered by Calvin Lin on July 31, 2020