cp's OEIS Frontend

A023137 Number of cycles of function f(x) = 5x mod n.

%I A023137 #31 Apr 10 2024 03:30:20
%S A023137 1,2,2,4,1,4,2,6,3,2,3,8,4,4,2,8,2,6,3,4,5,6,2,14,1,8,4,8,3,4,11,10,6,
%T A023137 4,2,12,2,6,11,6,3,10,2,12,3,4,2,20,3,2,5,16,2,8,3,14,6,6,3,8,3,22,12,
%U A023137 12,4,12,4,8,5,4,15,22,2,4,2,12,6,22,3,8,5,6,2,20,2,4,8,18,3,6,11,8,22,4,3,26
%N A023137 Number of cycles of function f(x) = 5x mod n.
%C A023137 Number of factors in the factorization of the polynomial x^n-1 over GF(5). - _T. D. Noe_, Apr 16 2003
%D A023137 R. Lidl and H. Niederreiter, Finite Fields, Addison-Wesley, 1983, p. 65.
%H A023137 T. D. Noe, <a href="/A023137/b023137.txt">Table of n, a(n) for n = 1..10000</a>
%F A023137 a(n) = Sum_{d|m} phi(d)/ord(5, d), where m is n with all factors of 5 removed. - _T. D. Noe_, Apr 19 2003
%F A023137 a(n) = (1/ord(5,m))*Sum_{j = 0..ord(5,m)-1} gcd(5^j - 1, m), where m is n with all factors of 5 removed. - _Nihar Prakash Gargava_, Nov 14 2018
%e A023137 a(15) = 2 because (1) the function 5x mod 15 has the two cycles (0),(5,10) and (2) the factorization of x^15-1 over integers mod 5 is (4+x)^5 (1+x+x^2)^5, which has two unique factors. Note that the length of the cycles is the same as the degree of the factors.
%t A023137 Table[Length[FactorList[x^n - 1, Modulus -> 5]] - 1, {n, 100}]
%t A023137 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[5, n], {n, 100}]
%o A023137 (PARI) a(n)={sumdiv(n/5^valuation(n, 5), d, eulerphi(d)/znorder(Mod(5, d)));}
%o A023137 vector(100,n,a(n)) \\ _Joerg Arndt_, Jan 22 2024
%o A023137 (Python)
%o A023137 from sympy import totient, n_order, divisors
%o A023137 def A023137(n):
%o A023137     a, b = divmod(n,5)
%o A023137     while not b:
%o A023137         n = a
%o A023137         a, b = divmod(n,5)
%o A023137     return sum(totient(d)//n_order(5,d) for d in divisors(n,generator=True) if d>1)+1 # _Chai Wah Wu_, Apr 09 2024
%Y A023137 Cf. A000005, A000374.
%Y A023137 Cf. A023135, A023136, A023138, A023139, A023140, A023141, A023142.
%K A023137 nonn
%O A023137 1,2
%A A023137 _David W. Wilson_