My question is regarding the Legendre's formula (https://en.wikipedia.org/wiki/Legendre%27s_formula#Applications) (in it we calculate exponent of prime in n! where n is any natural number)
according to legendre's formula,
power of $x$ in $n! = \lfloor n/x\rfloor + \lfloor n/x^2\rfloor + ... + \lfloor n/x^k\rfloor$ where $x^k \leq n \lt x^{(k + 1)}$
Is it same as if I calculate like this
$y_1 = \lfloor n/x\rfloor$
$y2 = \lfloor y_1/x\rfloor $
$y_3 = \lfloor y_2/x\rfloor$
...
$y_n = \lfloor y_{n-1}/x\rfloor$
then add all y, that is, exponent of $x$ in $n! = y_1 + y_2 + y_3 + y_4 + \dots + y_n$
Is the first method (Legendre's formula) same as second method?
I am asking this because when I calculate by hand, second method will be faster to calculate
If both methods are same, please provide an explanation too :)
Yes, you are using a particular case of the following result ( for each summand) :
Let $a_1,\dots,a_k$ be positive integers and $\alpha$ a positive real.
Then $\lfloor \alpha / (a_1a_2 \dots a_n) \rfloor$ is the same as the final term of the sequence $\alpha_0,\alpha_1,\dots, \alpha_n$ when $\alpha_0 = \alpha$ and $\alpha_{i+1} = \lfloor \alpha_i/a_i\rfloor $.
Proof: Write $\alpha$ as $k(a_1\dots a_n) + \beta$ with $\beta\in [0,1)$.
We must prove $\alpha_n$ is equal to $k$.
We can prove that each $\alpha_i$ is of the form $k(a_{i+1}\dots a_n) + \beta_i$ with $\beta_i \in [0,1)$ by induction.