|
|
A191311
|
|
Numbers n such that exactly half of the a such that 0<a<n and (a,n)=1 satisfy a^(n-1) = 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=2p-1 prime, a^(n-1) = 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 b-file: (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, x-1, x) == 1):
false_witnesses += 1
if false_witnesses * 2 == relatively_prime_values:
print(x, "is a Fermat Half-Prime")
|
|
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
|
|
|
|