cp's OEIS Frontend

A063994 a(n) = Product_{primes p dividing n } gcd(p-1, n-1).

%I A063994 #61 Apr 09 2020 10:51:16
%S A063994 1,1,2,1,4,1,6,1,2,1,10,1,12,1,4,1,16,1,18,1,4,1,22,1,4,1,2,3,28,1,30,
%T A063994 1,4,1,4,1,36,1,4,1,40,1,42,1,8,1,46,1,6,1,4,3,52,1,4,1,4,1,58,1,60,1,
%U A063994 4,1,16,5,66,1,4,3,70,1,72,1,4,3,4,1,78,1,2,1,82,1,16,1,4,1,88,1,36,1
%N A063994 a(n) = Product_{primes p dividing n } gcd(p-1, n-1).
%C A063994 a(n) = number of bases b modulo n for which b^{n-1} == 1 (mod n).
%C A063994 a(A209211(n)) = 1. - _Reinhard Zumkeller_, Mar 02 2013
%C A063994 A049559(n) divides a(n) divides A000010(n). - _Thomas Ordowski_, Dec 14 2013
%C A063994 Note that a(n) = phi(n) iff n = 1 or n is prime or n is Carmichael number A002997. - _Thomas Ordowski_, Dec 17 2013
%H A063994 Amiram Eldar, <a href="/A063994/b063994.txt">Table of n, a(n) for n = 1..10000</a> (terms 1..1000 from T. D. Noe)
%H A063994 W. R. Alford, A. Granville and C. Pomerance, <a href="http://www.dms.umontreal.ca/~andrew/Postscript/carmichael.ps">There are infinitely many Carmichael numbers</a>, Ann. of Math. (2) 139 (1994), no. 3, 703-722.
%H A063994 R. Baillie and S. S. Wagstaff, <a href="http://dx.doi.org/10.1090/S0025-5718-1980-0583518-6">Lucas pseudoprimes</a>, Mathematics of Computation, 35 (1980), 1391-1417.
%H A063994 P. Erdős and C. Pomerance, <a href="http://www.math.dartmouth.edu/~carlp/PDF/paper55.pdf">On the number of false witnesses for a composite number</a>, Mathematics of Computation, 46 (1986), 259-279.
%H A063994 Keith Gibson, <a href="https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;3c0a5dbc.0109">NMBRTHRY posting</a>, Sep 07, 2001.
%H A063994 Romeo Meštrović, <a href="http://arxiv.org/abs/1305.1867">Generalizations of Carmichael numbers I,</a> arXiv:1305.1867v1 [math.NT], May 04 2013.
%H A063994 Carl Pomerance, <a href="https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;d1046c7.0107">NMBRTHRY posting</a>, Jul 26, 2001.
%F A063994 a(p^m) = p-1 and a(2p^m) = 1 for prime p and integer m > 0. - _Thomas Ordowski_, Dec 15 2013
%F A063994 a(n) = Sum_{k=1..n}(floor((k^(n-1)-1)/n)-floor((k^(n-1)-2)/n)). - _Anthony Browne_, May 11 2016
%t A063994 f[n_] := Times @@ GCD[n - 1, First /@ FactorInteger@ n - 1]; f[1] = 1; Array[f, 92] (* _Robert G. Wilson v_, Aug 08 2011 *)
%o A063994 (PARI) for (n=1, 1000, f=factor(n)~; a=1; for (i=1, length(f), a*=gcd(f[1, i] - 1, n - 1)); write("b063994.txt", n, " ", a) ) \\ _Harry J. Smith_, Sep 05 2009
%o A063994 (PARI) a(n)=my(f=factor(n)[,1]);prod(i=1,#f,gcd(f[i]-1,n-1)) \\ _Charles R Greathouse IV_, Dec 10 2013
%o A063994 (Python)
%o A063994 def a(n):
%o A063994     if n == 1: return 1
%o A063994     return len([1 for witness in range(1,n) if pow(witness, n - 1, n) == 1])
%o A063994 [a(n) for n in range(1, 100)]
%o A063994 (Haskell)
%o A063994 a063994 n = product $ map (gcd (n - 1) . subtract 1) $ a027748_row n
%o A063994 -- _Reinhard Zumkeller_, Mar 02 2013
%Y A063994 Cf. A002997, A027748.
%K A063994 nonn,easy,nice
%O A063994 1,3
%A A063994 _N. J. A. Sloane_, Sep 18 2001
%E A063994 More terms from _Robert G. Wilson v_, Sep 21 2001