<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META http-equiv=content-type content=text/html;charset=us-ascii>
<META content="MSHTML 6.00.2600.0" name=GENERATOR></HEAD>
<BODY bottomMargin=0 leftMargin=3 topMargin=0 rightMargin=3>
<DIV>I made a typo in (1) - it should have read A000120(n-k) not
A000120(k); </DIV>
<DIV>the correct formula is given below. </DIV>
<DIV> </DIV>
<DIV>
<DIV>The formula for the (Mod 2 Binomial transformation)^M of
A is: </DIV>
<DIV>(1) a(n) = Sum_{k=0..n} M^A000120(n-k)*(C(n,k) Mod
2)*A(k) </DIV>
<DIV> </DIV>
<DIV>Again, the transform has nice factorization properties for A(n)=B^n. </DIV>
<DIV> </DIV>
<DIV>Is it easy to prove that the following sum is equal to the
product below?</DIV>
<DIV>(empirically, this holds true to at least n=4096 for all integer B and
M). </DIV>
<DIV> </DIV>
<DIV> Sum_{k=0..n} M^A000120(n-k)*(C(n,k) Mod 2)*B^k = </DIV>
<DIV> Product_{k=0..[log_2(n)]} ( B^(2^k) + M )^b(n,k) </DIV></DIV>
<DIV> </DIV>
<DIV>
<DIV>where A000120(k) = number of 1's in binary expansion of k </DIV>
<DIV>and where b(n,k) = coefficient of 2^k in the binary expansion of
n. </DIV>
<DIV> </DIV>
<DIV>This PARI code gives the difference of these two formulas,
and </DIV>
<DIV>returns all zeros for all B and M up to n=4096: </DIV>
<DIV>a(n)=sum(k=0,n,M^subst(Pol(binary(n-k)),x,1)*(binomial(n,k)%2)*B^k)<BR>b(n)=prod(k=0,length(binary(n))-1,(B^(2^k)+M)^bittest(n,k))
<BR>for(n=0,4096,print1(a(n)-b(n),","))<BR> </DIV>
<DIV>Thanks,</DIV>
<DIV> Paul</DIV>
<DIV>------------------------------------------------------------------------</DIV></DIV>
<DIV>On Sat, 25 Dec 2004 16:28:56 -0500 Paul D. Hanna <<A
href="mailto:pauldhanna@juno.com">pauldhanna@juno.com</A>> writes:</DIV>
<BLOCKQUOTE dir=ltr
style="PADDING-LEFT: 10px; MARGIN-LEFT: 10px; BORDER-LEFT: #000000 2px solid">
<DIV>One last note regarding Paul Barry's Modulo 2 Binomial
Transform. </DIV>
<DIV> </DIV>
<DIV>If we apply the triangle formed by reading Pascal's triangle mod 2:
</DIV>
<DIV><A
href="http://www.research.att.com/projects/OEIS?Anum=A047999">http://www.research.att.com/projects/OEIS?Anum=A047999</A> </DIV>
<DIV>as a transformation on a sequence A, and apply this transform M times,
</DIV>
<DIV>the formula for this (Mod 2 Binomial transformation)^M of
A is: </DIV>
<DIV> </DIV>
<DIV>(1) a(n) = Sum_{k=0..n} M^A000120(k)*(C(n,k) Mod
2)*A(k) </DIV>
<DIV>where A000120(k) = number of 1's in binary expansion of k. </DIV>
<DIV> </DIV>
<DIV>This can be expressed using PARI code as:</DIV>
<DIV>a(n)=sum(k=0,n,M^subst(Pol(binary(n-k)),x,1)*(binomial(n,k)%2)*A(k))</DIV>
<DIV> </DIV>
<DIV> </DIV>
<DIV>A special case exists when A(n) = B^n for integer B; </DIV>
<DIV>for then (1) is equivalent to the product formula: </DIV>
<DIV> </DIV>
<DIV>
<DIV>(2) a(n) = Product_{k=0..[log_2(n)]} ( B^(2^k) + M )^b(n,k)
</DIV>
<DIV>where b(n,k) = coefficient of 2^k in the binary expansion of
n. </DIV></DIV>
<DIV> </DIV>
<DIV>This can be expressed using PARI code as:</DIV>
<DIV>a(n)=prod(k=0,length(binary(n))-1,(B^(2^k)+M)^bittest(n,k))
<BR> </DIV>
<DIV>The product formula (2) explains the factorization behavior noted
earlier. </DIV>
<DIV> </DIV>
<DIV>(Merry Christmas)^2,</DIV>
<DIV> Paul</DIV>
<DIV> </DIV></BLOCKQUOTE></BODY></HTML>