A181697 Length of the complete Cunningham chain of the first kind starting with prime(n).

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

Offset: 1

Author

M. F. Hasler, Nov 17 2010

Keywords

• nonn

Comments

Number of iterations x->2x+1 needed to get a composite number, when starting with prime(n).

prime(n) is in A005384, i.e., a Sophie Germain prime, iff a(n)>1.

a(n) is the least k such that 2^k * (prime(n)+1) - 1 is composite. Note that a(n) is well defined since 2^(p-1) * (p+1) - 1 is divisible by p for odd primes p. - Jianing Song, Nov 24 2021

Examples

			2 -> 5 -> 11 -> 23 -> 47 -> 95 = 5*19, so a(1) = 5, a(3) = 4, a(5) = 3, a(9) = 2, and a(15) = 1. - _Jonathan Sondow_, Oct 30 2015
		

Links

• T. D. Noe, 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. A005602, A181715, A263879.

See also A075712, A338945.

Programs

Mathematica

Table[p = Prime[n]; cnt = 1; While[p = 2*p + 1; PrimeQ[p], cnt++]; cnt, {n, 100}] (* T. D. Noe, Jul 12 2012 *)

PARI

a(n)= n=prime(n); for(c=1,1e9, is/*pseudo*/prime(n=2*n+1) || return(c))

Formula

a(n) < prime(n) for n > 1; see Löh (1989), p. 751. - Jonathan Sondow, Oct 28 2015

max(a(n), A181715(n)) = A263879(n) for n > 2. - Jonathan Sondow, Oct 30 2015

Extensions

Definition clarified by Jonathan Sondow, Oct 28 2015