A023139 - OEIS

%I #32 Apr 10 2024 03:30:32

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

%T 6,4,2,15,5,14,6,13,2,6,8,7,10,4,3,27,1,14,6,7,3,14,5,5,21,10,3,21,2,

%U 6,5,17,7,12,2,7,6,4,2,25,4,10,21,21,2,12,2,25,9,4,3,9,7,16,15,13,2,20,2,7,9,6

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

%C Number of factors in the factorization of the polynomial x^n-1 over GF(7). - _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="/A023139/b023139.txt">Table of n, a(n) for n = 1..10000</a>

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

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

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

%e a(10) = 2 because the function 8x mod 10 has the two cycles (0),(2,6,8,4).

%t Table[Length[FactorList[x^n - 1, Modulus -> 7]] - 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[7, n], {n, 100}]

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

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

%o (Python)

%o from sympy import totient, n_order, divisors

%o def A023139(n):

%o     a, b = divmod(n,7)

%o     while not b:

%o         n = a

%o         a, b = divmod(n,7)

%o     return sum(totient(d)//n_order(7,d) for d in divisors(n,generator=True) if d>1)+1 # _Chai Wah Wu_, Apr 09 2024

%Y Cf. A000005, A000374.

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

%K nonn

%O 1,2

%A _David W. Wilson_