4
$\begingroup$

Given numbers $k$ and $n$ how can I find the maximum $x$ where: $n! \equiv\ 0 \pmod{k^x}$?

I tried to compute $n!$ and then make binary search over some range $[0,1000]$ for example compute $k^{500}$ if $n!$ mod $k^{500}$ is greater than $0$ then I compute $k^{250}$ and so on but I have to compute every time value $n!$ (storing it in bigint and everytime manipulate with it is a little ridiculous) And time to compute $n!$ is $O(n)$, so very bad. Is there any faster, math solution to this problem? Math friends?:) Cheers Chris

4 Answers 4

7

For a prime $p$, the highest power of $p$ that divides $n!$ is $f(n,p) = \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \left\lfloor \frac{n}{p^3} \right\rfloor + \dots.$

So if $k$ is prime, you have the answer. (You can plug in $k$ into the above formula in place of $p$.)

Else, let the prime factorisation of $k$ be $k = p_1^{e_1}p_2^{e_2}\dots p_r^{e_r}$. Then, the highest power of $p_i^{e_i}$ dividing $n!$ is $\displaystyle\left\lfloor\frac{f(n,p_i)}{e_i}\right\rfloor$. The minimum of this expression over all $i$ gives the answer for $k$.

  • 0
    Oh, my bad, wolfram has something like "quick calculate", but after pressing ENTER you got totally different result :) Thanks once again2011-07-07
4

Computing $n!$ it is a very bad idea for great numbers $n$. To find the desired exponent you should develop something similar to the Legendre formula.

You could also search for Legendre in the following document.

4

Here is a possible approach. If $p$ is prime, the largest value of $p$ dividing $n!$ is $\sum_{k=1}^\infty \left\lfloor {n\over p^k}\right\rfloor.$ If the number $k$ you are considering is easily factorable into primes, you can adapt this result to your needs.

  • 2
    @Chris: $\lfloor 10/8 \rfloor = 1$, not $0$. Similarly, for $k=3$, we have $\lfloor 10/3 \rfloor =3$ and $\lfloor 10/9 \rfloor = 1$, so $3+1=4$ is right. (And BTW you should think yourself about how to adapt this result for the case when $k$ is not prime; if you don't get it then see my answer.)2011-07-05
0

A little terminology: The highest power of a prime $p$ that can divide some number $m$ is called the multiplicity (or less memorably the $p$-adic order) of $p$ in $m$, denoted $\nu_p(m)$.

For a general $k$ you would need to consider the prime factors of $k$ in turn and find which $\dfrac{\nu_{p_i}(m)}{\nu_{p_i}(k)}$ is the least.

One common question is to ask how many trailing zeroes there are on some factorial. Then $k=10$ with single prime factors $2$ and $5$.

To find $\nu_p(n!)$ is a particularly rapid evaluation. Effectively we are being asked to sum the mulitplicities of $p$ across all the values up to $n$, and of course many of these values are coprime to $p$ - in fact only $s_1:=\left\lfloor \dfrac{n}{p} \right\rfloor$ values make any contribution. Then $s_2:=\left\lfloor \dfrac{n}{p^2} \right\rfloor=\left\lfloor \dfrac{s_1}{p} \right\rfloor$ have a second power of $p$ involved, and $s_3:=\left\lfloor \dfrac{n}{p^3} \right\rfloor=\left\lfloor \dfrac{s_2}{p} \right\rfloor$ have a third power of $p$, etc. So the simple process here is to repeatedly divide each term by the prime concerned until the term falls to zero.

For example, $\nu_2(555!) = 277+138+69+34+17+8+4+2+1 = 550$ and $\nu_5(555!) = 111+22+4 = 137$ so $555!$ has $137$ trailing zeroes.