[seqfan] Almost a proof for Olson's A347113

Neil Sloane njasloane at gmail.com
Sun Nov 14 20:29:08 CET 2021

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


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.


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 =

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.


(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

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

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.


More information about the SeqFan mailing list