2
$\begingroup$

Exponent of $p$ in the prime factorization of $n!$ is given by $\large \sum \limits_{i=1}^{\lfloor\log_p n \rfloor } \left\lfloor \dfrac{n}{p^i}\right\rfloor $. Can this sum be simplified further to some direct expression so that the number of calculations are reduced?

$\endgroup$
  • 2
    $\begingroup$ This is an incredibly small calculation... $\endgroup$ – user98602 Aug 9 '14 at 17:18
  • 1
    $\begingroup$ I am looking at @robjohn 's reply in below thread which shows that the sum simplifies to $\dfrac{n-\lfloor \log_p n\rfloor }{p-1}$ , but I don't really understand it and it is not giving correct answer for n=20 and p=2 math.stackexchange.com/questions/590885/… $\endgroup$ – ganeshie8 Aug 9 '14 at 17:19
  • 1
    $\begingroup$ robjohn's answer says that the sum simplifies to $\dfrac{n-\sigma_p(n)}{p-1}$, where $\sigma_p(n)$ is the sum of the digits of $n$ in the base-$p$ representation, just like David Holden's answer here. Where did you get the $\lfloor \log_p n\rfloor$ from? $\endgroup$ – Daniel Fischer Aug 9 '14 at 17:31
  • $\begingroup$ @DanielFischer, he seems to have figured out about the digit sum... if $i > \log_p n$ then $p^i > n$ and the floor of the fraction is zero. $\endgroup$ – Will Jagy Aug 9 '14 at 17:39
  • $\begingroup$ @WillJagy I was referring to the formula in the comment, not the bound on the sum. (Didn't even notice that there appeared a $\lfloor \log_p n\rfloor$ too.) $\endgroup$ – Daniel Fischer Aug 9 '14 at 17:41
3
$\begingroup$

yes:

$$ \frac{N-\sigma_p(N)}{p-1} $$ where $\sigma_p(N)$ is the sum of digits in the $p$-ary expression of $N$

$\endgroup$
  • $\begingroup$ I think $\sigma_p (N) $ is same as $\lfloor \log_p N\rfloor$ ? i am trying to work below example : exponent of 2 in prime factorization of $20!$ is $18$ : wolframalpha.com/input/?i=prime+factorization+of+20%21 but your expression gives a different number : $\dfrac{20-\lfloor \log_2 20\rfloor }{2-1} = 16$ $\endgroup$ – ganeshie8 Aug 9 '14 at 17:33
  • $\begingroup$ @GaneshTadi No. In binary, $20$ is $10100$, so the digit sum of $20$ in base-$2$ is $2$. $\frac{20-2}{2-1} = 18$, as it should be. $\lfloor \log_p n\rfloor$ is one less than the number of digits in base $p$. $\endgroup$ – Daniel Fischer Aug 9 '14 at 17:35
  • $\begingroup$ if in binary $N=1101101$ then $\sigma_2(N) = 1+1+0+1+1+0+1=5$ $\endgroup$ – David Holden Aug 9 '14 at 17:35
  • $\begingroup$ Gotcha :) I see my error in interpreting the formula, thanks a lot xD $\endgroup$ – ganeshie8 Aug 9 '14 at 17:37
1
$\begingroup$

note what Daniel says. $\lfloor \log_p N\rfloor$ is the exponent of $p$ in $N$ not in $N!$. let $P_N$ be the exponent of $p$ in $N!$ and consider $P_{N+1}$.

if $N+1$ is not divisible by $p$ then the least significant $p$-ary digit of $N$ increases by $1$ and so $$ N+1 - \sigma_p(N+1) = N - \sigma_p(N) $$ and the exponent is unchanged.

suppose $N+1$ is divisible by $p^r$ for $r \gt 0$ but not by $p^{r+1}$ then each of the $r$ least significant binary digits must take the value $p-1$ but $1$ is added to the $r^{\text{th}} $ digit, which is not equal to $p-1$ hence: $$ \sigma_p(N+1) = \sigma_p(N)+1 - r(p-1) $$ and $$ N+1 - \sigma_p(N+1) = N - \sigma_p(n) + r(p-1) $$ hence $$ P_{N+1} = \frac{N+1 - \sigma_p(N+1) }{p-1} \\ = P_N + r $$

$\endgroup$
1
$\begingroup$

The idea of this theorm is to reduce manual calculation , try to find exp of 2 for (23263662!) :P so i guess its fair to follow the theorm . Origion theorm was $\large \sum \limits_{i=1}^{\infty} \left\lfloor \dfrac{n}{p^i}\right\rfloor$ , the floor log n function come from condition that i<=n thus any i after n give term of zero.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.