cp's OEIS Frontend

A211395 Number of Sophie Germain primes between 2^n and 2^(n+1).

%I A211395 #43 Jul 25 2025 09:00:09
%S A211395 1,1,1,1,2,2,3,7,8,13,23,41,67,111,193,360,630,1091,1938,3558,6448,
%T A211395 11876,21649,40151,73658,135711,251786,468678,875247,1634069,3060794,
%U A211395 5746245,10806204,20356921,38433398,72656139,137562095,260848098,495343258,941805467,1792999074
%N A211395 Number of Sophie Germain primes between 2^n and 2^(n+1).
%C A211395 To be precise, the number of Sophie Germain primes p, 2^n < p <= 2^(n+1). Since 2 is a Sophie Germain prime, this precise definition is important only for determining a(0) and a(1). The alternative definition (with 2^n <= p < 2^(n+1)) would give the sequence 0, 2, 1, 1, 2, 2, 3, 7, 8, 13, 23, 41, 67, 111, 193, ...
%C A211395 The Sophie Germain primes p are in A005384. The corresponding primes s = 2p + 1 are called safe primes, and are in A005385. The number of safe primes between 2^(n+1) and 2^(n+2) is given by the sequence in the previous paragraph.
%H A211395 Paul D. Beale, <a href="http://arxiv.org/abs/1411.2484">A new class of scalable parallel pseudorandom number generators based on Pohlig-Hellman exponentiation ciphers</a>, arXiv preprint arXiv:1411.2484 [physics.comp-ph], 2014-2015.
%H A211395 Jetanat Datephanyawat and Paul D. Beale, <a href="https://arxiv.org/abs/1811.11629">Class of scalable parallel and vectorizable pseudorandom number generators based on non-cryptographic RSA exponentiation ciphers</a>, arXiv:1811.11629 [cs.CR], 2018-2021.
%F A211395 a(n) = A211397(n+1) - A211397(n). - _Michel Marcus_, Sep 22 2014
%t A211395 nmax = 36; rtable = Table[0, {nmax}];
%t A211395 Do[r = 0;
%t A211395   Do[If[And[PrimeQ[i], PrimeQ[2 i + 1]], r++], {i, 1 + 2^n,
%t A211395     2^(n + 1)}]; Print[n, " ", r];
%t A211395   rtable[[n + 1]] = r, {n, 0, nmax - 1}];
%t A211395 rtable (* _Paul D. Beale_, Sep 19 2014 *)
%o A211395 (PARI) a211395(n) = {local(r,i); r=0; for(i=2^n+1, 2^(n+1), if(isprime(i)&&isprime(2*i+1), r=r+1)); r} \\ _Michael B. Porter_, Feb 08 2013
%Y A211395 Cf. A005384, A005385, A211397.
%K A211395 nonn
%O A211395 0,5
%A A211395 _Brad Clardy_, Feb 08 2013
%E A211395 a(29)-a(36) from _Paul D. Beale_, Sep 19 2014
%E A211395 a(37)-a(40) from _Amiram Eldar_, Jul 25 2025