Determine the smallest positive integer $n$ such that $n^n$ has at least one million positive divisors

Question

A problem on a national olympiad.

thanks for the replies!

Answer 1

I have never seen Olympics in my life (except on TV) so I gave up almost immediately. But I gave it a go and...

Suppose that $n$ has $k$ different prime factors:

$$n=p_1^{a_1}p_2^{a_2}\dots p_k^{a_k}$$

$$n^n=p_1^{na_1}p_2^{na_2}\dots p_k^{na_k}$$

So the number of divisors is:

$$\sigma=(1+na_1)(1+na_2)...(1+na_k)$$

Suppose that the target number $n$ has 4 distinct prime factors. The smallest such number is $n=2\times3\times5\times7=210$. The number of divisors of $n^n$ is $(1+210)^4$ which is obviously greater than $10^6$. There is no need to consider any other number $n$ with 4 or more disitnct prime factors and we already know that the solution is not greater than 210.

Ok, let us consider numbers with 3 distinct prime factors. Start with the smallest ones: 30, 42, 60, 66, 70, 78, 84... The checks are quick and simple, you won't waste too muct time (thanks $\color{red}{\text{EspeciallyLime}}$ for providing the right sequence, I have skipped a few possible values initially).

Just a few examples:

$n=2\times3\times5=30$, number of divisors is $31^3<10^6$, solution discarded.

$\dots$

$n=2^2\times3\times5=60$, number of divisors is $121\times61\times61<10^6$, solution discarded.

$\dots$

$n=2^2\times3\times7=84$, number of divisors is $169\times85\times85=1221025$, stop!

There is no need to consider any other number $n$ with three distinct prime factors because they are all bigger than 84.

Let's move to numbers with two distinct prime factors. Obviously, we'll have to check only numbers less than 84. Such numbers will have the following form:

$$n=p_1^{a_1}p_2^{a_2}$$

$$n^n=p_1^{na_1}p_2^{na_2}$$

...with the number of divisors equal to:

$$\sigma=(1+na_1)(1+na_2)>1000000\tag{1}$$

So at least one of the factors will have to be greater than $\sqrt {1000000}=1000$. But:

$$1+na_i>1000\implies a_i>{999 \over n}>{999\over 84}>11$$

But this is nonsense, because the smallest number with two prime factors and $a_i$=12 is $2^{12}\times3$ which is way above our best value so far (84).

In the same way (even easier) you can show that $n$ cannot be a power of a single prime. So achille hui was right in his comment. The answer is 84, "double the answer to life, the universe and everything".