Friday, April 14, 2017

permutations - How many factors of $10$ in $100!$












How many factors of 10 are there in $100!$ (IIT Question)?



Is it 26,25,24 or any other value



Please tell how you have done it


Answer



So first, we want to find how many factors of $5$ there are in $100!$. There are $20$ numbers divisible by $5$ from $1$ to $100$, so we start off our count at $20$. Then, we count how many numbers are divisble by $5^2$. There are four: $25, 50, 75, 100$, and so we add four to our count to get $24$ factors of $5$. (Note that we don't add eight fives - if we did so, we would be counting the first factors of five twice!)



Since $5^3>100$, we don't have to worry about third powers of five. There are at least $100/2=50$ factors of $2$ in $100!$, but we're only going to use $24$ of them to get our $24$ multiples of $10$, so we don't have to calculate the exact number of factors of $2$ in $100!$.




So basic method: To find how many factors of $a$ there are in $b!$, first decompose $a$ into its primes $p_n$, and then find out how many factors of each prime $p_n$ are in numbers less than $b$, by using the method I described of checking for divisibility by $p_n$, then $p_n^2$, etc. Then, from this pool of factors, figure out how many you can take. In our examples to make $10^n$ we could take a maximum of $24$ fives and $24$ twos. If we wanted to find how many factors of $40$ (=$2^3 5$) were less than $100$, we would have needed to find out exactly how many factors of $2$ were less than $100$, and then either take $24*3$ twos if there are enough, or less, if there aren't.



See also: youtube Factors of Factorials Part 1


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...