# 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.

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

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

### Ask a Question

Get help from others!

© 2022 AnswerBun.com. All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP, SolveDir