[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