login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A086908 Let R be the polynomial ring GF(2)[x]. Then a(n) = number of distinct products f*g with f,g in R and 0 <= deg(f),deg(g) <= n. 1
7, 23, 79, 272, 991, 3587, 13499, 50838, 194251, 745754, 2883084, 11173940, 43487349, 169658939, 663264004, 2598336785, 10190703415, 40038964037, 157431540197, 619871791795, 2442107730237, 9632769956279, 38008189846122, 150127214291450, 593141915883700 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

Either polynomial may be 0. - Andrew Howroyd, Jul 10 2018

LINKS

Table of n, a(n) for n=1..25.

EXAMPLE

From Andrew Howroyd, Jul 10 2018: (Start)

Case n=1: Except for x^2 + x + 1 all polynomials with degree <= 2 are represented:

  0 = 0*1,

  1 = 1*1,

  x = 1*x,

  x + 1 = 1*(x + 1),

  x^2 = x*x,

  x^2 + 1 = (x + 1)*(x + 1),

  x^2 + x = x*(x + 1).

Case n=3: There are 128 polynomials with degree <= 6. From this must be subtracted those polynomials whose factorizations into irreducible polynomials have degrees in the set {(6), (5+1), (4+1+1), (2+2+2), (5), (4+1), (4)}. 48 of these exclusions include an irreducible factor with degree >= 4. The other exclusion is (x^2 + x + 1)^3 which cannot be represented as the product of two polynomials of degree <= 3. Then a(3) = 128 - 48 - 1 = 79.

(End)

PROG

(PARI) \\ here b(n) is A001037.

b(n)={sumdiv(n, d, moebius(d)*2^(n/d))/n}

PartitionProduct(p, f)={my(r=1, k=0); for(i=1, length(p), if(i==length(p) || p[i]!=p[i+1], r*=f(p[i], i-k); k=i)); r}

ok(p, n, r)={poldegree(Pol(prod(i=1, #p, 1 + x^p[i] + O(x*x^n)))) >= r}

a(n)={my(u=vector(n, i, b(i)), s=2^(n+1)); for(r=1, n, forpart(p=n+r, if(ok(p, n, r), s+=PartitionProduct(p, (t, e)->binomial(u[t]+e-1, e))), [1, n])); s} \\ Andrew Howroyd, Jul 10 2018

CROSSREFS

Cf. A001037, A073961.

Sequence in context: A240526 A018886 A145842 * A093069 A341665 A322269

Adjacent sequences:  A086905 A086906 A086907 * A086909 A086910 A086911

KEYWORD

nonn

AUTHOR

Yuval Dekel (dekelyuval(AT)hotmail.com), Sep 19 2003

EXTENSIONS

a(9)-a(25) from Andrew Howroyd, Jul 10 2018

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 April 14 19:20 EDT 2021. Contains 342951 sequences. (Running on oeis4.)