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

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, 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, 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

Offset: 1

Author

David W. Wilson

Keywords

• nonn

Examples

			a(12) = 3 because the function 10x mod 12 has the three cycles (0),(1,10,4),(2,8).
		

Links

• T. D. Noe, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000374, A023135-A023142.

Programs

Mathematica

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}]

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

Python

from sympy import totient, n_order, divisors
def A023142(n):
    m = n>>(~n & n-1).bit_length()
    a, b = divmod(m,5)
    while not b:
        m = a
        a, b = divmod(m,5)
    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

Formula

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