Summation with Ceilinged Logarithmic Function

Question

According to Johann Blieberger's paper - "Discrete Loops and Worst Case Performance" (1994): $$ \sum_{i = 1}^{n}\left \lceil \log_2{(i)} \right \rceil = n\left \lceil \log_2{(n)} \right \rceil - 2^{\left \lceil \log_2{(n)} \right \rceil} + 1 $$

Now, I was wondering if someone knows what the following may equal?

$$ \sum_{i = 1}^{n}i\left \lceil \log_2{(i)} \right \rceil = ? $$

Answer 1

I could come with a solution with an incisive precision for any base a by doing this: $$ \\ T(n) = \sum_{i= 1}^{n}i\left \lceil \log_a(i) \right \rceil = \left[\sum_{i= 1}^{\left \lfloor \log_a(n) \right \rfloor}i \left(\sum_{j = a^{i - 1} + 1}^{a^i} j\right)\right] + \left \lceil \log_a(n) \right \rceil\sum_{i = a^{\left \lfloor \log_a(n) \right \rfloor} + 1}^{n}i \\ T(n) = \left[\frac{1}{2}\sum_{i= 1}^{\left \lfloor \log_a(n) \right \rfloor}i \left(a^{i - 2}(a -1)(a^{i + 1} + a^i + a)\right)\right] + \left \lceil \log_a(n) \right \rceil\sum_{i = a^{\left \lfloor \log_a(n) \right \rfloor} + 1}^{n}i \\ \text{Let } T_1(n) = \left[\frac{1}{2}\sum_{i= 1}^{\left \lfloor \log_a(n) \right \rfloor}i \left(a^{i - 2}(a -1)(a^{i + 1} + a^i + a)\right)\right] \\ \text{And } T_2(n) = \left \lceil \log_a(n) \right \rceil\sum_{i = a^{\left \lfloor \log_a(n) \right \rfloor} + 1}^{n}i \\ T_1(n) = \frac{1}{2(a^2 - 1)}\left((-1 - \left \lfloor \log_a(n) \right \rfloor)a^{2\left \lfloor \log_a(n) \right \rfloor} - a^{\left \lfloor \log_a(n) \right \rfloor + 1} + \left \lfloor \log_a(n) \right \rfloor a^{\left \lfloor \log_a(n) \right \rfloor+ 2} + \left \lfloor \log_a(n) \right \rfloor a^{2\left \lfloor \log_a(n) \right \rfloor+ 2} - (\left \lfloor \log_a(n) \right \rfloor + 1)a^{\left \lfloor \log_a(n) \right \rfloor} + a + 2 \right) \\ T_2(n) = \frac{\left \lceil \log_a(n) \right \rceil(n - a^{\left \lfloor \log_a(n) \right \rfloor})(a^{\left \lfloor \log_a(n) \right \rfloor} + n + 1)}{2} \\\\ \text{Therefore } T(n) = T_1(n) + T_2(n) $$

Answer 2

Use sum by parts: $$ \sum_{1 \le k \le n} x_k \Delta y_k = x_{n + 1} y_{n + 1} - x_1 y_1 - \sum_{1 \le k \le n} y_{k + 1} \Delta x_k $$ In your case $\Delta y_k = \lceil \log_2 k \rceil$ and $x_k = k$. You'll get a sum similar to the original, you should be able to solve for that one.

Answer 3

Based on @vonbrand's answer, using integration by parts is a good approximation:

Concretely,

$$ \\ \int_{1}^{n}i\left \lceil \log_a{(i)} \right \rceil di = n.n(\left \lceil \log_a{(n)} \right \rceil - 1) - 1(\left \lceil \log_a{(1)} \right \rceil - 1) - \int_{1}^{n}i(\left \lceil \log_a{(i)} \right \rceil - 1) di \\ \int_{1}^{n}i\left \lceil \log_a{(i)} \right \rceil di = n^2(\left \lceil \log_a{(n)} \right \rceil - 1) + 1 - \left [ \frac{i^2(2\left \lceil \log_a{(i)} \right \rceil - 3)}{4}\right ]_{1}^{n} \\ \int_{1}^{n}i\left \lceil \log_a{(i)} \right \rceil di = n^2(\left \lceil \log_a{(n)} \right \rceil - 1) + 1 - \left [ \frac{n^2(2\left \lceil \log_a{(n)} \right \rceil - 3)}{4} - \frac{1(2\left \lceil \log_a{(1)} \right \rceil - 3)}{4}\right] \\ \int_{1}^{n}i\left \lceil \log_a{(i)} \right \rceil di = n^2(\left \lceil \log_a{(n)} \right \rceil - 1) + 1 - \left [ \frac{n^2(2\left \lceil \log_a{(n)} \right \rceil - 3)}{4} + \frac{3}{4}\right] \\ \int_{1}^{n}i\left \lceil \log_a{(i)} \right \rceil di = n^2\left \lceil \log_a{(n)} \right \rceil - n^2 + \frac{1}{4} - \frac{n^2\left \lceil \log_a{(n)} \right \rceil}{2} +\frac{3n^2}{4} \\ \int_{1}^{n}i\left \lceil \log_a{(i)} \right \rceil di = \frac{n^2\left \lceil \log_a{(n)} \right \rceil}{2} - \frac{n^2}{4} + \frac{1}{4} \\\\ \text{Therefore, } \sum_{i = 1}^{n}i\left \lceil \log_a(i) \right \rceil \approx \left \lfloor \frac{n^2\left \lceil \log_a{(n)} \right \rceil}{2} - \frac{n^2}{4} + \frac{1}{4} \right \rfloor $$