login
This site is supported by donations to The OEIS Foundation.

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005385 Safe primes p: (p-1)/2 is also prime.
(Formerly M3761)
178
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

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

Or, 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

Near subset of A161897. - Reikku Kulon, Jun 21 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)

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].

B. Cloitre, On the fractal behavior of primes, 2011.

David Naccache, Double-Speed Safe Prime Generation

Planetmath, Safe prime

Michael J. Wiener, Safe Prime Generation with a Combined Sieve

Wikipedia, Safe prime

FORMULA

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

a(n) = A077065(n) + 1. - Paolo P. Lava, Jun 10 2013

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 *)

PROG

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

(Haskell)

a005385 n = a005385_list !! (n-1)

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

-- Reinhard Zumkeller, Sep 18 2011

CROSSREFS

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

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

Cf. A161897.

Subsequence of A088707.

Subsequence of A072055.

Sequence in context: A226027 A090810 A092307 * A181602 A075705 A141305

Adjacent sequences:  A005382 A005383 A005384 * A005386 A005387 A005388

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified July 30 11:24 EDT 2014. Contains 245063 sequences.