|
%I #19 Apr 09 2024 14:19:03
%S 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 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 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 Number of cycles of function f(x) = 10x mod n.
%H T. D. Noe, <a href="/A023142/b023142.txt">Table of n, a(n) for n = 1..10000</a>
%F 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 a(12) = 3 because the function 10x mod 12 has the three cycles (0),(1,10,4),(2,8).
%t 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 (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 (Python)
%o from sympy import totient, n_order, divisors
%o def A023142(n):
%o m = n>>(~n & n-1).bit_length()
%o a, b = divmod(m,5)
%o while not b:
%o m = a
%o a, b = divmod(m,5)
%o 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 Cf. A000374, A023135-A023142.
%K nonn
%O 1,3
%A _David W. Wilson_
|
