Wild About Math!Making Math fun and accessible

21Dec/082

MMM #21: We have a winner!

MMM #21 was easier than I thought as most of the submitters got the right answer. Random.org picked Khey Jenq Lim as winner. Congratulations, Khey! I'll be contacting you to get you your prize.

Everyone solved the problem the same way, as a combinatorics problem involving the prime factors of 10! Jay Hutfles had a very nice explanation of how to solve the problem:

In the Monday Math Madness problem, we're asked how many factors the number 10! has. Starting from the example, it is given that 10 has four divisors (1, 2, 5 and 10). Since division is the inverse operation of multiplication, maybe it'd be easier to count the factors of 10 if we wrote it as a multiplication problem. That's exactly what the prime factorization of a number gives us. Doing so tells us that

10 = 2^1 * 5^1, or "two to the first power multiplied by five to the first power"

If we also factor the 4 natural numbers known to be factors of 10, we can see a clear pattern:

10 = 2^1 * 5^1
5 = 2^0 * 5^1
2 = 2^1 * 5^0
1 = 2^0 * 5^0

So a factor of 10 can itself have factors of 2^0, 2^1, 5^0 or 5^1. Since 2 has two possible exponents, as does 5, there are 2*2=4 possible factors of 10.

Let's try this with another example. How many natural numbers divide into 72?

Determining that the prime factorization of 72 is 2^3 * 3^2, a factor of 72 will have either 0, 1, 2 or 3 powers of 2, and will also have either 0, 1 or 2 powers of 3. So there are 4*3 = 12 factors of 72.

We can now examine the larger problem of 10!. Since 10! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10, its prime factorization is

10! = (1) * (2^1) * (3^1) * (2^2) * (5^1) * (2^1 * 3^1) * (7^1) * (2^3) * (3^2) * (2^1 * 5^1)
10! = 2^8 * 3^4 * 5^2 * 7^1

There are 9 choices for a power of 2, 5 choices for powers of 3, 3 choices for powers of 5 and two choices for powers of 7. In other words, there are

9 * 5 * 3 * 2 = 270

possible factors of 10!.

1. Yes! Also, prime factorization of a factorial is easier than of a number in general.

For example, let’s look at 1000 factorial and ask what the exponent for a particular prime factor is… say 17:

We know 1000 factorial is the product of ALL numbers between 1 and 1000. Of those, only
floor(1000/17)=58 are divisible by 17. (They are: 17, 34, … 969, 986). If we divide all of these by 17, (so: 1, 2 … 57, 58), now we
still have floor(58/17)=floor(1000/(17^2))=3 multiples of 17 left: (17, 34, 51). If we divide all *these* by 17 (so: 1,2,3), there are no more factors of 17. Thus there are 58+3+0=61 powers of 17 in 1000 factorial.

In general, in the prime factorization of N factorial, the exponent for prime p is equal to

floor(N/p)+floor(N/p^2)+floor(N/p^3)+…

which is not really reducible to anything simpler, but is fairly easy to calculate (on the order of log N for each prime, and there
are about log N primes, so roughly O[(log N)^2].)

Matlab script:

function alpha = factorfactorial(n);
clear alpha;
ps = primes(n);
for i=1:length(ps),
p = ps(i);
k = 1:(ceil(log(n)./log(p)));
alpha(i) = sum(floor(n.*p.^-k));
end

For large N, this turns out to be quite a bit faster than prime-factoring each number less than N separately… something between O[N log N] and O[N^2].

..

And then to get the number of factors, you add one to all the entries in that alpha vector and multiply:

prod(factorfactorial(n)+1)

For 1000, this returns something like 3×10^107

(29,999,835,807,159,345,371,240,484,098,931,829,728,259,413,697,143,443,122,742,335,764,172,165,451,110,353,469,440,000,000,000,000,000,000,000)

Wheeeee!

2. Nice! Yes, there is much efficiency that one can gain in factoring a factorial.