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

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

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(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
(Python)
from sympy import totient, n_order, divisors
def A023136(n): return sum(totient(d)//n_order(4, d) for d in divisors(n>>(~n & n-1).bit_length(), generator=True) if d>1)+1 # Chai Wah Wu, Apr 09 2024

Crossrefs

Cf. A000374, A133703, A133702.

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

Sequence in context: A173854 A059789 A275367 * A337333 A348665 A152774

Adjacent sequences: A023133 A023134 A023135 * A023137 A023138 A023139

Keyword

nonn

Author

David W. Wilson

Status

approved