1
$\begingroup$

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.

I've been trying to figure this out, but I haven't made much progress... Please help!

$\endgroup$
  • $\begingroup$ see if you can do it for 1 or 2 or 3 squares first $\endgroup$ – Will Jagy May 9 '15 at 2:25
  • $\begingroup$ Also do you know how to count how many factors a number has? $\endgroup$ – jgon May 9 '15 at 2:26
  • 1
    $\begingroup$ 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. $\endgroup$ – Thomas Andrews May 9 '15 at 2:36
  • 1
    $\begingroup$ 2015 is the current year, which suggests that the problem might be from an ongoing competition.Where did you find it? $\endgroup$ – Henning Makholm May 9 '15 at 2:49
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.