cp's OEIS Frontend

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

%I A145918 #19 Feb 16 2025 08:33:09
%S A145918 11,23,83,179,359,719,1439,2903,5903,11831,23819,47639,95723,191459,
%T A145918 383219,766763,1533599,3067511,6135023,12271019,24542351,49085819,
%U A145918 98172131,196344719,392689439,785379359,1570758719,3141519443
%N A145918 Subset of Sophie Germain primes generated by an iterative process starting from 11.
%C A145918 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 A145918 The time needed grows according to O(n^log(4)) for iterations n, or O(log(v)^log(4)) for values v.
%C A145918 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 A145918 Also note the surprising value of the final term given.
%H A145918 C. K. Caldwell, The Prime Glossary, <a href="https://t5k.org/glossary/page.php?sort=SophieGermainPrime">Sophie Germain Prime</a>.
%H A145918 C. K. Caldwell, <a href="https://t5k.org/glossary/page.php?sort=CunninghamChain">Cunningham Chain</a>.
%H A145918 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/FigurateNumber.html">Figurate Number</a>.
%F A145918 Define:
%F A145918 n, a positive integer congruent to 11 (mod 12);
%F A145918 o, 2n + 1;
%F A145918 Mn, Mersenne number n: A000225(n);
%F A145918 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 A145918 Fo, figurate kernel o = A000217(o) - o = (o^2 - o) / 2.
%F A145918 Observe that Pn (mod Fo) is calculable by modular exponentiation.
%F A145918 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 A145918 Cf. A005384, A005385 (Sophie Germain primes).
%Y A145918 Cf. A000225, A006516, A000217.
%K A145918 easy,nice,nonn
%O A145918 1,1
%A A145918 _Reikku Kulon_, Oct 24 2008