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

[Robert Gerbicz]

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/
>