Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 = ? $$

share|improve this question
2  
Hint: take a look at the output from the following Mathematica command: Differences[Table[Sum[i*Ceiling[Log[2, i]], {i, 1, n}], {n, 1, 32}]] –  A.E May 22 at 15:31
1  
Look at the lengths of runs of arithmetic sequences –  A.E May 22 at 15:34
    
I looked at the sequence ... But I couldn't figure out the closed-form. Could you? –  Mohamed Ennahdi El Idrissi May 22 at 18:13

3 Answers 3

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.

share|improve this answer

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

enter image description here

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 $$

share|improve this answer
up vote 0 down vote accepted

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) $$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.