# Modulo 2 Binomial Transform

Paul D. Hanna pauldhanna at juno.com
Sun Dec 26 01:09:24 CET 2004

```I made a typo in (1) - it should have read A000120(n-k) not A000120(k);
the correct formula is given below.

The formula for the (Mod 2 Binomial transformation)^M of A is:
(1)  a(n) = Sum_{k=0..n} M^A000120(n-k)*(C(n,k) Mod 2)*A(k)

Again, the transform has nice factorization properties for A(n)=B^n.

Is it easy to prove that the following sum is equal to the product below?
(empirically, this holds true to at least n=4096 for all integer B and
M).

Sum_{k=0..n} M^A000120(n-k)*(C(n,k) Mod 2)*B^k  =
Product_{k=0..[log_2(n)]} ( B^(2^k) + M )^b(n,k)

where A000120(k) = number of 1's in binary expansion of k
and where b(n,k) = coefficient of 2^k in the binary expansion of n.

This PARI code gives the difference of these two formulas, and
returns all zeros for all B and M up to n=4096:
a(n)=sum(k=0,n,M^subst(Pol(binary(n-k)),x,1)*(binomial(n,k)%2)*B^k)
b(n)=prod(k=0,length(binary(n))-1,(B^(2^k)+M)^bittest(n,k))
for(n=0,4096,print1(a(n)-b(n),","))

Thanks,
Paul
------------------------------------------------------------------------
On Sat, 25 Dec 2004 16:28:56 -0500 Paul D. Hanna <pauldhanna at juno.com>
writes:
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/82a0b8f3/attachment-0001.htm>
```