cp's OEIS Frontend

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.

%I A086908 #10 Dec 30 2024 03:51:57
%S A086908 7,23,79,272,991,3587,13499,50838,194251,745754,2883084,11173940,
%T A086908 43487349,169658939,663264004,2598336785,10190703415,40038964037,
%U A086908 157431540197,619871791795,2442107730237,9632769956279,38008189846122,150127214291450,593141915883700
%N 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.
%C A086908 Either polynomial may be 0. - _Andrew Howroyd_, Jul 10 2018
%H A086908 Sean A. Irvine, <a href="/A086908/b086908.txt">Table of n, a(n) for n = 1..45</a>
%e A086908 From _Andrew Howroyd_, Jul 10 2018: (Start)
%e A086908 Case n=1: Except for x^2 + x + 1 all polynomials with degree <= 2 are represented:
%e A086908   0 = 0*1,
%e A086908   1 = 1*1,
%e A086908   x = 1*x,
%e A086908   x + 1 = 1*(x + 1),
%e A086908   x^2 = x*x,
%e A086908   x^2 + 1 = (x + 1)*(x + 1),
%e A086908   x^2 + x = x*(x + 1).
%e A086908 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.
%e A086908 (End)
%o A086908 (PARI) \\ here b(n) is A001037.
%o A086908 b(n)={sumdiv(n, d, moebius(d)*2^(n/d))/n}
%o A086908 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}
%o A086908 ok(p,n,r)={poldegree(Pol(prod(i=1, #p, 1 + x^p[i] + O(x*x^n)))) >= r}
%o A086908 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
%Y A086908 Cf. A001037, A073961.
%K A086908 nonn
%O A086908 1,1
%A A086908 Yuval Dekel (dekelyuval(AT)hotmail.com), Sep 19 2003
%E A086908 a(9)-a(25) from _Andrew Howroyd_, Jul 10 2018