Results 1 to 6 of 6

Math Help - Factorial

  1. #1
    Junior Member
    Joined
    Jun 2010
    Posts
    39

    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?

    Thank you in advance.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member MaxJasper's Avatar
    Joined
    Aug 2012
    From
    Canada
    Posts
    482
    Thanks
    55

    Lightbulb 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: \frac{10000!}{(100!)^{104}} = 2^{-93} * M
    Last edited by MaxJasper; October 22nd 2012 at 03:48 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jun 2010
    Posts
    39

    Re: Factorial

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

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

    I did it this way:

    Factorial-img_20121022_220507.jpg
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Oct 2012
    From
    India
    Posts
    61
    Thanks
    3

    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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jun 2010
    Posts
    39

    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
    Last edited by swordfish774; October 26th 2012 at 03:49 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Oct 2012
    From
    India
    Posts
    61
    Thanks
    3

    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Factorial
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 11th 2012, 04:42 AM
  2. factorial
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: January 8th 2011, 08:42 AM
  3. Sum of Factorial
    Posted in the Calculus Forum
    Replies: 2
    Last Post: January 4th 2011, 01:10 PM
  4. Factorial N
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: August 28th 2010, 11:18 PM
  5. factorial
    Posted in the Algebra Forum
    Replies: 3
    Last Post: January 15th 2009, 08:13 AM

Search Tags


/mathhelpforum @mathhelpforum