A023140 - OEIS

A023140

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

1, 1, 2, 1, 2, 2, 7, 1, 5, 2, 2, 2, 4, 7, 5, 1, 3, 5, 4, 2, 14, 2, 3, 2, 3, 4, 8, 7, 2, 5, 7, 1, 5, 3, 14, 5, 4, 4, 11, 2, 3, 14, 4, 2, 14, 3, 3, 2, 13, 3, 8, 4, 2, 8, 5, 7, 11, 2, 2, 5, 4, 7, 35, 1, 17, 5, 4, 3, 6, 14, 3, 5, 25, 4, 8, 4, 14, 11, 7, 2, 11, 3, 2, 14, 12, 4, 5, 2, 9, 14, 28, 3, 14, 3, 11, 2, 7

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,3

LINKS

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

FORMULA

a(n) = Sum_{d|m} phi(d)/ord(8, d), where m is n with all factors of 2 removed. - T. D. Noe, Apr 21 2003

a(n) = (1/ord(8,m))*Sum_{j = 0..ord(8,m)-1} gcd(8^j - 1, m), where m is n with all factors of 2 removed. - Nihar Prakash Gargava, Nov 14 2018

EXAMPLE

a(10) = 2 because the function 8x mod 10 has the two cycles (0),(2,6,8,4).

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[8, n], {n, 100}]

CROSSREFS

Cf. A000374.

Cf. A023135, A023136, A023137, A023138, A023139, A023141, A023142.

Sequence in context: A000020 A077014 A093655 * A145859 A145863 A240492

Adjacent sequences: A023137 A023138 A023139 * A023141 A023142 A023143

KEYWORD

nonn

AUTHOR

David W. Wilson

STATUS

approved