Number theory

[thankont]

What is the highest power of 7 in 5000! (five thousand factorial)?
Ans: 832

[Swiss_boy]

5000/7 = 714
714/7 = 102
102/7 = 14
14 / 7 = 2
2 / 7 = 0

714+102+14+2+0 = 832

Don't ask me how. I just know that to identify power of a number in a factorial, u need to sum the successive quotients.

[aashu_79]

thats a great approach..

i think the logic goes like this.. consider highest power of 2 that devides 10!

10! = 1*2*3*4*5*6*7*8*9*10

we know that every 2nd(2^1) number is even no, hence divisible by 2
numbers of such factors of 2 in 10! = 10/2 = 5 (so 2^5 divides 10!)

But there are more numbers, every 4th (2^2) number has an extra factor of 2(apart from what we have already counted).

numbers of such additional factors of 2 in 10! = 10/4 = 2 (integral part of 10/4)

similarly every 8th (2^3) number has one additional factor of 2 that is not counted yet.

numbers of such additional factors of 2 in 10! = 10/8 = 1 (integral part of 10/8)

so, in general highest power of a number x that devides n! is given by

= n/x + n/x^2 + n/x^3.... +n/x^k (where k is such that x^k <= n)
each term here denotes the integral part of the division.

[thankont]

great work from both of you v_spirada and of course aashu.
logic of v_spirada is that first we see how many divisors of 7 are there
in numbers 1...5000. There are 5000/7 = 714. Now that we are done with 7 look how many divisors
of 7^2 are there in 5000 so 5000/7^2 = 714/7= 102 etc.
so results are equivalent since 5000/7 + 714/7+... = 5000/7+5000/7^2+...

[natalie82]

thnx for posting this q. I would have surely missed this one if it were on my exam!!

[MikeJung]

thanks for posting.

[asdada1]

5000/7 = 714
714/7 = 102
102/7 = 14
14 / 7 = 2
2 / 7 = 0

714+102+14+2+0 = 832

Don't ask me how. I just know that to identify power of a number in a factorial, u need to sum the successive quotients.

great stuff

[Divin]

great !

[target_g]

Is it not simply sum of - 5000/7, 5000/49, 5000/7^3, ... 5000/7^5

[pach2212]

target_g.

You are correct. the method illustrated above is just another way of presenting the same.