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

[Neil Sloane]

Benoit, Excellent!  That cuts the number of steps in the proof from 4 to 3.

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


On Sun, Dec 21, 2014 at 9:26 AM, Benoît Jubin <benoit.jubin at gmail.com>
wrote:
>
> 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/
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>