A063377 - OEIS

%I #30 Oct 30 2022 18:19:59

%S 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,

%T 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,

%U 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

%N 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.

%C 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?

%C A339579 is an essentially identical sequence from 1981. - _N. J. A. Sloane_, Dec 24 2020

%C From _Michael S. Branicky_, Dec 24 2020: (Start)

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

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

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

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

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

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

%C (End)

%C From _Peter Schorn_, Jan 18 2021: (Start)

%C The Sophie Germain degree is always finite.

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

%C There are three cases for n:

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

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

%C 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.

%C (End)

%H Antti Karttunen, <a href="/A063377/b063377.txt">Table of n, a(n) for n = 1..20000</a>

%H Antti Karttunen, <a href="/A063377/a063377.txt">Data supplement: n, a(n) computed for n = 1..100000</a>

%F From _Michael S. Branicky_, Dec 24 2020: (Start)

%F See proof above.

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

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

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

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

%F (End)

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

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

%o (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

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

%Y For records see A339581.

%Y See also Cunningham chains, A005602, A005603.

%K nonn

%O 1,2

%A _Reiner Martin_, Jul 14 2001

%E Term a(1) = 0 prepended by _Antti Karttunen_, Oct 09 2018.