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
Keywords
Examples
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.
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
- Jean-Paul Allouche, Manon Stipulanti, and Jia-Yan Yao, Doubling modulo odd integers, generalizations, and unexpected occurrences, arXiv:2504.17564 [math.NT], 2025.
- 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.
Crossrefs
Programs
-
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}] -
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
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
Comments