login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A145918 Subset of Sophie Germain primes generated by an iterative process starting from 11. 5

%I

%S 11,23,83,179,359,719,1439,2903,5903,11831,23819,47639,95723,191459,

%T 383219,766763,1533599,3067511,6135023,12271019,24542351,49085819,

%U 98172131,196344719,392689439,785379359,1570758719,3141519443

%N Subset of Sophie Germain primes generated by an iterative process starting from 11.

%C Prime numbers of this form are exceptionally easy to generate. The hundredth term in this sequence is 14835409839824806270695281050319, which can be determined to be prime in a fraction of a second, or produced starting from 11 in less than a second using a 2GHz Athlon. The number of decimal digits increases by one within four iterations.

%C The time needed grows according to O(n^log(4)) for iterations n, or O(log(v)^log(4)) for values v.

%C Note that these are considered to be safe primes for cryptography. This may be very unwise, as the average time to produce any particular value is many orders of magnitude less than its size. Consider that the guaranteed prime 4.149...063 * 10^278 can be generated in fifteen seconds.

%C Also note the surprising value of the final term given.

%H C. K. Caldwell, The Prime Glossary, <a href="http://primes.utm.edu/glossary/page.php?sort=SophieGermainPrime">Sophie Germain Prime</a>

%H C. K. Caldwell, <a href="http://primes.utm.edu/glossary/page.php/CunninghamChain">Cunningham Chains</a>

%H Weisstein, Eric W. <a href="http://mathworld.wolfram.com/FigurateNumber.html">Figurate Number</a>

%F Define:

%F n, a positive integer congruent to 11 (mod 12);

%F o, 2n + 1;

%F Mn, Mersenne number n: A000225(n);

%F Pn, pseudoperfect number n: A006516(n) and note its simple construction from Mn: Pn = A000217(A000225(n)) = (Mn^2 + Mn + 1) / 2 = (4^n - 2^n) / 2;

%F Fo, figurate kernel o = A000217(o) - o = (o^2 - o) / 2.

%F Observe that Pn (mod Fo) is calculable by modular exponentiation.

%F Then n is a Sophie Germain prime and o is its matching safe prime iff Pn is congruent to o (mod Fo). n and o are therefore members of a Cunningham chain.

%Y Cf. A005384, A005385 (Sophie Germain primes).

%Y Cf. A000225, A006516, A000217.

%K easy,nice,nonn

%O 1,1

%A _Reikku Kulon_, Oct 24 2008

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 August 6 19:52 EDT 2020. Contains 336256 sequences. (Running on oeis4.)