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

[Benoît Jubin]

Very nice!
It seems that you can group Propositions (1b) and (2), with a proof
very similar to that in the Comments of A098550:

Proposition 2: Every prime power divides a term (hence infinitely many
terms) of the sequence.
Proof: Let p^i be a counterexample. (i) Let q > p^i be prime. Then q
does not divide any term in the sequence: if a(n) = tq is the first
such term, then a(n) = tp^i would have worked, contradiction. (ii) Let
m be such that a(m) >= p^(2i) and let q be a common prime factor of
a(m) and a(m-2). Since q < p^i, one has qp^i < p^(2i) <= a(m), so
qp^i, which does not appear among a(1),..., a(m-1), would have worked
for a(m). Contradiction.

On Sun, Dec 21, 2014 at 12:01 PM, Vladimir Shevelev <shevelev at bgu.ac.il> wrote:
> 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/
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/