Added by Nitin B on December 01, 2001 at 03:14:46:
Please note that I have derived these formulae myself. I would be grateful to anyone who proves any of the below formulae wrong. I advise everyone to check the validity of the formulae.
Update, 5 April 2002:
I found a flaw in the formula (max value of x such that n! divisible by m^x). It counts only the direct factors.
That is in 1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19*20 we know
that it is divisible by 10^4. But the formula returns only 100. That
is because it counts only 10 and 20. It doesn't take into consideration
the influence of 4,5,15 which contribute another 100. You can
download an improved and more stable algorithm.
(You will need Microsoft Word or
the free Microsoft Word Viewer.)
Formula 1: Product of odd positive integers
(1 * 3 * 5 * 7 * ... * n) = (n!) / { (2[n/2]) * ([n/2]!) }
where n is any positive integer (odd or even) and [x] denotes the Greatest Integer Function of a real number x and x! denotes the factorial of 'x'. The formula gives the product of all odd numbers up to any given integer.
Formula 2: Largest possible power of m in N!
x = [n/m] + [ [n/m] / m ] + [ [ (n/m) / m ] / m ] + ..... until ...+ 1 is obtained.
The notations as in the previous formula apply here too. This means (formula) that the person should divide n by m and apply the greatest integer function to it. Go on dividing the previous term by m and applying the greatest integer function to these until 1 (which should also be added) is obtained.
Example: Find the greatest value of x such that 95! is divisible by 2x.
Solution: Using the above formula,
Step 1: [ 95 / 2 ] = [ 47.5 ] = 47
Step 2: [ 47 / 2 ] = [ 23.5 ] = 23
Step 3: [ 23 / 2 ] = [ 11.5 ] = 11
Step 4: [ 11 / 2 ] = [ 5.5 ] = 5
Step 5: [ 5 / 2 ] = [ 2.5 ] = 2
Step 6: [ 2 / 2 ] = [ 1.0 ] = 1
STEP 7 ::::: Sum up all the above : 47 + 23 + 11 + 5 + 2 + 1 = 89 (Answer)
Formula 3: Ways to get at least 1 out of n possible pairs right
The number of ways by which at least one pair is matched correctly out of n possible pairs given
n items and n places to fill them in are (Please see rephrased statement):
n
x = Σ [ (-1)^(i+1) ] * [ n!/i! ]
i=1
The sum of [ (-1)^(i+1) ] * [ n!/i! ] for all values of i from 1 to n
Corollary to formula 3
The ways in which no pair is matched correctly out of n possible pairs given n items and n places to fill them in are given by:
x' = n! - x
n
x' = Σ [ (-1)^i ] * [ n!/i! ]
i = 2
(The sum of [ (-1)^i ] * [ n!/i! ] for values of i from 2 to n.)
Rephrased statement of Ways to get at least 1 out of n possible pairs right. (Formula 3)
If a student wants to match n pairs:
A1 A2 A3 ... An
B1 B2 B3 ... Bn
where the right pairs are (A1-B1),(A2-B2),...(An-Bn), one mark being awarded for the right match.
The number of ways in which the student can get at least 1 mark are:
n
x = Σ [ (-1)^(i+1) ] * [ (n!/i!) ]
i = 1
The Greatest Integer Function of a real number x is defined as the greatest integer lesser than or equal to x and is denoted by [x].
Examples:
| [5] = 5 | [-5] = -5 | |
| [3.00001] = 3 | [-3.00001] = -4 (-4 < -3.00001) | |
| [3.5] = 3 | [-3.5] = -4 | |
| [3.9999999] = 3 | [-3.9999999]= -4 | |
| [pi] = 3 | pi = 3.141592654... (approx) |