The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005384 Sophie Germain primes p: 2p+1 is also prime.
(Formerly M0731)

%I M0731

%S 2,3,5,11,23,29,41,53,83,89,113,131,173,179,191,233,239,251,281,293,

%T 359,419,431,443,491,509,593,641,653,659,683,719,743,761,809,911,953,

%U 1013,1019,1031,1049,1103,1223,1229,1289,1409,1439,1451,1481,1499,1511,1559

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

%C Then 2p+1 is called a safe prime: see A005385.

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

%C Subsequence of A117360. - _Reinhard Zumkeller_, Mar 10 2006

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

%C A156660(a(n)) = 1; A156874 gives numbers of Sophie Germain primes <= n. - _Reinhard Zumkeller_, Feb 18 2009

%C a(n) mod 10 <> 7. - _Reinhard Zumkeller_, Feb 12 2009

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

%C Also solutions to the equation: floor(4/A000005(2*n^2+n)) = 1. - _Enrique Pérez Herrero_, May 03 2012

%C Solutions of the equation n'+(2n+1)'=2, where n' is the arithmetic derivative of n. - _Paolo P. Lava_, Aug 10 2012

%C tau(4*a(n) + 2) = tau(4*a(n)) - 2, for n > 1. - _Arkadiusz Wesolowski_, Aug 25 2012

%C eulerphi(4*a(n) + 2) = eulerphi(4*a(n)) + 2, for n > 1. - _Arkadiusz Wesolowski_, Aug 26 2012

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

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

%C Giovanni Resta found the first Sophie German prime which is also Brazilian number (A125134), 28792661 = 1 + 73 + 73^2 + 73^3 + 73^4 = (11111)_73. - _Bernard Schott_, Mar 07 2019

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

%D A. Peretti, The quantity of Sophie Germain primes less than x, Bull. Number Theory Related Topics, 11:1-3 (1987) 81-92

%D J. Roberts, Lure of the Integers, Math. Assoc. America, 1992, p. 83.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H J. S. Cheema, <a href="/A005384/b005384.txt">Table of n, a(n) for n = 1..100000</a>. [This replaces an earlier b-file computed by T. D. Noe]

%H M. Abramowitz and I. A. Stegun, eds., <a href="http://www.convertit.com/Go/ConvertIt/Reference/AMS55.ASP">Handbook of Mathematical Functions</a>, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].

%H R. P. Boas & N. J. A. Sloane, <a href="/A005381/a005381.pdf">Correspondence, 1974</a>

%H P. Bruillard, S.-H. Ng, E. Rowell, Z. Wang, <a href="http://arxiv.org/abs/1310.7050">On modular categories</a>, arXiv preprint arXiv:1310.7050 [math.QA], 2013.

%H C. K. Caldwell, The Prime Glossary, <a href="http://primes.utm.edu/glossary/page.php?sort=SophieGermainPrime">Sophie Germain Prime</a>

%H Del Centina, Andrea. <a href="http://web.unife.it/progetti/geometria/Germain.html">Letters of Sophie Germain preserved in Florence</a> Historia Mathematica, Vol. 32 (2005), 60-75.

%H H. Dubner, <a href="http://dx.doi.org/10.1090/S0025-5718-96-00670-9">Large Sophie Germain Primes</a>, Math. Comp., 65 (1996), 393-396.

%H L. H. Gallardo, O. Rahavandrainy, <a href="http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/241">There are finitely many even perfect polynomials over F_p with p+1 irreducible divisors</a>, Acta Mathematica Universitatis Comenianae, Vol. 83, No. 2, 2016, 261-275.

%H Reikku Kulon, <a href="/A005384/a005384.c">Sublinear arbitrary precision generator of Sophie Germain and safe primes in C</a> (public domain)

%H H. Lifchitz, <a href="http://ourworld.compuserve.com/homepages/hlifchitz/Henri/us/ThSgus.htm">A new and simpler primality test for Sophie-Germain numbers(q=2*p+1)</a>

%H Victor Meally, <a href="/A006556/a006556.pdf">Letter to N. J. A. Sloane</a>, no date.

%H Romeo Meštrović, <a href="http://arxiv.org/abs/1305.1867">Generalizations of Carmichael numbers I,</a> arXiv:1305.1867v1 [math.NT], May 4, 2013.

%H F. Oort, <a href="http://www.math.uu.nl/~oort0109/Taiwan-PrimeNu2012-2013.pdf">Prime numbers</a>, 2013.

%H Larry Riddle, <a href="http://www.agnesscott.edu/lriddle/women/germain-flt/sgandflt.htm">Sophie Germain and Fermat's Last Theorem</a>, Agnes Scott College, Math. Dept., Jul, 1999.

%H Maxie D. Schmidt, <a href="https://arxiv.org/abs/1701.04741">New Congruences and Finite Difference Equations for Generalized Factorial Functions</a>, arXiv:1701.04741 [math.CO], 2017.

%H Rosemary Sullivan and Neil Watling, <a href="http://www.emis.de/journals/INTEGERS/papers/n65/n65.Abstract.html">Independent divisibility pairs on the set of integers from 1 to n</a>, INTEGERS 13 (2013) #A65.

%H A. Takashi, <a href="http://tatra.mat.savba.sk/paper.php?id_paper=532">On Sophie Germain primes</a>, Number theory (Liptovský Ján, 1999), Tatra Mt. Math. Publ. 20 (2000), 65-73.

%H T. Tao, <a href="https://arxiv.org/abs/math/0505402">Obstructions to uniformity and arithmetic patterns in the primes</a>, arXiv:math/0505402 [math.NT], 2005.

%H Apoloniusz Tyszka, <a href="https://philarchive.org/rec/TYSDAS">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)</a>, 2019.

%H Vmoraru, PlanetMath.org, <a href="http://planetmath.org/encyclopedia/GermainPrime.html">Germain prime</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/SophieGermainPrime.html">Sophie Germain Prime</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/IntegerSequencePrimes.html">Integer Sequence Primes</a>

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Sophie_Germain_prime">Sophie Germain prime</a>

%H S. Yates, <a href="https://doi.org/10.1142/9789814503457_0058">Sophie Germain primes</a>, in "The mathematical heritage of C. F. Gauss," World Sci. Publ., River Edge, NJ, 1991, pp. 882-886.

%F A005097 INTERSECT A000040. - _R. J. Mathar_, Mar 23 2017

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

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

%o (MAGMA) [ p: p in PrimesUpTo(1560) | IsPrime(2*p+1) ]; // _Klaus Brockhaus_, Jan 01 2009

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

%o (PARI) forprime(n=2, 10^3, if(ispseudoprime(2*n+1), print1(n, ", "))) \\ _Felix Fröhlich_, Jun 15 2014

%o (PARI) is_A005384=(p->isprime(2*p+1)&&isprime(p));

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

%o (GAP) Filtered([1..1600],p->IsPrime(p) and IsPrime(2*p+1)); # _Muniru A Asiru_, Mar 06 2019

%o (Python)

%o from sympy import isprime, nextprime

%o def ok(p): return isprime(2*p+1)

%o def aupto(limit): # only test primes

%o alst, p = [], 2

%o while p <= limit:

%o if ok(p): alst.append(p)

%o p = nextprime(p)

%o return alst

%o print(aupto(1559)) #_Michael S. Branicky_, Feb 03 2021

%Y Cf. A005385, A057331, A005602, A087634.

%Y Cf. also A000355, A156541, A156542, A156592, A161896, A156660, A156874, A092816, A023212, A007528 (primes of the form 6k-1).

%Y 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).

%K nonn,nice

%O 1,1

%A _N. J. A. Sloane_

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 10 16:05 EDT 2021. Contains 342845 sequences. (Running on oeis4.)