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

5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, 467, 479, 503, 563, 587, 719, 839, 863, 887, 983, 1019, 1187, 1283, 1307, 1319, 1367, 1439, 1487, 1523, 1619, 1823, 1907, 2027, 2039, 2063, 2099, 2207, 2447, 2459, 2579, 2819, 2879, 2903, 2963

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

Comments

Then (p-1)/2 is called a Sophie Germain prime: see A005384.

Or, primes of the form 2p+1 where p is prime.

Primes p such that denominator(Bernoulli(p-1) + 1/p) = 6. - Mohammed Bouayoun (bouyao(AT)wanadoo.fr), Feb 10 2004

Primes p such that p-1 is a semiprime. - Zak Seidov, Jul 01 2005

A156659(a(n)) = 1; A156875 gives numbers of safe primes <= n. - Reinhard Zumkeller, Feb 18 2009

From Daniel Forgues, Jul 31 2009: (Start)

A safe prime p is 7 or of the form 6k-1, k >= 1, i.e., p == 5 (mod 6).

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)

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

From Bob Selcoe, Apr 14 2014: (Start)

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.

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.

Refer to the rows in triangle A207409 for illustration and further explanation. (End)

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

The six known safe primes p such that (p-1)/2 is a Fibonacci prime are in A263880. - Jonathan Sondow, Nov 04 2015

The only term in common with A005383 is 5. - Zak Seidov, Dec 31 2015

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

Primes p with the property that there is a prime q such that p+q^2 is a square. - Zak Seidov, Feb 16 2017

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

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.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• T. D. Noe, Table of n, a(n) for n = 1..10000
• 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].
• A. R. Ashrafi and F. Koorepazan-Moftakhar, Towards the Classification of Finite Simple Groups with exactly Three or Four Supercharacter Theories, arXiv preprint arXiv:1605.08971 [math.GR], 2016.
• R. P. Boas & N. J. A. Sloane, Correspondence, 1974.
• Siji Chen and Sheng Chen, Connectedness of digraphs from quadratic polynomials, Involve (2020) Vol. 13, No. 2, 357-360.
• Benoit Cloitre, On the fractal behavior of primes, 2011.
• L. H. Gallardo and O. 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.
• David Naccache, Double-Speed Safe Prime Generation, IACR, Report 2003/175, 2003.
• Planetmath, Safe prime.
• Michael J. Wiener, Safe Prime Generation with a Combined Sieve, IACR, Report 2003/186, 2003.
• Wikipedia, Safe prime.

Crossrefs

Cf. A007700, A023272, A023302, A023330, A057331, A005602, A207409, A263880.

Except for the initial term, this is identical to A079148.

Cf. A005384, A005383.

Subsequence of A088707.

Primes in A072055.

Programs

Haskell

a005385 n = a005385_list !! (n-1)
a005385_list = filter ((== 1) . a010051 . (`div` 2)) a000040_list
-- Reinhard Zumkeller, Sep 18 2011

Magma

[p: p in PrimesUpTo(3000) | IsPrime((p-1) div 2)]; // Vincenzo Librandi, Jul 06 2015

Maple

with(numtheory); [ seq(safeprime(i),i=1..3000) ]: convert(%,set); convert(%,list); sort(%);
A005385_list := n->select(i->isprime(iquo(i,2)),select(i->isprime(i),[$1..n])): # Peter Luschny, Nov 08 2010

Mathematica

Select[Prime[Range[1000]],PrimeQ[(#-1)/2]&] (* Zak Seidov, Jan 26 2011 *)

PARI

g(n) = forprime(x=2,n,y=x+x+1;if(isprime(y),print1(y","))) \\ Cino Hilliard, Sep 12 2004

PARI

[x|x<-primes(10^3), bigomega(x-1)==2] \\ Altug Alkan, Nov 04 2015

Python

from sympy import isprime, primerange
def aupto(limit):
  alst = []
  for p in primerange(1, limit+1):
    if isprime((p-1)//2): alst.append(p)
  return alst
print(aupto(2963)) # Michael S. Branicky, May 07 2021

Formula

a(n) = 2 * A005384(n) + 1.

Extensions

More terms from Larry Reeves (larryr(AT)acm.org), Feb 15 2001