3
$\begingroup$

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!

$\endgroup$
5
  • 4
    $\begingroup$ What is the base of your $\log$ ? In base 2 or 10 you might find something more easily than in base e $\endgroup$
    – Damien
    Sep 4, 2020 at 16:51
  • $\begingroup$ Give it a name and it becomes a "closed form". $\endgroup$
    – WhatsUp
    Sep 4, 2020 at 17:14
  • $\begingroup$ 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. $\endgroup$ Sep 4, 2020 at 17:18
  • $\begingroup$ Possible solution for integer bases math.stackexchange.com/questions/1816094/… $\endgroup$
    – kingW3
    Sep 4, 2020 at 17:24
  • $\begingroup$ 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. $\endgroup$
    – fleablood
    Sep 4, 2020 at 17:33

4 Answers 4

2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .