Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

As mentioned in an answer to this question an integer less than $n$ with largest number of divisors can be found exploring the numbers $x$ of the form $$ x = 2^{a_1} 3^{a_2} \dots p_k^{a_k} \dots $$ (where $p_k$ is the $k$-th prime number) with the conditions $$ x \le n < 2x \quad \text{and}\quad a_1 \ge a_2 \ge \dots \ge a_k \ge \dots$$ to determine the complexity of this algorithm I would like to know the asymptotic number of tuples $(a_1, a_2, \dots)$ verifying these conditions as $n\to \infty$. I suspect that this number is $\gg_l \log^l n$ for every $l$ and $\ll_\epsilon n^\epsilon$ for every $\epsilon > 0$, but I don't know how to prove it.

Thanks for your help.

share|improve this question
oeis.org/A002182 might have information. –  Qiaochu Yuan Jun 19 '11 at 22:51
Can you explain further what you mean by " $\gg \log^k n$ for every $k$"? If this means $(\log n)^k$, is there some upper limit on $k$, perhaps based on primorial numbers? –  Henry Jun 19 '11 at 23:33
@Henry: I don't understand what you are asking. Although I will guess that the problem is that the OP should not use the same $k$ to denote both the $k^{th}$ prime and the growth condition concerning $\log n$. Specifically, the last line should read "I suspect that this number is $\gg_l \log^l n$ for every $l$, and $\dots$" –  Eric Naslund Jun 20 '11 at 2:39

Your Answer


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

Browse other questions tagged or ask your own question.