A092816 -id:A092816 - cp's OEIS frontend

A005384 Sophie Germain primes p: 2p+1 is also prime.

2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113, 131, 173, 179, 191, 233, 239, 251, 281, 293, 359, 419, 431, 443, 491, 509, 593, 641, 653, 659, 683, 719, 743, 761, 809, 911, 953, 1013, 1019, 1031, 1049, 1103, 1223, 1229, 1289, 1409, 1439, 1451, 1481, 1499, 1511, 1559

Offset: 1

N. J. A. Sloane

Then 2p+1 is called a safe prime: see A005385.
Primes p such that the equation phi(x) = 2p has solutions, where phi is the totient function. See A087634 for another such collection of primes. - T. D. Noe, Oct 24 2003
Subsequence of A117360. - Reinhard Zumkeller, Mar 10 2006
Let q = 2n+1. For these n (and q), the difference of two cyclotomic polynomials can be written as a cyclotomic polynomial in x^2: Phi(q,x) - Phi(2q,x) = 2x Phi(n,x^2). - T. D. Noe, Jan 04 2008
A Sophie Germain prime p is 2, 3 or of the form 6k-1, k >= 1, i.e., p = 5 (mod 6). A prime p of the form 6k+1, k >= 1, i.e., p = 1 (mod 6), cannot be a Sophie Germain prime since 2p+1 is divisible by 3. - Daniel Forgues, Jul 31 2009
Also solutions to the equation: floor(4/A000005(2*n^2+n)) = 1. - Enrique Pérez Herrero, May 03 2012
In the spirit of the conjecture related to A217788, we conjecture that for any integers n >= m > 0 there are infinitely many integers b > a(n) such that the number Sum_{k=m..n} a(k)*b^(n-k) is prime. - Zhi-Wei Sun, Mar 26 2013
If k is the product of a Sophie Germain prime p and its corresponding safe prime 2p+1, then a(n) = (k-phi(k))/3, where phi is Euler's totient function. - Wesley Ivan Hurt, Oct 03 2013
Giovanni Resta found the first Sophie Germain prime which is also a Brazilian number (A125134), 28792661 = 1 + 73 + 73^2 + 73^3 + 73^4 = (11111)73. - _Bernard Schott, Mar 07 2019
For all Sophie Germain primes p >= 5, 2*p + 1 = min(A, B) where A is the smallest prime factor of 2^p - 1 and B the smallest prime factor of (2^p + 1) / 3. - Alain Rocchelli, Feb 01 2023
Consider a pair of numbers (p, 2*p+1), with p >= 3. Then p is a Sophie Germain prime iff (p-1)!^2 + 6*p == 1 (mod p*(2*p+1)). - Davide Rotondo, May 02 2024

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 870.
A. Peretti, The quantity of Sophie Germain primes less than x, Bull. Number Theory Related Topics, Vol. 11, No. 1-3 (1987), pp. 81-92.
Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See pp. 76, 227-230.
Joe Roberts, Lure of the Integers, Math. Assoc. America, 1992, p. 83.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, page 114.

J. S. Cheema, Table of n, a(n) for n = 1..100000. [This replaces an earlier b-file computed by T. D. Noe]
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
R. P. Boas & N. J. A. Sloane, Correspondence, 1974
P. Bruillard, S.-H. Ng, E. Rowell and Z. Wang, On modular categories, arXiv preprint arXiv:1310.7050 [math.QA], 2013.
Chris K. Caldwell, The Prime Glossary, Sophie Germain Prime
Andrea Del Centina, Letters of Sophie Germain preserved in Florence Historia Mathematica, Vol. 32 (2005), pp. 60-75.
Harvey Dubner, Large Sophie Germain Primes, Math. Comp., Vol. 65, No. 213 (1996), pp. 393-396.
Luis H. Gallardo and Olivier Rahavandrainy, There are finitely many even perfect polynomials over F_p with p+1 irreducible divisors, Acta Mathematica Universitatis Comenianae, Vol. 83, No. 2, 2016, 261-275.
Ernest G. Hibbs, Component Interactions of the Prime Numbers, Ph. D. Thesis, Capitol Technology Univ. (2022), see p. 33.
Reikku Kulon, Sublinear arbitrary precision generator of Sophie Germain and safe primes in C (public domain).
Henri Lifchitz, A new and simpler primality test for Sophie-Germain numbers(q=2*p+1).
Victor Meally, Letter to N. J. A. Sloane, no date.
Romeo Meštrović, Generalizations of Carmichael numbers I, arXiv:1305.1867v1 [math.NT], May 04 2013.
Frans Oort, Prime numbers, 2013.
Mario Raso, Integer Sequences in Cryptography: A New Generalized Family and its Application, Ph. D. Thesis, Sapienza University of Rome (Italy 2025). See p. 31, 114.
Larry Riddle, Sophie Germain and Fermat's Last Theorem, Agnes Scott College, Math. Dept., Jul, 1999.
Carlos Rivera, Puzzle 1122. OEIS A005385, The Prime Puzzles & Problems Connection.
Carlos Rivera, Puzzle 1140. Test for Sophie Germain primes, The Prime Puzzles & Problems Connection.
Maxie D. Schmidt, New Congruences and Finite Difference Equations for Generalized Factorial Functions, arXiv:1701.04741 [math.CO], 2017.
Anthony G. Shannon, Peter J.-S. Shiue, Tian-Xiao He, and Christopher Saito, On the special cases of Carmichael's totient conjecture, Notes Num. Theor. Disc. Math. (2025) Vol. 31, No. 3, 504-534.
Rosemary Sullivan and Neil Watling, Independent divisibility pairs on the set of integers from 1 to n, INTEGERS, Vol. 13 (2013), Article A65.
Agoh Takashi, On Sophie Germain primes, Number theory (Liptovský Ján, 1999), Tatra Mt. Math. Publ., Vol. 20 (2000), pp. 65-73.
Terence Tao, Obstructions to uniformity and arithmetic patterns in the primes, arXiv:math/0505402 [math.NT], 2005.
Apoloniusz Tyszka, On sets X subset of N for which we know an algorithm that computes a threshold number t(X) in N such that X is infinite if and only if X contains an element greater than t(X), 2019.
Vmoraru, PlanetMath.org, Sophie Germain prime.
Samuel S. Wagstaff, Jr., Sum of Reciprocals of Germain Primes, Journal of Integer Sequences, Vol. 24, No. 2 (2021), Article 21.9.5.
Eric Weisstein's World of Mathematics, Sophie Germain Prime.
Eric Weisstein's World of Mathematics, Integer Sequence Primes.
Wikipedia, Sophie Germain prime.
Samuel Yates, Sophie Germain primes, in "The mathematical heritage of C. F. Gauss," World Sci. Publ., River Edge, NJ, 1991, pp. 882-886.

Cf. A005385, A057331, A005602, A087634.
Cf. also A000355, A156541, A156542, A156592, A161896, A156660, A156874, A092816, A023212, A007528 (primes of the form 6k-1).
For primes p that remains prime through k iterations of the function f(x) = 2x + 1: this sequence (k=1), A007700 (k=2), A023272 (k=3), A023302 (k=4), A023330 (k=5), A278932 (k=6), A138025 (k=7), A138030 (k=8).

Filtered([1..1600],p->IsPrime(p) and IsPrime(2*p+1)); # Muniru A Asiru, Mar 06 2019

[ p: p in PrimesUpTo(1560) | IsPrime(2*p+1) ]; // Klaus Brockhaus, Jan 01 2009

A:={}: for n from 1 to 246 do if isprime(2*ithprime(n)+1) then A:=A union {ithprime(n)} fi od: A:=A; # Emeric Deutsch, Dec 09 2004

Select[Prime[Range[1000]],PrimeQ[2#+1]&]
lst = {}; Do[If[PrimeQ[n + 1] && PrimeOmega[n] == 2, AppendTo[lst, n/2]], {n, 2, 10^4}]; lst (* Hilko Koning, Aug 17 2021 *)

select(p->isprime(2*p+1), primes(1000)) \\ In old PARI versions <= 2.4.2, use select(primes(1000), p->isprime(2*p+1)).

forprime(n=2, 10^3, if(ispseudoprime(2*n+1), print1(n, ", "))) \\ Felix Fröhlich, Jun 15 2014

is_A005384=(p->isprime(2*p+1)&&isprime(p));
  {A005384_vec(N=100,p=1)=vector(N,i,until(isprime(2*p+1),p=nextprime(p+1));p)} \\ M. F. Hasler, Mar 03 2020

from sympy import isprime, nextprime
def ok(p): return isprime(2*p+1)
def aupto(limit): # only test primes
  alst, p = [], 2
  while p <= limit:
    if ok(p): alst.append(p)
    p = nextprime(p)
  return alst
print(aupto(1559)) # Michael S. Branicky, Feb 03 2021

a(n) mod 10 <> 7. - Reinhard Zumkeller, Feb 12 2009
A156660(a(n)) = 1; A156874 gives numbers of Sophie Germain primes <= n. - Reinhard Zumkeller, Feb 18 2009
tau(4*a(n) + 2) = tau(4*a(n)) - 2, for n > 1. - Arkadiusz Wesolowski, Aug 25 2012
eulerphi(4*a(n) + 2) = eulerphi(4*a(n)) + 2, for n > 1. - Arkadiusz Wesolowski, Aug 26 2012
A005097 INTERSECT A000040. - R. J. Mathar, Mar 23 2017
Sum_{n>=1} 1/a(n) is in the interval (1.533944198, 1.8026367) (Wagstaff, 2021). - Amiram Eldar, Nov 04 2021
a(n) >> n log^2 n. - Charles R Greathouse IV, Jul 25 2024

A156660 Characteristic function of Sophie Germain primes.

Original entry on oeis.org

0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

Offset: 0

Reinhard Zumkeller, Feb 13 2009

nonn

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Wikipedia, Sophie Germain prime
Index entries for characteristic functions

Cf. A156659.

Cf. A005384, A156874, A092816.

a156660 n = fromEnum $ a010051 n == 1 && a010051 (2 * n + 1) == 1
-- Reinhard Zumkeller, May 01 2012

a(n)=isprime(n)&&isprime(2*n+1) \\ Felix Fröhlich, Aug 11 2014

a(n) = if n and also 2*n+1 is prime then 1 else 0.
a(A005384(n)) = 1; a(A138887(n)) = 0; a(A053176(n)) = 0.
A156874(n) = Sum_{k=1..n} a(k). - Reinhard Zumkeller, Feb 18 2009
a(n) = A010051(n)*A010051(2*n+1).
For n>1 a(n) = floor((floor(phi(n)/(n-1)) + floor(phi(2*n+1)/(2*n)))/2). - Enrique Pérez Herrero, Apr 28 2012
For n>1 a(n) = floor(phi(2*n^2+n)/(2*n^2-2*n)). - Enrique Pérez Herrero, May 02 2012

Definition corrected by Daniel Forgues, Aug 04 2009

A156874 Number of Sophie Germain primes <= n.

Original entry on oeis.org

0, 1, 2, 2, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10

Offset: 1

Reinhard Zumkeller, Feb 18 2009

nonn

a(n) = Sum_{k=1..n} A156660(k).
a(n) = A156875(2*n+1).
Hardy-Littlewood conjecture: a(n) ~ 2*C2*n/(log(n))^2, where C2=0.6601618158... is the twin prime constant (see A005597).
The truth of the above conjecture would imply that there exists an infinity of Sophie Germain primes (which is also conjectured).
a(n) ~ 2*C2*n/(log(n))^2 is also conjectured by Hardy-Littlewood for the number of twin primes <= n.

			a(120) = #{2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113} = 11.

R. Zumkeller, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Sophie Germain prime
Wikipedia, Sophie Germain prime

A156875, A156876, A156877, A156878, A000720.
Cf. A005384 Sophie Germain primes p: 2p+1 is also prime.
Cf. A092816.

Accumulate[Table[Boole[PrimeQ[n]&&PrimeQ[2n+1]],{n,1,200}]] (* Enrique Pérez Herrero, Apr 26 2012 *)
Accumulate[Table[If[AllTrue[{n,2n+1},PrimeQ],1,0],{n,200}]]

a(10^n)= A092816(n). - Enrique Pérez Herrero, Apr 26 2012

Edited and commented by Daniel Forgues, Jul 31 2009

A182265 Number of primes p < 10^n such that 4*p+1 is also prime.

Original entry on oeis.org

2, 9, 31, 176, 1057, 7422, 53709, 407198, 3198946, 25773602, 212205881, 1777532673

Offset: 1

Enrique Pérez Herrero, Apr 22 2012

nonn

Cf. A023212, A092816.

f[n_] := Length[Select[Range[10^n], PrimeQ[#] && PrimeQ[4#+1]&]]; Table[f[n], {n,7}]

a(n)=my(s=0); forprime(p=2,10^n,s+=isprime(4*p+1));s \\ Charles R Greathouse IV, Apr 23 2012

a(10)-a(12) from Charles R Greathouse IV, Apr 23 2012

A182434 Number of primes p < n such that 4*p+1 is also prime.

Original entry on oeis.org

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

Offset: 1

Enrique Pérez Herrero, Apr 28 2012

nonn

Enrique Pérez Herrero, Table of n, a(n) for n = 1..10000

Cf. A023212, A182265.

Cf. A005384, A156660, A156874, A092816.

Accumulate[Table[Boole[PrimeQ[n]&&PrimeQ[4n+1]],{n,1,200}]]
Accumulate[If[AllTrue[{#,4#+1},PrimeQ],1,0]&/@Range[90]] (* The program uses the AllTrue function from Mathematica version 10 *) (* Harvey P. Dale, Feb 26 2015 *)

a(10^n) = A182265(n).

a(n) = sum(i=2..n, floor(phi(4*i^2+i)/(4*i^2-4*i))). - Enrique Pérez Herrero, May 02 2012.

A210684 Number of primes p < 10^n such that both 2p+1 and 4p+1 are composite.

Original entry on oeis.org

0, 7, 101, 864, 7365, 63331, 554839, 4931118, 44339730, 402709395, 3687732409, 34007530868

Offset: 1

Enrique Pérez Herrero, May 09 2012

nonn

Cf. A006880, A092816, A182265, A156660, A005384, A156874.

f[n_] := Length[Select[Range[10^n], PrimeQ[#] && !PrimeQ[2#+1] && !PrimeQ[4#+1]&]]; Table[f[n], {n,7}]

a(n) = A006880(n) - A092816(n) - A182265(n) + 1.

a(n) ~ 10^n / (n log 10). - Charles R Greathouse IV, May 11 2012

A307121 Number of Lucasian primes less than 10^n.

Original entry on oeis.org

1, 4, 19, 100, 581, 3912, 28091, 211700, 1655601, 13286320, 109058381, 911436949, 7731247492

Offset: 1

Rodolfo Ruiz-Huidobro, Mar 26 2019

The Lucasian primes are those Sophie Germain primes of the form 4k + 3. They are interesting because if they are infinite in number, then the sequence of Mersenne numbers with prime exponents contains an infinite number of composite integers.

Conjecture: about half of all Sophie Germain primes are Lucasian primes, and the rest are either 2 or a prime of the form 4k + 1.

			There are 4 Lucasian primes below 10^2: {3,11,23,83}, therefore a(2) = 4.

Simon Davis, Arithmetical sequences for the exponents of composite Mersenne numbers, Notes on Number Theory and Discrete Mathematics 20, no. 1 (2014): 19-26.

Cf. A092816, A002515, A307176.

c = 0; r = 10; s = {}; Do[If[p > r, AppendTo[s, c]; r *= 10]; If[PrimeQ[p] && PrimeQ[2p + 1], c++], {p, 3, 1000003, 4}]; s (* Amiram Eldar, Mar 27 2019 *)
lucSophies = Select[4Range[2500000] - 1, PrimeQ[#] && PrimeQ[2# + 1] &]; Table[Length[Select[lucSophies, # < 10^n &]], {n, 0, 7}]

a(n) = { my(t=0); forprime(p=2,10^n,p%4==3 && ispseudoprime(1+(2*p)) && t++);t } \\ Dana Jacobsen, Mar 28 2019

use ntheory ":all"; sub a { my($n,$t)=(shift,0); forprimes { $t++ if ($&3) == 3 && is_prime(1+($<<1)) } 10**$n; $t; } # Dana Jacobsen, Mar 28 2019

a(9)-a(11) from Amiram Eldar, Mar 27 2019
a(12) from Amiram Eldar, Mar 31 2019
a(13) from Dana Jacobsen, Apr 02 2019

cp's OEIS Frontend

A005384 Sophie Germain primes p: 2p+1 is also prime.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

PARI

PARI

Python

Formula

A156660 Characteristic function of Sophie Germain primes.

Views

Author

Keywords

Links

Crossrefs

Programs

Haskell

PARI

Formula

Extensions

A156874 Number of Sophie Germain primes <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A182265 Number of primes p < 10^n such that 4*p+1 is also prime.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

PARI

Extensions

A182434 Number of primes p < n such that 4*p+1 is also prime.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A210684 Number of primes p < 10^n such that both 2*p+1 and 4*p+1 are composite.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Formula

A307121 Number of Lucasian primes less than 10^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Perl

A210684 Number of primes p < 10^n such that both 2p+1 and 4p+1 are composite.