login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A301643 Strong pseudo safe-primes: numbers n = 2m+1 with 2^m == +-1 (mod n) and m a strong pseudoprime A001262. 0
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 (list; graph; refs; listen; history; text; internal format)
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

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 May 26 07:44 EDT 2019. Contains 323579 sequences. (Running on oeis4.)