A082595 - OEIS

A082595

Let QR be the set of quadratic residues mod n: QR = {x^2 mod n, 1 <= x <= n-1}. Let MR be the set of values taken by 2^x mod n: MR = {2^x mod n, 0 <= x <= n-2}. Usually if QR is a subset of MR then n is prime and otherwise n is composite. Sequence gives numbers that violate this rule, i.e., composites where QR is a subset of MR and primes where QR is not a subset of MR.

4, 8, 31, 43, 73, 89, 109, 113, 127, 151, 157, 223, 229, 233, 241, 251, 257, 277, 281, 283, 307, 331, 337, 353, 397, 431, 433, 439, 457, 499, 571, 577, 593, 601, 617, 631, 641, 643, 673, 683, 691, 727, 733, 739, 811, 881, 911, 919, 937, 953, 971, 997, 1013

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,1

COMMENTS

It seems (although it is far from proved) that except for 4 and 8, if the routine declares n a prime, then it is.

LINKS

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

FORMULA

a(n) ~ 3n log(3n). - Arkadiusz Wesolowski, May 23 2023

EXAMPLE

For n = 8, QR = {0, 1, 4} and MR = {0, 1, 2, 4}, so QR is a subset of MR, but 8 is not prime, so 8 is in the sequence.

MATHEMATICA

With[{s = Association@ Table[n -> SubsetQ @@ Map[Union@ # &, {Array[PowerMod[2, #, n] &, n - 1, 0], Array[PowerMod[#, 2, n] &, n - 1]}], {n, 10^3}]}, Rest@ Keys@ KeySelect[s, Or[! PrimeQ@ # && Lookup[s, #] == True, PrimeQ@ # && Lookup[s, #] == False] &]] (* Michael De Vlieger, Jul 30 2017 *)

PROG

(PARI) quad(n)=local(v, vc); vc=1; v=vector(n-1); for (i=1, n-1, v[vc]=i^2%n; vc++); v

mr(n)=local(v, vc, m); vc=1; v=vector(n-1); m=1; for (i=1, n-1, v[vc]=m%n; m=(2*m)%n; vc++); v

mqsort(n)=local(u, v); u=vecsort(mr(n)); v=vecsort(quad(n)); [u, v]

mqcomp(n)=local(w, wl, qc, pr); w=mqsort(n); wl=length(w[1]); qc=1; for (i=1, wl, pr=0; for (j=1, wl, if (w[2][i]==w[1][j], pr=1); if (pr==1, break)); if (pr==0, break)); pr

for(i=1, 500, if (isprime(i)!=mqcomp(i), print1(i, ", ")))

CROSSREFS

Sequence in context: A317583 A020331 A248476 * A262154 A080072 A374319

Adjacent sequences: A082592 A082593 A082594 * A082596 A082597 A082598

KEYWORD

nonn

AUTHOR

Jon Perry, May 08 2003

EXTENSIONS

More terms from David Wasserman, Sep 21 2004

STATUS

approved