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

Get help from others!

Recent Questions

- How can I transform graph image into a tikzpicture LaTeX code?
- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?

Recent Answers

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

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP