A023135 - OEIS

%I #30 Jan 22 2024 11:52:33

%S 1,2,1,3,2,2,2,5,1,4,3,3,5,4,2,7,2,2,2,7,2,6,3,5,3,10,1,7,2,4,2,9,3,4,

%T 5,3,3,4,5,13,6,4,2,9,2,6,3,7,3,6,2,15,2,2,6,13,2,4,3,7,7,4,2,11,10,6,

%U 4,7,3,10,3,5,7,6,3,7,6,10,2,23,1,12,3,7,7,4,2,15,2,4,18,9,2,6,5,9,3,6,3,11

%N Number of cycles of function f(x) = 3x mod n.

%C Number of factors in the factorization of the polynomial x^n-1 over GF(3). - _T. D. Noe_, Apr 16 2003

%D R. Lidl and H. Niederreiter, Finite Fields, Addison-Wesley, 1983, p. 65.

%H T. D. Noe, <a href="/A023135/b023135.txt">Table of n, a(n) for n = 1..10000</a>

%F a(n) = Sum_{d|m} phi(d)/ord(3, d), where m is n with all factors of 3 removed. - _T. D. Noe_, Apr 19 2003

%F a(n) = (1/ord(3,m))*Sum_{j = 0..ord(3,m)-1} gcd(3^j - 1, m), where m is n with all factors of 3 removed. - _Nihar Prakash Gargava_, Nov 14 2018

%e a(15) = 2 because (1) the function 3x mod 15 has the two cycles (0),(3,9,12,6) and (2) the factorization of x^15-1 over integers mod 3 is (2+x)^3 (1+x+x^2+x^3+x^4)^3, which has two unique factors. Note that the length of the cycles is the same as the degree of the factors.

%t Table[Length[FactorList[x^n - 1, Modulus -> 3]] - 1, {n, 100}]

%t CountFactors[p_, n_] := Module[{sum=0, m=n, d, f, i}, While[Mod[m, p]==0, m/=p]; d=Divisors[m]; Do[f=d[[i]]; sum+=EulerPhi[f]/MultiplicativeOrder[p, f], {i, Length[d]}]; sum]; Table[CountFactors[3, n], {n, 100}]

%o (PARI) a(n)={sumdiv(n/3^valuation(n, 3), d, eulerphi(d)/znorder(Mod(3, d)));}

%o vector(100,n,a(n)) \\ _Joerg Arndt_, Jan 22 2024

%Y Cf. A000005, A000374.

%Y Cf. A023136, A023137, A023138, A023139, A023140, A023141, A023142.

%K nonn

%O 1,2

%A _David W. Wilson_