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
    Do you really mean to not use $m$ anywhere in the summands of your initial sum?2012-04-23
  • 0
    @ThomasAndrews: typo, fixing it now. Thanks!2012-04-23
  • 0
    The OEIS expression has subsequently been corrected.2015-11-17
  • 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