Find the minimum N such that the sum of beauty of all numbers from 1 to N is at least X
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&lt; 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&lt;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) &gt; 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.