Number Theory : Factorials - Vikas Saini



  • Basic Formula :-

    Highest power of any prime number p in any number n! = [n/p]+[n/p^2]+[n/p^3]……

    Where [d] denotes the greatest integer function less than or equal to d.

    Q. Find the highest power of  2 in 100!

    Solution :-

    [100/2]+[100/2^2]+[100/2^3]+[100/2^4]+[100/2^5]+[100/2^6]

    = 50+25+12+6+3+1

    =97.

    Q. Find highest power of 3 in 200!

    Solution :-

    [200/3]+[200/3^2]+[200/3^3]+[200/3^4]

    = 66+22+7+2

    =97.

    Q. Find the highest power of 30 in 50!

    Solution :-

    30 = 2 x 3 x 5.

    5 is largest prime factor of 30.

    [50/5]+[50/5^2]

    = 10+2 = 12.

    Q. Find the least number which highest power of 7 is 52.

    Solution :-

    We know highest power comes by this formula.

    Highest power = [n/p]+[n/p^2]+[n/p^3]……..

    52 = [n/7] + [n/7^2] + [n/7^3]

    The only things strike in our mind to split 52.

    1+7+49 (not equal to 52)

    6+42 (not equal)

    7+49 (not equal)

    6+42 < 52 < 7+49

    6+43 < 52

    6+46 = 52.

    [n/7] = 46

    n > 7 x 46.

    n > 322.

    [n/49] = 6.

    n > 49 x 6.

    n > 294.

    For least possible number n = 322.

    Q. Find the least number which highest power of 13 is 52.

    Solution :-

    52 = [n / 13] + [n / 13^2]

    52 = [ n / 13 ] + [ n / 169 ]

    Let’s think , how 52 can be split.

    3 + 39  <   52  < 4 + 52

    3+49 = 52.

    [ n / 13 ] = 49.

    n > 13 x 49

    n > 637.

    [ n / 169 ] = 3

    n = 169 x 3

    n  >  507.

    For least value, n = 637.

    Q. Find highest power of 72 in 100!

    Solution :-

    72 = 2^3 x 3^2.

    Highest power of 2 = [100/2] + [100/2^2] + [100/2^3] + [100/2^4] + [100/2^5] + [100/2^6]

    = 50 + 25 + 12 + 6 + 3 + 1

    = 97.

    But power of  2 is 3 here, so 97/3 = 32.

    Highest power of 3 = [100/3] + [100/3^2] + [100/3^3] + [ 100/3^4]

    = 33 + 11 + 3 + 1

    = 48.

    But power of 3 is 2 here, so 48/2 = 24.

    24 < 32.

    Power of 72 in 100! Is 24.

    Q. Find the highest power of 24 in 50!

    Solution :-

    24 = 2^3 x 3.

    Power of 2 in 50! = [50/2] + [50/2^2] + [50/2^3] +[50/2^4]+[50/2^5]

    = 25+12+6+3+1

    = 47.

    Power of 2 is 3 here.

    47 / 3 = 15.

    Power of 3 in 50!

    [50/3]+[50/3^2]+[3^3]

    = 16+5+1

    = 21.

    15 < 21.

    Power of 24 in 50! is 15.

    Q. Find the total no of divisors of 17!

    Solution :-

    Prime factors are 2,3,5,7,11,13,17.

    Highest power of 2 = [17/2] + [ 17/2^2] + [ 17/2^3] + [17/2^4]

    8+4+2+1 = 17.

    Highest power of 3 = [17/3] + [17/3^2]

    5+1 = 6.

    Highest power of 5 = [17/5] + [17/5^2] = 3.

    Highest power of 7 = [17/7] + [17/7^2] = 2.

    Highest power of 11 = [17/11] = 1.

    Highest power of 13 = [17/13] = 1.

    Highest power of 17 = [17/17] = 1.

    17! = 2^17 x 3^6 x 5^3 x 7^2 x 11 x 13 x 17

    Factors = (17+1)(6+1)(3+1)(2+1)(1+1)(1+1)(1+1)

    = 18 x 7 x 4 x 3 x 2 x 2 x 2

    = 126 x 96

    = 12096.

    [ No of zeroes at the end of n! ]

    No of zeroes means no of 10’s.

    10 = 2 x  5.

    Basic formula

    No of zeroes = [ n / 5 ] + [ n / 5^2 ] + [ n / 5^3 ] …

    Q. Find the number of zeroes at the end of 250!

    Solution :-

    [ 250 / 5 ] + [ 250 / 5^2 ] + [ 250 / 5^3 ]

    = 50 + 10 + 2

    = 62.

    Q. Find the no of zeroes at the end of 100 x 99^2 x 98^3 x 97^4 ... 1^100.

    Solution :-

    100 x 99^2 x 98^3 ... 1^100

    = (100 x 99 x 98 ... 1) x (99 x 98 x 97... 1) x (98 x 97 x 96 ... 1) ... 1

    = 100! x  99! x  98! x 97! ... 1!

    = 1! x 2! ... 100!

    1! to 4! = 0.

    5! to 9! = 1 x 5 = 5.

    10! to 14! = 2 x 5 = 10.

    15! to 19! = 3 x 5 = 15.

    20! to 24! = 4 x 5 = 20.

    1! to 24! = 5(0+1+2+3+4) = 50.

    25! To 49! = 5(6+7+8+9+10) = 200.

    50! to 74! = 5(12+13+14+15+16)=350.

    75! to 99! = 5(18+19+20+21+22)=500.

    100! = 24.

    Total = 50 + 200 + 350 + 500 + 24 = 1124.

    Q. Find no of zeroes at the end of 250 x 255 x 260 ……….750.

    Solution :-

    5^101 (50 x 51 x 52 …………………150)

    = 5^101 (150 !)  / (49! )

    No of 5’s in 150! = [150 / 5] + [ 150 / 5^2 ] + [ 150 / 5^3 ]

    = 30 + 6 + 1 = 37.

    Total no of 5’s in numerator = 101 + 37 =  138.

    No of 2’s in 150!

    = [150 / 2] + [150 /2^2 ] + [ 150 /2^3 ] + [ 150/2^4 ] + [ 150 / 2^5 ] + [ 150 / 2^6 ] + [150 / 2^7]

    = 75 + 37 + 18 + 9 + 4 + 2 + 1

    = 146.

    No of 2’s > No of 5’s

    Hence no of zeroes at numerator = no of 5’s = 137.

    Number of zeroes at denominator = [ 49 / 5 ] + [ 49 / 5^2 ]

    = 9 + 1

    = 10.

    Total no of zeroes = 137 – 10 = 127.

    Q. For any value of k, k! has n zeroes at the end and (k+2)! has n+2 zeroes at the end. How many number of  possible values of k if  0 < k < 200.

    Solution :-

    We know no of zeroes increases by 2 only when no is in form of 25n+1.

    K+2 = 25n+1.

    K+2 = 26,51,76,101,126,151,176,201.

    But for 125, no of zeroes increase by 3.

    So we need to remove 126.

    k+2 = 26,51,76,101,151,176,201

    k = 24,49,74,99,149,174,199.

    Total possible values = 7.

    Q. k! has n number of zeroes at the end and (k+1)! has (n+3) zeroes at the end.

    Find the number of possible values of n if  100 < k < 1000.

    Solution :-

    We know for multiple of 5(5^1), no of zeroes increase by 1.

    For multiple of 25(5^2), no of zeroes increase by 2.

    For multiple of 125(5^3), no of zeroes increase by 3.

    It means k+1 = 125 a.

    k+1 = 125,250,375,500,625,750,875,1000.

    But  625(5^4), no of  zeroes increase by 4.

    So k+1 = 125,250,375,500,750,875,1000.

    Total values of k = 7.

    Q. Find the highest power of 2 in 128! + 129! + 130!  ... 200!

    Solution :-

    128! (1 + 129 + 129 x 128 + 129 x 130 x 131 + 129 x 130 x 131 x 132……………… + 129 x ………200 )

    = 128! ( 130 + 129 x 128 + 129 x 130 x 131 + 129 x 130 x 131 x 132………..)

    = 128! x 2   ( 65 + 129 x 64 + 129 x 65 x 131 + 129 x 65 x 131 x     132…………………………..)

    = 128! x 2 ( 65 + even + odd + odd …………….)

    = 128! x 2 ( odd + odd + odd ………………)

    No of 2’s in 128! = [ 128 / 2 ] + [ 128 / 2^2] + [ 128 / 2^3 ] + [ 128 / 2^4 ] + [128 / 2^5 ] + [ 128 / 2^6 ] + [ 128/ 2^7]

    = 64 + 32 + 16 + 8 + 4 + 2 + 1

    = 127.

    But there is one more 2.

    So total no of zeroes = 127 + 1 = 128.

    [ To find the non zero digit from right ]

    If we have to find first non zero digit from right in any number n!

    = > >   n = 5 x m + k.

    Then 2^m x m! x k! .

    Q. Find the first non zero digit of 26! .

    Solution :-

    26 = 5 x 5 + 1.

    n = 26, m = 5, k=1.

    First non zero digit = 2^5 x 5! X 1!

    = 32 x 120 x 1

    = 3840.

    4 is first non zero digit here.

    But any no n is as large that it can be written as

    n = 25 x m + k.

    Then first non zero digit = 4^m x m! x k!

    Q. Find the first non zero digit of 97! .

    Solution :-

    97 = 25 x 3 + 22.

    First non zero digit = 4^3 x 3! x 22!

    22! = 5 x 4 + 2.

    First non zero digit = 2^4 x 4! x 2!

    = 16 x 24 x 2

    =8 (first digit from right).

    First non zero digit of 97 = 4^3 x 3! x 8

    = 4 x 6 x 8

    = 2.

    Although it can be solved in another way.

    97 = 5 x 19 + 2.

    Digit = 2^19 x 19! x 2!

    19 = 5 x 3 + 4.

    Digit = 2^3 x 3! x 4! = 2.

    Digit of 97! = 2^19 x 2 x 2

    = 8 x 2 x 2

    = 2.

    Similarly, if n = 125 x m + k.

    Then first non zero digit = 8^m x m! x k!

    Q. Find the first non zero digit of 377! .

    Solution :-

    477 = 125 x 3 + 2.

    First non zero digit = 8^3 x 3! x 2! = 2 x 6 x 2 = 4.

    Another way :-

    377 = 25 x 15 + 2.

    Digit = 4^15 x 15! x 2! .

    15! = 3 x 5.

    Digit = 2^3 x 3! = 8.

    Digit of 377! = 4^15 x 8 x 2 =4.

     


Log in to reply
 

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