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

[Robert Gerbicz]

OK, it also has a hole, correction, similar to Neil's idea.
What I've left out in [3] is that in the definition you can't choose
a(n)=a(n-1)+1, [of course the reason is that otherwise a(n)=n would be the
sequence].

What happens if u=(2^k-1)*(2*m+1)=a(n-1)+1 ?
We can still choose v=(2^k-3)*(2*m+1) if k>1 and for this v>=a(n)/4.  Now
we have 2 odd candidates, and both of them can't be equal to a(n-1)+1. The
rest is the same.

But there is no similar argument for k=1, so now we can assume that
a(n)=2*(2*m+1) and a(n-1)=2*m for all n>N (with different m values)
The solution of this easy recursion:
a(N+c)=2^c*(a(N)+2)-2 for all c>=0.

We know that there is no infinite long Cunningham chain using primes
so for infinitely many c values we see that
x=a(N+c)+1=2^c*(a(N)+2)-1 is composite.
Let p<=sqrt(x) be the smallest prime divisor of x
then all p,2p,...,(x/p-1)*p would be a good candidate for a(N+c+1), all of
these are less than x, so can't be a(N+c)+1.
And should appear among a(1),...,a(N+c), because we have selected a larger
number a(N+c+1)=2*x; hence:

x/p-1<=N+c  but x/p>=sqrt(x)>=2^(c/2) so:
2^(c/2)-1<=N+c, that is a contradiction for large c value (N is fixed).

And now the proof is complete with the corrected [3] step.



Robert Gerbicz <robert.gerbicz at gmail.com> ezt írta (időpont: 2021. nov.
15., H, 11:35):

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