|
Search: id:A082595
|
|
|
| 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<=MR then n is prime, and if QR!<=MR then n is composite (<= subset, !<= not a subset). Sequence gives numbers that violate this rule, i.e. composites where QR<=MR, and primes where QR!<=MR. |
|
+0
2
|
|
| 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; listen)
|
|
|
OFFSET
|
0,1
|
|
|
COMMENT
|
It seems (although far from proved) that except for 4 and 8, if the routine declares n a prime, then it is.
|
|
EXAMPLE
|
For n = 8, QR = {0, 1, 4}, and MR = {0, 1, 2, 4}, so QR<=MR, but 8 is not prime, so 8 is in the sequence.
|
|
PROGRAM
|
(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":"isprime(i)", ")))}
|
|
CROSSREFS
|
Sequence in context: A025234 A075308 A020331 this_sequence A080072 A094502 A129195
Adjacent sequences: A082592 A082593 A082594 this_sequence A082596 A082597 A082598
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Jon Perry (perry(AT)globalnet.co.uk), May 08 2003
|
|
EXTENSIONS
|
More terms from David Wasserman (wasserma(AT)spawar.navy.mil), Sep 21 2004
|
|
|
Search completed in 0.002 seconds
|
