cp's OEIS Frontend

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

%I A023139 #32 Apr 10 2024 03:30:32
%S A023139 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 A023139 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 A023139 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 A023139 Number of cycles of function f(x) = 7x mod n.
%C A023139 Number of factors in the factorization of the polynomial x^n-1 over GF(7). - _T. D. Noe_, Apr 16 2003
%D A023139 R. Lidl and H. Niederreiter, Finite Fields, Addison-Wesley, 1983, p. 65.
%H A023139 T. D. Noe, <a href="/A023139/b023139.txt">Table of n, a(n) for n = 1..10000</a>
%F A023139 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 A023139 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 A023139 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 A023139 a(10) = 2 because the function 8x mod 10 has the two cycles (0),(2,6,8,4).
%t A023139 Table[Length[FactorList[x^n - 1, Modulus -> 7]] - 1, {n, 100}]
%t A023139 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 A023139 (PARI) a(n)={sumdiv(n/7^valuation(n, 7), d, eulerphi(d)/znorder(Mod(7, d)));}
%o A023139 vector(100,n,a(n)) \\ _Joerg Arndt_, Jan 22 2024
%o A023139 (Python)
%o A023139 from sympy import totient, n_order, divisors
%o A023139 def A023139(n):
%o A023139     a, b = divmod(n,7)
%o A023139     while not b:
%o A023139         n = a
%o A023139         a, b = divmod(n,7)
%o A023139     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 A023139 Cf. A000005, A000374.
%Y A023139 Cf. A023135, A023136, A023137, A023138, A023140, A023141, A023142.
%K A023139 nonn
%O A023139 1,2
%A A023139 _David W. Wilson_