

A191311


Numbers n such that exactly half of the a such that 0<a<n and (a,n)=1 satisfy a^(n1) = 1 (mod n).


4



4, 6, 15, 91, 703, 1891, 2701, 11305, 12403, 13981, 18721, 23001, 30889, 38503, 39865, 49141, 68101, 79003, 88561, 88831, 91001, 93961, 104653, 107185, 137149, 146611, 152551, 157641, 176149, 188191, 204001, 218791, 226801, 228241
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

Values of n for which half the witnesses in the Fermat primality test are false.
When n=pq with p,q=2p1 prime, a^(n1) = 1 (mod p) iff a is a quadratic residue mod q. So A129521 is a subsequence.  Gareth McCaughan, Jun 05 2011
Number of terms less than 10^n: 2, 4, 5, 7, 22, 60, 129, 303, 690, 1785, …, .
In reference to the numbers in the bfile: (1) number of terms which have k>0 prime factors: 1, 1058, 139, 512, 339, 102, 6; (2) about half of the terms, 1058, are members of A129521, those which have just two prime factors; (3) except for the first term, all terms are squarefree, except for the first two terms, all terms are odd; and (4) most terms, more than 98.5%, are congruent to 1 modulo 6. (End)


LINKS

While exploring Carmichael numbers, I noticed a few values on the chart on this page for which exactly half of the relatively prime witnesses to the Fermat primality test were false witnesses.


FORMULA



MATHEMATICA

fQ[n_] := Block[{pf = First /@ FactorInteger@ n}, 2Times @@ GCD[n  1, pf  1] == n*Times @@ (1  1/pf)]; Select[ Range@ 250000, fQ] (* Robert G. Wilson v, Aug 08 2011 *)


PROG

(Python)
import math
for x in range(2, 1000):
false_witnesses = 0
relatively_prime_values = 0
for y in range(x):
if math.gcd(y, x) == 1:
relatively_prime_values += 1
if (pow(y, x1, x) == 1):
false_witnesses += 1
if false_witnesses * 2 == relatively_prime_values:
print(x, "is a Fermat HalfPrime")


CROSSREFS

A063994 gives the number of false witnesses for every n.


KEYWORD

easy,nonn


AUTHOR



EXTENSIONS

Edited by N. J. A. Sloane, Jun 07 2011. I made use of a more explicit definition due to Gareth McCaughan, Jun 05 2011.


STATUS

approved



