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

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!

• What is the base of your $\log$ ? In base 2 or 10 you might find something more easily than in base e Sep 4, 2020 at 16:51
• Give it a name and it becomes a "closed form". Sep 4, 2020 at 17:14
• Similar to: Sum[Floor[Log[i]], {i, 1, n}]==1/2 (1 - n + 2 Log[Pochhammer[2, -1 + n]]) + I/(2 Pi)*Sum[Log[-j^(2 I Pi)], {j, 2, n}] a Mathematica code. Sep 4, 2020 at 17:18
• Possible solution for integer bases math.stackexchange.com/questions/1816094/… Sep 4, 2020 at 17:24
• If $b$ is the base of your log the trick is to realise that for all $i; b^k \le i < b^{k+1}$ then $[\log i]= k$. Can you take it from there. Sep 4, 2020 at 17:33

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.

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

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

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