12

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.

2 Answers2

3

For a given $n$, let $N(n)$ be the number of admissible exponent sequences, that is, the number of sequences $a_1 \geqslant a_2 \geqslant \ldots$ on nonnegative integers such that $$\frac{n}{2} < \prod_{\nu = 1}^{\infty} p_{\nu}^{a_{\nu}} \leqslant n\,. \tag{1}$$ Then indeed we have $N(n) \ll_{\epsilon} n^{\epsilon}$ for every $\epsilon > 0$ and $N(n) \gg_l \log^l n$ for every $l$.

This is easy to prove if we write the product in $(1)$ as a product of primorials. The non-increasingness of the exponent sequence makes this possible. Define $k = k(n)$ as the index such that $$p_k\# \leqslant n < p_{k+1}\#\,. \tag{2}$$ Then by the prime number theorem we have $k \sim \frac{\log n}{\log \log n}$. If $$\prod_{\nu = 1}^{k} (p_{\nu}\#)^{b_{\nu}} \leqslant n\,,$$ then a fortiori we have $$(p_{\nu}\#)^{b_{\nu}} \leqslant n \iff b_{\nu} \leqslant \frac{\log n}{\log (p_{\nu}\#)} = \frac{\log n}{\vartheta(p_{\nu})}$$ for each $\nu$. Hence $$N(n) \leqslant \prod_{\nu = 1}^{k}\biggl(1 + \biggl\lfloor \frac{\log n}{\vartheta(p_{\nu})}\biggr\rfloor\biggr) < 2^k\prod_{\nu = 1}^{k} \frac{\log n}{\vartheta (p_{\nu})}\,.$$ Now $$2^k = \exp (k\log 2) = \exp \frac{(1 + o(1))(\log 2)\log n}{\log \log n} = n^{o(1)}$$ and $$(\log n)^k = \exp (k\log \log n) = n^{1 + o(1)}$$ are straightforward. To estimate the denominator, we use \begin{align} \sum_{\nu = 1}^{k} \log \vartheta(p_{\nu}) &= \sum_{\nu = 1}^{k} \bigl(\log p_{\nu} + O(1)\bigr) \\ &= \vartheta(p_k) + O(k) \\ &= \log n + O(\log \log n) + O(k) \\ &= \log n + O\biggl(\frac{\log n}{\log \log n}\biggr) \end{align} per the Chebyshev bounds and $(2)$, thus $$\prod_{\nu = 1}^{k} \vartheta(p_{\nu}) = n^{1 + O\bigl(\frac{1}{\log \log n}\bigr)}\,.$$ Putting everything together gives $N(n) = n^{o(1)}$, whence $N(n) \ll_{\epsilon} n^{\epsilon}$ for all $\epsilon > 0$.

For the lower bound, fix an arbitrary $l > 0$ and assume $n$ is so large that $k > l+1$. Then we count the products $$\prod_{\nu = 2}^{l+1} (p_{\nu}\#)^{b_{\nu}} \leqslant n\,.\tag{3}$$ For every such product there is a unique $b_1$ such that $$\frac{n}{2} < \prod_{\nu = 1}^{l+1} (p_{\nu}\#)^{b_{\nu}} \leqslant n\,,$$ hence the number of products $(3)$ is a lower bound for $N(n)$. These products correspond to the lattice points in the simplex $S \subset \mathbb{R}^l$ with vertices $0$ and $$\frac{\log n}{\vartheta(p_{\nu})}\cdot e_{\nu-1},\qquad 2 \leqslant \nu \leqslant l+1,$$ whose ($l$-dimensional) volume is $$\frac{1}{l!}\prod_{\nu = 2}^{l+1} \frac{\log n}{\vartheta(p_{\nu})} = C_l \cdot \log^l n\,.$$ As $n \to \infty$ the number of lattice points in $S$ is asymptotically equal to the volume of $S$, hence $N(n) \gg_l \log^l n$ for every $l$.

Daniel Fischer
  • 206,697
-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.

Moti
  • 1,928
  • "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 '15 at 06:35