Improve your Vocabulary
I read somewhere a formula to calculate the number of powers of 2 in a factorial (100!). I then spent days to identify how this can be proved & generalized. After searching for days, I found a way & an excellent explanation. Here it goes,
Lets assume, we have a number n! for which we want to find the maximum value of k, such that n! is divisible by p^k (here p is a prime number). In simpler terms, the number of powers of p in n!.
The trick is simple:
n/p + n/p^2 + n/p^3.....
This can best be explained by an example:
Lets consider n as 100!, p as 5.Then, K = 100/5 + 100/5^2 + 100/5^3K = 20 + 4 + 0K = 24
Every 5th multiple contributes to 1 value in K, every 25th multiple contributes to 2 values in K (5*5). Out of th2 2 values in 25th multiple, we have already counted 1 value in 5th multiple.
I hope, I'm able to clarify it to some extent.
Labels: factorial , formula , Mathemagic , Prime Number , Quantitative Analysis
0 comments :
Subscribe to:
Post Comments
(
Atom
)