Friday 31 October 2014

prime factorization - Power of 2 & 5 in product of consecutive numbers



Is there any way to calculate the powers of 2 and 5 in a product of consecutive $n$ numbers, if given $l$ and $r$.




i.e Suppose $x = l \times (l+1) \times (l+2) \times ...... \times (r-1) \times r$, Then if $x = 2^{p_1}.3^{p_2}.5^{p_3}.7^{p_4}....$, So I am interested a direct way of calculating $p_1$ and $p_3$ with just $l$ and $r$



I am just curious about it. I just want $2$ & $5$, but if there is a general solution for any prime number, It would be great if you mention that.


Answer



Let, us define the product of first $n$ integers by $n!$.



Now,highest power of prime $p$ contained in $n!$ is given by-



$$p_{\text{highest power}}=\lfloor\frac{n}{p^1}\rfloor+\lfloor\frac{n}{p^2}\rfloor+\lfloor\frac{n}{p^3}\rfloor+...+\lfloor\frac{n}{p^n}\rfloor$$ where $p^n\leq n$ and $\lfloor x\rfloor$ is the greatest integer function.




For more information see this-De Polignac's Formula.


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...