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.