login
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.
9
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,2
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)
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)
EXAMPLE
a(2)=5 because 2, 5, 11, 23, 47 are prime but 95 is not.
MATHEMATICA
Table[Length[NestWhileList[2#+1&, n, PrimeQ[#]&]], {n, 100}]-1 (* Harvey P. Dale, Aug 08 2020 *)
PROG
(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
CROSSREFS
For records see A339581.
See also Cunningham chains, A005602, A005603.
Sequence in context: A093814 A212155 A269328 * A296493 A196821 A333419
KEYWORD
nonn
AUTHOR
Reiner Martin, Jul 14 2001
EXTENSIONS
Term a(1) = 0 prepended by Antti Karttunen, Oct 09 2018.
STATUS
approved