

A005384


Sophie Germain primes p: 2p+1 is also prime.
(Formerly M0731)


293



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

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
A156660(a(n)) = 1; A156874 gives numbers of Sophie Germain primes <= n. [Reinhard Zumkeller, Feb 18 2009]
a(n) mod 10 <> 7. [Reinhard Zumkeller, Feb 12 2009]
Near subset of A161896. [Reikku Kulon, Jun 21 2009]
Contribution from Daniel Forgues, Jul 31 2009: (Start)
A Sophie Germain prime p is 2, 3 or of the form 6k1, 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. (End)
Also solutions to the equation: floor(4/A000005(2*n^2+n)) = 1.  Enrique Pérez Herrero, May 03 2012
Solutions of the equation n'+(2n+1)'=2, where n' is the arithmetic derivative of n.  Paolo P. Lava, Aug 10 2012.
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
p and 2p+1 are Sophie Germain primes if and only if p is prime and 2^(2p) == 1 (mod 2p+1).  Vincenzo Librandi, Oct 09 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^(nk) is prime. [ZhiWei 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) = (kphi(k))/3, where phi is Euler's totient function.  Wesley Ivan Hurt, Oct 03 2013
First member of a prime pair (p, q) in a 2p+1 progression (q = prime = 2p + 1). Numbers p*q are in A156592.  Jaroslav Krizek, Nov 19 2013


REFERENCES

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.
H. Dubner, Large Sophie Germain Primes, Math. Comp., 65 (1996), 393396
F. Oort, Prime numbers, 2013, http://www.math.uu.nl/~oort0109/TaiwanPrimeNu20122013.pdf
A. Peretti, The quantity of Sophie Germain primes less than x, Bull. Number Theory Related Topics, 11:13 (1987) 8192
J. 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).
Rosemary Sullivan and Neil Watling, Independent divisibility pairs on the set of integers from 1 to n, INTEGERS 13 (2013) #A65.
A. Takashi, On Sophie Germain primes. Number theory (Liptovský Ján, 1999). Tatra Mt. Math. Publ. 20 (2000), 6573.
S. Yates, Sophie Germain primes. In "The mathematical heritage of C. F. Gauss," World Sci. Publ., River Edge, NJ, 1991. pp. 882886


LINKS

J. S. Cheema, Table of n, a(n) for n = 1..100000. [This replaces an earlier bfile 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].
P. Bruillard, S.H. Ng, E. Rowell, Z. Wang, On modular categories, arXiv preprint arXiv:1310.7050, 2013
C. K. Caldwell, The Prime Glossary, Sophie Germain Prime
Del Centina, Andrea. Letters of Sophie Germain preserved in Florence Historia Mathematica, Vol. 32 (2005), 6075
Reikku Kulon, Sublinear arbitrary precision generator of Sophie Germain and safe primes in C (public domain)
H. Lifchitz, A new and simpler primality test for SophieGermain numbers(q=2*p+1)
Romeo Meštrović, Generalizations of Carmichael numbers I, arXiv:1305.1867v1 [math.NT], May 4, 2013.
Larry Riddle, Sophie Germain and Fermat's Last Theorem, Agnes Scott College, Math. Dept., Jul, 1999.
T. Tao, Obstructions to uniformity and arithmetic patterns in the primes
Vmoraru, PlanetMath.org, Germain prime
Eric Weisstein's World of Mathematics, Sophie Germain Prime
Eric Weisstein's World of Mathematics, Integer Sequence Primes
Wikipedia, Sophie Germain prime


MAPLE

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


MATHEMATICA

Select[Prime[Range[1000]], PrimeQ[2#+1]&]


PROG

(MAGMA) [ p: p in PrimesUpTo(1560)  IsPrime(2*p+1) ]; [Klaus Brockhaus, Jan 01 2009]
(PARI) select(p>isprime(2*p+1), primes(1000)) \\ Newer versions
select(primes(1000), p>isprime(2*p+1)) \\ v. 2.4.2 and older


CROSSREFS

Cf. A005385, A007700, A023272, A023302, A023330, A057331, A005602, A087634.
Cf. also A000355, A156541, A156542, A156592, A161896, A156660, A156874, A092816, A023212.
Sequence in context: A131101 A188534 A214196 * A118571 A118504 A215714
Adjacent sequences: A005381 A005382 A005383 * A005385 A005386 A005387


KEYWORD

nonn,nice


AUTHOR

N. J. A. Sloane.


STATUS

approved



