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

Sun Dec 21 19:55:48 CET 2014

Yes, thanks!

What is your affiliation, and how do you want your name spelled?
I assume Ben\^{o}it Jubin (in latex) is correct?

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 1:31 PM, Benoît Jubin <benoit.jubin at gmail.com>
wrote:
>
> You're right, Neil, I should have rechecked.
> In the proof your Proposition 2, at the beginning, you probably mean
> something like "Choose i large enough so that p^i does not divide any
> term of the sequence" (rather than "is not in the sequence").
> Benoît
>
> On Sun, Dec 21, 2014 at 6:13 PM, Neil Sloane <njasloane at gmail.com> wrote:
> > Benoit, I was telling David Applegate about your message,
> > but he pointed out that this step fails:
> >
> > 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,...
> >
> > The difficulty is that a(n-1) could be divisible by p,
> > preventing a(n) = tp^i.
> >
> > That's why Proposition 1 was only stated for primes
> > not prime powers.
> >
> >
> >
> > 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 11:37 AM, Neil Sloane <njasloane at gmail.com>
> wrote:
> >>
> >> 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/
> >>>
> >>
> >
> > _______________________________________________
> >
> > Seqfan Mailing list - http://list.seqfan.eu/
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>