#55
For how many positive integers k does the ordinary decimal representation of the integer k! end in exactly 99 zeros?
a. None
b. One
c. Four
d. Five
e. Twenty four
The answer is d.
I know, from previous incomplete discussion, that it has something to do with the prime factorization of 2s and 5s. But the answer was incomplete.
Can anyone explain to me?
Thanks
0568: #55

 Posts: 61
 Joined: Sun Apr 04, 2010 1:08 pm
Re: 0568: #55
I'll help you out again... The number of zeroes in a number is how many factors of 10 you can pull out, and this is the same as min{powers of 2, powers of 5}. When you're talking about k!, it's pretty clear that factors of 2 grow much faster (you get 2^2 from 4, 2^3 from 8, and 2 from every even number less than k). Therefore, in k!'s prime factorization, the power of 5 is the number of zeroes by this logic.
From here, it's not too hard to see that, if k is a factor of 5, then the number of zeros in k! is the same number of zeros as (k+1)!, (k+2)!, (k+3)!, and (k+4)!. When you get to (k+5)!, the number of zeros jump, usually by 1, but as the number grow larger, this jump can be bigger.
To illustrate, 20! has 4 zeros, and so does 21!, 22!, 23! and 24! because you aren't tacking on any more factors of 5. When you get to 25!, you actually get 6 zeros.
From this logic, the answer is either 5 or none (none being the case that 99 is jumped over)
I don't know of a slick way to figure out if 99 is hit, but it doesn't take long to see the patten. The number of possible zeros is:
0 1 2 3 4
6 7 8 9 10
12 13 14 15 16
18 19 20 21 22
24 25 26 27 28
31 32 33 34 35
37 38 39 40 41
43 44 45 46 47
49 50 51 52 53
55 56 57 58 59
62 63 64 65 66
68 69 70 71 72
74 75 76 77 78
80 81 82 83 84
86 87 88 89 90
93 94 95 96 97
99 100...
There's probably a more elegant way to do the second part, but I'm too lazy to think about it. I'm sure somebody else has a good method
From here, it's not too hard to see that, if k is a factor of 5, then the number of zeros in k! is the same number of zeros as (k+1)!, (k+2)!, (k+3)!, and (k+4)!. When you get to (k+5)!, the number of zeros jump, usually by 1, but as the number grow larger, this jump can be bigger.
To illustrate, 20! has 4 zeros, and so does 21!, 22!, 23! and 24! because you aren't tacking on any more factors of 5. When you get to 25!, you actually get 6 zeros.
From this logic, the answer is either 5 or none (none being the case that 99 is jumped over)
I don't know of a slick way to figure out if 99 is hit, but it doesn't take long to see the patten. The number of possible zeros is:
0 1 2 3 4
6 7 8 9 10
12 13 14 15 16
18 19 20 21 22
24 25 26 27 28
31 32 33 34 35
37 38 39 40 41
43 44 45 46 47
49 50 51 52 53
55 56 57 58 59
62 63 64 65 66
68 69 70 71 72
74 75 76 77 78
80 81 82 83 84
86 87 88 89 90
93 94 95 96 97
99 100...
There's probably a more elegant way to do the second part, but I'm too lazy to think about it. I'm sure somebody else has a good method
Re: 0568: #55
If you pick a number that is not too big, say 50, then you can try to find the factorial decomposition of 50!
A prime number like 31 will not show up again. The next multiple of 31 is 62, bigger than 50. Same for any prime between 25 and 50. So, all these will be in the factorial decomposition of 50! only once.
What about prime numbers that are less than 25? Let's pick the ones that are between 25 and 50/3 (17 would be the last one). They will show up only twice.
13 will have a power of 3, 11 will be to the 4th power, and finally only 1 digit prime remain.
The power of 7 will be 8 since 7x7 = 49. So, we have 7 multiples of 7, but the last once contributes with 2 sevens. From now on we have to pay lots of attention.
Now, 50 will contribute will more than 10 fives. 5x5 and 5x10 mean 2 extra fives.
As we go down, things gets trickier. Let's check the prime number 3.
17x3 >50. How many extra threes in these 16 mutiples?
3x3, 3x6, 3x9, 3x12 and 3x15. Since 9 brings 2 threes, it's a total of 6. Every 3 mutiples of 3 we get a new power of 3. And 16+6 =22.
An easier way is to pcik 50 and divide it by 3, quotient 16, remainder 2. Let's dismiss all the remainders.
50 divided by 3 is 16
16 divided by 3 is 5
5 divided by 3 is 1
16 + 5 + 1 = 22 threes, as we just calculated.
Let's finish this with the prime numbers. Only the 2 is missing.
50 divided by 2 is 25
25 divided by 2 is 12 (Dismiss remainders)
12 divided by 2 i 6
6 divided by 2 is 3
And 3 divided by 2 is 1
A total of 25+12+6+3+1 = 47 twos, which proves that in fact there are more twos than fives.
As you can see, a complete factorial decomposition of 50! takes less time than it apppears.
About the question 5 or 0 that have 99 zeros:
We need 99 zeros. So, the number will be less than 500. In 500 there will be about 100 extra fives. So, let's try 400! And see what happens.
400 divided by 5 is 80
80 divided by 5 is 16
16 divided by 5 is 3
So, 80+16+3 is exactly 99 zeros. So, now we know for sure that 400!, 401!, 402!, 403! And 404! Have 99 zeros and that the answer is 5 and not 0 numbers.
A prime number like 31 will not show up again. The next multiple of 31 is 62, bigger than 50. Same for any prime between 25 and 50. So, all these will be in the factorial decomposition of 50! only once.
What about prime numbers that are less than 25? Let's pick the ones that are between 25 and 50/3 (17 would be the last one). They will show up only twice.
13 will have a power of 3, 11 will be to the 4th power, and finally only 1 digit prime remain.
The power of 7 will be 8 since 7x7 = 49. So, we have 7 multiples of 7, but the last once contributes with 2 sevens. From now on we have to pay lots of attention.
Now, 50 will contribute will more than 10 fives. 5x5 and 5x10 mean 2 extra fives.
As we go down, things gets trickier. Let's check the prime number 3.
17x3 >50. How many extra threes in these 16 mutiples?
3x3, 3x6, 3x9, 3x12 and 3x15. Since 9 brings 2 threes, it's a total of 6. Every 3 mutiples of 3 we get a new power of 3. And 16+6 =22.
An easier way is to pcik 50 and divide it by 3, quotient 16, remainder 2. Let's dismiss all the remainders.
50 divided by 3 is 16
16 divided by 3 is 5
5 divided by 3 is 1
16 + 5 + 1 = 22 threes, as we just calculated.
Let's finish this with the prime numbers. Only the 2 is missing.
50 divided by 2 is 25
25 divided by 2 is 12 (Dismiss remainders)
12 divided by 2 i 6
6 divided by 2 is 3
And 3 divided by 2 is 1
A total of 25+12+6+3+1 = 47 twos, which proves that in fact there are more twos than fives.
As you can see, a complete factorial decomposition of 50! takes less time than it apppears.
About the question 5 or 0 that have 99 zeros:
We need 99 zeros. So, the number will be less than 500. In 500 there will be about 100 extra fives. So, let's try 400! And see what happens.
400 divided by 5 is 80
80 divided by 5 is 16
16 divided by 5 is 3
So, 80+16+3 is exactly 99 zeros. So, now we know for sure that 400!, 401!, 402!, 403! And 404! Have 99 zeros and that the answer is 5 and not 0 numbers.