Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Do you really mean to not use $m$ anywhere in the summands of your initial sum? – Thomas Andrews Apr 23 '12 at 13:24
@ThomasAndrews: typo, fixing it now. Thanks! – Carolus Apr 23 '12 at 13:24
The OEIS expression has subsequently been corrected. – András Salamon Nov 17 '15 at 3:19
up vote 6 down vote accepted

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

share|cite|improve this answer

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

share|cite|improve this answer
Ah, of course, thanks. – Carolus Apr 23 '12 at 14:00

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?

share|cite|improve this answer
Yeah, I see that now. Thank you. – Carolus Apr 23 '12 at 14:24

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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