[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
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
More information about the SeqFan
mailing list