A063377 Sophie Germain degree of n: number of iterations of n under f(k) = 2k+1 before we reach a number that is not a prime.

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

Offset: 1

Author

Reiner Martin, Jul 14 2001

Keywords

• nonn

Comments

a(n) >= 1 means that n is prime; a(n) >= 2 means that n is a Sophie Germain prime. Is the Sophie Germain degree always finite? Is it unbounded?

A339579 is an essentially identical sequence from 1981. - N. J. A. Sloane, Dec 24 2020

From Michael S. Branicky, Dec 24 2020: (Start)

All n > 5 with a(n) >= 4 satisfy n == 9 (mod 10).

Proof. Let f^k(n) denote iterates of 2*k + 1, with f^0(n) = n.

n != 0, 2, 4, 5, 6, or 8 (mod 10), otherwise f^0(n) is not prime, and a(n) = 0.

n != 7 (mod 10) otherwise f^1(n) = 2*n + 1 == 5 (mod 10), not prime, and a(n) <= 1.

n != 3 (mod 10) otherwise f^2(n) = 4*r + 3 == 5 (mod 10), not prime, and a(n) <= 2.

n != 1 (mod 10) otherwise f^3(n) = 8*r + 7 == 5 (mod 10), not prime, and a(n) <= 3.

(End)

From Peter Schorn, Jan 18 2021: (Start)

The Sophie Germain degree is always finite.

Proof. Let f^k(n) denote iterates of 2*k + 1 with closed form f^k(n) = 2^k * n + 2^k - 1.

There are three cases for n:

1. If n is not a prime then f^0(n) = n is composite.

2. If n = 2 then f^5(2) = 95 is composite.

3. If n is an odd prime then f^(n-1)(n) = 2^(n-1) * n + 2^(n-1) - 1 is divisible by n since 2^(n-1) == 1 (mod n) by Fermat's theorem.

(End)

Examples

			a(2)=5 because 2, 5, 11, 23, 47 are prime but 95 is not.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..20000
• Antti Karttunen, Data supplement: n, a(n) computed for n = 1..100000

Crossrefs

Cf. A005384, A063378, A093008, A093007, A292936, A339579.

For records see A339581.

See also Cunningham chains, A005602, A005603.

Programs

Mathematica

Table[Length[NestWhileList[2#+1&,n,PrimeQ[#]&]],{n,100}]-1 (* Harvey P. Dale, Aug 08 2020 *)

PARI

a(n) = {if (! isprime(n), return (0)); d = 1; k = n; while(isprime(p = 2*k+1), k = p; d++;); return (d);} \\ Michel Marcus, Jul 22 2013

Formula

From Michael S. Branicky, Dec 24 2020: (Start)

See proof above.

a(n) = 0 if n == 0, 2, 4, 5, 6, 8 (mod 10), and n != 2 or 5.

a(n) <= 1 if n == 7 (mod 10).

a(n) <= 2 if n == 3 (mod 10).

a(n) <= 3 if n == 1 (mod 10).

(End)

Extensions

Term a(1) = 0 prepended by Antti Karttunen, Oct 09 2018.