The Number of 1’s in Binary Integers: Bounds and Extremal Properties
M. D. McIlroy · SIAM Journal on Computing · 1974
Closed formulas provide tight bounds for $G(n)$, the total number of 1’s in the binary representations of integers less than n. This function satisfies an extremal recurrence, which gives the maximum cost of a process that creates a set of n objects by repeatedly merging pairs of smaller sets, starting from n singletons, incurring a cost equal to the size of the smaller set at each merger: \[ G(n) = \max\limits_{1 \leqq i \leqq n /2} [i + G(i) + G(n - i)], \] where $G(1) = 0$. The set of pairs $(i,n - i)$ at which the maximum is attained has an interesting structure.