TAOCP 7.1.3 Exercise 41

Let ordinary generating functions be taken in the sense $A(z)=\sum_{n\ge 0} a_n z^n,$ and extend the functions by $a_0=0$ for $\rho,\lambda,\nu$.

taocpmathematicsalgorithmsvolume-4math-medium

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 41. [M22] What are the generating functions of the integer sequences (a) $\rho n$, (b) $\lambda n$, and (c) $\nu n$?

Verified: no
Solve time: 1m02s

Solution

Let ordinary generating functions be taken in the sense

$A(z)=\sum_{n\ge 0} a_n z^n,$

and extend the functions by $a_0=0$ for $\rho,\lambda,\nu$.

(a) Generating function of $\rho n$

For $n\ge 1$, $\rho n$ is the position of the least significant $1$-bit of $n$. Thus $\rho n = k$ if and only if $n$ is divisible by $2^{k-1}$ and not divisible by $2^k$, hence

$n = (2m+1)2^{k-1}, \qquad m\ge 0.$

The contribution of all such $n$ to the generating function is

$\sum_{m\ge 0} z^{(2m+1)2^{k-1}} = z^{2^{k-1}} \sum_{m\ge 0} (z^{2^k})^m = \frac{z^{2^{k-1}}}{1-z^{2^k}}.$

Weighting by the value $\rho n = k$ gives

$\sum_{n\ge 1} \rho n , z^n = \sum_{k\ge 1} k \frac{z^{2^{k-1}}}{1-z^{2^k}}.$

Hence

$\boxed{\sum_{n\ge 0} \rho n , z^n = \sum_{k\ge 1} \frac{k, z^{2^{k-1}}}{1-z^{2^k}}}.$

(b) Generating function of $\lambda n$

For $n\ge 1$, $\lambda n$ is the position of the most significant $1$-bit, so

$\lambda n = k+1 \quad \text{for} \quad 2^k \le n < 2^{k+1}.$

Hence

= \sum_{k\ge 0} (k+1)\sum_{n=2^k}^{2^{k+1}-1} z^n.$$ The inner sum is a finite geometric series, $$\sum_{n=2^k}^{2^{k+1}-1} z^n = z^{2^k}\frac{1-z^{2^k}}{1-z}.$$ Substitution yields $$\sum_{n\ge 1} \lambda n , z^n = \sum_{k\ge 0} (k+1)\frac{z^{2^k}-z^{2^{k+1}}}{1-z}.$$ Thus $$\boxed{\sum_{n\ge 0} \lambda n , z^n = \sum_{k\ge 0} (k+1)\frac{z^{2^k}-z^{2^{k+1}}}{1-z}}.$$ --- ### (c) Generating function of $\nu n$ Here $\nu n$ is the number of $1$-bits in the binary expansion of $n$. Each bit position $k$ contributes $1$ whenever that bit is $1$, so $$\nu n = \sum_{k\ge 0} [\text{bit }k\text{ of }n\text{ is }1].$$ For fixed $k$, the set of $n$ with the $k$-th bit equal to $1$ consists of disjoint blocks of length $2^{k+1}$, with $2^k$ consecutive ones in each block. Hence the generating function contribution of bit $k$ is $$\sum_{m\ge 0}\sum_{j=0}^{2^k-1} z^{m2^{k+1}+2^k+j} = z^{2^k}\left(\sum_{j=0}^{2^k-1} z^j\right)\left(\sum_{m\ge 0} z^{m2^{k+1}}\right).$$ Evaluating the two geometric sums gives $$z^{2^k}\frac{1-z^{2^k}}{1-z}\cdot \frac{1}{1-z^{2^{k+1}}} = \frac{z^{2^k}}{1-z^{2^{k+1}}}.$$ Summing over all bit positions, $$\sum_{n\ge 0} \nu n , z^n = \sum_{k\ge 0} \frac{z^{2^k}}{1-z^{2^{k+1}}}.$$ Therefore $$\boxed{\sum_{n\ge 0} \nu n , z^n = \sum_{k\ge 0} \frac{z^{2^k}}{1-z^{2^{k+1}}}}.$$ This completes the solution. ∎