login
This site is supported by donations to The OEIS Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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_{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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 17 06:34 EST 2019. Contains 319207 sequences. (Running on oeis4.)