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

$\endgroup$
4
  • $\begingroup$ Do you really mean to not use $m$ anywhere in the summands of your initial sum? $\endgroup$ Apr 23, 2012 at 13:24
  • $\begingroup$ @ThomasAndrews: typo, fixing it now. Thanks! $\endgroup$
    – Carolus
    Apr 23, 2012 at 13:24
  • $\begingroup$ The OEIS expression has subsequently been corrected. $\endgroup$ Nov 17, 2015 at 3:19
  • $\begingroup$ Connected with this math.stackexchange.com/a/2356019/312 $\endgroup$
    – leonbloy
    Sep 13, 2017 at 20:14

3 Answers 3

7
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Ah, of course, thanks. $\endgroup$
    – Carolus
    Apr 23, 2012 at 14:00
3
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Yeah, I see that now. Thank you. $\endgroup$
    – Carolus
    Apr 23, 2012 at 14:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .