Answer to question #19

How many consecutive zeros are there at the end of 100! (100 factorial). How would your solution change if there problem were in base 5? How about in Binary???

This is a little tricky, some thinking outside the box needed here...

(The base 5 problem is actually a fair bit easier than the base 10 problem, but for the sake of convention we'll look at the base 10 before the base 5.)

First lets make sure we know what is meant by 100!, 100! = (100 x 99 x 98 x 97 x.... ....x 3 x 2 x 1)

One solution would be to work this out and count the zeros, well I've done this so you don't have to. The answer is...

9332621544394415268169923885626670049071596826438162146859 29638952175999932299156089414639761565182862536979208272237582511852109168 64000000000000000000000000

Well now you can clearly just count the zeros but actually working out the number is not practical so we need another plan.

The clever bit here is thinking what numbers when multiplied together will end in a zero, if asked you how many zeros were on the end of 3 x 3 x 3 x 3 x 3 x 1,000,000 you wouldn't need to do the sum to know the answer is 6.

So the product of what numbers when multiplied ends in a zero:

1. When one of the things being multiplied ends in zero itself
2. A number ending in 5 multiplied by an even number
3. 25, 50 and 75 when multiplied by some of the small numbers available eg (4, 2 and 6)generate an extra zero

Below is tabulated the origin of all the zeros:

Number	Zeros	Number	Zeros
100	2	95	1
90	1	85	1
80	1	75	2
70	1	65	1
60	1	55	1
50	2	45	1
40	1	35	1
30	1	25	2
20	1	15	1
10	1	5	1
Total	12	Total	12

So that's it then there are 24 zeros on the end of 100!

---

Now the base 5 problem...

We will employ a technique similar to that we used in base 10, but first lets make sure we know what we mean by base five.

Base five is a counting system where rather than there being 10 available digits (0 - 9) there are 5 (0 - 4) hence the digits of a base 5 number represent from the right, 1's, 5's, 25's, 125's etc. rather than 1's, 10's, 100's, 1000's etc.

So the first few numbers in base 5 are 1, 2, 3, 4, 10, 11, 12, 13, 14, 20, 21... ...43, 44, 100, 101, 102...

Again we have to look at the sources of the zeros, only this time it's much easier. Since 5 is a prime number then there is no way of making a zero other than by multiplying by a number that ends in a zero when written in base 5. You could write down all the numbers and count the zeros. See the table below.

Number Base 10	Number Base 5	Zeros	Number Base 10	Number Base 5	Zeros
100	400	2	95	340	1
90	330	1	85	320	1
80	310	1	75	300	2
70	240	1	65	230	1
60	220	1	55	210	1
50	200	2	45	140	1
40	130	1	35	120	1
30	110	1	25	100	2
20	40	1	15	30	1
10	20	1	5	10	1
	Total	12		Total	12

 

So that's it then there are 24 zeros on the end of 100! in base 5 too.

---

The approach here is going to be roughly the same... We need to think what would cause a zero to be on the end of the product of multiplication.

I propose that like with the base 5 problem, because 2 is prime, (remember binary is base 2,) the only way to make a zero is to multiply by a number that ends in a zero. And therefor the number of zeros on the end of 100! in binary is the sum of the number of zeros on the end of the numbers from 1 to 100 when written in binary.

If this is not clear then think of two binary numbers, multiply them together and see that the numbers of zeros is conserved.

I have designed a spread sheet to convert the numbers 1 to 100 into binary and count up the number of zeros, you will need excel and possibly to have the analytics toolkit installed.

19binary100.xls (49kbytes) - 19binary100.zip (9.7kbytes)

Since not everyone has excel, or can be bothered to open a spread sheet the information is presented below...

Number	Binary	# of Zeros
1	0000001	0
2	0000010	1
3	0000011	0
4	0000100	2
5	0000101	0
6	0000110	1
7	0000111	0
8	0001000	3
9	0001001	0
10	0001010	1
11	0001011	0
12	0001100	2
13	0001101	0
14	0001110	1
15	0001111	0
16	0010000	4
17	0010001	0
18	0010010	1
19	0010011	0
20	0010100	2
21	0010101	0
22	0010110	1
23	0010111	0
24	0011000	3
25	0011001	0
26	0011010	1
27	0011011	0
28	0011100	2
29	0011101	0
30	0011110	1
31	0011111	0
32	0100000	5
33	0100001	0
34	0100010	1
35	0100011	0
36	0100100	2
37	0100101	0
38	0100110	1
39	0100111	0
40	0101000	3
41	0101001	0
42	0101010	1
43	0101011	0
44	0101100	2
45	0101101	0
46	0101110	1
47	0101111	0
48	0110000	4
49	0110001	0
50	0110010	1
51	0110011	0
52	0110100	2
53	0110101	0
54	0110110	1
55	0110111	0
56	0111000	3
57	0111001	0
58	0111010	1
59	0111011	0
60	0111100	2
61	0111101	0
62	0111110	1
63	0111111	0
64	1000000	6
65	1000001	0
66	1000010	1
67	1000011	0
68	1000100	2
69	1000101	0
70	1000110	1
71	1000111	0
72	1001000	3
73	1001001	0
74	1001010	1
75	1001011	0
76	1001100	2
77	1001101	0
78	1001110	1
79	1001111	0
80	1010000	4
81	1010001	0
82	1010010	1
83	1010011	0
84	1010100	2
85	1010101	0
86	1010110	1
87	1010111	0
88	1011000	3
89	1011001	0
90	1011010	1
91	1011011	0
92	1011100	2
93	1011101	0
94	1011110	1
95	1011111	0
96	1100000	5
97	1100001	0
98	1100010	1
99	1100011	0
100	1100100	2
		97

So that's it the answer is 97. There is though a more eloquent way of ariving at the sum other than directly counting them. There does seem to be something of a pattern. The trick is to think about the source of the zeros....

A number that has a factor of two will have atleast one zero on the end in the same way as, in base ten a number that has a factor of ten will have at least one zero.

A number that has a factor of four will end in atleast 2 zeros, factor 8 three zeros etc. etc.

The problem is this: because a number is a factor of say 16 and therefor has 4 zeros it we need to be careful not to double count the zeros we will have noted for it being a factor of 8, 4 and 2. Similarly the number may go on to be a factor of 32 and 64 as well.

The Solution to this is that when we note a number is a factor of 2, 4, 8, 16, 32 or 64 we only add one zero knowing that we will already have considered its lower factors and will go on to consider any higher factors.

now we just need to add up the number of factors of 2, 4, 8, 16, 32 & 64

Factor	occurences
2	50
4	25
8	12
16	6
32	3
64	1
total	97

So there we have it, 97 again!

 

BACK