# Find maximum divisors of a number in range

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,

-
I don't think you are correct that you need all the $a_i$ to be equal. For example, if $n=10$, the maximum number of divisors is $4$, and it is achieved both at $6$ and at $8$ ($6$ since $6=2\times 3$, so the number of divisors is $(1+1)(1+1) = 4$; and $8$ because $8=2^3$, so the number of divisors is $3+1=4$). For $n=19$, the maximum is $6$, which occurs at $12$ and at $18$, neither of which has $a_i=a_j$ for $1\leq i,j\leq k$. –  Arturo Magidin Mar 11 '11 at 18:02
@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. –  Chan Mar 11 '11 at 18:20

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.

-
@Ross Millikan: Thank you. Could you show me how to derive the increasing formula in term of $\log{n}$? –  Chan Mar 11 '11 at 22:54
For example, 12=2^2*3 has 6 divisors. To make more divisors, we could multiply by 2,3, or 5. This will take us to 24, with 8 divisors, 36 with 9, or 60 with 12. So the increase in $\ln(d(n))/\ln(n)$ for going to 24 is $\frac{\ln4-\ln3}{\ln2}=.41$. For going to 36 it is $\frac{\ln3-\ln2}{\ln3}=.369$ So we get a better return by going to 24. But for going to 5 it is $\frac{\ln2-\ln1}{\ln5}=.43$, even better. To derive the formula, just take the ln of the number of divisors and the number itself. My formula just looks at the prime factorization. –  Ross Millikan Mar 11 '11 at 23:09
It is slightly more than the references: it is the b-file. The largest number in the list less than $2^{64}$ is 18401055938125660800 i.e. $2^7 3^4 5^2 7^2 11 \,13\,17\,19\,29\,31\,37\,41$ with a total of 184320 factors/divisors. –  Henry Mar 12 '11 at 2:26
The reference A. Flammenkamp, List of the first 1200 highly composite numbers goes up to 10^88 with 4.45E15 divisors –  Ross Millikan Mar 12 '11 at 2:48
@Ross Millikan: Thank you. I got it now ;). –  Chan Mar 12 '11 at 5:56

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.

-
I haven't learned Langrange multiplier yet, but thanks anyway. –  Chan Mar 11 '11 at 18:54
@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. –  Mark Eichenlaub Mar 11 '11 at 19:10

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 $<n$.

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.

-
Thank you very much. The answer was actually much more than I expected. By the way, what's PARI-GP version? Could you briefly explain it? I looked at your implementation, and I really did not know it was also in TopCoder. I visit TopCoder sometimes, and love the algorithm arena. Very nice to meet you Esteban. –  Chan Mar 11 '11 at 22:52
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. –  Esteban Crespi Mar 11 '11 at 23:46