Difference between revisions of "Legendre's Formula"
m |
(Added a proof) |
||
Line 1: | Line 1: | ||
'''Legendre's Formula''' states that | '''Legendre's Formula''' states that | ||
− | <cmath>e_p(n!)=\sum_{i\ | + | <cmath>e_p(n!)=\sum_{i=1}^{\infty} \left\lfloor \dfrac{n}{p^i}\right\rfloor =\frac{n-S_{p}(n)}{p-1}</cmath> |
where <math>p</math> is a prime and <math>e_p(n)</math> is the [[exponent]] of <math>p</math> in the [[prime factorization]] of <math>n</math> and <math>S_p(n)</math> is the [[sum]] of the [[digit]]s of <math>n</math> when written in [[base]] <math>p</math>. | where <math>p</math> is a prime and <math>e_p(n)</math> is the [[exponent]] of <math>p</math> in the [[prime factorization]] of <math>n</math> and <math>S_p(n)</math> is the [[sum]] of the [[digit]]s of <math>n</math> when written in [[base]] <math>p</math>. | ||
==Proof== | ==Proof== | ||
− | {{ | + | === Part 1 === |
+ | We could say that <math>e_p(n!)</math> is equal to the number of multiples of <math>p</math> less than <math>n</math>, or <math>\lfloor \frac{n}{p}\rfloor</math>. But the multiples of <math>p^2</math> are only counted once, when they should be counted twice. So we need to add <math>\lfloor \frac{n}{p^2}\rfloor</math> on. But this only counts the multiples of <math>p^3</math> twice, when we need to count them thrice. Therefore we must add a <math>\lfloor \frac{n}{p^3}\rfloor</math> on. We continue like this to get <math>e_p(n!)=\sum_{i=1}^{\infty} \left\lfloor \dfrac{n}{p^i}\right\rfloor</math>. This makes sense, because the terms of this series tend to 0. | ||
+ | |||
+ | === Part 2 === | ||
+ | Let the base <math>p</math> representation of <math>n</math> be <math>e_xe_{x-1}e_{x-2}\dots e_0</math>, where <math>e_i</math> is a digit for all <math>0\leq i\leq x</math>. Therefore the base <math>p</math> representation of <math>\lfloor \frac{n}{p^i}\rfloor</math> is <math>e_xe_{x-1}\dots e_{x-i}</math>. Note that the infinite sum of these numbers (which is <math>e_p(n!)</math>) is | ||
+ | |||
+ | <math>\sum_{j=1}^{x} e_j(p^{j-1}+p^{j-2}+\cdots +1)=\sum_{j=1}^{x} e_j(\frac{p^j-1}{p-1})=\frac{\sum_{j=1}^{x} e_jp^j -\sum{j=1}^{x} e_j}{p-1}</math> | ||
+ | |||
+ | <math>=\frac{(n-e_0)-(S_p(n)-e_0)}{p-1}=\frac{n-S_p(n)}{p-1}</math>. | ||
{{stub}} | {{stub}} |
Revision as of 10:02, 31 August 2009
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
.
Proof
Part 1
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
is a digit for all
. Therefore 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.