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
Offset: 1
Keywords
Examples
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.
Programs
-
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 *) -
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, ", ")))
Formula
a(n) ~ 3n log(3n). - Arkadiusz Wesolowski, May 23 2023
Extensions
More terms from David Wasserman, Sep 21 2004
Comments