A263879 Length k of the longest chain of primes p_1, p_2, ..., p_k such that p_1 is the n-th prime and p_{i+1} equals 2*p_i + 1 or 2*p_i - 1 for all i < k, the +/- sign depending on i.

6, 5, 4, 2, 3, 1, 1, 3, 2, 2, 2, 2, 3, 1, 1, 2, 1, 1, 1, 1, 1, 3, 2, 6, 2, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 1, 2, 1, 1, 2, 5, 1, 2, 1, 1, 2, 2, 1, 1, 2, 2, 2, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 2, 1, 1, 1, 3, 2, 1, 1, 1, 4, 2, 1, 2, 1, 1, 1, 1, 1, 2, 1, 2, 1, 3, 2, 1, 1, 1, 1, 1, 1, 1, 2, 3, 1, 4, 1, 1, 1

Offset: 1

Author

Jonathan Sondow, Oct 28 2015

Keywords

• nonn

Comments

If the +/- signs are all + or all -, then p_1, p_2, ..., p_k is a Cunningham chain of the first or second kind, respectively.

If p_1 > 3, then the +/- signs must be all + or all -, because if e = +1 or -1, then one of p, 2*p + e, 2*(2*p + e) - e is divisible by 3; see Löh (1989), p. 751.

Cunningham chains of the first and second kinds of length > 1 cannot begin with the same prime p > 3, because one of the numbers p, 2*p-1, 2*p+1 is divisible by 3.

Examples

			2, 3, 5, 11, 23, 47 is the longest such chain of primes starting with 2. Their indices are 1, 2, 3, 5, 9, 15, respectively, so a(1) = 6, a(2) = 5, a(3) = 4, a(5) = 3, a(9) = 2, and a(15) = 1.
		

References

• R. K. Guy, Unsolved Problems in Number Theory, A7.

Links

• Robert Israel, Table of n, a(n) for n = 1..10000
• G. Löh, Long chains of nearly doubled primes, Math. Comp., 53 (1989), 751-759.
• Wikipedia, Cunningham chain

Crossrefs

Cf. A005384, A005602, A181697, A181715.

Programs

Maple

f:= proc(n) option remember; local x;
  if n mod 3 = 1 then x:= 2*n-1 else x:= 2*n+1 fi;
  if isprime(x) then 1 + procname(x) else 1 fi;
end proc:
f(2):= 6: f(3):= 5:
map(f, [seq(ithprime(i),i=1..100)]); # Robert Israel, Jul 04 2023

Mathematica

A263879 = Join[{6, 5},
  Table[p = Prime[n]; cnt = 1;
   While[PrimeQ[2*p + 1] || PrimeQ[2*p - 1],
    cnt++ && If[PrimeQ[2*p + 1], p = 2*p + 1, p = 2*p - 1 ]];
   cnt, {n, 3, 100}]]

Python

from sympy import prime, isprime
def A263879(n):
    if n <= 2: return 7-n
    p, c = prime(n), 1
    while isprime(p:=(p<<1)+(-1 if p%3==1 else 1)):
        c += 1
    return c # Chai Wah Wu, Jul 07 2023

Formula

a(n) = max(A181697(n), A181715(n)) for n > 2.

a(n) < prime(n) for n > 2; see Löh (1989), p. 751.