All numbers occur exactly once

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

All numbers occur exactly once

G H J

Reveal topic tags

relatively prime

L

G H BBookmark kLocked kLocked NReply

Source: St. Petersburg Olympiad 2015, 2nd Round, Grade 9, also known as Yellowstone Permutation

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3070 posts

#1 h Sep 24, 2016, 11:43 AM • 4 Y

Y by anantmudgal09, shinichiman, Adventure10, Mango247

A sequence of integers is defined as follows: $a_1=1,a_2=2,a_3=3$ and for $n>3$ , $a_n=\textsf{The smallest integer not occurring earlier, which is relatively prime to }a_{n-1}\textsf{ but not relatively prime to }a_{n-2}.$ Prove that every natural number occurs exactly once in this sequence.

M. Ivanov

This post has been edited 2 times. Last edited by Ankoganit, Sep 29, 2016, 3:59 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2649 posts

kk108

#2 h Sep 24, 2016, 12:07 PM • 2 Y

Y by Adventure10, Mango247

Ankoganit wrote:

A sequence of integers is defined as follows: $a_1=1,a_2=2,a_3=3$ and for $n>3$ , $a_n=\textsf{The smallest integer not occurring earlier, which is relatively prime to }a_{n-1}\textsf{ but not relatively prime to }a_{n-2}.$ Prove that every natural number occurs exactly once in this sequence.

M. Ivanov

Maybe induction ?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

226 posts

#3 h Sep 24, 2016, 12:19 PM • 1 Y

Y by Adventure10

Ankoganit wrote:

A sequence of integers is defined as follows: $a_1=1,a_2=2,a_3=3$ and for $n>3$ , $a_n=\textsf{The smallest integer not occurring earlier, which is relatively prime to }a_{n-1}\textsf{ but not relatively prime to }a_{n-2}.$ Prove that every natural number occurs exactly once in this sequence.

M. Ivanov

Try to show that $a_{n}=n$ , for all n. Then apply induction and that might bring you your required result

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3070 posts

#4 h Sep 24, 2016, 12:21 PM • 2 Y

Y by yrnsmurf, Adventure10

maths_isi wrote:

Try to show that $a_{n}=n$ , for all n.

That's not even true.

$a_5=9$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

226 posts

#5 h Sep 24, 2016, 12:38 PM • 1 Y

Y by Adventure10

Ankoganit wrote:

maths_isi wrote:

Try to show that $a_{n}=n$ , for all n.

That's not even true.

$a_5=9$ .

I apologise. Did a silly mistake

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2649 posts

kk108

#6 h Sep 24, 2016, 1:55 PM • 2 Y

Y by Adventure10, Mango247

Ankoganit wrote:

A sequence of integers is defined as follows: $a_1=1,a_2=2,a_3=3$ and for $n>3$ , $a_n=\textsf{The smallest integer not occurring earlier, which is relatively prime to }a_{n-1}\textsf{ but not relatively prime to }a_{n-2}.$ Prove that every natural number occurs exactly once in this sequence.

M. Ivanov

But I am quite sure you can do it by induction , right now I am a bit busy ; I will try it in 1 or 2 days .

This post has been edited 1 time. Last edited by kk108, Sep 24, 2016, 1:55 PM
Reason: Typo .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3070 posts

#7 h Sep 29, 2016, 4:00 PM • 2 Y

Y by Adventure10, Mango247

Hello, any ideas?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

9044 posts

#8 h Sep 29, 2016, 7:29 PM • 4 Y

Y by 62861, acegikmoqsuwy2000, Adventure10, Mango247

I can't quite believe that they really proposed this in a competition to students.
This sequence was first conjectured to be a permutation in $2004$ but the problem remained open for $10$ years until it was settled in $2014$ . See here for the proof and here for the corresponding OEIS entry.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4071 posts

#9 h Sep 29, 2016, 7:40 PM • 1 Y

Y by Adventure10

Especially for student in grade $9$
Anyway, the prove is quite simple and nice.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1001 posts

#10 h Sep 29, 2016, 8:08 PM • 1 Y

Y by Adventure10

ThE-dArK-lOrD wrote:

Especially for student in grade $9$
Anyway, the prove is quite simple and nice.

define "simple"

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2541 posts

#11 h Sep 30, 2016, 4:12 AM • 3 Y

Y by ThE-dArK-lOrD, Adventure10, Mango247

mathwiz_aku wrote:

ThE-dArK-lOrD wrote:

Especially for student in grade $9$
Anyway, the prove is quite simple and nice.

define "simple"

Perhaps he(she?) refers to the underlying ideas rather than the actual structure of the proof.

This post has been edited 1 time. Last edited by rafayaashary1, Sep 30, 2016, 4:12 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3212 posts

#12 h Sep 30, 2016, 3:01 PM • 7 Y

Y by anantmudgal09, Ankoganit, quangminhltv99, rafayaashary1, mijail, Adventure10, Mango247

Can some one please check this solution? Thanks.

Claim 1. There are infinite even numbers in the sequence.
Proof. Suppose that for all $i \ge K$ then $a_i$ is odd. Pick arbitrary large $N$ so $a_N$ is composite (it's possible since we can't have three consecutive primes in the sequence), we can substitute one of the prime divisor $p$ of $a_N$ by $2$ to get $\frac{2a_N}{p}$ . It's obvious that $\frac{2a_N}{p}< a_N$ and $\gcd \left( a_{N+1}, \frac{2a_N}{p} \right)=\gcd \left( a_{N+1},a_N \right)= 1$ . If $\frac{2a_N}{p} \ne a_i$ for all $i \le K$ then $a_{N+2}$ must be equal to some odd number that is less than $\frac{2a_N}{p}<a_{N}$ . Note that this is only true when $a_N$ is a composite. Similarly, we find $a_N>a_{N+2}>a_{N+4}> \cdots > a_{N+2i}=p$ for some $p$ . Such $p$ prime must exist since there are finite odd numbers less than $a_N$ . We can actually pick $N$ so that $2p \ne a_i$ for all $i \le K$ . Now, note that $p \mid a_{N+2i+2}$ and so $2p \ne a_{N+2i+2}$ , this can only happen when $2 \mid a_{N+2i+1}$ , a contradiction to the assumption. Otherwise if $2 \nmid a_{N+2i+1}$ we will get a contradiction to the smallest value possible of $a_{N+2i+2}$ . Thus, there are infinite even numbers in the sequence. $\square$

Claim 2. (the problem) Each natural number occurs exactly once in this sequence.

Proof. We prove by induction that each number occurs in the sequence. Suppose that $1,2, \cdots , t-1$ appear in the the sequence in the following order $a_{b_1},a_{b_2}, \cdots , a_{b_{t-1}}$ where $b_i<b_{i+1}$ with $1 \le i \le t-2$ . We will prove that $t$ is in the sequence. Assume not.

Case 1. If there exists $a_k>t$ such that $k>b_{t-1}$ and $\gcd (a_k,t)>1$ then we must have $\gcd (a_{k+1},t )>1$ , otherwise $a_{k+2}=t$ , the smallest number possible, a contradiction. Similarly, we find $\gcd (a_l,t)>1$ for all $l>k$ . Now, we pick a prime $p>t$ .

Suppose that there are $h$ numbers less than $pt$ and only receive prime divisors different from $p$ , occurring in this sequence. Pick $a_m<pt$ as one of such numbers where $m$ is maximal. We will prove that there exists prime $p>a_k$ in this sequence to give a contradiction in $\gcd (a_l,t)>1$ for all $l>k$ . Indeed, if $p$ occurs before $a_m$ then we are done. If not, consider $a_{m+2}$ . We follow $a_{m+2}=dp$ where $d\ne 1$ is the least divisor of $t$ , otherwise if $a_{m+2}<dp$ then all prime divisors of $a_{m+2}<pt$ are different from $p$ , a contradiction to the maximum of $m$ . Thus, $dp=a_{m+2}$ is in this sequence, which follows $a_{m+4}=p$ , a contradiction since $\gcd (a_{m+4},t )>1$ .

Thus, we can't have $\gcd (a_l,t)>1$ for all $l>k$ , which means $t$ is in this sequence.

Case 2. If for all $a_k>t$ and $k>b_{t-1}$ then $\gcd (a_k,t)=1$ . If $t$ is even then from Claim 1 we have a contradiction. Thus, $t$ is odd. Assume that all $h$ numbers less than $2t$ and relative prime to $t$ have been listed on the sequence. We pick an even number that occurs after those $h$ numbers, call it $a_m$ . It obvious that $\gcd (a_{m+1},2t)=1$ and $a_{m+2} \ge 2t$ . This follows $a_{m+2}=2t$ , a contradiction since $\gcd (a_{m+2},t)=t$ . Thus, this case can't happen.

Thus, in all case, $t$ is in the sequence. Hence, all natural number occurs exactly once in this sequence.

This post has been edited 3 times. Last edited by shinichiman, Oct 3, 2016, 8:20 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4071 posts

#13 h Sep 30, 2016, 3:18 PM • 2 Y

Y by shinichiman, Adventure10

shinichiman wrote:

Can some one please check this solution? Thanks.

Claim 1. There are infinite even numbers in the sequence.
Proof. Suppose that for all $i \ge K$ then $a_i$ is odd. For arbitrary large $N$ , consider odd $a_N$ , we can substitute one of the prime divisor $p$ of $a_N$ by $2$ to get $\frac{2a_N}{p}$ . It's obvious that $\frac{2a_N}{p}< a_N$ and $\gcd \left( a_{N+1}, \frac{2a_N}{p} \right)=\gcd \left( a_{N+1},a_N \right)= 1$ . If $\frac{2a_N}{p} \ne a_i$ for all $i \le N$ then $a_{N+2}$ must be equal to some odd number that is less than $\frac{2a_N}{p}<a_{N}$ .

What if $\gcd\left( a_N,\frac{2a_N}{p}\right) =1$ which occur when $a_N$ is prime.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3212 posts

#14 h Sep 30, 2016, 3:23 PM • 2 Y

Y by Adventure10, Mango247

ThE-dArK-lOrD wrote:

What if $\gcd\left( a_N,\frac{2a_N}{p}\right) =1$ which occur when $a_N$ is prime.

I don't quite get your question. In that part, I just want to show that $\gcd \left( a_{N+1}, \frac{2a_N}{p} \right)=1$ which is true whether $a_N$ is prime or not.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4071 posts

#15 h Sep 30, 2016, 3:26 PM • 3 Y

Y by shinichiman, Adventure10, Mango247

Hmm, but you conclude that $a_{N+2}$ must be odd number less than $\frac{2a_n}{p}$ .

But $\frac{2a_n}{p}$ is possible to not be one of the "candidates" (which require both $\gcd( \square , a_{N+1})=1,\gcd (\square ,a_N)\neq 1$ .)

Or I miss something?

This post has been edited 2 times. Last edited by ThE-dArK-lOrD, May 3, 2018, 7:43 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3212 posts

#16 h Sep 30, 2016, 3:34 PM • 2 Y

Y by ThE-dArK-lOrD, Adventure10

ThE-dArK-lOrD wrote:

Hmm, but you conclude that $a_{N+2}$ must be odd number less than $\frac{2a_n}{p}$

But $\frac{2a_n}{p}$ is possible to not be one of the "candidates" $\Big($ Which require both $\gcd( \square , a_{N+1})=1,\gcd (\square ,a_N)\neq 1$ $\Big)$

Or I miss something $?$

Oh, you're right. There's a case where $a_N$ is prime also. If that then we just have to pick $N$ so that $a_N$ is not a prime (because in this sequence, there are infinite composite numbers where we can't have three consecutive primes).

Thanks for the correction, ThE-dArK-lOrD.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2541 posts

#17 h Nov 24, 2016, 11:46 PM • 3 Y

Y by shinichiman, Adventure10, Mango247

Similar to a China TST Problem

This post has been edited 1 time. Last edited by rafayaashary1, Nov 24, 2016, 11:47 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

731 posts

#18 h Apr 15, 2025, 3:33 PM

Y by

Call the positive integers which belong to this sequence good.
Claim: There are infinitely many good primes.
Proof: Assume contrary. First suppose that a prime $q$ has infinitely many multiples in this sequence. Let $p$ be a sufficiently large prime. Each good number smaller than $qp$ will eventually occur in the sequence. There exists $q|a_m$ where $m$ is sufficiently large. Then, $a_{m+2}$ must be equal to $qp$ . If $p|a_{m+4}$ then $a_{m+4}=p$ . If $q|a_{m+4}$ , then $a_{m+4}\geq q(p+1)>p$ which is impossible.
Now suppose that each prime has finitely many multiples in the sequence. Notice that the smallest prime divisor of $a_n$ must be unbounded. Let $p$ be the smallest prime divisor of $a_m$ . Then, $a_{m+2}=p$ .

Claim: There are infinitely many even numbers in $\{a_i\}$ .
Proof: Suppose that all good evens are in $\{a_1,\dots,a_k\}$ . Pick a good prime $p>a_1,\dots, a_k$ . Then, $2p$ doesn't occur in this sequence. This implies $a_{\ell+2}=2p$ which is a contradiction.

Claim: All even positive integers are good.
Proof: Suppose that $2r$ is the smallest not-good even. For sufficiently large even $a_x$ , we see that $a_{x+2}=2r$ .

The Finish: Let $m$ be the smallest not-good positive integer. Let $p|m$ be any prime divisor. There are infinitely many good numbers multiple of $2p$ thus, if $a_y=2ps$ then $a_{y+2}=2p$ which yields $a_{y+4}=m$ . So any positive integers occurs in $\{a_i\}$ as desired. $\blacksquare$

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a