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
3  
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

1 Answer 1

As the question is posed, it is the largest m that 2^m is smaller than n. m is the answer. In the discussion of the question, there is no mention the devisors are different from one another. If there is such requirement than the solution is the largest 2*3*5*7... all primes that maintain a value less than n.

share|improve this answer
    
"number of divisors" means "number of distinct divisors" ---- what sense would it make to say a number has 17 divisors, only 11 of which are distinct? And $2\times3\times5\times7=210$ has 16 divisors, but the smaller number $2^3\times3\times5$ also has 16 divisors, and $2^2\times3^2\times5=180$ has 18 divisors. –  Gerry Myerson Feb 16 at 6:35

Your Answer

 
discard

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.