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,

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.

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.

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.