# Modulo 2 Binomial Transform

Paul D. Hanna pauldhanna at juno.com
Sat Dec 25 22:28:56 CET 2004

```One last note regarding Paul Barry's Modulo 2 Binomial Transform.

If we apply the triangle formed by reading Pascal's triangle mod 2:
http://www.research.att.com/projects/OEIS?Anum=A047999
as a transformation on a sequence A, and apply this transform M times,
the formula for this (Mod 2 Binomial transformation)^M of A is:

(1)  a(n) = Sum_{k=0..n} M^A000120(k)*(C(n,k) Mod 2)*A(k)
where A000120(k) = number of 1's in binary expansion of k.

This can be expressed using PARI code as:
a(n)=sum(k=0,n,M^subst(Pol(binary(n-k)),x,1)*(binomial(n,k)%2)*A(k))

A special case exists when A(n) = B^n for integer B;
for then (1) is equivalent to the product formula:

(2)  a(n) = Product_{k=0..[log_2(n)]} ( B^(2^k) + M )^b(n,k)
where b(n,k) = coefficient of 2^k in the binary expansion of n.

This can be expressed using PARI code as:
a(n)=prod(k=0,length(binary(n))-1,(B^(2^k)+M)^bittest(n,k))

The product formula (2) explains the factorization behavior noted
earlier.

(Merry Christmas)^2,
Paul
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20041225/f8d9c457/attachment.htm>
```