Waste less time on Facebook — follow Brilliant.
×

Number theory

What is the algorithm to find exponent of a prime p in n! ?

Note by Goutam Narayan
3 years, 2 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

The highest power of p that divides n! is

\(\displaystyle\sum_{i=1}^{j}\left \lfloor \frac{n}{p^i} \right \rfloor\)

,where j is the biggest integer, for which \(p^j<n\) Bogdan Simeonov · 3 years, 2 months ago

Log in to reply

@Bogdan Simeonov I think it should be \(p^j \leq n\) Labib Rashid · 3 years, 2 months ago

Log in to reply

@Labib Rashid True. But you could save yourself from the trouble by just putting \[\displaystyle \sum_{i=1}^\infty \lfloor\frac{n}{p^i}\rfloor\]. Mursalin Habib · 3 years, 2 months ago

Log in to reply

@Mursalin Habib He asked for an algorithm. A code with your algo would run for an infinite time. Labib Rashid · 3 years, 2 months ago

Log in to reply

@Labib Rashid Oh! I think I missed the word 'algorithm'. But I don't think the OP meant algorithm literally [It's tagged with number theory]. Despite that, you're right. That algorithm will go on forever in the natural sense. I just posted that because I think that looks cool :) Mursalin Habib · 3 years, 2 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...