login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

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

REFERENCES

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

LINKS

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

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

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 */

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 A110012 A233542

Adjacent sequences:  A081841 A081842 A081843 * A081845 A081846 A081847

KEYWORD

nonn

AUTHOR

N. J. A. Sloane, Apr 11 2003

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 21 16:04 EDT 2019. Contains 328301 sequences. (Running on oeis4.)