|
| |
|
|
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).
|
|
3
|
|
|
|
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.
Comment from Gareth McCaughan, Jun 05 2011: 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.
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 square free, except for the first two terms, all terms are odd; and (4) most terms, more than 98½%, are congruent to 1 modulo 6. - Robert G. Wilson v, Aug 13 2011.
|
|
|
LINKS
|
David W. Wilson and Robert G. Wilson v, Table of n, a(n) for n = 1..2157
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
|
Integers, n, such that A063994(n) = 2*A000010(n). - Robert G. Wilson v, Aug 13 2011.
|
|
|
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 8 2011 *)
|
|
|
PROG
|
(Python)
import math
import fractions
for x in range(2, 1000):
false_witnesses = 0
relatively_prime_values = 0
for y in range(x):
if fractions.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.
A129521 is a subsequence. See also A191592.
Sequence in context: A007135 A073603 A064910 * A086714 A009463 A066260
Adjacent sequences: A191308 A191309 A191310 * A191312 A191313 A191314
|
|
|
KEYWORD
|
easy,nonn
|
|
|
AUTHOR
|
Jason Holt, Jun 04 2011
|
|
|
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
|
| |
|
|
