How to solve $ \sum_{i=1}^{n} \left \lfloor{\log{i}}\right \rfloor $ for closed form

Question

I'm trying to get a closed form of this equation:

$$ \sum_{i=1}^{n} \left \lfloor{\log{i}}\right \rfloor $$

I know that

$$ \sum_{i=1}^{n} {\log{i}} = \log{n!}$$

But I'm confused about how the floor operator affects this and just adding the floor operator seems to break down after trying a few small examples.

Thanks!

Answer 1

Throughout, $\log$ is assumed to be $\log_{10}$.

---

Note that

$\lfloor\log k \rfloor = 0, \ \ (k=1,2,...,9)$

$\lfloor\log k \rfloor = 1, \ \ (k=10,11,...,99)$

$...$

$\lfloor\log k \rfloor = m, \ \ (k=10^m,...,10^{m+1}-1), \ \ m \in \mathbb{Z}_{\ge 0}$

Thus, number of $k$'s such that $\lfloor\log k \rfloor = m \ \ $ is $ \ \ (10^{m+1}-1)-(10^m-1)=9\cdot10^m$.

Therefore, $$\sum_{i=1}^n\lfloor \log i \rfloor = \left[\sum_{i=0}^{\lfloor \log n \rfloor-1}i\cdot(9\cdot10^i)\right]+(m+1)(n-10^{\lfloor \log n \rfloor}+1)$$

Is the part "$n-10^{\lfloor \log n \rfloor}+1$" unclear? To understand, take $n=123$. Then, we have $9$ zero summands, and $90$ one summands (upper bound of the sum, namely $\lfloor \log n \rfloor-1$ is reached here). To find the number of $2$ summands, we calculate $123-10^2+1=24$.

Now, it shouldn't be difficult to work with the last sum.

Answer 2

Yes, there is. I assume you are talking about base 10 - notice that in base 10, we can find the number of digits of a number using this formula:

$$ \left \lfloor \log{n} \right \rfloor - 1$$

For example:

$$ \left \lfloor \log_{10}(7521) \right \rfloor + 1 = 4$$

For simplicity we will denote:

$$\left \lfloor \log{n} \right \rfloor = c$$

Because we floor the logarithmic function, it looks as so:

• For values between $1-9$ it will output a $0$
• For values between $10 - 99$ it will output a $1$
• For values between $100 - 999$ it will output a $2$
• etc..

We can see the pattern here! for numbers with $d$ digits it will actually sum:

$$ 1 \cdot 90 + 2 \cdot 900 + \dots + d \cdot 9 \cdot 10^d$$

But what about the left-over? If we for example have $n = 1005$ then it will sum:

$$ 1 \cdot 90 + 2 \cdot 900 + ... \text{stop!}$$ What about $$ \left \lfloor 1000 \right \rfloor + \left \lfloor 1001 \right \rfloor + \dots + \left \lfloor 1005 \right \rfloor$$

Fortunately we can find this, by subtracting what we already found from the number ( not forgetting to include the last number:

$$ (n - 10^c + 1) \cdot (c)$$

Now what is left is to calculate what we already know.. if $n$ is given, we can know the number of digits so we can be sure it have $c-1$ digits right? ( if for example $n=7000$ then we can sure iterate $\left \lfloor \log{n} \right \rfloor - 1$ times) so we can sum:

$$ \sum_{i=1}^{c-1} 9 \cdot 10^i \cdot i = \frac{1}{9}( 9 \cdot 10^c \cdot c - 10( 10^c - 1)) $$

And so the final closed formula is:

$$ \frac{1}{9}( 9 \cdot 10^c \cdot c - 10( 10^c - 1)) + (n - 10^c + 1) \cdot (c)$$

Answer 3

Many terms of the sum $$ \sum_{i=1}^{n} \left \lfloor{\log{i}}\right \rfloor $$ will be the same because of the floor. In particular, if the base of the logarithm, $b$, is at least $3^{1/3} \approx 1.44$, then the integers $i$ that have $\lfloor \log i \rfloor = k$ are exactly $\lceil b^k\rceil, \lceil b^k\rceil + 1, \dots, \lceil b^{k+1}\rceil - 1$, so there are $\lceil b^{k+1}\rceil - \lceil b^k\rceil$ of them in the sum. That is, unless $\lfloor \log n \rfloor = k$, in which case there are only $n - \lceil b^k\rceil + 1$ of them. So, we can simplify the sum to $$ \left(\sum_{k=1}^{\lfloor \log n\rfloor} k(\lceil b^{k+1}\rceil - \lceil b^k\rceil)\right) - \lfloor \log n \rfloor(\lceil b^{\lfloor \log n\rfloor}\rceil - n - 1). $$ Here, we've just grouped together all the terms whose log rounds down to $k$, counting how many there are. That's as simple as we can get, without further assumptions.

If $\lfloor \log (n+1)\rfloor > \lfloor \log n\rfloor$ (that is, if $n+1 = \lceil b^k\rceil$ for some $k$), then the extra term outside the sum disappears and we only have the sum to simplify.

Separately, if $b$ is an integer, then we can get a closed form for the sum (keeping the term outside it, if $n+1$ is not a power of $b$): $$ \sum_{k=1}^{\lceil \log n\rceil} k(b^{k+1} - b^k) = \sum_{k=1}^{\lceil \log n \rceil} \sum_{j=1}^k (b^{k+1}-b^k) = \sum_{j=1}^{\lceil \log n \rceil} \sum_{k=j}^{\lceil \log n\rceil} (b^{k+1}-b^k) $$ and now the inner sum telescopes, giving us $$ \sum_{j=1}^{\lceil \log n\rceil} (b^{\lceil \log n\rceil + 1} - b^j) = \lceil \log n \rceil b^{\lceil \log n \rceil + 1} - \sum_{j=1}^{\lceil \log n\rceil}b^j = \lceil \log n \rceil b^{\lceil \log n \rceil + 1} - \frac{b^{\lceil \log n\rceil+1} - b}{b-1}. $$

Answer 4

You don't state what the base of your $\log$ is. If it is base $10$ or any integer this is little easier than if it is base $e$.

Notice that if it is base $b$ ($b > 1$) then if $k$ is so that $b^m \le k < b^{m+1}$ then $m \le \log k < m+1$ and $\lfloor \log k \rfloor = m$.

I'm going to assume your base is ten. Now if $10^m \le n < 10^{m+1}$ then

Then $\sum_{k=1}^n \lfloor \log k \rfloor = \sum_{k=1}^9 \lfloor\log k \rfloor + \sum_{k=10}^{99} \lfloor\log k \rfloor + \sum_{k=100}^{999}\lfloor \log k \rfloor + ........ + \sum_{k=10^{m-1}}^{10^m-1} \lfloor \log k \rfloor + \sum_{k=10^m}^n \lfloor \log k \rfloor =$

$\sum_{k=1}^9 0 + \sum_{k=10}^{99} 1 + \sum_{k=100}^{999} 2 + ........ + \sum_{k=10^{m-1}}^{10^m-1} (m-1) + \sum_{k=10^m}^n m =$

$89*1 + 899*2 + 8999*3 + ...... + (10^{j+1}-10^{j}-1)*j + ...... +(n-10^m+1) m=$

$[\sum_{j=1}^{\lfloor \log n\rfloor} (10^{j+1}-10^{j}-1)*j]+ (n+1 -10^{\lfloor \log n\rfloor} + 1)\lfloor \log n\rfloor$