cp's OEIS Frontend

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

%I A191311 #64 May 20 2021 18:29:54
%S A191311 4,6,15,91,703,1891,2701,11305,12403,13981,18721,23001,30889,38503,
%T A191311 39865,49141,68101,79003,88561,88831,91001,93961,104653,107185,137149,
%U A191311 146611,152551,157641,176149,188191,204001,218791,226801,228241
%N 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).
%C A191311 Values of n for which half the witnesses in the Fermat primality test are false.
%C A191311 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
%C A191311 From _Robert G. Wilson v_, Aug 13 2011: (Start)
%C A191311 Number of terms less than 10^n: 2, 4, 5, 7, 22, 60, 129, 303, 690, 1785, …, .
%C A191311 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)
%H A191311 David W. Wilson and Robert G. Wilson v, <a href="/A191311/b191311.txt">Table of n, a(n) for n = 1..2157</a>
%H A191311 While exploring Carmichael numbers, I noticed a few values on the <a href="http://credentiality2.blogspot.com/2010/12/guess-mystery-plot.html">chart on this page</a> for which exactly half of the relatively prime witnesses to the Fermat primality test were false witnesses.
%F A191311 Integers, n, such that A063994(n) = 2*A000010(n). - _Robert G. Wilson v_, Aug 13 2011
%t A191311 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 *)
%o A191311 (Python)
%o A191311 import math
%o A191311 for x in range(2, 1000):
%o A191311   false_witnesses = 0
%o A191311   relatively_prime_values = 0
%o A191311   for y in range(x):
%o A191311     if math.gcd(y, x) == 1:
%o A191311       relatively_prime_values += 1
%o A191311     if (pow(y, x-1, x) == 1):
%o A191311       false_witnesses += 1
%o A191311   if false_witnesses * 2 == relatively_prime_values:
%o A191311     print(x, "is a Fermat Half-Prime")
%Y A191311 A063994 gives the number of false witnesses for every n.
%Y A191311 A129521 is a subsequence. See also A191592.
%K A191311 easy,nonn
%O A191311 1,1
%A A191311 _Jason Holt_, Jun 04 2011
%E A191311 Edited by _N. J. A. Sloane_, Jun 07 2011. I made use of a more explicit definition due to Gareth McCaughan, Jun 05 2011.