# Complexity of divisor function

I've been looking at this the past few days, but can't figure it out. Maybe I don have enough mathematical background, but most probably I'm overlooking something super basic from times long gone. Anyway, my problem:

What is the complexity of:
$$\limsup _{n \to \infty} \; d(n)$$

With $d(n)$ the divisor function. I know that the average complexity is $O(log n)$ and that the infinum is $2$ (for primes), but I can't figure out the complexity of the limit of the supremum.

Ridicule and actual solutions both much appreciated. Also, feel free to retag, I have no clue under what I should tag this.

 I should have mentioned that I was aware of the Wikipedia article. Here's what I don't get about it. Wikipedia states:

$$\limsup_{n\to\infty}\frac{\log d(n) \log\log n}{\log n} = \log 2$$

$$d(n) = O(n^{\frac{\log 2}{\log \log n}})$$

But then, as $n \to \infty$, the exponent will go to $0$, since $\lim _{n \to \infty} \log \log n = \infty$. And thus

$$\lim _{n \to \infty} d(n) = O(1)$$

That seems wrong, am I making a mistake? And if so, where?

• Yes, you are making a mistake. Apr 22, 2011 at 13:35
• @user9325 You don't say :).
– AVH
Apr 22, 2011 at 13:48
• – lhf
Apr 22, 2011 at 21:45

(answering your edited question): When you have an expression $x^y$ where $y$ tends to $0$ as some parameter (say $n$) tends to infinity, you can't conclude that the expression tends to a constant. Yes, $y$ goes to $0$, but $x$ may tend to $\infty$ (as it does in your case). Who's winning? You should be able to come up with examples where the result is $0$, $\infty$ or anything in between. Give it a try.

Also, from $\limsup \frac{d(n)\log \log n}{\log n} = \log 2$ you can immediately see that there's no way $d(n)$ would be $O(1)$. Had it been, the LHS would go to $0$.

You can find the answer on wikipedia:

http://en.wikipedia.org/wiki/Arithmetic_function#Summation_functions

$$\limsup_{n\to\infty}\frac{\log d(n) \log\log n}{\log n} = \log 2$$

with a reference to the book of Hardy & Wright, §§ 18.1–18.2.

(To get an approximate idea, you can consider what happens to the product of the first $k$ primes that have sizes of about $k\log k$ each. This product has $2^k$ divisors. Of course, this is not a proof of the above result.)

• @user9325 Please see the edit to my question.
– AVH
Apr 22, 2011 at 11:38

Since $d(2^k)=k+1$, the lim sup is $\infty$.

• I might be mistaken, but for your example, isn't the complexity $O(log_2 n)$? I understand that the limit, is per definition $\infty$, I want to know the complexity of the supremum.
– AVH
Apr 22, 2011 at 10:34
• This not the sequence with the most divisors, compare $d(30)=8$ and $d(32)=6$. Apr 22, 2011 at 10:55
• Ah, do you mean the growth of $f(n) = \sup_{m\le n} d(m)$?
– lhf
Apr 22, 2011 at 11:03
• – lhf
Apr 22, 2011 at 11:11
• Yes, that's what I meant. I was, however, aware of the Wikipedia article, should have stated that, sorry. I've updated my question a bit more.
– AVH
Apr 22, 2011 at 11:43