A023136 - OEIS

%I #36 Apr 10 2024 03:30:11

%S 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 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 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 Number of cycles of function f(x) = 4x mod n.

%H T. D. Noe, <a href="/A023136/b023136.txt">Table of n, a(n) for n = 1..10000</a>

%F 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 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 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 a(9) = 5 because the function 4x mod 9 has the five cycles (0),(3),(6),(1,4,7),(2,8,5).

%t 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 (PARI) a(n)=sumdiv(n>>valuation(n,2), d, eulerphi(d)/znorder(Mod(4,d))) \\ _Charles R Greathouse IV_, Aug 05 2016

%o (Python)

%o from sympy import totient, n_order, divisors

%o 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 Cf. A000374, A133703, A133702.

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

%K nonn

%O 1,3

%A _David W. Wilson_