1
$\begingroup$

Background: I was trying to derive an asymptotic formula for the following:

$\sum_{m\leqslant n}\sum_{k\leqslant m}(m\ \mathrm{mod}\ k),$ which I think I succeeded in doing (I will skip some steps below to come to my question sooner). We have

\begin{align} \sum_{m\leqslant n}\sum_{k\leqslant m}(m\ \mathrm{mod}\ k)&=\sum_{m\leqslant n}\left(m^2-\sum_{k\leqslant m}\sigma(k)\right)\\ &=\sum_{m\leqslant n}\left(m^2-\frac{\pi^2}{12}m^2+O(m\log m)\right)\\ &=\frac{1}{72}(12-\pi^2)n(n+1)(2n+1)+O(\log H(n)), \end{align} where $H(n)$ is the hyperfactorial of $n$. According to the Wikipedia page, it is asymptotic to $ H(n)\sim An^{(6n^2+6n+1)/12}e^{-n^2/4}, $ where $A=1.2824\ldots$ is the Glaisher–Kinkelin constant. So "naturally", the question on my mind was - can the term $O(\log H(n))$ be written in a less complicated way? Rather quickly I found the following $ \log H(n)=\frac{1}{2}n^2\log n+\frac{1}{4}n^2+O(n\log n) $ here (OEIS). The problem is, I can't see how to derive this. I would very much appreciate someone showing me.

  • 0
    Connected with this https://math.stackexchange.com/a/2356019/3122017-09-13

3 Answers 3

7

Perhaps there is a sign error in their entry:$ \log H(n) = \sum_{k=1}^n k \log k.$ Integration by parts gives

$ \int^n_0 x \log x dx = \frac{1}{2}n^2 \log n - \frac{n^2}{4} $ and since $ \sum_{k=1}^n \left(k\log k - \int^k_{k-1} x \log x dx \right)=\mathcal{O}\left( n\log n \right) $ we have $\log H(n) = \frac{1}{2}n^2 \log n - \frac{n^2}{4} + \mathcal{O}\left( n\log n \right).$

4

It's pretty easy to show that $\sum_{m\leq n} m \log m = O(n^2\log n)$. There are $n$ terms, each no bigger than $n\log n$.

  • 0
    Ah, of course, thanks.2012-04-23
3

If you take the asymptotic you've quoted from Wikipedia, and take logarithms, you get $\log H(n)=(1/2)n^2\log n-(1/4)n^2+O(n\log n)$ which is what you want except it has a minus sign where you want a plus sign (as Ragib has noted). Or were you asking how to get the Wikipedia formula?

  • 0
    Yeah, I see that now. Thank you.2012-04-23