[seqfan] Re: Counting bitcounts

Richard Mathar mathar at strw.leidenuniv.nl
Mon Apr 20 21:41:15 CEST 2009


dw> From seqfan-bounces at list.seqfan.eu Mon Apr 20 21:31:14 2009
dw> Date: Mon, 20 Apr 2009 15:00:29 -0400
dw> From: David Wilson <dwilson at gambitcomm.com>
dw> To: Sequence Fanatics <seqfan at list.seqfan.eu>
dw> Subject: [seqfan]  Counting bitcounts
dw> 
dw> For b >= 0 and n >= 0, let C(b, n) be the number of nonnegative integers
dw> < n having exactly b 1's in their binary representation.
dw> 
dw> Suppose we wish to compute, say, C(3, 1000).  First we write 1000 in binary:
dw> 
dw>         1111101000
dw> 
dw> Then we form the finite sequence e of the places of the 1's within this 
dw> numeral:
dw> 
dw>         e = (9,8,7,6,5,3)
dw> 
dw> This sequence is indexed starting at 0.
dw> 
dw> 
dw> Then we have
dw> 
dw>         SUM (x^i*(x+1)^e(i)) = SUM C(b, n) x^b
...

An associated article discussing these generating functions is

@article{BorweinAMM99,
author={J. M. Borwein and P. B. Borwein},
title={Strange series and high precision fraud},
journal={Amer.\ Math.\ Monthly},
volume= 99,
number=7,
pages={622--640},
url={www.jstor.org/stable/2324993},
year=1992}





More information about the SeqFan mailing list