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 ?

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

maths_isi wrote: Try to show that $a_{n}=n$ , for all n. That's not even true. $a_5=9$.

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

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 .

Hello, any ideas?

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.

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

ThE-dArK-lOrD wrote: Especially for student in grade $9$ Anyway, the prove is quite simple and nice. define "simple"

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.

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.

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.

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.

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?

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.

Similar to a China TST Problem