1
$\begingroup$

This is probably an easy question, but I don't know how to do it: In the prime factorization of $30!$, how many perfect factors occur?

This is from a timed competition, any answers that take more than 3 minutes are not great.

Do I prime factorize every number from $1$ to $30$? That would be extremely slow.

I would like a hint in the right direction.

$\endgroup$
4
  • 2
    $\begingroup$ To be clear, what do you mean by "perfect factor"? A factor who is itself a perfect number such as $6,28,496,\dots$? A factor who is itself a perfect power such as $4,9,16,25,32,\dots$? Or do you mean to just ask about proper factors? $\endgroup$
    – JMoravitz
    Commented Sep 13, 2020 at 19:35
  • $\begingroup$ @JMoravitz, This isn't my writing, it's my teacher. I'm assuming it means perfect numbers, but I'm not 100% sure $\endgroup$
    – user807252
    Commented Sep 13, 2020 at 19:42
  • $\begingroup$ Yea, it doesn't make sense either way. I'll ask my teacher for more clarification. $\endgroup$
    – user807252
    Commented Sep 13, 2020 at 19:45
  • 1
    $\begingroup$ Uh..... that seems incredibly unlikely to be talking about perfect numbers... if so, then I suppose if you have a prime checker or a list of primes, then you can just ask how many mersenne primes there are less than or equal to $n$ if you are asking how many perfect numbers are factors of $n!$ noting that for prime $q = 2^p-1$ you definitely have $(q+1)/2$ is a smaller integer than $q$, but the full list of mersenne primes are incomplete and there are some numbers of the form $2^p-1$ who are not prime. It is also still an open problem to prove that no odd perfect numbers exist. $\endgroup$
    – JMoravitz
    Commented Sep 13, 2020 at 19:47

1 Answer 1

Reset to default
0
$\begingroup$

Assuming the problem is talking about perfect numbers (although then it's unclear what "in the prime factorization" means) you only need to consider $6$ and $28$. All higher even perfect numbers have the form $2^{p-1} (2^p - 1)$ where $2^p - 1$ is a Mersenne prime and the next Mersenne prime is $3^5 - 1 = 31$ which doesn't divide $30!$. And since $6, 28 \le 30$ it's clear that they both divide. So the answer is $\boxed{2}$.

The question is a little ambiguous even beyond the perfect issue; if $k$ isn't prime it's unclear how to interpret the question of "how many times" $k$ occurs as a factor in another number.

If "perfect" means something else, the prime factorization of $n!$ is given by Legendre's formula

$$\nu_p(n!) = \sum_{k \ge 1} \left\lfloor \frac{n}{p^k} \right\rfloor$$

for the greatest power of $p$ dividing $n!$, and it would be just about doable to compute this by hand for $n = 30$ and all primes $\le 30$. From here you can answer whatever questions you want about the factors.

Among other things you can compute that

$$\nu_2(30!) = 15 + 7 + 3 + 1 = 26$$ $$\nu_3(30!) = 10 + 3 + 1 = 14$$ $$\nu_7(30!) = 4$$

which gives that the greatest powers $k$ such that $6^k$ or $28^k$ divide $30!$ are $14$ and $4$ respectively. I don't know if that's what's intended.

Overall it's not the best-written question and should have been test-solved.

$\endgroup$

You must log in to answer this question.