### 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 2^{m} and 5^{n}. 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 5
^{th}number is a multiple of 5. - Every 25
^{th}number is a multiple of 25 - which has an additional factor of 5. - Every 125
^{th}number is a multiple of 125 - which has yet another factor of 5. - And 625 has another factor 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 2
^{nd}number has a factor of 2. - Every 4
^{th}number has an additional factor of 2 - Every 8
^{th}number has yet another factor of 2.

## 1 comment:

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.

Post a Comment