9
$\begingroup$

While playing around with programming, a problem suddenly came across my mind.

Given $n$ let's say $2^{64}$ (64-bit unsigned integer). Find a positive integer $x$, $1 \leq x \leq n$, such that $x$ has maximum divisors.

My attempt was:
Let $n = p_1^{a_1} \times p_2^{a_2} \times ... \times p_k^{a_k}.$
The number of divisors is given by: $(a_1 + 1) \times (a_2 + 1) \times ... \times (a_k + 1)$

We need to find the maximum of these products. Since $(a_1 + 1)_{max} \implies {a_1}_{max}$, the product becomes: $a_1 \times a_2 \times .... \times a_k$
Let $P = a_1 \times a_2 \times .... \times a_k$.
The maximum of $P$ means $a_i = a_j$ where $1 \leq i, j \leq k$.

So I guess my question is how can we find a number that is less than $n$ which has this property?

Thanks,

  • 0
    @Arturo Magidin: Thanks for pointing that out. The reason that I came up with that idea is because if given two numbers less than n. Their sum is unchanged, their product will be maximum when they're equal.2011-03-11

3 Answers 3

7

Sequence A002182 gives the highly composite numbers, where the number of divisors sets a record.

You want the largest under $2^{64}$. Unfortunately the table doesn't go that high, but the references do. Somewhat in the spirit of Mark Eicenlaub's answer, if you think of $n = p_1^{a_1} \times p_2^{a_2} \times ... \times p_k^{a_k} \text{ and } d(n)=(a_1 + 1) \times (a_2 + 1) \times ... \times (a_k + 1)$ and think of adding one to the exponent of $p_i$, $\log (n)$ increases by $\log (p_i)$ and $\log (d(n))$ increases by $\log(a_i+2)-\log(a_i+1)$.

So the figure of merit for an increase is $\frac{\log(a_i+2)-\log(a_i+1)}{\log (p_i)}$ and you can just look through the primes to find which you should add in. This will miss some, where taking out one and adding another gets you a step up.

  • 0
    @Ross Milikan: In $f$act, I thought o$f$ greedy algorithm initially with several constrains base on the maximum power o$f$ each prime factor. The thing that I was confused about Esteban Crespi's approach was why he choose 47 at his maximum prime.2011-03-12
5

I don't know the exact answer to the question, but here is a way to get an approximate solution.

We are maximizing $a_1a_2a_3\ldots$ subject to a constraint $p_1^{a_1}p_2^{a_2}p_3^{a_3}\ldots \leq n$. Let's treat the $a_i$ as continuous variables that we can differentiate. In that case we might as well set the constraint $=n$ rather than $\leq n$.

Take logarithms of both products. Now we are maximizing $\ln a_1 + \ln a_2 + \ln a_3 \ldots$ subject to $a_1 \ln p_1 + a_2 \ln p_2 + a_3 \ln p_3 \ldots = \ln n$.

Introduce a Langrange multiplier and set the gradients of the two sums to be proportional to each other.

$ \frac{1}{a_1} \hat{a_1} + \frac{1}{a_2} \hat{a_2} + \frac{1}{a_3} \hat{a_3 }+ \ldots = \lambda (\ln p_1 \hat{a_1} + \ln p_2 \hat{a_2} + \ln p_3 \hat{a_3} + \ldots) $

Dotting both sides with $\hat{a_i}$ gives

$\frac{1}{a_i} = \lambda \ln p_i$

or

$a_i = \frac{1}{\lambda \ln p_i}$

$\lambda$ is then chosen to satisfy the original constraint.

This should specify the maximum $a_i$ treating $a_i$ as continuous. To get the $a_i$ to be integers you would round some up and some down. Since you're writing code, you could simply brute-force search this much smaller space of possible integer solutions.

  • 0
    @Chan Think of the constraint as a surface in some high-dimensional space. You want to find the spot on the surface where some function is maximized. Then the directional derivative of the function along the surface must be zero in all directions of the surface. The directional derivative is the dot product of the gradient with the tangent to the surface, so the gradient of the function must be normal to the surface. The gradient of the constraint function is also normal to the surface, so these two gradients must differ by only a constant multiplier, called the Lagrange multiplier.2011-03-11
5

This answer might be useful if you are loking for an actual algorithm to solve the problem (and not a thoretical approach). If $x$ is an integer in the range $[1,n]$ with maximum number of divisors write $ x = q_1^{a_1} q_2^{a_2} \dots q_k^{a_k} $ with the $q_i$ distinct primes and $ a_1 \ge a_2 \ge \cdots \ge a_k. \quad(*)$

Then we see that the integer x' = 2^{a_1} 3^{a_2} \dots p_k^{a_k} \quad (**) has the same number of divisors and is $\le x$. So we can limit our search to the integers of the form $(**)$ which verify $(*)$. This makes the search really easy, and fast in small ranges: start with $(a_1,\dots,a_k) = (t,0,\dots,0)$ and $k$ such that $2\cdot3\cdot\dots\cdot p_{k+1} > n$, and $2^t \le n < 2^{t+1}$ and go through all the $k$-tuples verifying $(*)$ and $(**)$ in decreasing lexicographic order, keeping their product maximal and $.

You can find a C++ program that performs this task in this thread at TopCoder, though you need to adapt it to arrive up to $2^{64}$, since it is limited to $n\le 2^{64}/47$.

EDIT: I have written a PARI-GP version which can arrive much further, for $n=2^{64}$ the probably non-unique integer with maximum number of divisors is: $ 18401055938125660800 = 2^7\cdot 3^4\cdot 5^2\cdot 7^2\cdot 11 \cdot 13 \cdot 17 \cdot 19 \cdot 23 \cdot 29 \cdot 31 \cdot 37 \cdot 41 $ with 184320 divisors.

  • 0
    PARI-GP is a great program to perform number theoretic calculations. The algorithm I've used is the same I have described, but PARI-GP knows how to handle big numbers and that makes everything easier.2011-03-11