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
Problem
Source: St. Petersburg Olympiad 2015, 2nd Round, Grade 9, also known as Yellowstone Permutation
Tags: number theory, relatively prime
24.09.2016 15:07
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 ?
24.09.2016 15:19
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
24.09.2016 15:21
maths_isi wrote: Try to show that $a_{n}=n$ , for all n. That's not even true. $a_5=9$.
24.09.2016 15:38
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
24.09.2016 16:55
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 .
29.09.2016 19:00
Hello, any ideas?
29.09.2016 22:29
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.
29.09.2016 22:40
Especially for student in grade $9$ Anyway, the prove is quite simple and nice.
29.09.2016 23:08
ThE-dArK-lOrD wrote: Especially for student in grade $9$ Anyway, the prove is quite simple and nice. define "simple"
30.09.2016 07:12
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.
30.09.2016 18:01
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.
30.09.2016 18:18
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.
30.09.2016 18:23
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.
30.09.2016 18:26
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?
30.09.2016 18:34
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.
25.11.2016 02:46
Similar to a China TST Problem