Notes on A127202.
================
N. J. A. Sloane (njasloane@gmail.com), Mar 01 2017.

Definition: A127202 is defined by the rule that a(1)=1, a(2)=2; 
and thereafter a(n) is the the smallest positive integer not occurring
earlier in the sequence such that gcd(a(n), a(n-1)) does not equal 
gcd(a(n-1), a(n-2)).

Notation: (r,s) denotes the gcd of r and s.

Theorem: A127202 is a permutation of the positive integers.

Proof: 
1. Sequence is infinite.
Proof: Let g = (a(n-1), a(n)). If g = 1 then Q*a(n) is a candidate for a(n+1),
where Q is any prime not already in the sequence. If g > 1 then Q itself is a 
candidate for a(n+1). So the sequence can always be extended.

2. For all m, there exists an n_0 such that for all n > n_0, a(n) > m.
Proof: The sequence contains no repeated terms.  So n_0 = max{ n : a(n) <= m } 
is well-defined (whether or not m actually appears in the sequence).

3. If a prime p does not divide any term, then no prime q>p can divide 
any term either.
Proof: 
Look at the first term which is a multiple of q. Then
replacing q by p would give a smaller term that satisfies the conditions.

4. For all primes p, there is a term divisible by p.
Proof: Suppose no term is divisible by p. By 3, no prime greater than
p can divide any term. So all terms are products of the primes 
p_1 = 2, p_2 = 3, ..., p_k = previous_prime(p).
Using 2, go out far enough in the sequence so that all terms are > p!^3.
Consider two successive terms,
a(n)   = p_1^e_1 p_2^e_2 ... p_k^e_k,
a(n+1) = p_1^f_1 p_2^f_2 ... p_k^f_k;
with (a(n-1), a(n)) = Product_i p_i^min{e_i,f_i}.
Let f_j = max f_i (so f_j >= 2).
If e_j = 0 or e_j >= 2 then p_j*p < p!^3 is a smaller candidate for a(n+2),
since (a(n), a(n+1)) != (a(n-1), a(n));
if e_j = 1 then p_j^2*p < p!^3 is a smaller candidate for a(n+2),
since again (a(n), a(n+1)) != (a(n-1), a(n)).
In either case there is a contradiction.

5. For all primes p, there are infinitely many multiples of p in the sequence.
Proof: Suppose there are only finitely many multiples of p.
Choose p^s greater than any of these multiples.
Go out far enough in the sequence so that all terms are > p^s and are
not multiples of p. Consider terms
a(n), a(n+1), a(n+2), a(n+3), ... with gcds
...g_1.....g_2.....g_3...
All the g_i are relatively prime to p. If g_1 = 1 then g_2 != 1, and p^s
is a smaller candidate for a(n+2), a contradiction. 
If g_1 > 1 then p^s is a smaller candidate for a(n+1), again a contradiction. 
  
6. Every prime p appears in the sequence.
Proof: Suppose p is missing from the sequence.
Go out far enough in the sequence until all terms are > p^2.
Using 5, choose a term a(n) = k*p > p^2. Then p is a smaller candidate for a(n+1)
unless a(n-1) = m*p with (a(n-1),a(n)) = (m,k) = 1. But then p was
a smaller candidate for a(n). Contradiction. 

7. For any number m, there are infinitely many multiples of m in the sequence.
Proof: By 5 we can assume that m is not a prime. To present the proof we will 
assume that m is divisible by exactly three primes, say m = p^i q^j r^k,
with p,q,r, distinct primes and i,j,k >= 1.
The general case is similar.
We classify numbers into 8 classes:
C000 = numbers not divisible by p, q, or r.
C100 = numbers divisible by p but not divisible by q or r.
C010 = numbers divisible by q but not divisible by p or r.
C101 = numbers divisible by both p and r but not divisible by q.
etc.,
C111 = numbers divisible by all of p,q,r,
Suppose there are only finitely many multiples of m in the sequence,
let m^s be greater than any of these multiples, and go out
far enough in the sequence so that all terms are > m^s and are not
multiples of m -- that is, are not in C111.
If we see a gcd that is in C000 and is > 1 then the next term 
could have been m^s, a contradiction.
So from now on all gcds must be 1 or in one of C100,..., C011 (but not in C111).
If we see a term a(n) in C000 then its gcds with its two neighbors are both 1,
which is illegal. 
So all terms from here on are divisible by p, q, or r. But this contradicts 6.

8. Every number m appears in the sequence.
Proof: Same argument as in 6.

This completes the proof of the theorem.