Sophie Germain Prime

Author

Eric W. Weisstein
February 29, 2016

This notebook downloaded from http://mathworld.wolfram.com/notebooks/PrimeNumbers/SophieGermainPrime.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/SophieGermainPrime.html.

©2016 Wolfram Research, Inc. except for portions noted otherwise

Initialization

SophieGermainPrimeQ[p_Integer?Positive]:=And@@PrimeQ/@{p,2p+1}

Enumeration

(p=Select[Prime[Range[100]],SophieGermainPrimeQ])//Timing

http://www.research.att.com/projects/OEIS?Anum=A077065

p/2

http://www.research.att.com/projects/OEIS?Anum=A005384

Select[Prime[Range[100]],PrimeQ[2#+1]&]//Timing

Length[p=Select[Prime[Range[PrimePi[10^9]]],PrimeQ[2#+1]&]]//Timing

Table[Count[p,_?(#<10^n&)],{n,9}]//Timing

Length[p=Select[Prime[Range[PrimePi[10^10]]],PrimeQ[2#+1]&]]//Timing

...out of memory...

With[{n=10,chunksize=5 10^6},Plus@@Table[Count[Prime[Range[k,Min[k+chunksize-1,PrimePi[10^n]]]],_?(PrimeQ[2#+1]&)],{k,PrimePi[10^(n-1)]+1,PrimePi[10^n],chunksize}]]//Timing

3308859+23260656

Large Primes

http://primes.utm.edu/top20/page.php?id=2#records

5122 digits (p==92305 (2^16998)+1)

Digits[p1=92305 2^16998+1]

SophieGermainPrimeQ[p1]//Timing

20013 digits (p==109433307 (2^66452)-1)

IntegerLength[p2=109433307 2^66452-1]

SophieGermainPrimeQ[p2]//Timing

36523 digits (p==7068555 (2^121301)-1)

Subtract@@{2(7068555 (2^121301)-1)+1,7068555 (2^121302)-1}

IntegerLength[p2=7068555 (2^121301)-1]

SophieGermainPrimeQ[p2]//Timing

51780 digits (p==137211941292195 (2^171960)-1)

IntegerLength[p2=137211941292195 (2^171960)-1]

SophieGermainPrimeQ[p2]//Timing

79911 digits (p==183027 (2^265440)-1)

IntegerLength[p=183027*2^265440-1]

PrimeQ[p]//Timing

PrimeQ[2p+1]//Timing

388342 digits (p=2618163402417 (2^1290000)-1)

IntegerLength[p=2618163402417 2^1290000-1]

2p+1==2618163402417 2^1290001-1

IntegerLength[2p+1]