# Closed formula or approximations for $\sum_{i=2}^{n} \lfloor \log_{i}(n) \rfloor$

I was working on this problem:

How many integer pairs $$2\le x, y \le 2019$$ exist such that $$\log_x(y)$$ is an integer?

I found this to be $$\sum_{i=2}^{2019} \lfloor \log_i(2019) \rfloor = 2086$$

This led me to the question of a general formula or an asymptotic approximation for $$f(n) = \sum_{i=2}^{n} \lfloor \log_{i}(n) \rfloor$$. A "more continuous" version of this would be $$g(n) = \sum_{i=2}^{n} \log_{i}(n)$$, while an even more continuous version would be $$h(n)=\int_2^n \log_x(n)dx$$.

I wasn't able to find an approximation or bounds for $$f(n)$$, but did manage to get an asymptotic recurrence relation of $$f(n^2) \approx n^2-n+2f(n)$$

For $$g(n)$$, I found this question which shows that $$g(n) = \text{li}(n) \ln(n) + C \ln(n) + O(1)$$ where $$C=\frac{1}{\log2}+\int_{2}^{\infty}\frac{\{x\}}{x\log^{2}x}dx$$

and I found that $$h(n) = \int_2^{n} \frac{\ln(n)}{\ln(x)} dx = \ln(n)(\text{li}(n)-\text{li}(2))$$

Can I get a closed formula for $$f(n)$$? If not, how can I find bounds?

• It is also equal to $\sum_{n=1}^{\infty}\left(\left\lfloor2019^{1/n}\right\rfloor -1\right)$ Oct 9 '19 at 23:16

Note that $$\log_i n\ge k \iff n\ge i^k \iff i\le\sqrt[k]{n}$$.
We can use this to rewrite the sum in terms of the number of integers $$i,k$$ for which this is satisfied. $$\sum_{i=2}^n \lfloor\log_i n\rfloor = \sum_{i=2}^n \sum_{k=1}^{\lfloor\log_i n\rfloor} 1 = \sum_{\substack{2\le i\le n \\ 1\le k\\ i^k\le n}} 1 = \sum_{k=1}^{\lfloor\log_2 n\rfloor} \sum_{i=2}^{\lfloor\sqrt[k]{n}\rfloor} 1 = \sum_{k=1}^{\lfloor\log_2 n\rfloor} \lfloor\sqrt[k]{n}\rfloor - 1$$ Note that the upper bound of $$k\le\log_2 n$$ may be placed since higher values do not contribute.
In terms of approximations, you may note that the size of the terms $$\lfloor\sqrt[k]{n}\rfloor-1$$ drops fast as $$k$$ increases, so just the first few terms of the sum should provide a good approximation except for very small $$n$$.