## NOTES ON LEGENDRE´S FORMULA

18 12 2009

MORE FACTS ABOUT PRIME FACTORIZATION OF FACTORIALS.

In the previous post, we introduced these functions, just as a small trick to calculate the limit we were looking for, but unlikely of what they seem to be, they are less artificial than expected.

Legendre´s formula for the exponent of p in the prime factorization of n!:

$\displaystyle\alpha(n,p)=\sum _{i=1}^{\lfloor log_p(n)\rfloor}{ \bigg\lfloor\frac{n}{p^i} \bigg\rfloor }= \sum _{i=1}^{\infty} { \bigg\lfloor\frac{n}{p^i} \bigg\rfloor}$

Integer Approximation for the Legendre´s formula:

$\displaystyle \alpha^{*}(n,p)=\bigg\lfloor \frac{n}{p-1}\bigg\rfloor = \bigg\lfloor\sum _{i=1}^{\infty}{\frac{n}{p^i}}\bigg\rfloor$

The diference between one function and its approximation is the error function.

Error Function for the Legendre´s formula:

$\displaystyle \epsilon(n,p)=|\alpha^{*}(n,p) - \alpha(n,p) |= \alpha^{*}(n,p) - \alpha(n,p)$

$\displaystyle \epsilon(n,p)= \bigg\lfloor\sum _{i=1}^{\infty}{\frac{n}{p^i}}\bigg\rfloor - \sum _{i=1}^{\infty} { \bigg\lfloor\frac{n}{p^i} \bigg\rfloor }$

We can use $\lfloor x \rfloor = x - \left\{ x \right\}$ to get another beautiful expression for the error function:

$\displaystyle \epsilon(n,p)= \sum _{i=1}^{\infty} { \left\{ \frac{n}{p^i} \right\} } - \left\{ \sum _{i=1}^{\infty}{\frac{n}{p^i}} \right\}$

This function shows fractal behavior:

Particular Values for $\epsilon(n,p)$:

$\epsilon(n,2)=A011371(n)=n-A000120(n)$, References [1] and [2]

$\epsilon(2^{n},2)=1$

$\epsilon(2^{n}+1,2)=2$

$\epsilon(p^{n},p)=0; \; (p > 2)$

$\epsilon(p^{n}-1,p)=n$

$\epsilon(p^{n}+1,p)=0; \; (p > 3)$

More facts about Legendre´s $\alpha(n,p)$

$\alpha(n,2)$ gives also the number of 1’s in binary expansion of $n$ (or the sum of all its binary digits).

And if we extend the range of this formula, been $b$ any number not necessarily prime, then:

$\displaystyle \alpha(b^{n},b)=\frac{b^{n}-1}{b-1}=R_{n}^{(b)}$

It gives the base $b$ repunits, and so for base $2$:

$\alpha(2^{n},2)=2^{n}-1=M_{n}$

It gives the Mersenne Numbers.

Amazingly, this uninteresting topic, at first sight, becomes a joint between: Repunits, Mersenne numbers, Factorials, primes, fractals, counting of digits…

Number Theory is it!

References:

[1]-A011371-n minus (number of 1’s in binary expansion of n). Also highest power of 2 dividing n!. The On-Line Encyclopedia of Integer Sequences!
[2]-A000120-1’s-counting sequence: number of 1’s in binary expansion of n (or the binary weight of n). The On-Line Encyclopedia of Integer Sequences!
[3]-Cooper, Topher and Weisstein, Eric W. “Digit Sum.” From MathWorld–A Wolfram Web Resource. http://mathworld.wolfram.com/DigitSum.html

Archives: