Question

show that the exponent of a prime \(\large p\) in the prime factorization of \(\large n!\) is

\[\Large \sum \limits_{i=1}^c \left\lfloor \dfrac{n}{p^i}\right\rfloor\]

where \(c\) is the # of digits of \(\large n\) in base-\(p\) number system

Answer 1

for example : \(\large n=20!\)
\(\large 20\) takes \(5\) digits in base-\(2\) number system : \(\large 10100\)

exponent of \(2\) in prime factorization of \(\large 20!\) = \(\large \sum \limits_{i=1}^5 \left\lfloor \dfrac{20}{2^i}\right\rfloor = 18\)

Answer 2

basically that formula gives the \(power\) of a prime number in the prime factorization of \(n!\)

prime factorization of \(\large 20!\) :
http://www.wolframalpha.com/input/?i=prime+factorization+20%21
Notice that the power of \(2\) is \(18\) as given by the formula

Answer 3

let me know if there is any specific part that doesn't make sense... I'll modify/try to explain :)

Answer 4

So, let's see. Every other factor of 20! contains a factor of 2, (that's 10), every other one of those contains another factor of 2, (that's 5 more), and every other one of those contains another factor of 2, making 18 in all. So I suppose it is not breaking news that the example checks out.

Answer 5

i think the same, the formula is counting number of 2's, 4's, 8's, 16's etc that occur in \(n!\)

that base-\(p\) part is bit throwing me off in the question, how does number of digits of \(n\) in base-\(p\) give us the upper limit \(c\) ?

Answer 6

for n=31

\[ \large \sum \limits_{i=1}^5 \left\lfloor \dfrac{31}{2^i}\right\rfloor\]

Answer 7

yes! it looks the upper limit doesnt matter as for i>5 we get all 0's,
so im thinking the upper limit could as well be infinity... i don't really get that base-\(p\) part yet :o

Answer 8

Okay. Back to the general statement.
The number of factors of p in the prime factorization of n! (I'll call t)

\[ \Large t= \sum \limits_{i=1}^{\sigma_p (n)} \left\lfloor \dfrac{n}{p^i}\right\rfloor \]

where \(\large \sigma_p (n) \) is the number of digits in the base-p representation of n,

Answer 9

Suppose there is a q which is the least such that \(\large p^q > n\), then \(\large p^q \) is also larger than any of the factors less than n. Then \(\large p^{q-1} \le n\), according to how we defined q. Since n! is the product of n and all the positive integers less than n, at least one of n and the positive integers less than n is equal to \(\large p^{q-1} \).

\(\large \sigma_p (p^{q-1}) = q\)

\(\large \sigma_p (n) \ngtr q\), because \(p^q > n\) (definition of q).\)

\(\large \sigma_p (n) \nless q\), because \(\large n \ge p^{q-1} \)

So, \(\large \sigma_p (p^{q-1}) = q = \sigma_p (n) \)

That's all there is to the mystery of the number of digits. What remains is proving the thrust of the proposition, which stangely enough now seems intuitively obvious to me.

Answer 10

Now is should be seen the proposition is inexact. The last term of the sum must always be zero

Here is the example: \( n=20!\) 20 takes 5 digits in base-2 number system:: 10100
\[\large \sum \limits_{i=1}^5 \left\lfloor \dfrac{20}{2^i}\right\rfloor = 18\]

But \(2^5 = 32 \), so the last term must always be zero. It does no harm, but it is pointless.

Answer 11

that remind me of last lesson in NT at univ hehe

Answer 12

I think you must be talking about it:

http://openstudy.com/users/waterineyes#/updates/521052bbe4b00ebc7dbf07f2
http://openstudy.com/users/waterineyes#/updates/52104dcde4b00ebc7dbf06d7

Answer 13

The first link is going to be good... :)

Answer 14

Ooh this is really cool, it's rare for me to see floor functions haha, where can I learn more about this?

Answer 15

This is almost identical to a project euler question I worked on about a week ago, http://projecteuler.net/problem=5

Answer 16

cool :D

Answer 17

reminds me of chinese remainder theorem
guess we need to find a number such that :

\[\large \begin{align} \\ n &\equiv 0 \mod 1 \\ &\equiv 0 \mod 2 \\
&\equiv 0 \mod 3 \\
&\equiv 0 \mod 4 \\
&\cdots \\
&\equiv 0 \mod 20 \\

\end{align} \]

Answer 18

*least positive number

Answer 19

but this is not related to exponent of a prime in n!, right ?

Answer 20

Dan can probably explain this better than I can, but for the project euler question we needed to find the smallest possible number divisible by all the numbers less than 20. So what we did is went through the prime numbers and raised it to the highest possible power we could without exceeding 20.

To do that, you would have to do: \[\LARGE p^{ \lfloor{\log_p20 \rfloor}}\] So we can see that we'll get for p=2 that this will give us 16.

Slightly related right?

Answer 21

omg! isn't it a LCM problem ?

Answer 22

Not exactly I think. The prime factorization of the smallest number divisible by all the numbers less than 20 is:

\[\Large 2^4 * 3^2 * 5^1 * 7^1 * 11^1 * 13^1 * 17^1 * 19^1 = 232792560 \]

Answer 23

what would be a function we can come with mathematically that would automatically cut off everything after decimal place

Answer 24

I see... clever method xD

Answer 25

:D

Answer 26

still bit confusing...
so you're saying the exponent(\(e_i\)) of prime in the prime factorization of a number(\(n\)) cannot exceed \(\log_p n\)

Answer 27

the reasoning is pretty simple actually

Answer 28

and it will include all the primes <= n

Answer 29

there are a certain number of primes

Answer 30

for any chosen number.. ie lets say 20

Answer 31

every other number is prime1^k * prime2^j

Answer 32

so first we see how many of the exponents of 2s did we miss out on in our given number 20

Answer 33

which is 2,4,8,16, so 2^4 fit in... or floor of Log_2 or 20

Answer 34

now we check the next prime how many of those primes can fit in

Answer 35

we check all primes below root 20

Answer 36

log_2 of* 20

Answer 37

and the multiplication of these primes and their exponents, must give the lowest number possible that is divisible by all numbers from 1 to 20

Answer 38

got it :) thats because all the other numbers can be cooked up from existing prime powers in the factorization... really a very nice method to find LCM !!

Answer 39

right, but how do we apply this to your problem

Answer 40

\(\large \log_p n\) gives number of digits of \(n\) in base-\(p\), right ?
(more or less )

Answer 41

thats the link i think

Answer 42

floor \(log_p n \)

Answer 43

this should work then : \[\large \sum \limits_{i=1}^{\lfloor\log_p n \rfloor } \left\lfloor \dfrac{n}{p^i}\right\rfloor\]

Answer 44

yeah!!

Answer 45

wait...

Answer 46

noo?

Answer 47

why noo ?

Answer 48

Yes.

Answer 49

I dont know

Answer 50

why does it work?? it wont work for the case n=20 though

Answer 51

\( log_2 20 \approx 4.23\)

Answer 52

you need the upper found on the sum to be 5. but if you do it for n!. you only get an upper found of 4* when p =2

Answer 53

it works beautifully i think... upper limit of 5 is useless as pointed out by @LarsEighner some 100 replies back...

Answer 54

but this log form is not so useful in extending/deriving further results

Answer 55

You do not need the upper bount to be 5. In the original formulation in the question, it was found the last term of the sum must always be zero.

Answer 56

^^
example : when n=32, upperbound becomes 6, and the last term of sum would be 0

Answer 57

The discrepancy in the original come from the fact that the low order digit is the base to the zeroth power, that is it is the unit digit. Therefore the highest power of a base that can be expressed in q digits is the q-1 power.

Answer 58

okayy i get it thats awesome

Answer 59

with some simplification we can get that sum into below cool form :

exponent of \(p\) in the prime factorization of \(n!\) is \[\large \sum \limits_{i=1}^{\lfloor\log_p n \rfloor } \left\lfloor \dfrac{n}{p^i}\right\rfloor = \dfrac{n-\lfloor \log_p n\rfloor }{p-1}\]

Answer 60

maybe try the proof in free time :)

Answer 61

If you do not mind zero terms, you might as well make the upper index infinite. @ganeshie8 pointed this out to me in a message I did not understand at the time. However I would like the upper index to be exact, because I am more comfortable working the powers down (that is taking the sum backwards). That does not really matter: just a quirk in my thinking.

Answer 62

agree :) previous result requires some tweaking i guess...

Answer 63

i see that expression was not working, but it would be great if we can simplify that sum... then we can easily work out the exponent of a prime in 10000000000! without evaluating log_p(10000000000) terms painfully and adding them

Answer 64

What

\[ \large \left\lfloor \dfrac{n}{p^i}\right\rfloor \] is saying to us is: find the greatest \(\Large j \le n\) that is evenly divisible by \(\Large p^i \), divide it by \(\Large p^i\) and return the result \(\Large t_i\).

\[ \Large {j \over p^i} = t_i \]

Now the claim is, no number < j can contain more factors of \(\Large p^t\) than j.

Therefore \(\Large t_i\) is the exponent on \(\Large p^i\) in "a" (not "the prime") factorization of n!.

Eventually we have as factors of n!

\[\Large (p^1)^{t_1}(p^2)^{t_2}(p^3)^{t_3}...(p^{\left\lfloor log_p n \right\rfloor})^t_{\left\lfloor log_p n \right\rfloor}) (junk)\]

However, in a prime factorization we only want p, so invokeing laws of exponents, yadda, yadda we have

\[\Large (p^t)(prime\;junk)\]

Answer 65

:) thanks everyone !
here is a nice discussion on further simplifying the formula
http://math.stackexchange.com/questions/892215/exponent-of-p-in-the-prime-factorization-of-n/892266#892266

Answer 66

well this is what im thinking of let p , be any factor of n then then
\(p,2p,3p,...tp \) such that \(tp \le n\) also factorz of n thus \(t =\left[ n/p \right]\) so same with \(p^2...p^i\)
\(p^2,2p^2,3p^2,...,tp^2 =[n/p^2]p^2\) such that \(tp^2 \le n\)
....
\(p^i,2p^i,3p^i,...tp^i=[n/p^3]p^3 \) such that \(tp^i \le n\)

after infinitly presentation we could get exponent of the highest power of prime \(\sum_{i =1}^\infty \left[ n/p^i\right]\)

now result is finite since p^i <=n , and \( \left[ n/p^i\right]=0 \) for p^i>n so we can replace infty with the condition \(p^i\le n\) \(i\le \log_p n\) so we would finally get \(\sum_{i =1}^{\log_p n }= \left[ n/p^i\right]\) hope this was usfull if you have any doubt , ill be glad to explain ;)

Answer 67

made typo there should be some comma
\( p^i≤n\)
\( i≤log_p n\) so we would get

\(\large \sum_{i=1}^{\log_pn} [n/p^i] \)

Answer 68

if p is a factor of n , then thos are factorz of n!
\(\large p,2p,3p,4p ,......,t_1p\)
\(\large p^2,2p^2,3p^3,.....,t_2p^2\)
\(\large p^3,2p^3,3p^3,.....,t_3 p^3\)
,,,,,
\(t_i <n\) thus if we continued like this we would get some G ,
at the end s.t G is the greatest factor of n! that devide p
then \(G=P^g\)

\(\large p^g,2p^g,3p^g,.....,t_k p^g\)
(the first term )
so its like g=t_1+t_2+t_3...t_k