# 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

## Related Questions

### stationary independent increments: f(t+s) = f(t) + f(s), therefore f(t)=ct

2  Asked on December 20, 2021

### Let $Phi$ be standard Gaussian CDF and $u > 0$. What is good u-bound for $int_0^1Phi(u/r – ur)dr$ as a function of $u$?

1  Asked on December 20, 2021

### Diagonal of (self) product of doubly stochastic transition matrix

1  Asked on December 20, 2021 by lovemath

### $mathbb R$ as continuum many of pairwise disjoint of Bernstein sets

1  Asked on December 20, 2021 by 00gb

### How to evaluate the following limit: $lim_{xto 0}frac{12^x-4^x}{9^x-3^x}$?

6  Asked on December 20, 2021 by user811107

### Is my proof for $f$ is convex iff $f’$ is monotonically increasing correct?

2  Asked on December 20, 2021

### Is difference of two projection matrices positive semi-definite or negative definite or indefinite?

2  Asked on December 20, 2021

### Directly Calculating Birthday Paradox Probabilites

2  Asked on December 20, 2021 by user553664

### Show that $mathfrak{m}_p$ is an ideal in $mathcal{O}_V.$

1  Asked on December 20, 2021 by user525033

### Nonlinear diffusion (heat) equation

0  Asked on December 20, 2021 by vertum

### What is the difference between a semiconnected graph and a weakly connected graph?

2  Asked on December 20, 2021 by maximilian-levine

### For $pin (0, 1)$ and $nrightarrow infty$, how do I evaluate a general term in the binomial expansion of $(p+1-p)^n$?

2  Asked on December 20, 2021

### If $|{z}|=maxbig{|{z}+2|,|{z}-2|big}$, then which is true: $|zpm bar{z}|=2$ or $|zpm bar{z}|=1/2$?

2  Asked on December 18, 2021

### Is there an explicit solution to $a^x+b^x=1$?

4  Asked on December 18, 2021

### Let $Acup B$ be open, disconnected in $Bbb{R}^2$ where $A,B$ are non-empty, disjoint. Are both $A,B$ open in $Bbb{R}^2$?

2  Asked on December 18, 2021 by mathbs

### How do we apply the dominated convergence theorem to conclude the proposed claim?

2  Asked on December 18, 2021 by user0102

### $G$ acts faithfully on $Omega$, $Aleq G$, $A$ transitive on $Omega$. Then $|C_G(A)|$ is a divisor of $|Omega|$.

1  Asked on December 18, 2021 by stf91

### Kirby and Siebenmann obstruction for $D neq 5$?

0  Asked on December 18, 2021

### CDF approximation – L’Hopital’s rule

2  Asked on December 18, 2021 by mina-kay-nak

### What does the ‘expected value’ E represent in mean integrated squared error (MISE)

0  Asked on December 18, 2021 by metioche