1. ## Factorial

10000! = (100!)K × P, where P and K are integers. What can be the maximum value of K?

Consider,

5! = (3!)K × P
here, k = min [quotient of 3/1, quotient of 1/1] = 1 [there are 3 2s in 5! ; 1 2s in 3! ; 1 3s in 5! ; 1 3s in 3!]

25! = (5!)K × P
here, k = min [quotient of 22/3, quotient of 10/1, quotient of 6/1] = 6 [there are 22 2s in 25! ; 3 2s in 5! ; 10 3s in 5! ; 1 3s in 3!; 6 5s in 25!, 1 5s in 5!]

100! = (10!)K × P

here, k = min [quotient of 97/8, quotient of 48/4, quotient of 24/2, quotient 16/1] = 12

Now returning to the original question,
The maximum value of k will depend on highest or lowest or some other prime containted in 100?

ie will it depend on number of 2s, 97s or some other prime number? and why?

2. ## Re: Factorial

The only K values that result in integer P values are:

K = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18,
19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35,
36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52,
53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69,
70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86,
87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102,
103}

with the Kmax=103

Check: $\displaystyle \frac{10000!}{(100!)^{104}} = 2^{-93} * M$

3. ## Re: Factorial

I did not understand this part:
Originally Posted by MaxJasper
The only K values that result in integer P values are:

check: $\displaystyle \frac{10000!}{(100!)^{104}} = 2^{-93} * M$
what's M?

I did it this way:

4. ## Re: Factorial

Guys, it depends on the maximum primes <= 100 (for considering (100!)^k). Why is that? Because, for a number a to be a factor of b, any prime number dividing into a should also divide into b. If p^k divides a, then p^k should also divide b, because otherwise, it would not divide properly, and remainders/fractions would result. If you take the equation:

10000! = (100!)^k

every prime factor (with powers) dividing (100!)^k should be dividing 10000! too. That means, if you consider some prime number p <= 100, p^k should divide 10000! too. Now, after some inspection, you can conclude that the formula for prime p's power in n! is "Floor(n/p) + Floor(n/(p^2)) + Floor(n/(p^3)) + ...".

If you try to understand powers of 2, in both parts of equation, what you get is, the following:

Floor(100/2) + Floor(100/4) + Floor(100/8) + Floor(100/16) + Floor(100/32) + Floor(100/64) for 100.
Floor(10000/2) + Floor(10000/4) + Floor(10000/8) + Floor(10000/16) + Floor(10000/32) + Floor(10000/64) + Floor(10000/128) + Floor(10000/256) + ... for 10000.

Notice that, for Floor(100/2) to Floor(100/64), exponents are proportionally present in 10000!. So, this means, for any prime p below 100, 10000/100 = 100 is a safe exponent. The problem is with the latter terms being present in 10000!, like Floor(10000/128) etc... Also, notice that these will be more (and of more value), if prime number p is small.

Since all primes dividing (100!)^k should also divide 10000!, we need to find a common exponent k, that works for all primes <= 100. Since the common exponent is minimum one, we need to find the prime <= 100, which results in a minimum exponent k, namely the largest prime, 97.

Got it?

Salahuddin
Maths online

5. ## Re: Factorial

^ You are on the right track. But the largest prime is not the determining factor. 97 is not the limiting prime in this question. 2 is. Answer is k=103 not k=104

Here: Sum based on number of primes in a factorial

6. ## Re: Factorial

I think I got it. He segregated the categories of primes into ones which have the same power in 100!, and considered the maximum in each interval, as that is sufficient, good. Now, since the ratio matters than the actual numbers, we need to evaluate for all these 11 numbers, ok. Got it, great!

Salahuddin
Maths online