cp's OEIS Frontend

A301643 Strong pseudo safe-primes: numbers n = 2m+1 with 2^m == +-1 (mod n) and m a strong pseudoprime A001262.

%I A301643 #30 Jun 24 2018 11:14:15
%S A301643 715523,2651687,2882183,10032383,14924003,15640403,30278399,32140859,
%T A301643 45698963,86727203,129210083,202553159,257330639,271938803,274831643,
%U A301643 294056003,307856267,332164619,413008067,437894243,447564527,494832203,654796019,689552603,735119003
%N A301643 Strong pseudo safe-primes: numbers n = 2m+1 with 2^m == +-1 (mod n) and m a strong pseudoprime A001262.
%C A301643 Equivalently, numbers n = 2m+1 that are not safe primes A005385 even though n and m are strong probable primes (that is, prime or strong pseudoprime A001262). That follows from a result by Fedor Petrov.
%C A301643 All known terms are prime, including the 542622 less than 2^65 (obtained by post-processing Jan Feitsma and William Galway's table).
%H A301643 Jan Feitsma, <a href="http://www.janfeitsma.nl/math/psp2/index">The pseudoprimes below 2^64</a>
%H A301643 William Galway, <a href="http://www.cecm.sfu.ca/Pseudoprimes/index-2-to-64.html">Tables of pseudoprimes and related data</a> [Includes a file with pseudoprimes up to 2^64.]
%H A301643 Fedor Petrov, <a href="https://mathoverflow.net/a/295517/122065">The question's congruence and m prime imply n prime</a>, MathOverflow.
%e A301643 n = 715523 is in the sequence because n = 2m+1 with m = 357761, and 2^m mod n = 715522 which is among 1 or n-1 (the latter), and m is a strong pseudoprime A001262. The latter holds because m = 131*2731 is composite, and m passes the strong probable prime test. The latter holds because when writing m-1 as d*(2^s) with d odd, it holds that 2^d mod m = 1 or there exists an r with 0 <= r < s and 2^(d*(2^r)) == -1 (mod m); specifically, d = 2795, s = 7, 2^2795 mod 357761 = 357760 = m-1, thus 2^(d*(2^r)) == -1 (mod m) for r = 0.
%t A301643 For[m=3,(n=2m+1)<13^8,m+=2,If[MemberQ[{1,n-1},PowerMod[2,m,n]]&&(d=m-1;t=1;While[EvenQ[d],d/=2;++t];If[(x=PowerMod[2,d,m])!=1,While[--t>0&&x!=m-1,x=Mod[x^2,m]]];t>0)&&!PrimeQ[m],Print[n]]]
%o A301643 (PARI) is_A001262(n, a=2)={ (bittest(n, 0) && !isprime(n) && n>8) || return; my(s=valuation(n-1, 2)); if(1==a=Mod(a, n)^(n>>s), return(1)); while(a!=-1 && s--, a=a^2); a==-1; } \\ after A001262
%o A301643 isok(n) = if (n%2, my(m = (n-1)/2, r = Mod(2, n)^m); ((r==1) || (r==-1)) && is_A001262(m)); \\ derived from _Michel Marcus_, May 07 2018
%Y A301643 Subsequence of A300193.
%Y A301643 Cf. A001262, A005385.
%K A301643 nonn
%O A301643 1,1
%A A301643 _Francois R. Grieu_, Mar 25 2018