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

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