Find the minimum N such that the sum of beauty of all numbers from 1 to N is at least X

Question

The beauty of a number is defined as follows :-

public int beauty(long number)
{
     int count = 0;

     while( number > 0 )
     {
         count += (number & 1);
         number = number / 2;
     }

     return count;
}

Given X, we need to find the minimum N such that the sum of beauty of all numbers from 1 to N (inclusive) is at least X. X may be as large as upto 10^18 and there are 2*(10^4) test cases.

As far as I have understood, the beauty of the number is the count of set bits in the integer. So we need to find the sum of count of set-bits from 1 to N. But numbers such as X = 10^18 give the values 10^15 for N. It is not feasible to run loop from 1 to 10^15. Is there a better algorithm ?

Answer 1

Notations :

• $b(x)$ is the beauty of $x$.
• $S_c(n) = \sum_{x = 0}^{2^n-1} (b(x)+c)$ where $c\in\mathbb N$
• $\tilde O(\log t)$ : polylogarithmic in $t$

Argument :

Let's first show that $S_c(n)$ is easy to calculate for any $c,n\in\mathbb N$. Each number in $[\![0, 2^{n-1}]\!]$ has at most $n$ bits, and for each $i\in[\![1, n]\!]$, exactly half of the numbers below $2^n$ have the $i$-th bit set to 1. Therefore, we can rewrite $$\sum_{x =0}^{2^n-1} b(x) = \sum_{i = 1}^n 2^n/2 = n\cdot 2^{n-1}$$ (in 0, the result is 0). This leads to : $$ S_c(n) = 2^{n-1}\cdot (c+2n)$$ Since $S_c(n)$ grows exponentially and is computable in $O(n)$, it takes $\tilde O(\log X)$ time to find the (unique) $n$ such that \begin{equation}S_c(n)\le X< S_c(n+1)\end{equation}

We'll note $n_0$ this $n$ for $c = 0$. One should notice that this $n_0$ is the index of the leftmost bit set to 1 in $N$ $$\sum_{x = 0}^N b(x) = \sum_{x = 0}^{2^{n_0}-1} b(x) + \sum_{x = 2^{n_0}}^N b(x)$$ Moreover, $N<2^{n+1}$, so each $x$ in the rightmost sum has $n$ bits and the leftmost bit set to 1, i.e. : $$\sum_{x = 2^n}^N b(x) = \sum_{x = 0}^{N-2^n} b(x) + 1$$

We therefore get a recursive call : we can find the index of the leftmost bit set to 1 in $N-2^n$ by finding $n_1$ such that $S_1(n_1)\le (X- S_0(n_0)) \le S_1(n_1+1)$

This lends the following algorithm :

s(n,c) =
    if n = 0 then c
    else (2^(n-1)*(c+2*n))

smallest_n(x,c,n) = //We shall call this function with n = 0
    if s(n+1,c) > x then n
    else smallest_n(x,c,n+1)

sum_beauties_above(x,c) =
    if x = 0 then 0
    else
        let n = smallest_n(x,c,0) in
        let n' = sum_beauties_above(x - s(n,c),c+1) in
        2^n + n'
sum_beauties_above(x,0)

the first function takes $O(n)$ time, the second takes $\tilde O(\log X)$. The main function calls itself as many times as $N$ has bits set to $1$, which is bounded by $\log N\le \log X$, and each call has complexity $\tilde O(\log X)$, so we keep a polylogarithmic complexity in $X$.

However, this has been written in functionnal programming style, and is not tail-recursive, therefore, it is highly suboptimal, but this way of writing seems easier to understand, and one should take care of optimization.

Answer 2

Let us first solve the following problem:

Given $n$, count the total number of 1-bits of all integers from $0$ to $n-1$.

Suppose that $n = 2^{m_1} + 2^{m_2} + \cdots + 2^{m_k}$, where $m_1 > m_2 > \cdots > m_k$; every positive integer has such a representation. We can divide the range $[0,n) := \{0,\ldots,n-1\}$ into the following ranges: $$ [0,n) = [0,2^{m_1}) + [2^{m_1}, 2^{m_1}+2^{m_2}) + \cdots + [2^{m_1} + \cdots + 2^{m_{k-1}}, 2^{m_1} + \cdots + 2^{m_k}). $$ Let's start with the first range, $[0,2^{m_1})$. This range consists of all $m_1$-bit numbers. Each particular bit is 1 exactly half the time, and so the total number of 1-bits in $[0,2^{m_1})$ is $m_12^{m_1-1}$.

The second range consists of all numbers in $[0,2^{m_2})$ to which $2^{m_1}$ was added. The additional power contributes an extra 1-bit to each number in the range, for a total of $m_2 2^{m_2-1} + 2^{m_2}$, which can also be written as $2^{m_2} (m_2/2 + 1)$.

Continuing in this way, we see that the total number of 1-bits of all integers in $[0,n)$ is $$ 2^{m_1}(m_1/2) + 2^{m_2}(m_2/2+1) + 2^{m_3}(m_3/2+2) + \cdots + 2^{m_k}(m_k/2+k-1). $$

This suggests the following algorithm:

1. Find the maximal $m_1$ such that $\sigma_1 := 2^{m_1}(m_1/2) \leq x$. In case of equality, return $2^{m_1}-1$.
2. Find the maximal $m_2 < m_1$ (if any) such that $\sigma_2 := \sigma_1 + 2^{m_2}(m_2/2+1) \leq x$. In case of equality, return $2^{m_1} + 2^{m_2}-1$.
3. Continue in this way. If you get stuck at $m_1,\ldots,m_k$, return $2^{m_1} + \cdots + 2^{m_k}$.

(Getting stuck means that there is no $m_{k+1} < m_k$ such that $\sigma_{k+1} \leq x$.)