Monday, December 25, 2006

1000! revisited

It's been a few days since I posed the 1000! question and while cjg posted the correct answer he used a brute force approach. Here is a more formal solution:

The only way to get a zero at the end of a number is by multiplying by 10. The prime factorization of 10 is 5*2. The prime factorization of 1000! will contain 2m and 5n. So the number of 0s at the end of 1000! will be the minimum of m and n.

1000! contains a factor of every number from 1 to 1000, so we start by counting how many of those numbers contain a factor of 5.

  • Every 5th number is a multiple of 5.
  • Every 25th number is a multiple of 25 - which has an additional factor of 5.
  • Every 125th number is a multiple of 125 - which has yet another factor of 5.
  • And 625 has another factor of 5.
So, we get 1000! has 200+40+8+1 = 249 factors of 5.

We know every other number has a factor of 2, so 1000! trivially has at least 500 factors of 2. since 500>249, the number of zeros at the end of 1000! is 249.

Now, through all of this we assumed I was asking base 10. If, for interests sake I really meant everything in base 2, the answer would be derived identically:

In base 2, a zero at the end occurs for each factor of 10 (2 base 10). 1000 base 2 is 8 base 10.
  • Every 2nd number has a factor of 2.
  • Every 4th number has an additional factor of 2
  • Every 8th number has yet another factor of 2.
So we see that 1000! (base 2) has 4+2+1 = 7 zeros at the end.

1 comment:

cjg said...

If only I had been more coherent... I was grasping at prime factorizations. Instinctively, I used the prime factors of 10 as the basis, but I didn't make the jump. Instinct, of course, is something that was trained by U(W). Ah well - excellent explanation.