cp's OEIS Frontend

A005385 Safe primes p: (p-1)/2 is also prime.

%I A005385 M3761 #195 Dec 18 2024 15:05:24
%S A005385 5,7,11,23,47,59,83,107,167,179,227,263,347,359,383,467,479,503,563,
%T A005385 587,719,839,863,887,983,1019,1187,1283,1307,1319,1367,1439,1487,1523,
%U A005385 1619,1823,1907,2027,2039,2063,2099,2207,2447,2459,2579,2819,2879,2903,2963
%N A005385 Safe primes p: (p-1)/2 is also prime.
%C A005385 Then (p-1)/2 is called a Sophie Germain prime: see A005384.
%C A005385 Or, primes of the form 2p+1 where p is prime.
%C A005385 Primes p such that denominator(Bernoulli(p-1) + 1/p) = 6. - Mohammed Bouayoun (bouyao(AT)wanadoo.fr), Feb 10 2004
%C A005385 Primes p such that p-1 is a semiprime. - _Zak Seidov_, Jul 01 2005
%C A005385 A156659(a(n)) = 1; A156875 gives numbers of safe primes <= n. - _Reinhard Zumkeller_, Feb 18 2009
%C A005385 From _Daniel Forgues_, Jul 31 2009: (Start)
%C A005385 A safe prime p is 7 or of the form 6k-1, k >= 1, i.e., p == 5 (mod 6).
%C A005385 A prime p of the form 6k+1, k >= 2, i.e., p = 1 (mod 6), cannot be a safe prime since (p-1)/2 is composite and divisible by 3. (End)
%C A005385 If k is the product of the n-th safe prime p and its corresponding Sophie Germain prime (p-1)/2, then a(n) = 2(k-phi(k))/3 + 1, where phi is Euler's totient function. - _Wesley Ivan Hurt_, Oct 03 2013
%C A005385 From _Bob Selcoe_, Apr 14 2014: (Start)
%C A005385 When the n-th prime is divided by all primes up to the (n-1)-th prime, safe primes (p) have remainders of 1 when divided by 2 and (p-1)/2 and no other primes. That is, p(mod j)=1 iff j={2,(p-1)/2}; p>j, {p,j}=>prime.  Explanation: Generally, x(mod y)=1 iff x=y'+1, where y' is the set of divisors of y, y'>1. Since safe primes (p) are of the form p(mod j)=1 iff p and j are prime, then j={j'}. That is, since j is prime, there are no divisors of j (greater than 1) other than j.  Therefore, no primes other than j exist which satisfy the equation p(mod j)=1.
%C A005385 Except primes of the form 2^n+1 (n>=0), all non-safe primes (p') will have at least one prime (p") greater than 2 and less than (p-1)/2 such that p'(mod p")=1. Explanation: Non-safe primes (p') are of the form p'(mod k)=1 where k is composite. This means prime divisors of k exist, and p" is the set of prime divisors of k (example p'=89: k=44; p"={2,11}).  The exception applies because p"={2} iff p'=2^n+1.
%C A005385 Refer to the rows in triangle A207409 for illustration and further explanation. (End)
%C A005385 Conjecture: there is a strengthening of the Bertrand postulate for n >= 24: the interval (n, 2*n) contains a safe prime. It has been tested by _Peter J. C. Moses_ up to n = 10^7. - _Vladimir Shevelev_, Jul 06 2015
%C A005385 The six known safe primes p such that (p-1)/2 is a Fibonacci prime are in A263880. - _Jonathan Sondow_, Nov 04 2015
%C A005385 The only term in common with A005383 is 5. - _Zak Seidov_, Dec 31 2015
%C A005385 From the fourth entry onward, do these correspond to Smarandache's problem 34 (see A007931 link), specifically values which cannot be used (do not meet conditions) to confirm the conjecture? - _Bill McEachen_, Sep 29 2016
%C A005385 Primes p with the property that there is a prime q such that p+q^2 is a square. - _Zak Seidov_, Feb 16 2017
%C A005385 It is conjectured that there are infinitely many safe primes, and their estimated asymptotic density ~ 2C/(log n)^2 (where C = 0.66... is the twin prime constant A005597) converges to the actual value as far as we know. - _M. F. Hasler_, Jun 14 2021
%D A005385 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 A005385 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A005385 T. D. Noe, <a href="/A005385/b005385.txt">Table of n, a(n) for n = 1..10000</a>
%H A005385 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 A005385 A. R. Ashrafi and F. Koorepazan-Moftakhar, <a href="https://arxiv.org/abs/1605.08971">Towards the Classification of Finite Simple Groups with exactly Three or Four Supercharacter Theories</a>, arXiv preprint arXiv:1605.08971 [math.GR], 2016.
%H A005385 R. P. Boas & N. J. A. Sloane, <a href="/A005381/a005381.pdf">Correspondence, 1974</a>.
%H A005385 Siji Chen and Sheng Chen, <a href="https://doi.org/10.2140/involve.2020.13.357">Connectedness of digraphs from quadratic polynomials</a>, Involve (2020) Vol. 13, No. 2, 357-360.
%H A005385 Benoit Cloitre, <a href="https://web.archive.org/web/20150923071043/http://bcmathematics.monsite-orange.fr/FractalOrderOfPrimes.pdf">On the fractal behavior of primes</a>, 2011.
%H A005385 L. H. Gallardo and 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 A005385 David Naccache, <a href="https://eprint.iacr.org/2003/175">Double-Speed Safe Prime Generation</a>, IACR, Report 2003/175, 2003.
%H A005385 Planetmath, <a href="https://planetmath.org/SafePrime">Safe prime</a>.
%H A005385 Michael J. Wiener, <a href="https://eprint.iacr.org/2003/186">Safe Prime Generation with a Combined Sieve</a>, IACR, Report 2003/186, 2003.
%H A005385 Wikipedia, <a href="http://en.wikipedia.org/wiki/Safe_prime">Safe prime</a>.
%F A005385 a(n) = 2 * A005384(n) + 1.
%p A005385 with(numtheory); [ seq(safeprime(i),i=1..3000) ]: convert(%,set); convert(%,list); sort(%);
%p A005385 A005385_list := n->select(i->isprime(iquo(i,2)),select(i->isprime(i),[$1..n])): # _Peter Luschny_, Nov 08 2010
%t A005385 Select[Prime[Range[1000]],PrimeQ[(#-1)/2]&] (* _Zak Seidov_, Jan 26 2011 *)
%o A005385 (PARI) g(n) = forprime(x=2,n,y=x+x+1;if(isprime(y),print1(y","))) \\ _Cino Hilliard_, Sep 12 2004
%o A005385 (PARI) [x|x<-primes(10^3), bigomega(x-1)==2] \\ _Altug Alkan_, Nov 04 2015
%o A005385 (Haskell)
%o A005385 a005385 n = a005385_list !! (n-1)
%o A005385 a005385_list = filter ((== 1) . a010051 . (`div` 2)) a000040_list
%o A005385 -- _Reinhard Zumkeller_, Sep 18 2011
%o A005385 (Magma) [p: p in PrimesUpTo(3000) | IsPrime((p-1) div 2)]; // _Vincenzo Librandi_, Jul 06 2015
%o A005385 (Python)
%o A005385 from sympy import isprime, primerange
%o A005385 def aupto(limit):
%o A005385   alst = []
%o A005385   for p in primerange(1, limit+1):
%o A005385     if isprime((p-1)//2): alst.append(p)
%o A005385   return alst
%o A005385 print(aupto(2963)) # _Michael S. Branicky_, May 07 2021
%Y A005385 Cf. A007700, A023272, A023302, A023330, A057331, A005602, A207409, A263880.
%Y A005385 Except for the initial term, this is identical to A079148.
%Y A005385 Cf. A005384, A005383.
%Y A005385 Subsequence of A088707.
%Y A005385 Primes in A072055.
%K A005385 nonn,easy,nice
%O A005385 1,1
%A A005385 _N. J. A. Sloane_
%E A005385 More terms from Larry Reeves (larryr(AT)acm.org), Feb 15 2001