# Find the smallest integer that is divisible by exactly $X$ perfect squares.

Is there a method to find the smallest integer divisible by exactly $X$ perfect squares? Example: find the smallest positive integer divisible by exactly 2015 perfect squares.

• see if you can do it for 1 or 2 or 3 squares first – Will Jagy May 9 '15 at 2:25
• Also do you know how to count how many factors a number has? – jgon May 9 '15 at 2:26
• Find the smallest number $N$ which is divisible by exactly $X$ natural numbers, and then $N^2$ is the smallest divisible by exactly $X$ perfect squares. – Thomas Andrews May 9 '15 at 2:36
• 2015 is the current year, which suggests that the problem might be from an ongoing competition.Where did you find it? – Henning Makholm May 9 '15 at 2:49

First of all, there won't be a simple formula.

If $X$ is prime, the smallest number is $2^{2X-2}$. So the smallest number divisible by example five perfect squares is $2^{8}=256$.

More generally, it will depend on factorizations of $X$.

In general, if $N$ is the smallest integer with exactly $X$ positive integer divisors, then $N^2$ will be the smallest integer with exactly $X$ perfect square divisors.

The number of divisors of $N$ is in terms of the prime factorization of $N$. So if $$N=p_1^{a_1}p_2^{a_2}\cdots p_n^{a_n}$$ then the number of divisors is:

$$\tau(N) = (a_1+1)(a_2+1)\cdots(a_n+1)$$

So lets try the example $X=15$. Then either $N=p_1^{14}$ or $N=p_1^{4}p_2^{2}$. In this case $2^43^2=144$ is the smallest number with exactly $15$ divisors, o $144^2$ is the smallest with number with exactly $15$ perfect square divisors.

It gets harder with even more facts. Try $X=12$. Then there are many different ways to factor \begin{align}X&=24\\&=12\cdot 2 \\&=8\cdot 3 \\&=6\cdot 4 \\&=6\cdot 2\cdot 2 \\&=4\cdot 3\cdot 2 \\&= 3\cdot 2\cdot 2\cdot 2\end{align}

Which yields prospects:

$$N=2^{23},2^{11}3^1, 2^{7}3^2, 2^{5}3^{3}, 2^{5}3^15^1, 2^33^25^1, 2^23^15^17^1$$

Here, the best value is $2^33^25^1=360$, and $N^2=360^2$ is your answer.