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
Keywords
Examples
a(9) = 5 because the function 4x mod 9 has the five cycles (0),(3),(6),(1,4,7),(2,8,5).
Links
- T. D. Noe, Table of n, a(n) for n = 1..10000
Crossrefs
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[4, n], {n, 100}] -
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
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