Just Sum Logs

Relevant wiki: Arithmetic-Geometric Progression

Note that for $\left \lfloor \log_b a \right \rfloor = k$ for $b^k \le a < b^{k+1}$ , where $k$ is a positive integer. Therefore, $\displaystyle \sum_{a = b^k}^{b^{k+1}-1} \left \lfloor \log_b a \right \rfloor = \left(b^{k+1}-b^k\right)k = (b-1)kb^k$ . And the general solution is

$\begin{aligned} S_b & = (b-1){\color{#3D99F6}\sum_{k=1}^{{\color{#D61F06}n}-1}kb^k} + \left(101-b^{\color{#D61F06}n}\right)\color{#D61F06}n & \small \color{#3D99F6} \text{An AGP sum} \\ & = ({\color{#D61F06}n}-1)b^{\color{#D61F06}n} - \frac {b(b^{{\color{#D61F06}n}-1}-1)}{b-1}+ \left(101-b^{\color{#D61F06}n}\right)\color{#D61F06}n & \small \color{#D61F06} \text{where } n = \left \lfloor \log_b 100 \right \rfloor \\ S_2 & = 5(2^6) - \frac {2(2^5-1)}1 + (101-2^6)6 = 480 \\ S_3 & = 3(3^4) - \frac {3(3^3-1)}2 + (101-3^4)4 = 284 \\ S_4 & = 2(4^3) - \frac {4(4^2-1)}3 + (101-4^3)3 = 219 \end{aligned}$

For $5 \le b \le 10$ , $n = \left \lfloor \log_b 100 \right \rfloor = 2$ , then

$\begin{aligned} S_b & = 202-b^2 - b \\ \implies \sum_{b=5}^{10} S_b & = \sum_{b=5}^{10} \left(202-b^2 - b\right) = 202(6) - \frac {10(11)(21)}6 + \frac {4(5)(9)}6 - \frac {10(11)}2 + \frac {4(5)}2 = 812 \end{aligned}$

For $11 \le b \le 100$ , $n=1$ , then $S_b = 101 - b$ $\implies \displaystyle \sum_{b=11}^{100} (101-b) = \sum_{k=1}^{90} k = \frac {90(91)}2 = 4095$ .

Therefore, $\displaystyle \sum _{a=2}^{100} \sum _{b=2}^{100} \left\lfloor \log_b a \right\rfloor = \sum_{b=2}^{100} S_b = 480+284+219+812+4095 = \boxed{5890}$ .

We will use the fact that $\lfloor \log_b a \rfloor = k$ iff $b^k \le a < b^{k+1}$ , and this inequality holds for exactly $b^{k+1} - b^k = b^k (b - 1)$ natural numbers.

To develop this into a formula, we consider what happens when $b = 4$ . For $a < 4$ , we will have $\lfloor \log_4 a \rfloor = 0$ , so they contribute nothing to our sum. When $4 \le a < 4^2$ , we will have $\lfloor \log_4 a \rfloor = 1$ , and there will be $4(3)$ such terms, so they contribute $4(3) \cdot 1$ to our sum. Similarly, when $4^2 \le a < 4^3$ , we will have $\lfloor \log_4 a \rfloor = 2$ , and there will be $4^2(3)$ such terms, so they contribute $4^2(3) \cdot 2$ to our sum. Now, however, we have to use a different formula for the contribution of the remaining terms, because the next power, $4^4$ is greater than $100$ . So for $4^3 \le a \le 100$ , we will have $\lfloor \log_4 a \rfloor = 1$ , and there will be $100 - 4^3 + 1$ such terms, so they contribute $(100 - 4^3 + 1) \cdot 3$ to our sum. So the total contribution to our sum for $b = 4$ is

$4(3) \cdot 1 + 4^2(3) \cdot 2 + (100 - 4^3 + 1) \cdot 3 = 219$

In general, for $b = k$ , the contribution will be

$k(k - 1) \cdot 1 + k^2(k - 1) \cdot 2 + k^3(k - 1) \cdot 3 \ + .... + \ k^{n - 1}(k - 1) \cdot (n-1) + (100 - k^n + 1) \cdot n$

where $n \in \mathbb{N}$ is the highest exponent such that $k^n \le 100$ .

Admittedly, this is not very efficient for very low values of $\ b$ , even if there's a fairly simple pattern to the terms; however, the number of terms quickly decreases as there are fewer and fewer powers of $\ b \$ under $100$ , and in fact as we will see, when $\ b > 10 \$ we will be able to count all the contributions in one step.

\begin{aligned} &b = 2: \qquad &&2(1) \cdot 1 + 2^2(1) \cdot 2 + 2^3(1) \cdot 3 + 2^4(1) \cdot 4 + 2^5(1) \cdot 5 + (100 - 2^6 + 1) \cdot 6 &= 480 \\ &b = 3: &&3(2) \cdot 1 + 3^2(2) \cdot 2 + 3^3(2) \cdot 3 + (100 - 3^4 + 1) \cdot 4 &= 284 \\ &b = 4: &&4(3) \cdot 1 + 4^2(3) \cdot 2 + (100 - 4^3 + 1) \cdot 3 &= 219 \\ &b = 5: &&5(4) \cdot 1 + (100 - 5^2 + 1) \cdot 2 &= 172 \\ &b = 6: &&6(5) \cdot 1 + (100 - 6^2 + 1) \cdot 2 &= 160 \\ &b = 7: &&7(6) \cdot 1 + (100 - 7^2 + 1) \cdot 2 &= 146 \\ &b = 8: &&8(7) \cdot 1 + (100 - 8^2 + 1) \cdot 2 &= 130 \\ &b = 9: &&9(8) \cdot 1 + (100 - 9^2 + 1) \cdot 2 &= 112 \\ &b = 10: &&10(9) \cdot 1 + (100 - 10^2 + 1) \cdot 2 &= 92 \\ &\hline \\ & b = 2 \text{ to } 10: &&\text{ } &= 1795 \end{aligned}

For $b \ge 11$ we will only have one term, namely $(100 - b +1) \cdot 1$ as there is only a single power of $b$ under 100. So all those contributions can be calculated as

$\begin{aligned} \sum_{b = 11}^{100} (101 - b) &= \sum_{c = 1}^{90} c \qquad \qquad \small \text{[Using the substitution } c = 101 - b \ ] \\ \\ &= \dfrac{(90)(91)}{2} \\ \\ &= 4095 \end{aligned}$

Thus we finally arrive (not too painfully) at

$\sum_{a = 2}^{100} \sum_{b = 2}^{100} \lfloor \log_b a \rfloor = 1795 + 4095 = \boxed{5890}$