

A023136


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


12



1, 1, 3, 1, 3, 3, 3, 1, 5, 3, 3, 3, 3, 3, 9, 1, 5, 5, 3, 3, 9, 3, 3, 3, 5, 3, 7, 3, 3, 9, 7, 1, 9, 5, 9, 5, 3, 3, 9, 3, 5, 9, 7, 3, 15, 3, 3, 3, 5, 5, 15, 3, 3, 7, 9, 3, 9, 3, 3, 9, 3, 7, 23, 1, 13, 9, 3, 5, 9, 9, 3, 5, 9, 3, 15, 3, 9, 9, 3, 3, 9, 5, 3, 9, 23, 7, 9, 3, 9, 15, 17, 3, 21, 3, 9, 3, 5, 5, 15, 5, 3, 15
(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_{dm} phi(d)/ord(4, d), where m is n with all factors of 2 removed. The formula was developed by extending the ideas in A000374 to composite multipliers.  T. D. Noe, Apr 21 2003
Mobius transform of A133702: (1, 2, 4, 3, 4, 8, 4, 4, 9, 8,...). = Row sums of triangle A133703.  Gary W. Adamson, Sep 21 2007
a(n) = (1/ord(4, m))*Sum_{j = 0..ord(4, m)  1} gcd(4^j  1, m), where m is the odd part of n (A000265).  Nihar Prakash Gargava, Nov 14 2018


EXAMPLE

a(9) = 5 because the function 4x mod 9 has the five cycles (0),(3),(6),(1,4,7),(2,8,5).


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


PROG

(PARI) a(n)=sumdiv(n>>valuation(n, 2), d, eulerphi(d)/znorder(Mod(4, d))) \\ Charles R Greathouse IV, Aug 05 2016


CROSSREFS

Cf. A000374, A133703, A133702.
Cf. A023135, A023137, A023138, A023139, A023140, A023141, A023142.
Sequence in context: A173854 A059789 A275367 * A152774 A275820 A210146
Adjacent sequences: A023133 A023134 A023135 * A023137 A023138 A023139


KEYWORD

nonn


AUTHOR

David W. Wilson


STATUS

approved



