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!:
$latex \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:
$latex \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:
$latex \displaystyle \epsilon(n,p)=|\alpha^{*}(n,p) - \alpha(n,p) |= \alpha^{*}(n,p) - \alpha(n,p)$
$latex \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 $latex \lfloor x \rfloor = x - \left\{ x \right\}$ to get another beautiful expression for the error function:
$latex \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 $latex \epsilon(n,p)$:
$latex \epsilon(n,2)=A011371(n)=n-A000120(n)$, References [1] and [2]
$latex \epsilon(2^{n},2)=1$
$latex \epsilon(2^{n}+1,2)=2$
$latex \epsilon(p^{n},p)=0; \; (p > 2)$
$latex \epsilon(p^{n}-1,p)=n$
$latex \epsilon(p^{n}+1,p)=0; \; (p > 3)$
More facts about Legendre´s $latex \alpha(n,p)$
$latex \alpha(n,2)$ gives also the number of 1's in binary expansion of $latex n$ (or the sum of all its binary digits).
And if we extend the range of this formula, been $latex b$ any number not necessarily prime, then:
$latex \displaystyle \alpha(b^{n},b)=\frac{b^{n}-1}{b-1}=R_{n}^{(b)}$
It gives the base $latex b$ repunits, and so for base $latex 2$:
$latex \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
