[seqfan] Almost a proof for Olson's A347113

[Neil Sloane]

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