Factorials - Number System - Albanian PDF Download

Factorial is an important topic in quantitative aptitude preparation not just because of its importance as an independent concept, but also because of its application in many topics like permutation & Combination, Probability etc… The factorial of a non negative integer n is denoted as n! The notation was introduced by Christian Kramp in 1808.
n! is calculated as the product of all positive integers less than or equal to n.
i.e 6! = 1 * 2 * 3 * 4 * 5 * 6 = 720
n! = 1 when n = 0, and n! = (n - 1)! * n if n > 0

➢ What is the significance of n! 
"n! is the number of ways we can arrange n distinct objects into a sequence".
Example: 2! = 2 means numbers 1, 2 can be arranged in 2 sequences (1, 2) and (2, 1).
We can arrange 0 in one way. So 0! = 1, not zero. Now we know why, and no need to say “its like that” if someone asks.

➢ Find the highest power of a prime number in a given factorial.
The highest power of prime number p in n! = [n/p¹] + [n/p²] + [n/p³] + [n/p⁴] + …
[x] denotes the greatest integer less than or equal to x.
[1.2] =1
[4] = 4
[-3.4] = -4 (why? Because -4 is less than -3.2)

Example 1: Find the highest power of 3 in 100!
Solution: [100/3] + [100/3²] + [100/3³] + [100/3⁴] + [100/3⁵] + …
= 33 + 11 + 3 + 1 + 0 (from here on greatest integer function evaluates to zero)
= 48.

Example 2: What is the greatest power of 5 which can divide 80! exactly?
Solution: [80/5] + [80/5²] + [80/5³] + …
= 16 + 3 + 0 + … = 19.

➢ Find the highest power of a non prime number in a given factorial
We learnt before that any non prime number can be expressed as a product of its prime factors. We will use this concept to solve this type of questions.

Example 1: What is the greatest power of 30 in 50!
Solution: 30 = 2 * 3 * 5.
Find what the highest power of each prime is in the given factorial
We have 25 + 12 + 6 + 3 + 1 = 47    2s in 50!
16 + 5 + 1 = 22    3s in 50!
10 + 2 = 12    5s in 50!
We need a combination of one 2, one 3 and one 5 to get 30. In the given factorial we have only 12 5s. Hence only twelve 30s are possible. So the greatest power of 30 in 50! is 12.

Note: We don’t have to find the power of all prime factors of a given number. It is enough to find the greatest power of the highest prime factor in the factorial (here 5).

Example 2: What is the greatest power of 8 in 50!
Solution: 8 =2³
50! has 47 twos. We need 3 two to get an 8.
We can have a maximum of [47/3] = 15 8s in 50!

Note: The highest power of the number p^a in n! = [Highest power of p in n!]/a.

➢ Find the highest power of all prime numbers, less than n, in n!
Example 1: What are the number of factors of 15!
Solution: 2, 3, 5, 7, 11 and 13 are the prime numbers less than 15.
Highest power of 2 in 15! = 11
Highest power of 3 in 15! = 6
Highest power of 5 in 15! = 3
Highest power of 7 in 15! = 2
Highest power of 11 in 15! = 1
Highest power of 13 in 15! = 1
15! = 2¹¹ * 3⁶ * 5³ * 7²* 11¹ * 13¹
Thus we can find the number of divisors, sum of divisors and other values for 15!
number of factors of 15! = (11 +1) (6 + 1) (3 + 1) ( 2 + 1) ( 1 + 1) (1 + 1) = 4032

➢ Find the number of zeros at the end of a factorial value
This is just another way of asking what highest power of 10 is in a given factorial.
10 = 2*5, we need a combination of one 2 and one 5 to get a zero at the end. Just find the number of 5s in the given factorial as number of 2s will be always more than number of 5s.

Example 1: Find the number of zeros at the end of 100!
Solution: [100/5] + [100/25] + … = 20 + 4 + 0 + … = 24.

Example 2: Find the number of zeros at at the end of 100! in base 7
Solution: Concept is same as before. in base 10 we need a 2 and 5 to get a zero but in base 7 we need a 7 to get a zero. so we have to find the highest power of 7 in 100!
[100/7] + [100/49] + ... = 14 + 2 = 16. There will be 16 zeros at the end of 100! in base 7

Note:  To find the number of zeros of a factorial in a base b, calculate the highest power of b in that factorial. b need not be prime, we already know how to find the highest power of a composite number in a factorial expression.

WILSON'S THEOREM
For every prime number p, (p-1)! + 1 is divisible by p
Take p =7, then as per Wilson's theorem 7 is prime only if (6!) + 1 is divisible by 7 and some useful results derived from Wilson's theorem.

Remainder [(p-1)!/p] = p - 1 ( where p is a prime number )
Remainder [6!/7] = 7; Remainder [100!/101] = 100 and so on...

Remainder [(p-2)!/p] = 1 ( where p is a prime number )
Remainder [5!/7] = 1; Remainder [99!/101] = 1 and so on...

SOME EXTRA CONCEPTS
➢ Product of n consecutive natural numbers is divisible by n!
11 * 12 * 13 * 14 is completely divisible by 4!
This can be extended to obtain other interesting results.
Consider 1 * 2 * 3 * 4 * 5 * 6 . as per above result 1 * 2 * 3 * 4 * 5 * 6 is divisible by 6!.
Now take (1 * 2 * 3) * (4 * 5 * 6) . each of this is divisible by 3!
so 1 * 2 * 3 * 4 * 5 * 6 is completely divisible by (3!)²  
similarly 1 * 2 * 3 * 4 * 5 * 6 is completely divisible by (2!)³ also.

Note: To generalise (a*n)! is completely divisible by (n!)^a,  where a and n are integers.

➢ The product of all odd (even) integers up to an odd (even) positive integer n is called the double factorial of n. (though it has only about half the factors of the original factorial!). It is denoted as n!!
9!! = 1 * 3 * 5 * 7 * 9 = 945
8!! = 2 * 4 * 6 * 8 = 384

➢ Product of first n! is called the super factorial of n, denoted as sf(n).
sf(4) = 1! * 2! * 3! * 4!

➢ A factorion is a natural number that equals the sum of the factorials of its decimal digits.
Example: 145 is a factorion because 1! + 4! + 5! = 1 + 24 + 120 = 145.

Note: There are just four factorions (in base 10) and they are 1, 2, 145 and 40585.

➢ A factorial prime is a prime number that is one less or one more than a factorial.
2 = 1! + 1, 3 = 2! + 1, 5 = 3! -1, 7 = 3! + 1 etc…