2IIM Quant Notes - Factorial


  • Director, 2IIM Online CAT Preparation | IIT Madras | IIM Bangalore | CAT 100th percentile - CAT 2011, 2012 and 2014.


    A number n! is written in base 6 and base 8 notation. Its base 6 representation ends with 10 zeroes. Its base 8 representation ends with 7 zeroes. Find the smallest n that satisfies these conditions. Also find the number of values of n that will satisfy these conditions.
    22 and 4
    32 and 2
    24 and 3
    25 and 4

    Base 6 representation ends with 10 zeroes, or the number is a multiple of 6^10. If n! has to be a multiple of 6^10, it has to be a multiple of 3^10. The smallest factorial that is a multiple of 3^10 is 24!. So, when n = 24, 25 or 26, n! will be a multiple of 6^10 (but not 6^11).

    Similarly, for the second part, we need to find n! such that it is a multiple of 2^21, but not 2^24. When n = 24, n! is a multiple of 2^22. S0, when n = 24, 25, 26, 27, n! will be a multiple of 2^21 but not 2^24.

    The smallest n that satisfies the above conditions is 24. n = 24, 25 or 26 will satisfy the above conditions.

    Given N is a positive integer less than 31, how many values can n take if (n + 1) is a factor of n!?
    18
    16
    12
    20

    The best starting point for this question is to do some trial and error.
    3 is not a factor of 2!
    4 is not a factor of 3!
    5 is not a factor of 4!

    6 is a factor of 5!
    7 is not a factor of 6!
    8 is a factor of 7!

    The first thing we see is that n + 1 cannot be prime. If (n + 1) were prime, it cannot be a factor of n!.

    So, we can eliminate all primes.

    Now, let us think of all numbers where (n + 1) is not prime. In this instance, we should be able to write (n + 1) as a * b where a,b are not 1 and (n + 1). So, (a, b) will lie in the set {1, 2, 3........n} or, a * b will be a factor of (n + 1)!

    So, for any composite (n + 1), (n + 1) will always be a factor of n! {Is there any exception?}

    For any prime number (n + 1), (n + 1) will never be a factor of n!

    The above rule works well even for all the examples we have seen, except when (n + 1) = 4. 4 = 2 * 2; So, 4 is not a factor of 3!. But this is the only exception.

    Counting on from here, we can see that n can take values 5, 7, 8, 9, 11, 13, 14, 15, 17, 19, 20, 21, 23, 24, 25, 26, 27, 29. Essentially, all numbers where N + 1 is greater than 4 and is not prime will feature in this list. If N + 1 is not prime, we should be able to write it as a product of 2 numbers less than N + 1. This will feature in n!. This question is just a different way of asking one to count primes (and then account for the exception of 4)

    n can take 18 different values.

    How many values can natural number n take, if n! is a multiple of 7^6 but not 7^9?
    7
    21
    14
    12

    The smallest factorial that will be a multiple of 7 is 7!
    14! will be a multiple of 7^2
    Extending this logic, 42! will be a multiple of 7^6

    However, 49! will be a multiple of 7^8 as 49 (7 * 7) will contribute two 7s to the factorial. (This is a standard question whenever factorials are discussed). Extending beyond this, 56! will be a multiple of 7^9.

    In general for any natural number n,
    n! will be a multiple of [n/7] + [n/49] + [n/343] + ...........
    where [x] is the greatest integer less than or equal to x. A more detailed discussion of this is available on this link

    So, we see than 42! is a multiple of 7^6. We also see that 56! is the smallest factorial that is a multiple of 7^9. So, n can take values {42, 43, 44, 45........55}

    There are 14 values that n can take.

    How many values can natural number n take, if n! is a multiple of 2^20 but not 3^20?
    11
    21
    16
    5

    he highest power of 2 that will divide n! = [n/2]+[n/4]+[n/8]+[n/16]........ and so on.
    So, let us try to find the smallest n such that n! is a multiple of 2^20.
    If n = 10, the highest power of 2 that will divide n! = [10/2]+[10/4]+[10/8] = 5 + 2 + 1 = 8
    If n = 20, the highest power of 2 that will divide n! = [20/2]+[20/4]+[20/8]+[20/16] = 10 + 5 + 2 + 1 = 18
    If n = 24, the highest power of 2 that will divide n! = [24/2]+[24/4]+[24/8]+[24/16] = 12 + 6 + 3 + 1 = 22
    {Here we can also see that each successive number is just the quotient of dividing the previous number by 2. As in, [12/2] = 6, [6/2] = 3, [3/2] = 1. This is a further short-cut one can use.}
    So the lowest number of n such that n! is a multiple of 2^20 is 24.

    Now, moving on to finding n! that is a multiple of 3.
    The highest power of 3 that will divide n! = [n/3]+[n/9]+[n/27]+[n/81] and so on.
    When n = 20, the highest power of 3 that can divide 20! = [20/3]+[6/3] = 6 + 2 = 8
    When n = 35, the highest power of 3 that can divide 35! = [35/3]+[11/3]+[3/3] = 11 + 3 + 1 = 15
    When n = 45, the highest power of 3 that can divide 45! = [45/3]+[15/3]+[5/3] = 15 + 5 + 1 = 21
    The lowest number n such that n! is a multiple of 3^20 is 45.

    When n takes values from 24 to 44, n! will be a multiple of 2^20 and not 3^20. n can take 21 values totally

    How many trailing zeroes (zeroes at the end of the number) does 60! have?
    14
    12
    10
    8

    To start with, the number of trailing zeroes in the decimal representation of a number = highest power of 10 that can divide the number.

    For instance,
    3600 = 36 * 10^2
    45000 = 45 * 10^3

    In order to approach this question, let us first see the smallest factorial that ends in a zero.
    1! = 1
    2! = 2
    3! = 6
    4! = 24
    5! = 120

    Now, 5! ends in a zero as we have get a product of 10 when we compute 1 * 2 * 3 * 4 * 5.
    10 is 2 * 5, so we get a factor of 10 every time we get a 2 and a 5 in the factorial.
    So, 5! has 1 zero. The factorial that ends with 2 zeroes is 10!
    15! has 3 zeroes.
    20! has 4 zeroes and so on.

    An extra zero is created every time a 2 and 5 combine. Every even number gives a two, while every fifth number gives us a 5.

    Now, the critical point here is that since every even number contributes at least a 2 to the factorial, 2 occurs way more frequently than 5. So, in order to find the highest power of 10 that can divide a number, we need to count the highest power of 5 that can divide that number. We do not need to count the number of 2’s in the system as there will be more than 2’s than 5’s in any factorial.

    Now, every multiple of 5 will add a zero to the factorial. 1 * 2 * 3 *.......59 * 60 has twelve multiples of 5. So, it looks like 60! will end in 12 zeroes. But we need to make one more adjustment here.

    25 is 5^2, so 25 alone will contribute two 5’s, and therefore add two zeroes to the system. Likewise, any multiple of 25 will contribute an additional zero.

    So, 20! has 4 zeroes, 25! has 6 zeroes.

    60! will have [60/5] zeroes arising due to the multiples of and an additional [60/25] due to the presence of 25 and 50. {We retain only the integer component of [6025] as the decimal part has no value}

    So, 60! will end with 12 + 2 zeros. = 14 zeros.

    In general, any n! will end with [n/5]+[n/25]+[n/125]+[n/625] ... zeroes.

    Generalizing further, in case we want to find the highest power of 3 that divides n!, this is nothing but [n/3] + [n/9] + [n/27] + [n/81] ...

    The highest power of 7 that divides n! is [n/7] + [n/49] + [n/343] ....

    In case of a composite number, we need to break into the constituent primes and compute the highest power that divides the number.

    For instance, if we want to find the largest power of 15 that divides n!, this will be driven by the highest powers of 3 and 5 that divide n!. Similar to the scenario we saw with trailing zeroes, we can observe that there will definitely be at least as many 3’s than 5’s in any factorial. So, the highest power of 15 that divides n! is simply [n/5] + [n/25] + [n/125] + [n/625] ...

    What is the highest power of 12 that divides 54!?
    25
    26
    30
    4

    12 = 2^2 * 3, so we need to count the highest power of 2 and highest power of 3 that will divide 54! and then we can use this to find the highest power of 12.

    The method to find highest powers of 2 and 3 are similar to the one outlined in the previous question.

    Highest power of 2 that divides 54! = [54/2]+[54/4]+[54/8]+[54/16]+[54/32] = 27 + 13 + 6 + 3 + 1 = 50
    Highest power of 3 that divides 54! = [54/3]+[54/9]+[54/27] = 18 + 6 + 2 = 26

    Or 54! is a multiple of 2^50 * 3^26. Importantly, these are the highest powers of 2 and 3 that divide 54!.
    2^2 * 3 = 12. We need to see what is the highest power of 2^2 * 3 that we can accommodate within 54!

    In other words, what is the highest n such that (2^2 * 3)^n can be accommodated within 2^50 * 3^26.

    Let us try some numbers, say, 10, 20, 30

    (2^2 * 3)^10 = 2^20 * 3^10, this is within 2^50 * 3^26
    (2^2 * 3)^20 = 2^40 * 3^20, this is within 2^50 * 3^26
    (2^2 * 3)^30 = 2^60 * 3^30, this is not within 2^50 * 3^26

    The highest number possible for n is 25.
    (2^2 * 3)^25 = 2^50 * 3^25, this is within 2^50 * 3^26, but (2^2 * 3)26 = 2^52 * 3^26, this is not within 250 * 326.

    So, 54! can be said to be a multiple of (2^2 * 3)25. Or, the highest power of 12 that can divide 54! is 25.

    Note: For most numbers, we should be able to find the limiting prime. As in, to find the highest power of 10, we need to count 5s. For the highest power of 6, we count 3s. For 15, we count 5s. For 21, we count 7’s. However, for 12, the limiting prime could be 2 or 3, so we need to check both primes and then verify this.

    Find the least number n such that no factorial has n trailing zeroes, or n + 1 trailing zeroes or n + 2 trailing zeroes.
    153
    126
    624
    18

    We see that 24! has [24/5] = 4 zeroes
    25! ends with [25/5]+[25/5] = 6 zeroes. There is no natural number m such that m! has exactly 5 zeroes.
    Similarly, we see that 49! ends with [49/5]+[49/25] = 10 zeroes, whereas 50! ends with [50/5]+[50/25] = 12 zeroes. No factorial ends with 11 zeroes.

    So, any time we have a multiple of 25, we 'skip' a zero. This is because a multiple of 25 adds two zeroes to the factorial.

    Extrapolating this, we can see that 125 might actually 'skip' two zeroes. 124! ends with [124/5]+[124/25] = 24 + 4 = 28 zeros, whereas 125! has [125/5]+[125/25]+[125/125] = 25 + 5 + 1 = 31 zeros. There is no factorial with 29 or 30 zeros.

    In order to jump three zeros, think about what we need to look at. Every multiple of 25 gives us one 'skipped' zero. Every multiple of 125 gives us two 'skipped' zeroes.

    In order to have three skipped zeroes, we need to look at 624! and 625!
    624! has [624/5]+[624/25]+[624/125] = 124 + 24 + 4 = 152 zeros
    625! has [625/5]+[625/25]+[625/125]+[625/625] = 125 + 25 + 5 + 1 = 156 zeros

    When 40! is expressed in base 8 form, what is the last non–zero digit in the base 8 expansion?
    2
    6
    4
    2 or 6

    We need to find the largest power of 8 that divides 40!.
    We need to find the largest power of 2 that divides 40!

    This is given by (40/2) and then successive division by 2. = 20 + 10 + 5 + 2 + 1 = 38

    So, 2^38 divides 40! Or, (2^3)^12 × 2^2 divides 40!

    (2^3)^12 divides the number, or the base 8 representation ends with 12 zeroes. Now, the base 8 representation of this number will be some (abcd…n){Base 8} × (1000000000000){Base 8}. Now, (abcd…n){Base 8} does not end in 0 and is a multiple of 2^2. The last digit has to be 4.

    The last non–zero digit is 4.

    Let K be the largest number with exactly 3 factors that divide 25! How many factors does (k – 1) have?
    16
    12
    9
    14

    A number with exactly 3 factors has to be square of a prime.
    Now, 3^2 divides 25! So do 5^2, 7^2, 11^2.
    13^2 will not divide 25!
    So the largest number with 3 factors that divide 25! is 121.
    K – 1 = 120 = 2^3 × 3 × 5
    K – 1 has 16 factors.


Log in to reply
 

Looks like your connection to MBAtious was lost, please wait while we try to reconnect.