smallest child number

Question

Problem :

Let 'Child number' of positive integer $n$ be a positive integer that is divisible at least half of the factors of $n$.

Find smallest 'Child number' of $21600$.

---

My Attempt

Since $$21600 = 2^5 \times 3^3 \times 5^2 $$ we know that $21600$ has $6\times 4\times 3 = 72$ distinct divisors.

Let we call divisors $d_1, d_2, \cdots d_{72}\quad (d_1 < d_2 < \cdots < d_{72}).$

And, 'Child number' must be divisible at least half of them.

Since 'Child number' has $36$ of them, the original problem changes to "Find minimum product of $36$ divisors."

But the problem is I can not sure that the answer is $d_1 \times d_2 \times \cdots \times d_{36}$.

Because there is a divisor which is factorized to two divisors.

For example, $d_{10} = 12$. and we can write this $d_{10} = d_2 \times d_5$ because $d_2 = 2, d_5 = 5$.

I can not sure that should I remove cases like above, if I must how can I?

Thanks for your help.

Answer 1

I believe the answer here is $1800$. You've given us that $21600 = 2^5 \times 3^3 \times 5^2$ has $6\times 4\times 3 = 72$ distinct divisors. To find the smallest child number, we want to divide by the largest primes possible that still give at least $36$ distinct factors.

In the comments, lulu provided that $2160 = 2^4 \times 3^3 \times 5$ has $40$ factors as a starting point, but we can go one step further: $1800 = 2^3 \times 3^2 \times 5^2$ has $36$ factors, and we've divided by $12$ rather than $10$. I looked to remove as many factors as possible to get a clean $d(n)/2$ factors. I'm not sure there's a good algorithm for doing this, as the choices will vary based on the factors. Hence, there's likely no closed form for doing this for other values of $n$, though except for highly composite numbers it's likely doable by hand so long as you have a factorization handy.

Answer 2

The lowest common multiple of the lower half of a list of factors sorted by size is not guaranteed to give the answer you're looking for. Consider rather than finding the smallest child number of $21600$, you're trying to find the smallest child number of $1798=2\times29\times31$. This number has $8$ factors. The $4$ smallest are $1,2,29,$ and $31$, the lcm of which would be the original number, yet the smallest child number would be $58$.

All factors of $21600$ are of the form $2^a3^b5^c$ where $a\le5,b\le3,c\le2$ and the smallest child number must be of this form as well. Any number not of this form is greater than the greatest common factor of itself and $21600$, yet contains no extra factors of $21600$.

Using calculus (finding the minimum of $2^a3^b5^c$ given $(a+1)(b+1)(c+1)=36$) isn't likely to lead to valid integer solutions, so I'll refer back to my previous comment. Try to find the smallest value of $2^a3^b5^c$ such that $(a+1)(b+1)(c+1)\ge36$. $c$ cannot be $0$. Let's illustrate with the case $c=2$. Then $(a+1)(b+1)\ge12$. $b$ can be $1,2,$ or $3$ here as again $0$ is too small. For the different values of $b$, the values of $(a,b,c)$ to check here are $(5,1,2),(3,2,2),$ and $(2,3,2)$. So the values of $2^a3^b$ are $96,72,$ or $108$. Our first candidate is $72\times25=1800$.

Now check the possibilility that $c=1$.

Answer 3

I'm very sorry, but I believe that there is only one way to solve this question, and it's using a computer:

As you mention, $21600 = 2^5 \times 3^3 \times 5^2$

You write the following algorithm (pseudo-code):

List<int> l = new List<int>();
for (int a = 0 to 5)
  for (int b = 0 to 3)
    for (int c = 0 to 2)
      if (a+1)*(b+1)*(c+1) >= 36 // half of 72
      then l.Add(2^a*3^b*5^c);
    next
  next
next

l.Sort();
if (l.Count>=1)
then write("The solution is " + IntToStr(l[1]));
           // or l[0], most computer lists start counting at zero.

I can imagine that a lot of mathematical enthousiasts will freak out now, seeing a brute force computer "program" for a mathematical question, but I fear that the solution of this question is too difficult to solve without such an approach. (In case you don't believe me, try to change the values of the prime factors and you'll see that the smallest child number will be formed out of other exponents)