|
| |
|
|
A081844
|
|
Number of irreducible factors of x^(2n+1) - 1 over GF(2).
|
|
4
| |
|
|
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
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,2
|
|
|
COMMENTS
| Also number of nonisomorphic "pure" chain rings with certain parameters.
|
|
|
REFERENCES
| G. Chass\'e, 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.
R. Lidl and H. Niederreiter, Finite Fields, Addison-Wesley, 1983; Theorem 2.47 page 65.
Pieter Moree, 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.
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.
|
|
|
LINKS
| T. D. Noe, Table of n, a(n) for n=0..10000
Pieter Moree, Number of irreducible factors of x^n-1 over a finite field, Posting to Number Theory List, Apr 11, 2003.
D. Ulmer, Elliptic curves with large rank over function fields, Ann. of Math. 155 (2002), 295-315.
T. Vasiga and J. 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.
|
|
|
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}] (* From 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 */
|
|
|
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).
Sequence in context: A049113 A055093 A196058 * A110012 A023514 A179751
Adjacent sequences: A081841 A081842 A081843 * A081845 A081846 A081847
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com), Apr 11 2003
|
| |
|
|
