|
| |
|
|
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.
|
|
1
|
|
|
|
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
|
|
|
|
FORMULA
|
|
|
|
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
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
