# perfect factors from the prime factorization of a large number

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.

• 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? Commented Sep 13, 2020 at 19:35
• @JMoravitz, This isn't my writing, it's my teacher. I'm assuming it means perfect numbers, but I'm not 100% sure
– user807252
Commented Sep 13, 2020 at 19:42
• Yea, it doesn't make sense either way. I'll ask my teacher for more clarification.
– user807252
Commented Sep 13, 2020 at 19:45
• 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. Commented Sep 13, 2020 at 19:47

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.