A000374 Number of cycles (mod n) under doubling map.

1, 1, 2, 1, 2, 2, 3, 1, 3, 2, 2, 2, 2, 3, 5, 1, 3, 3, 2, 2, 6, 2, 3, 2, 3, 2, 4, 3, 2, 5, 7, 1, 5, 3, 6, 3, 2, 2, 5, 2, 3, 6, 4, 2, 8, 3, 3, 2, 5, 3, 8, 2, 2, 4, 5, 3, 5, 2, 2, 5, 2, 7, 13, 1, 7, 5, 2, 3, 6, 6, 3, 3, 9, 2, 8, 2, 6, 5, 3, 2, 5, 3, 2, 6, 12, 4, 5, 2, 9, 8, 10, 3, 14, 3, 5, 2, 3, 5, 8, 3

Offset

1,3

Comments

Number of cycles of the function f(x) = 2x mod n. Number of irreducible factors in the factorization of the polynomial x^n-1 over GF(2). - T. D. Noe, Apr 16 2003

References

R. Lidl and H. Niederreiter, Finite Fields, Addison-Wesley, 1983, p. 65.

Links

T. D. Noe, Table of n, a(n) for n = 1..10000

Jarkko Peltomäki and Aleksi Saarela, Standard words and solutions of the word equation X_1^2 ... X_n^2 = (X_1 ... X_n)^2, Journal of Combinatorial Theory, Series A (2021) Vol. 178, 105340. See also arXiv:2004.14657 [cs.FL], 2020.

Formula

a(n) = Sum_{d|m} phi(d)/ord(2, d), where m is n with all factors of 2 removed. - T. D. Noe, Apr 19 2003

a(n) = (1/ord(2,m))*Sum_{j = 0..ord(2,m)-1} gcd(2^j - 1, m), where m is n with all factors of 2 removed. - Nihar Prakash Gargava, Nov 12 2018

Example

a(14) = 3 because (1) the function 2x mod 14 has the three cycles (0),(2,4,8),(6,12,10) and (2) the factorization of x^14-1 over integers mod 2 is (1+x)^2 (1+x+x^3)^2 (1+x^2+x^3)^2, which has three unique factors. Note that the length of the cycles is the same as the degree of the factors.

Mathematica

Table[Length[FactorList[x^n - 1, Modulus -> 2]] - 1, {n, 100}]
CountFactors[p_, n_] := Module[{sum=0, m=n, d, f, i}, While[Mod[m, p]==0, m/=p]; d=Divisors[m]; Do[f=d[[i]]; sum+=EulerPhi[f]/MultiplicativeOrder[p, f], {i, Length[d]}]; sum]; Table[CountFactors[2, n], {n, 100}]

Prog

(PARI) a(n)={sumdiv(n >> valuation(n, 2), d, eulerphi(d)/znorder(Mod(2, d))); }
vector(100, n, a(n)) \\ Andrew Howroyd, Nov 12 2018
(Python)
from sympy import totient, n_order, divisors
def A000374(n): return sum(totient(d)//n_order(2, 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. A000005, A023135-A023142.

Cf. A081844 (number of irreducible factors of x^(2n+1) - 1 over GF(2)).

Cf. A037226 (number of primitive irreducible factors of x^(2n+1) - 1 over integers mod 2).

Sequence in context: A261787 A302480 A329656 * A355735 A355733 A256757

Adjacent sequences: A000371 A000372 A000373 * A000375 A000376 A000377

Keyword

nonn,changed

Author

Shel Kaphan

Status

approved