%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: (p1)/2 is also prime.
%C Then (p1)/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(p1) + 1/p) = 6.  Mohammed Bouayoun (bouyao(AT)wanadoo.fr), Feb 10 2004
%C Or, primes p such that p1 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 6k1, 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 (p1)/2 is composite and divisible by 3. (End)
%C If k is the product of the nth safe prime p and its corresponding Sophie Germain prime (p1)/2, then a(n) = 2(kphi(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 nth prime is divided by all primes up to the (n1)th prime, safe primes (p) have remainders of 1 when divided by 2 and (p1)/2 and no other primes. That is, p(mod j)=1 iff j={2,(p1)/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 nonsafe primes (p') will have at least one prime (p") greater than 2 and less than (p1)/2 such that p'(mod p")=1. Explanation: Nonsafe 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 (p1)/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. KoorepazanMoftakhar, <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/fractalorderofprimes">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, 261275.
%H David Naccache, <a href="https://eprint.iacr.org/2003/175">DoubleSpeed 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) [xx<primes(10^3), bigomega(x1)==2] \\ _Altug Alkan_, Nov 04 2015
%o (Haskell)
%o a005385 n = a005385_list !! (n1)
%o a005385_list = filter ((== 1) . a010051 . (`div` 2)) a000040_list
%o  _Reinhard Zumkeller_, Sep 18 2011
%o (MAGMA) [p: p in PrimesUpTo(3000)  IsPrime((p1) 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
