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:

[a]-121809-Notes on Legendre´s Formula.nb


Advertisements

Actions

Information




%d bloggers like this: