12
$\begingroup$

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.

  • 3
    http://oeis.org/A002182 might have information.2011-06-19

2 Answers 2

-2

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.

  • 0
    "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.2015-02-16