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,1

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

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

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

Example

2 -> 3 -> 5 -> 9 = 3^2, so a(1) = 3 and a(2) = 2. - Jonathan Sondow, Oct 30 2015

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 *)

Prog

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

Crossrefs

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

Cf. A137288 (positions of terms > 1).

Sequence in context: A331539 A306287 A016457 * A077089 A156352 A175191

Adjacent sequences: A181712 A181713 A181714 * A181716 A181717 A181718

Keyword

nonn

Author

M. F. Hasler, Nov 17 2010

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

Status

approved