|
%I M0731 #311 Feb 05 2024 00:57:08
%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 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 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 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
%C 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
%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, Vol. 11, No. 1-3 (1987), pp. 81-92.
%D Joe 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 and Z. Wang, <a href="http://arxiv.org/abs/1310.7050">On modular categories</a>, arXiv preprint arXiv:1310.7050 [math.QA], 2013.
%H Chris K. Caldwell, The Prime Glossary, <a href="https://t5k.org/glossary/page.php?sort=SophieGermainPrime">Sophie Germain Prime</a>
%H Andrea Del Centina, <a href="http://web.unife.it/progetti/geometria/Germain.html">Letters of Sophie Germain preserved in Florence</a> Historia Mathematica, Vol. 32 (2005), pp. 60-75.
%H Harvey Dubner, <a href="http://dx.doi.org/10.1090/S0025-5718-96-00670-9">Large Sophie Germain Primes</a>, Math. Comp., Vol. 65, No. 213 (1996), pp. 393-396.
%H Luis H. Gallardo and Olivier 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 Ernest G. Hibbs, <a href="https://www.proquest.com/openview/4012f0286b785cd732c78eb0fc6fce80">Component Interactions of the Prime Numbers</a>, Ph. D. Thesis, Capitol Technology Univ. (2022), see p. 33.
%H Reikku Kulon, <a href="/A005384/a005384.c">Sublinear arbitrary precision generator of Sophie Germain and safe primes in C</a> (public domain).
%H Henri Lifchitz, <a href="http://www.primenumbers.net/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 Frans Oort, <a href="https://webspace.science.uu.nl/~oort0109/Oort3Taiwan-PrimeNu-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, Vol. 13 (2013), Article A65.
%H Agoh 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., Vol. 20 (2000), pp. 65-73.
%H Terence 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="https://planetmath.org/sophiegermainprime">Sophie Germain prime</a>.
%H Samuel S. Wagstaff, Jr., <a href="https://cs.uwaterloo.ca/journals/JIS/VOL24/Wagstaff/wag4.html">Sum of Reciprocals of Germain Primes</a>, Journal of Integer Sequences, Vol. 24, No. 2 (2021), Article 21.9.5.
%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 Samuel 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.
%H Carlos Rivera, <a href="https://www.primepuzzles.net/puzzles/puzz_1122.htm">Puzzle 1122 OEIS A005385</a>, The Prime Puzzles & Problems Connection.
%F a(n) mod 10 <> 7. - _Reinhard Zumkeller_, Feb 12 2009
%F A156660(a(n)) = 1; A156874 gives numbers of Sophie Germain primes <= n. - _Reinhard Zumkeller_, Feb 18 2009
%F tau(4*a(n) + 2) = tau(4*a(n)) - 2, for n > 1. - _Arkadiusz Wesolowski_, Aug 25 2012
%F eulerphi(4*a(n) + 2) = eulerphi(4*a(n)) + 2, for n > 1. - _Arkadiusz Wesolowski_, Aug 26 2012
%F A005097 INTERSECT A000040. - _R. J. Mathar_, Mar 23 2017
%F Sum_{n>=1} 1/a(n) is in the interval (1.533944198, 1.8026367) (Wagstaff, 2021). - _Amiram Eldar_, Nov 04 2021
%p 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
%t Select[Prime[Range[1000]],PrimeQ[2#+1]&]
%t lst = {}; Do[If[PrimeQ[n + 1] && PrimeOmega[n] == 2, AppendTo[lst, n/2]], {n, 2, 10^4}]; lst (* _Hilko Koning_, Aug 17 2021 *)
%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_
|
