[seqfan] Re: A short proof that A098550 is a permutation

[Vladimir Shevelev]

Thank you! Breathtakingly beautiful !

Best regards,
Vladimir

________________________________________
From: SeqFan [seqfan-bounces at list.seqfan.eu] on behalf of Neil Sloane [njasloane at gmail.com]
Sent: 21 December 2014 02:29
To: Sequence Fanatics Discussion list
Subject: [seqfan] A short proof that A098550 is a permutation

Dear Seqfans, There has been some progress on A098550.
After discussions involving David Applegate, Brad Klee,
Bob Selcoe and myself, we now have a short proof
that the sequence is a permutation of the natural numbers.

Proposition 1:  The sequence is infinite. For any prime p, there is a
term divisible by p. [Proof - see Comments in A098550]

Proposition 2: Any prime p divides infinitely many terms.
Proof: Suppose not.
Let M be such that p does not divide a(n) for n >= M.
Choose a value of p^i that is not in the sequence.
Choose a prime q > p^i which does not divide any of a(1),...,a(M).
There is some term divisible by q, so let a(k)=tq be the first such term.
Certainly k>M. Then gcd(a(k-2),t) > 1. But then tp^i < tq is a smaller
candidate for a(k), a contradiction.

Proposition 3: For any prime p there is a term with a(n)=p.
Proof: Suppose not. Choose M large enough so that, for all n >= M, a(n)>p.
(In other words, choose M so that all numbers <= p which
are ever going to appear have appeared.)
Choose n>=M such that a(n)=kp for some k. Then a(n+2)=p,
a contradiction.

Proposition 3: For any prime p there is a term with a(n)=p.
Proof: Suppose not. Choose M large enough so that, for all n >= M, a(n)>p.
(In other words, choose M so that all numbers <= p which
are ever going to appear have already appeared.)
Choose n>=M such that a(n)=kp for some k. Then a(n+2)=p,
a contradiction.

Proposition 4: All numbers appear.
Proof: If not, let q be the smallest missing number, and choose M
such that 1,...,q-1 have occurred in a(1),...,a(M).
Let p be a prime dividing q.  Since p divides infinitely many terms,
there is a number N>M such that gcd(a(N),q)>1.
Then gcd(a(n),q)>1 for ALL n>N.  ...... (*)
[If not, for some k>=N we would have
gcd(a(k),q)>1 and gcd(a(k+1),q)=1, implying a(k+2)=q.]
But (*) is impossible, because we know there are infinitely many
primes in the sequence.
This completes the proof that A098550 is a permutation.

For the moment that is all we know for certain. We also have a
number of conjectures about the numerical behavior - when primes
occur, etc., including a conjectured upper bound
that, asymptotically, a(n) < n*log(n) / (2*loglog(n)).
We are in the process of writing all this up.

Best regards
Neil

Neil J. A. Sloane, President, OEIS Foundation.
11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
Phone: 732 828 6098; home page: http://NeilSloane.com
Email: njasloane at gmail.com

_______________________________________________

Seqfan Mailing list - http://list.seqfan.eu/