cp's OEIS Frontend

A023142 Number of cycles of function f(x) = 10x mod n.

%I A023142 #19 Apr 09 2024 14:19:03
%S A023142 1,1,3,1,1,3,2,1,9,1,6,3,3,2,3,1,2,9,2,1,6,6,2,3,1,3,15,2,2,3,3,1,18,
%T A023142 2,2,9,13,2,9,1,9,6,3,6,9,2,2,3,3,1,6,3,5,15,6,2,6,2,2,3,2,3,18,1,3,
%U A023142 18,3,2,6,2,3,9,10,13,3,2,17,9,7,1,21,9,3,6,2,3,6,6,3,9,16,2,9,2,2,3,2,3,54,1,26
%N A023142 Number of cycles of function f(x) = 10x mod n.
%H A023142 T. D. Noe, <a href="/A023142/b023142.txt">Table of n, a(n) for n = 1..10000</a>
%F A023142 a(n) = Sum_{d|m} phi(d)/ord(10, d), where m is n with all factors of 2 and 5 removed. - _T. D. Noe_, Apr 21 2003
%e A023142 a(12) = 3 because the function 10x mod 12 has the three cycles (0),(1,10,4),(2,8).
%t A023142 CountFactors[p_, n_] := Module[{sum=0, m=n, d, f, i, ps, j}, ps=Transpose[FactorInteger[p]][[1]]; Do[While[Mod[m, ps[[j]]]==0, m/=ps[[j]]], {j, Length[ps]}]; d=Divisors[m]; Do[f=d[[i]]; sum+=EulerPhi[f]/MultiplicativeOrder[p, f], {i, Length[d]}]; sum]; Table[CountFactors[10, n], {n, 100}]
%o A023142 (PARI) a(n)=n/=2^valuation(n,2)*5^valuation(n,5);sumdiv(n,d,eulerphi(d)/znorder(Mod(10,d))) \\ _Charles R Greathouse IV_, Apr 24 2013
%o A023142 (Python)
%o A023142 from sympy import totient, n_order, divisors
%o A023142 def A023142(n):
%o A023142     m = n>>(~n & n-1).bit_length()
%o A023142     a, b = divmod(m,5)
%o A023142     while not b:
%o A023142         m = a
%o A023142         a, b = divmod(m,5)
%o A023142     return sum(totient(d)//n_order(10,d) for d in divisors(m,generator=True) if d>1)+1 # _Chai Wah Wu_, Apr 09 2024
%Y A023142 Cf. A000374, A023135-A023142.
%K A023142 nonn
%O A023142 1,3
%A A023142 _David W. Wilson_