Wednesday, January 22nd, 2014
Dealing with Factorials
We all know what factorials (n!) are. They look friendly and helpful but looks can be deceiving, as many quant problems have taught us. Probably it is because that Factorials are simple looking creatures, most students prefer attempting questions based on them rather than on Permutation & Combination or Probability. I will cover P&C and Probability at a later date but in today’s post I would like to discuss some fundas related to factorials, which as a matter of fact form the basis of a large number of P&C and Probability problems.
Some of the factorials that might speed up your calculation are:
0! = 1; 1! = 1; 2! = 2; 3! = 6; 4! = 24; 5! = 120; 6! = 720; 7! = 5040.
Funda 1: Rightmost non-zero digit of n! or R(n!)
R(n!) = Last Digit of [ 2a x R(a!) x R(b!) ]
where n = 5a + b
Eg 1.1: What is the rightmost non-zero digit of 37! ?
Eg 1.2: What is the rightmost non-zero digit of 134! ?
We need to find out R (26!) = Last Digit of [ 25 x R (5!) x R (1!) ] = Last digit of [ 2 x 2 x 1 ] = 4
Funda 2: Power of a prime ‘p’ in a factorial (n!)
The biggest power of a prime ‘p’ that divides n! (or in other words, the power of prime ‘p’ in n!) is given by the sum of quotients obtained by successive division of ‘n’ by p.
Eg 2.1: What is the highest power of 7 that divides 1342!
Eg 2.2: What is the highest power of 6 that divides 134! ?
As 6 is not a prime number, we will divide it into its prime factors. 3 is the bigger prime, so its power will be the limiting factor. Hence, we need to find out the power of 3 in 134!
Eg 2.3: What is the highest power of 9 that divides 134! ?
As 9 is not a prime number, we will divide it into its prime factors. 9 is actually 32. The number of 3s available is 63, so the number of 9s available will be [63/2] = 31.
Highest power of 9 that divides 134! is 31.
Highest power of 18 and 36 will also be 31. Highest power of 27 will be [63/3] = 21.
Note: To find out the highest power of a composite number, always try and find out which number (or prime number) will become the limiting factor. Use that to calculate your answer. In most cases you can just look at a number and say that which one of its prime factors will be the limiting factor. If it is not obvious, then you may need to find it out for two of the prime factors. The above method can be used for doing the same.
Funda 3: Number of ending zeroes in a factorial (n!)
Number of zeroes is given by the sum of the quotients obtained by successive division of ‘n’ by 5.
This is actually an extension of Funda 1. Number of ending zeroes is nothing else but the number of times n! is divisible by 10 or in other words, the highest power of 10 that divides n!. 10 is not a prime number and its prime factors are 2 and 5. ‘5’ becomes the limiting factor and leads to the above-mentioned idea.
Eg 3.1: What is the number of ending zeroes in 134! ?
I hope that this gets you started with factorials and you might start singing this song.