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

715523, 2651687, 2882183, 10032383, 14924003, 15640403, 30278399, 32140859, 45698963, 86727203, 129210083, 202553159, 257330639, 271938803, 274831643, 294056003, 307856267, 332164619, 413008067, 437894243, 447564527, 494832203, 654796019, 689552603, 735119003

Offset

1,1

Comments

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.

All known terms are prime, including the 542622 less than 2^65 (obtained by post-processing Jan Feitsma and William Galway's table).

Links

Table of n, a(n) for n=1..25.

Jan Feitsma, The pseudoprimes below 2^64

William Galway, Tables of pseudoprimes and related data [Includes a file with pseudoprimes up to 2^64.]

Fedor Petrov, The question's congruence and m prime imply n prime, MathOverflow.

Example

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.

Mathematica

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

Prog

(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
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

Crossrefs

Subsequence of A300193.

Cf. A001262, A005385.

Sequence in context: A232578 A249210 A102501 * A252887 A204403 A250372

Adjacent sequences: A301640 A301641 A301642 * A301644 A301645 A301646

Keyword

nonn

Author

Francois R. Grieu, Mar 25 2018

Status

approved