cp's OEIS Frontend

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

%I A023136 #36 Apr 10 2024 03:30:11
%S A023136 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,
%T A023136 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,
%U A023136 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
%N A023136 Number of cycles of function f(x) = 4x mod n.
%H A023136 T. D. Noe, <a href="/A023136/b023136.txt">Table of n, a(n) for n = 1..10000</a>
%F A023136 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
%F A023136 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
%F A023136 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
%e A023136 a(9) = 5 because the function 4x mod 9 has the five cycles (0),(3),(6),(1,4,7),(2,8,5).
%t A023136 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}]
%o A023136 (PARI) a(n)=sumdiv(n>>valuation(n,2), d, eulerphi(d)/znorder(Mod(4,d))) \\ _Charles R Greathouse IV_, Aug 05 2016
%o A023136 (Python)
%o A023136 from sympy import totient, n_order, divisors
%o A023136 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
%Y A023136 Cf. A000374, A133703, A133702.
%Y A023136 Cf. A023135, A023137, A023138, A023139, A023140, A023141, A023142.
%K A023136 nonn
%O A023136 1,3
%A A023136 _David W. Wilson_