1
$\begingroup$

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?

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

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.

I doubt if there is a simple closed form for this.

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.