A sequence of integers is defined as follows: a1=1,a2=2,a3=3 and for n>3, an=The smallest integer not occurring earlier, which is relatively prime to an−1 but not relatively prime to an−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: a1=1,a2=2,a3=3 and for n>3, an=The smallest integer not occurring earlier, which is relatively prime to an−1 but not relatively prime to an−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: a1=1,a2=2,a3=3 and for n>3, an=The smallest integer not occurring earlier, which is relatively prime to an−1 but not relatively prime to an−2.Prove that every natural number occurs exactly once in this sequence. M. Ivanov Try to show that an=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 an=n , for all n. That's not even true. a5=9.
24.09.2016 15:38
Ankoganit wrote: maths_isi wrote: Try to show that an=n , for all n. That's not even true. a5=9. I apologise. Did a silly mistake
24.09.2016 16:55
Ankoganit wrote: A sequence of integers is defined as follows: a1=1,a2=2,a3=3 and for n>3, an=The smallest integer not occurring earlier, which is relatively prime to an−1 but not relatively prime to an−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≥K then ai is odd. Pick arbitrary large N so aN 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 aN by 2 to get 2aNp. It's obvious that 2aNp<aN and gcd. 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