A063994 - OEIS

%I #61 Apr 09 2020 10:51:16

%S 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 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 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 a(n) = Product_{primes p dividing n } gcd(p-1, n-1).

%C a(n) = number of bases b modulo n for which b^{n-1} == 1 (mod n).

%C a(A209211(n)) = 1. - _Reinhard Zumkeller_, Mar 02 2013

%C A049559(n) divides a(n) divides A000010(n). - _Thomas Ordowski_, Dec 14 2013

%C 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 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 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 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 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 Keith Gibson, <a href="https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;3c0a5dbc.0109">NMBRTHRY posting</a>, Sep 07, 2001.

%H 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 Carl Pomerance, <a href="https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;d1046c7.0107">NMBRTHRY posting</a>, Jul 26, 2001.

%F a(p^m) = p-1 and a(2p^m) = 1 for prime p and integer m > 0. - _Thomas Ordowski_, Dec 15 2013

%F a(n) = Sum_{k=1..n}(floor((k^(n-1)-1)/n)-floor((k^(n-1)-2)/n)). - _Anthony Browne_, May 11 2016

%t f[n_] := Times @@ GCD[n - 1, First /@ FactorInteger@ n - 1]; f[1] = 1; Array[f, 92] (* _Robert G. Wilson v_, Aug 08 2011 *)

%o (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 (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 (Python)

%o def a(n):

%o     if n == 1: return 1

%o     return len([1 for witness in range(1,n) if pow(witness, n - 1, n) == 1])

%o [a(n) for n in range(1, 100)]

%o (Haskell)

%o a063994 n = product $ map (gcd (n - 1) . subtract 1) $ a027748_row n

%o -- _Reinhard Zumkeller_, Mar 02 2013

%Y Cf. A002997, A027748.

%K nonn,easy,nice

%O 1,3

%A _N. J. A. Sloane_, Sep 18 2001

%E More terms from _Robert G. Wilson v_, Sep 21 2001