This site is supported by donations to The OEIS Foundation.



Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005385 Safe primes p: (p-1)/2 is also prime.
(Formerly M3761)

%I M3761

%S 5,7,11,23,47,59,83,107,167,179,227,263,347,359,383,467,479,503,563,

%T 587,719,839,863,887,983,1019,1187,1283,1307,1319,1367,1439,1487,1523,

%U 1619,1823,1907,2027,2039,2063,2099,2207,2447,2459,2579,2819,2879,2903

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

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

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

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

%C Or, primes p such that p-1 is a semiprime. - _Zak Seidov_, Jul 01 2005

%C A156659(a(n)) = 1; A156875 gives numbers of safe primes <= n. - _Reinhard Zumkeller_, Feb 18 2009

%C Near subset of A161897. - _Reikku Kulon_, Jun 21 2009

%C From Daniel Forgues, Jul 31 2009: (Start)

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

%C 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 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 From _Bob Selcoe_, Apr 14 2014: (Start)

%C 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 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 Refer to the rows in triangle A207409 for illustration and further explanation. (End)

%C 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 The six known safe primes p such that (p-1)/2 is a Fibonacci prime are in A263880. - _Jonathan Sondow_, Nov 04 2015

%C The only term in common with A005383 is 5. - _Zak Seidov_, Dec 31 2015

%C 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 Primes p with the property that there is a prime q such that p+q^2 is a square. - _Zak Seidov_, Feb 16 2017

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

%H T. D. Noe, <a href="/A005385/b005385.txt">Table of n, a(n) for n = 1..10000</a>

%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 A. R. Ashrafi, 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 R. P. Boas & N. J. A. Sloane, <a href="/A005381/a005381.pdf">Correspondence, 1974</a>

%H B. Cloitre, <a href="http://www.ebah.com.br/content/ABAAAgYboAK/fractal-order-of-primes">On the fractal behavior of primes</a>, 2011.

%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 David Naccache, <a href="https://eprint.iacr.org/2003/175">Double-Speed Safe Prime Generation</a>, IACR, Report 2003/175, 2003.

%H Planetmath, <a href="http://planetmath.org/encyclopedia/SafePrime.html">Safe prime</a>

%H 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 Wikipedia, <a href="http://en.wikipedia.org/wiki/Safe_prime">Safe prime</a>

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

%F a(n) = A077065(n) + 1. - _Paolo P. Lava_, Jun 10 2013

%p with(numtheory); [ seq(safeprime(i),i=1..3000) ]: convert(%,set); convert(%,list); sort(%);

%p A005385_list := n->select(i->isprime(iquo(i,2)),select(i->isprime(i),[$1..n])): # _Peter Luschny_, Nov 08 2010

%t Select[Prime[Range[1000]],PrimeQ[(#-1)/2]&] (* _Zak Seidov_, Jan 26 2011 *)

%o (PARI) g(n) = forprime(x=2,n,y=x+x+1;if(isprime(y),print1(y","))) \\ _Cino Hilliard_, Sep 12 2004

%o (PARI) [x|x<-primes(10^3), bigomega(x-1)==2] \\ _Altug Alkan_, Nov 04 2015

%o (Haskell)

%o a005385 n = a005385_list !! (n-1)

%o a005385_list = filter ((== 1) . a010051 . (`div` 2)) a000040_list

%o -- _Reinhard Zumkeller_, Sep 18 2011

%o (MAGMA) [p: p in PrimesUpTo(3000) | IsPrime((p-1) div 2)]; // _Vincenzo Librandi_, Jul 06 2015

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

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

%Y Cf. A161897, A005384.

%Y Subsequence of A088707.

%Y Primes in A072055.

%K nonn,easy,nice

%O 1,1

%A _N. J. A. Sloane_

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

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 January 18 20:57 EST 2019. Contains 319282 sequences. (Running on oeis4.)