login
A081844
Number of irreducible factors of x^(2n+1) - 1 over GF(2).
5
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,2
COMMENTS
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
REFERENCES
R. Lidl and H. Niederreiter, Finite Fields, Addison-Wesley, 1983; Theorem 2.47 page 65.
LINKS
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.
FORMULA
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
MAPLE
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(%);
MATHEMATICA
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 *)
PROG
(PARI) a(n)=sumdiv(2*n+1, d, eulerphi(d)/znorder(Mod(2, d)));
vector(122, n, a(n-1)) /* Joerg Arndt, Jan 18 2011 */
(Python)
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
CROSSREFS
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) ).
Sequence in context: A049113 A055093 A196058 * A233549 A334475 A110012
KEYWORD
nonn
AUTHOR
N. J. A. Sloane, Apr 11 2003
STATUS
approved