[seqfan] Re: The iterations (x -> 2x-1) and (x -> 2x+1) of primes

[M. F. Hasler]

On Mon, Aug 10, 2020 at 8:47 AM Tomasz Ordowski <tomaszordowski at gmail.com>
wrote:

> The recursion a(n) = 2 a(n-1) - 1 with a(0) = p is given by the formula
> a(n) = (p-1)2^n+1.
> The recursion b(n) = 2 b(n-1) + 1 with b(0) = p is given by the formula
> b(n) = (p+1)2^n-1.
> Problem:
> Are there primes p such that both a(n) and b(n) are all composite for 0 <
> n < p ?
> Conjecture:
> If p is a prime, then there exists 0 < n < p such that a(n) or b(n) is
> prime.
> Try to disprove this strong conjecture!
>

It is certainly difficult to find small counter-examples. The first
iteration k>0 that gives again a prime of the form ...+1 when starting with
the n-th prime is:

apply( a(n)={n=prime(n)-1;for(k=1,oo,ispseudoprime(n<<k+1)&&return(k))},
[1..99])
%1 = [1, 1, 2, 1, 2, 3, 4, 1, 2, 2, 1, 1, 4, 3, 8, 6, 2, 2, 5, 2, 3, 1, 10,
2, 1, 2, 2, 4, 2, 2, 3, 2, 12, 1, 2, 2, 1, 3, 4, 4, 6, 7, 2, 2, 4, 1, 1, 3,
4, 1, 2, 2, 5, 4, 8, 2, 4, 1, 8, 4, 2, 4, 1, 6, 2, 8, 1, 1, 12, 4, 2, 2, 1,
2, 1, 4, 2, 3, 2, 4, 4, 3, 2, 3, 1, 6, 8, 4, 10, 3, 4, 2, 3, 4, 1, 10, 10,
2, 2, 2, 1, 12, 6]
Worth to add to OEIS? (with "0" when no such k exists? Can this occur, if
so for which indices?)

Record values are the following:
m=0;for(n=1,999,m<(m=max(a(n),m))&&printf("a(%d)=%d, ",n,m))
a(1)=1, a(3)=2, a(6)=3, a(7)=4, a(15)=8, a(23)=10, a(33)=12, a(184)=24,
a(262)=56, a(268)=168, a(288)=188, a(298)=678, a(514)=1840, ...
(Are these alway multiples of 4, after 10?)

The -1 version is already there: oeis.org/A257495 = A050412(prime(n))
with first 0 conjectured at prime(42228) = 509203 = A076337(1) : Riesel
number(s).

apply( (a(n)=n=prime(n)+1;for(k=1,oo,ispseudoprime(n<<k-1)&&return(k))),
[1..99])
%3 = [1, 1, 1, 2, 1, 4, 2, 2, 1, 1, 2, 2, 1, 24, 2, 1, 2, 4, 2, 4, 2552, 4,
1, 1, 4, 8, 4, 2, 2, 1, 6, 1, 3, 4, 2, 2, 2, 8, 4, 1, 1, 2, 1, 8, 3, 6, 4,
4, 2, 2, 1, 1, 2, 1, 2, 3, 8, 2, 4, 1, 12, 1, 2, 21, 4, 3, 2, 4, 6, 2, 11,
1, 2, 16, 4, 4, 2, 4, 2, 8, 1, 12, 1, 8, 2, 1, 22, 2, 2, 12, 2, 5, 2, 1, 2,
5, 1, 2, 12]
(13:21) gp > m=0;for(n=1,999,m<(m=max(a(n),m))&&printf("a(%d)=%d, ",n,m))
a(1)=1, a(4)=2, a(6)=4, a(14)=24, a(21)=2552, ... ~> oeis.org/A052340
(considering not only primes)

- Maximilian
PS: I found A078680 = Smallest m > 0 such that n*2^m + 1 is prime, or 0 if
no such m exists,
with first proven zero at n=78557 (which is not a prime, nor +-1 of a
prime).
With the the first a(n) above (...+1 primes) is a(n) =  A078680(prime(n)-1).
There's also
A040076 Smallest m >= 0 such that n*2^m+1 is prime, or -1 if no such m
exists.
with other relevant XFREFs:
Cf. A033809 <https://oeis.org/A033809>, A046067 <https://oeis.org/A046067>