[seqfan] Re: Almost a proof for Olson's A347113

[Neil Sloane]

Robert Gerbicz,  Your way of handling [3], there are infinitely many odd
terms, is very nice. Though I haven't checked all the details yet.  But the
basic idea is clear.
>From a certain point on, all the terms must be even.
So take each even term, say  a(n) = 2^k*(2m+1), k>0,
and construct a rival candidate, u = (2^k-1)*(2m+1) < a(n), which must be
blocked,
so it must already be in the sequence.  [There are complications because u
cannot be a(n-1)+1, but let's ignore that here.]
Also u >= a(n)/2, so there must be infinitely different u's, and all the
u's are odd.
So there are infinitely many odd terms.

Lovely!

Best regards
Neil

Neil J. A. Sloane, Chairman, OEIS Foundation.
Also Visiting Scientist, Math. Dept., Rutgers University,
Email: njasloane at gmail.com



On Mon, Nov 15, 2021 at 5:35 AM Robert Gerbicz <robert.gerbicz at gmail.com>
wrote:

> I've found a complete proof:
>
> 0. All terms are distinct.
>
> 1. The sequence is infinite.
>
> 2. The sequence goes to infinity (so lim a(n)=inf), trivially from [0] and
> [1].
>
> 3. It contains infinitely many odd numbers.
> proof:
> Suppose that not, in this case:
> let N for that a(n) is even for all n>=N, then
> a(n)=2^k*(2*m+1) for all n>N, where k>0 because a(n) is even,
> and let u=(2^k-1)*(2*m+1)<a(n) then
> 1<gcd(a(n),a(n-1)+1)<=gcd(u,a(n-1)+1)  [because a(n-1)+1 is odd]
> , but we haven't chosen u as a term, the only reason could be that u was
> already in the sequence, here u is odd and u>=a(n)/2, that is a
> contradiction because the odd numbers in the sequence would be also
> unbounded using [2]. [giving that we have infinitely many odd numbers].
>
> 4. It contains all even integers.
> proof: the same as in Neil's (3) proof, notice that from our [3] we already
> know that it contains infinitely many odd numbers.
>
> 5. It contains all odd integers. (you can also see Neil's last step (6):
> you need p>d prime and you can suppose that you've already seen all <d
> integers)
> One is in the sequence (a(1)=1). Suppose that d>1 is an odd integer and not
> in the sequence, then u=(2*k+1)*d-1 is even, hence that is in the sequence
> (say a(n)=u), and
> gcd(d,u+1)=gcd(d,(2*k+1)*d)=d>1, but d is not in the sequence giving that
> a(n+1)<d and that is contradicts to [2] as you select k->inf.  (or simply
> choose d different k values and for these you would see a(n+1)<d what is
> impossible, see [0].)
>
> The proof is complete.
>
> Neil Sloane <njasloane at gmail.com> ezt írta (időpont: 2021. nov. 14., V,
> 20:29):
>
> > Dear SeqFans, Remember the Yellowstone Permutation? We must have had a
> > dozen proofs that it was a permutation before we found one that held
> > water.  After a lot of struggling I have a proof that Grant Olson's
> A347113
> > is a permutation that has only a small hole (joke).  If someone can plug
> > the hole I would be very happy.  Here it is:
> >
> > A347113 was submitted to the OEIS by Grant Olson on August 18 2021.
> >
> > The definition is:
> >
> >
> > a(1)=1; for n > 1, a(n) is the smallest positive number k not yet in the
> > sequence such that gcd(k, a(n-1)+1) > 1 and k != a(n-1)+1.
> >
> >
> > Not a Theorem: A347113 is a permutation of the positive integers
> >
> >
> > Not a Proof:
> >
> >
> > The definition implies that all terms are distinct, so we just have to
> show
> > that every positive number appears.
> >
> >
> > 1. The sequence is infinite (for G*(a(n-1)+1) is always a candidate for
> > a(n), where G is larger than all previous terms).
> >
> >
> > 2. If k is in the sequence, say a(i) = k, let W(k) = i.
> >
> > If k is not in the sequence, let W(k) = -1.
> >
> > Let L(k) = max {W(i), i=1..k}. (W stands for "When", L stands for "Last")
> >
> > Then for n > L(k), a(n) > k.
> >
> >
> > 3. Claim: If the sequence contains infinitely many odd terms then every
> > positive even number appears.
> >
> > Proof: Suppose not, and let e denote the smallest missing even number.
> >
> > Choose an n > L(e^2) such that a(n) is odd. Then x = a(n) is odd and >
> e^2,
> > and a(n+1) > e^2.
> >
> > Since y = x+1 is even, gcd(e, y) >= 2, and e was a smaller candidate for
> > a(n+1).
> >
> > Contradiction.
> >
> >
> > 4. For the next step, we need a cunning lemma.
> >
> >
> > Lemma: A Cunningham chain of primes, p, 2*p+1, 4*p+3, 8*p+7, ... cannot
> > have infinite length.
> >
> > For proof see for example G. Löh, Long chains of nearly doubled primes,
> > Math. Comp., 53 (1989), 751-759.
> >
> >
> > THE NEXT STEP IS UNFINISHED.
> >
> > 5. Claim: If the sequence contains infinitely many even terms then it
> > contains infinitely many odd terms.
> >
> > Proof: Suppose not, let S denote the finite set of odd terms in the
> > sequence, and let sigma be the largest odd term.
> >
> > Our plan is to force another odd term, which will be a contradiction.
> >
> >
> > Choose an n > L(sigma^4). Then x = a(n) is even, and
> >
> >   y = x+1 is odd and greater than any member of S. We want to find Z =
> > a(n+1).
> >
> >
> > Let T denote the set of even numbers that are missing from {a(1), a(2),
> > ..., a(n)} and are <= 2*sigma.
> >
> >
> > When we have a candidate odd number d to add to the sequence, if there
> is a
> > rival even candidate t in T
> >
> >   that is less than d, t will be preferred to d.
> >
> >
> > It could happen that y is a prime p, in which case Z = x+1 = p is not
> > allowed, we are forced to take Z = 2*p, and we don't get the odd term we
> > need. So we repeat the process and consider x = a(n+1) = 2*p, and y =
> > 2*p+1, and again y could be a prime. (This would be the start of a
> > Cunningham chain.) But by the Lemma, eventually y will be composite.
> >
> >
> > So we can assume y is composite.
> >
> > For the next step, let's start with an easy case.
> >
> > If y = p*q where p <= q are both huge, then p is the smallest candidate
> for
> > the next term and since it is not in S, we have found a new odd term,
> which
> > contradicts the fact that S was the full list of odd terms.
> >
> >
> > In general, let p_1, p_2, ... be the distinct primes that divide y.
> >
> > The legal candidates for Z are the numbers lambda * p_i that are not yet
> in
> > the sequence.
> >
> >
> > If the smallest candidate is even, it may or may not be in T.
> >
> >
> > THERE IS A GAP HERE.
> >
> > (The idea was to show that either we get a new odd term, or the odd term
> is
> > blocked by a smaller even term which is in T, but then T shrinks by one
> > term, and we repeat the process.  But I can't quite get the argument to
> > work.)
> >
> >
> > 6. Claim: Every number appears.
> >
> > Proof: Since the sequence is infinite, from 3 and 4 we know every even
> > number appears.
> >
> > If it does not contain every odd number, let d be the smallest missing
> odd
> > number.
> >
> > Find a large even term a(n) = p*d - 1 where p is a prime. Then a(n) =
> p*d,
> > and d is the smallest candidate for a(n+1), so a(n+1) = d, contradiction.
> >
> >
> > QED
> >
> > --
> > Seqfan Mailing list - http://list.seqfan.eu/
> >
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>