Let n = 60! + 55! + 50! The unit digit of n and a number of digits to the left of the units digits are consecutive zeros before we come to the first non-zero digit. How many such consecutive zeros are there until the first non-zero digit?
Answers
Step-by-step explanation:
The answer is 2, see explanation below.
These are the primes up to 50, all you need to find them is paper, pencil, and the sieve of Eratosthenes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.
Now we can compute the factorization of 50! using the answer to What are some efficient algorithms to compute the prime factorization of n! (n factorial)?
prime, exponent
2, 47 = 25 + 12 + 6 + 3 + 1
3, 22 = 16 + 5 + 1
5, 12 = 10 + 2
7, 8 = 7 + 1
11, 4
13, 3
17, 2
19, 2
23, 2
29, 1
31, 1
37, 1
41, 1
43, 1
47, 1
The largest power of 10 that divides 50! is therefore max(47, 12) = 12, so it's going to have 12 zeros on the right.
In other words, what we're looking for is the least-significant digit of 50! / 10^12.
Notice that we already have the factorization of 50! / 10^12: just subtract 12 from the exponents of 2 and 5.
Now we can reassemble the number we're looking for:
50! / 10^12 = 2^35 * 3^22 * 5^0 * 7^8 * 11^4 * 13^3 * 17^2 * 19^2 * 23^2 * 29 * 31 * 37 * 41 * 43 * 47
Okay, but we only need the last digit, so:
x = 2^35 * 3^22 * 5^0 * 7^8 * 11^4 * 13^3 * 17^2 * 19^2 * 23^2 * 29 * 31 * 37 * 41 * 43 * 47 mod 10
Taking all the primes modulo 10:
x = 2^35 * 3^22 * 5^0 * 7^8 * 1^4 * 3^3 * 7^2 * 9^2 * 3^2 * 9 * 1 * 7 * 1 * 3 * 7 mod 10
Collecting:
x = 2^35 * 3^34 * 7^12 mod 10
Notice how powers of 2, 3, and 7 form cycles modulo 10:
2, 4, 8, 6, 2, ...
3, 9, 7, 1, 3, ...
7, 9, 3, 1, 7, ...
(Interestingly, all these cycles have length 4.)
35 mod 4 = 3, so 2^35 mod 10 = 8.
34 mod 4 = 2, so 3^34 mod 10 = 9.
12 mod 4 = 0, so 7^12 mod 10 = 1.
What we're looking for is then 8 * 9 * 1 mod 10 = 72 mod 10 = 2.