A048631 Xfactorials - like factorials but use carryless GF(2)[ X ] polynomial multiplication.

1, 1, 2, 6, 24, 120, 272, 1904, 15232, 124800, 848640, 7507200, 39738368, 433441792, 2589116416, 30419859456, 486717751296, 8128101580800, 132557598294016, 1971862458400768, 30421253686034432, 512675443057623040, 7176891455747129344, 130521457800367308800

Offset: 0

Author

Antti Karttunen, Jul 14 1999

Keywords

• easy
• nonn

Comments

In formula X stands for the multiplication in a ring of GF(2)[ X ] polynomials.

Links

• Vaclav Kotesovec, Table of n, a(n) for n = 0..475
• Vaclav Kotesovec, Graph a(n+1)/a(n)

Crossrefs

Cf. A000142, A048720, A048632, A061922.

Programs

Maple

Xfactorial := proc(n) option remember; if n=0 then 1
                else Xmult(n, Xfactorial(n-1)) fi
              end:
Xmult := proc(n, m) option remember; if n=0 then 0
           else Bits[Xor](((n mod 2)*m), Xmult(floor(n/2), m*2)) fi
         end:
seq(Xfactorial(n), n=0..23);

Mathematica

Xmult[nn_, mm_] := Module[{n = nn, m = mm, s = 0}, While[n > 0, If[1 == Mod[n, 2], s = BitXor[s, m]]; n = Floor[n/2]; m = m*2]; s];
Xfactorial[n_] := Xfactorial[n] = If[0 == n, 1, Xmult[n, Xfactorial[n - 1]] ];
Table[Xfactorial[n], {n, 0, 21}] (* Jean-François Alcover, Mar 04 2016, updated Mar 06 2016 after Maple *)

PARI

a(n)=my(s=Mod(1,2)); for(k=1,n, s*=Pol(binary(k))); fromdigits(Vec(lift(s)), 2) \\ Charles R Greathouse IV, Oct 03 2016

Formula

a(0) = 1, a(n) = n X a(n-1) (see the Maple function Xfactorial given below).

Using the notations introduced in A355891, we have a(n) = ivgenpoly(Product_{i=1..n} genpoly(n)). As an example, n = 6 corresponds to 1*x*(x+1)*x^2*(x^2+1)*(x^2+x) = x^8+x^4 in GF(2)[x], so a(6) = 2^8 + 2^4 = 272. - Jianing Song, Sep 30 2022