Difference between revisions of "Legendre's Formula"
m (→Part 2) |
m (fixing broxen latex) |
||
Line 14: | Line 14: | ||
Let the base <math>p</math> representation of <math>n</math> be <cmath>e_xe_{x-1}e_{x-2}\dots e_0</cmath> where the <math>e_i</math> are digits in base <math>p.</math> Then, the base <math>p</math> representation of <math>\lfloor \frac{n}{p^i}\rfloor</math> is <cmath>e_xe_{x-1}\dots e_{x-i}.</cmath> Note that the infinite sum of these numbers (which is <math>e_p(n!)</math>) is | Let the base <math>p</math> representation of <math>n</math> be <cmath>e_xe_{x-1}e_{x-2}\dots e_0</cmath> where the <math>e_i</math> are digits in base <math>p.</math> Then, the base <math>p</math> representation of <math>\lfloor \frac{n}{p^i}\rfloor</math> is <cmath>e_xe_{x-1}\dots e_{x-i}.</cmath> Note that the infinite sum of these numbers (which is <math>e_p(n!)</math>) is | ||
− | \begin{ | + | <cmath>\begin{align*} \sum_{j=1}^{x} e_j(p^{j-1}+p^{j-2}+\cdots +1) &= \sum_{j=1}^{x} e_j \left( \frac{p^j-1}{p-1} \right) \ |
+ | &=\frac{\sum_{j=1}^{x} e_jp^j -\sum_{j=1}^{x} e_j}{p-1} \ | ||
+ | &=\frac{(n-e_0)-(S_p(n)-e_0)}{p-1} \ | ||
+ | &=\frac{n-S_p(n)}{p-1}. | ||
+ | \end{align*}</cmath> | ||
{{stub}} | {{stub}} |
Revision as of 09:13, 9 November 2015
Legendre's Formula states that
where is a prime and is the exponent of in the prime factorization of and is the sum of the digits of when written in base .
Proofs
Part 1
We use a counting argument.
We could say that is equal to the number of multiples of less than , or . But the multiples of are only counted once, when they should be counted twice. So we need to add on. But this only counts the multiples of twice, when we need to count them thrice. Therefore we must add a on. We continue like this to get . This makes sense, because the terms of this series tend to 0.
Part 2
Let the base representation of be where the are digits in base Then, the base representation of is Note that the infinite sum of these numbers (which is ) is
This article is a stub. Help us out by expanding it.