A000374 -id:A000374 - cp's OEIS frontend

A037226 a(n) = phi(2n+1) / multiplicative order of 2 mod 2n+1.

1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 2, 2, 1, 1, 1, 6, 2, 2, 1, 2, 2, 3, 2, 2, 2, 4, 1, 2, 2, 1, 1, 6, 4, 1, 2, 2, 8, 2, 2, 2, 1, 1, 8, 2, 8, 6, 6, 2, 2, 2, 1, 2, 4, 1, 3, 2, 4, 2, 6, 4, 1, 4, 1, 18, 6, 1, 6, 2, 2, 1, 2, 2, 4, 2, 1, 10, 4, 6, 3, 2, 4

Offset: 0

N. J. A. Sloane

nonn

Number of primitive irreducible factors of x^(2n+1) - 1 over integers mod 2. There are no primitive irreducible factors for x^(2n)-1 because it always has the same factors as x^n-1. Considering that A000374 also counts the cycles in the map f(x) = 2x mod n, a(n) is also the number of primitive cycles of that mapping. - T. D. Noe, Aug 01 2003

Equals number of irreducible factors of the cyclotomic polynomial Phi(2n+1,x) over Z/2Z. All factors have the same degree. - T. D. Noe, Mar 01 2008

T. D. Noe, Table of n, a(n) for n = 0..10000
Brillhart, John; Lomont, J. S.; Morton, Patrick. Cyclotomic properties of the Rudin-Shapiro polynomials, J. Reine Angew. Math.288 (1976), 37--65. See Table 2. MR0498479 (58 #16589).
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.

Cf. A000374 (number of irreducible factors of x^n - 1 over integers mod 2), A081844.

Cf. A006694 (cyclotomic cosets of 2 mod 2n+1).

a[n_] := EulerPhi[2n+1]/MultiplicativeOrder[2, 2n+1]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Dec 10 2015 *)

a(n)=eulerphi(2*n+1)/znorder(Mod(2,2*n+1)) \\ Charles R Greathouse IV, Dec 29 2013

a(n) = Sum{d|2n+1} mu((2n+1)/d) A000374(d), the inverse Mobius transform of A000374 - T. D. Noe, Aug 01 2003

a(n) = A037225(n)/A002326(n).

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

Original entry on oeis.org

1, 2, 2, 3, 3, 2, 2, 5, 3, 2, 6, 3, 3, 4, 2, 7, 5, 6, 2, 5, 3, 4, 8, 3, 5, 8, 2, 5, 5, 2, 2, 13, 7, 2, 6, 3, 9, 8, 6, 3, 5, 2, 12, 5, 9, 10, 14, 5, 3, 8, 2, 3, 15, 2, 4, 5, 5, 6, 12, 9, 3, 8, 4, 19, 11, 2, 10, 11, 3, 2, 6, 5, 7, 10, 2, 11, 13, 14, 4, 5, 9, 2, 14, 3, 3, 12, 2, 9, 5, 2, 2, 5, 7, 8, 20, 3, 3, 20

Offset: 0

N. J. A. Sloane, Apr 11 2003

nonn

Also number of nonisomorphic "pure" chain rings with certain parameters.

Number of cycles under doubling map x -> 2*x (mod 2*n+1). - Joerg Arndt, Jan 22 2024

R. Lidl and H. Niederreiter, Finite Fields, Addison-Wesley, 1983; Theorem 2.47 page 65.

T. D. Noe, Table of n, a(n) for n = 0..10000
Jean-Paul Allouche, Manon Stipulanti, and Jia-Yan Yao, Doubling modulo odd integers, generalizations, and unexpected occurrences, arXiv:2504.17564 [math.NT], 2025.
G. Chassé, Combinatorial cycles of a polynomial map over a commutative field, Discrete Math. 61 (1986), 21-26.
E. W. Clark and J. J. Liang, Enumeration of finite commutative chain rings, J. Algebra 27 (1973), 445-453.
Pieter Moree, Number of irreducible factors of x^n-1 over a finite field, Posting to Number Theory List, Apr 11, 2003.
T. D. Rogers, The graph of the square mapping on the prime fields, Discrete Math. 148 (1996), 317-324
D. Ulmer, Elliptic curves with large rank over function fields, Ann. of Math. 155 (2002), 295-315
D. Ulmer, Elliptic curves with large rank over function fields, arXiv:math/0109163 [math.NT].
Troy Vasiga and Jeffrey Shallit, On the iteration of certain quadratic maps over GF(p), Discrete Mathematics, Volume 277, Issues 1-3, 2004, pages 219-240.

Cf. A001037.
A000374 gives number of factors of x^n-1 for any n.
Cf. A037226 (number of primitive irreducible factors of x^(2n+1) - 1 over integers mod 2).
Cf. A006694 (number of factors of (x^(2*n+1) - 1) / (x - 1) over GF(2) ).

with(numtheory); o := n->if n=1 then 1 else order(2,n); fi; A081844 := proc(n) local d, t1; t1 := 0; for d to n do if n mod d = 0 then t1 := t1 + phi(d)/o(d); end if; end do; t1; end proc;
Factor(x^(2*n+1)-1) mod 2; nops(%);

a[n_] := Length[Factor[x^(2n+1)-1, Modulus->2] ]; a[0]=1; (* or : *)
a[n_] := Sum[ EulerPhi[d] / MultiplicativeOrder[2, d ], {d, Divisors[2n + 1]}]; Table[ a[n], {n, 0, 97}] (* Jean-François Alcover, Dec 14 2011 *)

a(n)=sumdiv(2*n+1,d,eulerphi(d)/znorder(Mod(2,d)));
vector(122,n,a(n-1)) /* Joerg Arndt, Jan 18 2011 */

from sympy import totient, n_order, divisors
def A081844(n): return sum(totient(d)//n_order(2,d) for d in divisors((n+1<<1)-1,generator=True) if d>1) + 1 # Chai Wah Wu, Apr 09 2024

a(n) = Sum_{ d| 2*n+1 } phi(d)/ord_2(d), where phi = A000010, ord_2 = A002326.
a(n) = A006694(n) + 1. - Joerg Arndt, Apr 01 2019
a(n) = A000374(2*n+1). - Joerg Arndt, Jan 22 2024

A091248 Number of irreducible factors in the factorization of X^n + 1 over GF(2) (counted with multiplicity).

Original entry on oeis.org

1, 2, 2, 4, 2, 4, 3, 8, 3, 4, 2, 8, 2, 6, 5, 16, 3, 6, 2, 8, 6, 4, 3, 16, 3, 4, 4, 12, 2, 10, 7, 32, 5, 6, 6, 12, 2, 4, 5, 16, 3, 12, 4, 8, 8, 6, 3, 32, 5, 6, 8, 8, 2, 8, 5, 24, 5, 4, 2, 20, 2, 14, 13, 64, 7, 10, 2, 12, 6, 12, 3, 24, 9, 4, 8, 8, 6, 10, 3, 32, 5, 6, 2, 24, 12, 8, 5, 16, 9, 16

Offset: 1

Antti Karttunen, Jan 03 2004

nonn

Robert Israel, Table of n, a(n) for n = 1..10000
Antti Karttunen, Scheme-program for computing this sequence.
Index entries for sequences operating on GF(2)[X]-polynomials.

Cf. A000374 (number of distinct irreducible factors of the same polynomials).

Cf. A000051, A091222, A318622.

h:= proc(n) option remember;  numtheory:-phi(n)/numtheory:-order(2,n/2^padic:-ordp(n,2)) end proc:
f:= n -> add(h(d),d=numtheory:-divisors(n)):
map(f, [$1..100]); # Robert Israel, Aug 30 2018

h[n_] := EulerPhi[n]/MultiplicativeOrder[2, n/2^IntegerExponent[n, 2]];
a[n_] := DivisorSum[n, h];
Array[a, 100] (* Jean-François Alcover, Aug 19 2022, after Robert Israel *)

a(n) = A091222(A000051(n)).

a(n) = Sum_{d|n} A318622(d). - Robert Israel, Aug 30 2018

A175198 a(n) is the smallest integer k such that the polynomial x^k + 1 over the integers mod 2 has exactly n distinct irreducible factors.

Original entry on oeis.org

1, 3, 7, 27, 15, 21, 31, 45, 73, 91, 129, 85, 63, 93, 105, 275, 257, 219, 127, 189, 217, 453, 441, 357, 601, 741, 273, 837, 1191, 981, 513, 645, 903, 949, 255, 315, 1649, 341, 1103, 1235, 455, 651, 657, 1443, 775, 2795, 825, 1925, 1911, 771

Offset: 1

Michel Lagneau, Mar 02 2010

nonn

Example: the polynomial x^1649 + 1 over GF(2) is the product of 37 irreducible factors.

Records: 1, 3, 7, 27, 31, 45, 73, 91, 129, 275, 453, 601, 741, 837, 1191, 1649, 2795, 3045, 3913, 3955, 10719, 18875, 48631, 73143, 76373, 126191, 189061, 210105, 216481, 249891, 303021, 896041, 961185, 1063997, 1759603, 2555521, 3492783, 3923381, 5276409, 5529727, 6663515, 7234645, 8761553, 10488401, 11636993, 12290949, 20936365, 25099273, 25821285, 28081875, 28623469, 32848947, 48539883, 58885551, ..., . - Robert G. Wilson v, Feb 07 2018

			For n=1, x+1 is irreducible hence a(1) = 1.
For n=2, x^3 + 1 = (x+1)(x^2+x+1) mod 2 hence a(2) = 3.
For n=3, x^7 + 1 = (x+1)(x^3 + x^2 + 1)(x^3 + x + 1) mod 2 hence a(3) = 7.
For n=4, x^27 + 1 = (x+1)(x^2 + x + 1)(x^18 + x^9 + 1)(x^6 + x^3 + 1) mod 2 hence a(4) = 27.
For n=5, x^15 + 1 = (x+1)(x^4 + x^3 + x^2 + x + 1)(x^2 + x + 1)(x^4 + x^3 + 1)(x^4 + x + 1) mod 2 hence a(5) = 15.

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

Robert G. Wilson v, Table of n, a(n) for n = 1..10000 (first 300 terms from Charles R Greathouse IV)
Eric Weisstein's World on Math, Irreducible Polynomial

Cf. A023135, A000005, A000374, A023136-A023142.

with(numtheory):T:=array(0..50000000):U=array(0..50000000 ):nn:=3000: for k from 1 to nn do:liste:=Factors(x^k+ 1) mod 2;t1 := liste[2]:t2:=(liste[2][i], i=1..nops(t1)):a :=nops(t1):T[k]:=a:U[k]:=k:od:mini:=T[1]:ii:=1: print(mini):for p from 1 to nn-1 do:for n from 1 to nn-1 do:if T[n] < mini then mini:= T[n]:ii:=n: indice:=U[n]: else fi:od:print(indice):print(mini):T[ii]:= 99999999: ii:=1:mini:=T[1] :od:

With[{s = Array[Length@ FactorList[#, Modulus -> 2] &[x^# + 1] &, 500]}, Array[FirstPosition[s, #][[1]] &, 1 + LengthWhile[Differences@ #, # == 1 &], 2] &@ Union@ s] (* Michael De Vlieger, Feb 05 2018 *)
CountFactors[p_, n_] := 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](*after Shel Kaphan from A000374*); f[n_] := Block[{k = 1}, While[CountFactors[2, k] != n, k++]; k]; Array[f, 60] (* Robert G. Wilson v, Feb 07 2018 *)

first(n)=my(v=vector(n),left=n,k,t); while(left, t=#factor(Mod('x^k+++1,2))~; if(t<=n && v[t]==0, v[t]=k; left--)); v \\ Charles R Greathouse IV, Jan 28 2018

A000005(a(n)) <= n <= a(n). - Robert Israel, Feb 07 2018

Name corrected by Charles R Greathouse IV, Jan 28 2018

A323424 Number of cycles (mod n) under Collatz map.

Original entry on oeis.org

1, 1, 2, 1, 2, 2, 3, 2, 2, 2, 3, 2, 3, 2, 3, 2, 2, 2, 3, 2, 2, 2, 3, 2, 2, 2, 4, 2, 2, 2, 3, 2, 2, 2, 3, 2, 3, 3, 3, 2, 3, 2, 4, 2, 3, 2, 3, 2, 3, 2, 3, 2, 2, 2, 4, 2, 2, 2, 3, 2, 2, 2, 3, 2, 2, 2, 3, 2, 3, 2, 3, 2, 2, 2, 3, 3, 2, 2, 3, 2, 2, 2, 4, 2, 2, 2, 3

Offset: 1

Rémy Sigrist, Jan 14 2019

nonn

This sequence is likely to be unbounded.

			The initial terms, alongside the corresponding cycles, are:
  n   a(n)  cycles
  --  ----  --------------------
   1     1  (0)
   2     1  (0)
   3     2  (0), (1)
   4     1  (0)
   5     2  (0), (1, 4, 2)
   6     2  (0), (1, 4, 2)
   7     3  (0), (1, 4, 2), (3)
   8     2  (0), (1, 4, 2)
   9     2  (0), (1, 4, 2)
  10     2  (0), (1, 4, 2)
  11     3  (0), (1, 4, 2), (5)
  12     2  (0), (1, 4, 2)
  13     3  (0), (1, 4, 2), (3, 10, 5)
  14     2  (0), (1, 4, 2)
  15     3  (0), (1, 4, 2), (7)
  16     2  (0), (1, 4, 2)
  17     2  (0), (1, 4, 2)
  18     2  (0), (1, 4, 2)
  19     3  (0), (1, 4, 2), (9)
  20     2  (0), (1, 4, 2)

Rémy Sigrist, Illustration for n = 13
Index entries for sequences related to 3x+1 (or Collatz) problem

See A000374, A023135, A023153, A233521 for similar sequences.

Cf. A006370.

a(n, f = k -> if (k%2, 3*k+1, k/2)) = { my (c=0, s=0); for (k=0, n-1, if (!bittest(s, k), my (v=0, i=k); while (1, v += 2^i; i = f(i) % n; if (bittest(s, i), break, bittest(v, i), c++; break)); s += v)); return (c) }

a(n) >= 2 for any n > 4 (as we have at least the cycles (0) and (1, 4, 2)).

A352635 Number of cyclic orbits of the function f(x) = x^2 + 1 on Z/nZ.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 3, 2, 1, 1, 1, 1, 2, 1, 2, 2, 1, 1, 1, 4, 3, 2, 1, 1, 3, 1, 1, 2, 2, 1, 3, 2, 3, 1, 1, 2, 3, 2, 3, 2, 2, 1, 6, 1, 1, 4, 1, 3, 1, 2, 2, 2, 1, 1, 3, 3, 2, 1, 3, 2, 4, 2, 1, 2, 3, 1, 3, 4, 1, 2, 2, 4, 5, 1, 3, 1, 1, 2, 3, 4, 1, 2, 3, 3, 6, 2, 3, 3, 2, 1, 4, 10

Offset: 1

Jeroen van der Meer, Apr 12 2022

nonn

			If n = 6 then there is a single cyclic orbit of size 2, namely {2, 5}.
If n = 7 then there are two cyclic orbits, both of size 1, namely {3} and {5}.

Chai Wah Wu, Table of n, a(n) for n = 1..10000
Jeroen van der Meer, C implementation

Related to A000374 and A023153.

def o(n):
    orbits = set()
    for k in range(n):
        x, traj = k, []
        while x not in traj:
            traj.append(x)
            x = (x**2 + 1) % n
        orbits.add(tuple(sorted(traj[traj.index(x):])))
    return orbits
print([len(o(n)) for n in range(1, 100)]) # Andrey Zabolotskiy, Apr 12 2022

def A352635(n):
    cset, iset = set(), set()
    for i in range(n):
        if i not in iset:
            j, jset, jlist = i, set(), []
            while j not in jset:
                jset.add(j)
                jlist.append(j)
                iset.add(j)
                j = (j**2+1) % n
            cset.add(min(jlist[jlist.index(j):]))
    return len(cset) # Chai Wah Wu, Apr 13 2022

A108346 a(n) is the least positive number k such that P2(2n+1,q) divides Q(k,q), where both P2 and Q are polynomials in GF(2) and P2(n,q) is the n-th binary polynomial, i.e., P2(n,q) = Sum_{i>=0} b(i)q^i, with n = Sum_{i>=0} b(i)2^i; and Q(m,q) is 1 + q^m.

Original entry on oeis.org

1, 1, 2, 3, 3, 7, 7, 4, 4, 15, 6, 7, 15, 6, 7, 5, 5, 21, 31, 14, 31, 15, 12, 31, 21, 8, 15, 31, 14, 31, 31, 6, 6, 63, 14, 31, 9, 28, 31, 15, 14, 21, 8, 21, 31, 63, 15, 30, 63, 10, 21, 63, 28, 12, 63, 31, 31, 63, 21, 12, 15, 31, 30, 7, 7, 127, 93, 60, 127, 15, 62, 127, 127, 62

Offset: 0

Ralf Stephan, Jul 01 2005

nonn

J. N. Cooper, D. Eichhorn and K. O'Bryant, Reciprocals of binary power series, arXiv:math/0506496 [math.NT], 2005.

Cf. A000374.

A175190 Number of irreducible factors in the factorization of the polynomial x^n + x + 1 over the integers mod 2.

Original entry on oeis.org

0, 1, 1, 1, 2, 1, 1, 2, 1, 2, 2, 3, 2, 3, 1, 2, 3, 2, 4, 3, 2, 1, 3, 2, 3, 4, 2, 1, 2, 1, 3, 4, 3, 2, 2, 3, 2, 3, 3, 4, 3, 2, 2, 3, 4, 1, 3, 2, 3, 4, 4, 3, 4, 3, 3, 4, 3, 4, 6, 1, 2, 3, 1, 6, 5, 2, 2, 3, 4, 3, 5, 4, 5, 4, 4, 3, 4, 3, 5, 6, 3, 6, 4, 3, 4, 3, 5, 4, 5, 2, 2, 3, 4, 3, 3, 2, 3, 2, 2, 3, 6, 3, 5, 4, 3

Offset: 1

Michel Lagneau, Mar 01 2010

nonn

			the factorization of x^5+x+1 over integers mod 2 is (1+x^2+x^3)(1+x+x^2), which has two unique factors

Cf. A000374

with(numtheory): for k from 1 to 200 do:liste:=Factors(x^k+ x +1) mod 2; t1 := liste[2]:t2 := (liste[2][i], i=1..nops(t1)):print(nops(t1)) ;od :

A330878 Number of solutions of length n to the word equation X_1^2 ... X_n^2 = (X_1 ... X_n)^2 in the language of optimal squareful words.

Original entry on oeis.org

1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 14, 13, 14, 14, 15, 15, 16, 16, 17, 19, 18, 18, 20, 19, 20, 21, 22, 21, 24, 22, 23, 24, 24, 24, 27, 25, 26, 30, 27, 27, 30, 30, 32, 33, 30, 30, 35, 31, 32, 33, 33, 34, 38, 34, 35, 43

Offset: 1

Jarkko Peltomäki, Apr 30 2020

nonn

The solutions are counted up to the isomorphism 0 <-> 1 and the operation that exchanges the first two letters of a word.

			01010010 is a solution with X_1 = 01, X_2 = 0, X_3 = 10010. Other solutions of length 8 (up to isomorphism and exchange of first two letters) are 00000000, 01000000, 01000100, 01010101.

J. Peltomäki and A. Saarela, Standard words and solutions of the word equation X_1^2 .. X_n^2 = (X_1 .. X_n)^2, arXiv preprint arXiv:2004.14657 [cs.FL], 2020.
J. Peltomäki and M. A. Whiteland, A square root map on Sturmian words, The Electronic Journal of Combinatorics, Vol. 24.1 #P1.54 (2017).

Cf. A000005, A000010, A000374.

f(n) = {sumdiv(n >> valuation(n, 2), d, eulerphi(d)/znorder(Mod(2, d)))}; \\ A000374
a(n) = n\2 + 1 + sumdiv(n, d, if (d>2, (2^(f(n/d) - 1) - 1)*(eulerphi(d)/2 - numdiv(d-1) + 1))); \\ Michel Marcus, Apr 30 2020

a(n) = floor(n/2) + 1 + Sum_{d|n, d > 2} (2^(A000374(n/d) - 1) - 1)*(A000010(d)/2 - A000005(d-1) + 1).

cp's OEIS Frontend

A037226 a(n) = phi(2n+1) / multiplicative order of 2 mod 2n+1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

A091248 Number of irreducible factors in the factorization of X^n + 1 over GF(2) (counted with multiplicity).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A175198 a(n) is the smallest integer k such that the polynomial x^k + 1 over the integers mod 2 has exactly n distinct irreducible factors.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A323424 Number of cycles (mod n) under Collatz map.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A352635 Number of cyclic orbits of the function f(x) = x^2 + 1 on Z/nZ.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Python

Python

A108346 a(n) is the least positive number k such that P2(2n+1,q) divides Q(k,q), where both P2 and Q are polynomials in GF(2) and P2(n,q) is the n-th binary polynomial, i.e., P2(n,q) = Sum_{i>=0} b(i)*q^i, with n = Sum_{i>=0} b(i)*2^i; and Q(m,q) is 1 + q^m.

Views

Author

Keywords

Links

Crossrefs

A175190 Number of irreducible factors in the factorization of the polynomial x^n + x + 1 over the integers mod 2.

Views

A108346 a(n) is the least positive number k such that P2(2n+1,q) divides Q(k,q), where both P2 and Q are polynomials in GF(2) and P2(n,q) is the n-th binary polynomial, i.e., P2(n,q) = Sum_{i>=0} b(i)q^i, with n = Sum_{i>=0} b(i)2^i; and Q(m,q) is 1 + q^m.