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

[Benoît Jubin]

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/