1
$\begingroup$

Let $N$ a positive integer. Denote $\mathcal{P}$ the set of prime numbers. I have to show that \begin{align} \log(N!) = \sum_{p^{\nu}\leq N \\ p\in \mathcal{P}} \left\lfloor\dfrac{N}{p^{\nu}}\right\rfloor \cdot \log(p) \end{align}

To do it, I'd like to prove a more general statement, which says \begin{align} \sum_{n\leq x} \log(n) = \sum_{p^{\nu}\leq x \\ p\in \mathcal{P}} \left\lfloor\dfrac{x}{p^{\nu}}\right\rfloor \cdot \log(p) \qquad \forall\, x\geq1 \end{align}

$\textbf{My attempt}$:

I tried to using the Fundamental Theorem of Arithmetics to write every $n\in \mathbb{N}^{*}$ as product of primes, i.e. \begin{align} n= \prod_{p\in P \\ v\geq 0} p^{\nu} \ \end{align} Then, \begin{align} \log(n) = \sum_{p\in \mathcal{P}\\ v\geq 0} \nu \cdot \log(p) \qquad (\ast) \end{align} Now I have some problem to rewrite $\sum_{n\leq x} \log(n)$ using $(\ast)$. I tried to find an equivalent condition to $n\leq x$ whithout success.

Any suggestions? Thanks in advance!

$\endgroup$
2
$\begingroup$

Hint: Instead of taking each integer of $N!=\prod_{n=1}^N n$ separately, take them all together and consider each prime on the entire factorial. Specifically, show that the largest $E$ such that $p^E\mid N!$ is $$ \sum_{\nu=1}^\infty\left\lfloor\frac N{p^\nu}\right\rfloor $$

$\endgroup$
2
$\begingroup$

Note that $\lfloor \frac{N}{p^\nu} \rfloor$ counts the number of multiples of $p^\nu$ that are at most $n$. Note that every multiple of $p$ contributes a factor of $p$ in $N!$, giving $\lfloor \frac{N}{p} \rfloor$ in the exponent of $p$. But every multiple of $p^2$ contributes an additional factor not already accounted for, giving an additional $\lfloor \frac{N}{p^2} \rfloor$ in the exponent. Repeating, we find that the exponent of $p$ is $\sum \limits_{p^\nu \le n} \lfloor \frac{N}{p^\nu} \rfloor$. Decomposing $N!$ into its prime factorisation now finishes the problem.

For further information, see the following: https://en.m.wikipedia.org/wiki/Legendre%27s_formula

$\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.