A181715 Length of the complete Cunningham chain of the second kind starting with prime(n).

3, 2, 1, 2, 1, 1, 1, 3, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 3, 2, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 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).

Dickson's conjecture implies that, for every positive integer r, there exist infinitely many n such that a(n) = r. - Lorenzo Sauras Altuzarra, Feb 12 2021

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 -> 3 -> 5 -> 9 = 3^2, so a(1) = 3 and a(2) = 2. - _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.
• Michael Penn, Romanian Mathematical Olympiad Problem, Youtube video, 2020.
• Wikipedia, Cunningham chain

Crossrefs

Cf. A000040, A005382, A005408, A005602, A005603, A181697, A263879, A285700, A285706, A057326, A057327, A057328, A057329, A057330, A064812.

Cf. A137288 (positions of terms > 1).

Programs

Maple

a := proc(n)
   local c, l:
   c, l := 0, ithprime(n):
   while isprime(l) do c, l := c+1, 2*l-1: od:
   c:
end: # Lorenzo Sauras Altuzarra, Feb 12 2021

Mathematica

Table[p = Prime[n]; cnt = 1; While[p = 2*p - 1; PrimeQ[p], cnt++]; cnt, {n, 100}] (* T. D. Noe, Jul 12 2012 *)
Table[-1 + Length@ NestWhileList[2 # - 1 &, Prime@ n, PrimeQ@ # &], {n, 98}] (* Michael De Vlieger, Apr 26 2017 *)

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), A181697(n)) = A263879(n) for n > 2. - Jonathan Sondow, Oct 30 2015

a(n) = A285700(A000040(n)). - Antti Karttunen, Apr 26 2017

Extensions

Escape clause added to definition by N. J. A. Sloane, Feb 19 2021

Escape clause deleted from definition by Jianing Song, Nov 24 2021