A082595 - OEIS

%I #20 Jul 14 2023 18:04:35

%S 4,8,31,43,73,89,109,113,127,151,157,223,229,233,241,251,257,277,281,

%T 283,307,331,337,353,397,431,433,439,457,499,571,577,593,601,617,631,

%U 641,643,673,683,691,727,733,739,811,881,911,919,937,953,971,997,1013

%N 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.

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

%F a(n) ~ 3n log(3n). - _Arkadiusz Wesolowski_, May 23 2023

%e 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.

%t 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 *)

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

%o 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

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

%o 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

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

%K nonn

%O 1,1

%A _Jon Perry_, May 08 2003

%E More terms from _David Wasserman_, Sep 21 2004