Friday, January 4, 2019

2019/001) Find smallest n such that n! ends with 2019 zeroes.

n! ends with k zeroes if is is divisible by $2^k$ and $5^k$ but not with $2^{k+1}$ or $5^{k+1}$.
in the product the power 2

but in n! there are lot many 2 than 5 so it should be divisible by $5^k$  but not $5^{k+1}$.
$\lfloor\frac{n}{5}\rfloor$ numbers shall be divisible by 5
$\lfloor\frac{n}{5^2}\rfloor$numbers shall be divisible by $5^2$
$\lfloor\frac{n}{5^3}\rfloor$ numbers shall be divisible by $5^3$

so number of times 5 appears in product n ! = $p(n) =  \sum_{k=1}^{\inf}\lfloor\frac{n}{5^k}\rfloor$

this shall stop when $5^k > n$ so finite number is elements are to be taken.

We need to find an estimate for n and then correct the same.

Based on the we need to estimate n and then correct the same.

out of 25 consecutive numbers 5 numbers are divisible by 5 and one of those 5 is divisible by one more 5 so out of 25 so product of 25 consecutive numbers so 25 consective number product is divisble by $5^6$

so estimate for n = $\frac{2019*25}{6} = 8412.5$ so take 8410 the highest multiple of  5 less than 8412.

so n = 8410

now p(8410) = 2100

so we have overshot by 2100- 2019 = 81

so n should be reduced by $\frac{81*25}{6} = 337$

giving n -= 8410 - 337 = 8073 or highest multiple of 5 below it 8070.

n = 8070 and p(8070) = 2014

we fall short by 5 and next we take P(8075) = 2016 and P(8080) = 2017, P(8085) = 2018, P(8090) = 2019

so correct n = 8090


No comments: