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

2 Asked on December 20, 2021

1 Asked on December 20, 2021

gaussian integral probability real analysis special functions upper lower bounds

1 Asked on December 20, 2021 by lovemath

markov chains matrices probability stochastic matrices stochastic processes

1 Asked on December 20, 2021 by 00gb

6 Asked on December 20, 2021 by user811107

2 Asked on December 20, 2021

2 Asked on December 20, 2021

linear algebra matrices positive definite projection matrices

2 Asked on December 20, 2021 by user553664

1 Asked on December 20, 2021 by user525033

algebraic curves algebraic geometry field theory ideals maximal and prime ideals

0 Asked on December 20, 2021 by vertum

2 Asked on December 20, 2021 by maximilian-levine

2 Asked on December 20, 2021

2 Asked on December 18, 2021

absolute value complex analysis complex numbers solution verification

2 Asked on December 18, 2021 by mathbs

2 Asked on December 18, 2021 by user0102

1 Asked on December 18, 2021 by stf91

0 Asked on December 18, 2021

algebraic topology differential geometry differential topology geometric topology smooth manifolds

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

0 Asked on December 18, 2021 by metioche

density function mean square error probability riemann integration

Get help from others!

Recent Questions

Recent Answers

- Lex on Does Google Analytics track 404 page responses as valid page views?
- Jon Church on Why fry rice before boiling?
- haakon.io on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?

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