3
$\begingroup$

Got an interesting problem from a friend.

How many zeroes does $n!$ end in when written in base $n$?

For every factor of $n$ in $n!$, I know that there will be $1$ $0$ added. However, I'm not really sure how to proceed from here.

EDIT: A question I'm curious about: what would the value of $\frac{\#\{\text{number of zeros in $n!$ in base $n$}\}}{n}$ be?

$\endgroup$
  • $\begingroup$ This is mostly problem 3/3/27 from USAMTS round 3. $\endgroup$ – Daniel Fischer Dec 7 '15 at 14:36
4
$\begingroup$

In general, we want to write $n! = n^km$ where $k$ is maximal, and $k$ will be the number of zeros when $n!$ is written in base $n$.

Let's split the question into three cases:

  1. $n=p$ is prime.

  2. $n$ is square free.

  3. $n$ is arbitrary.

In the first case, $p! = p(p-1)!$, and since $p\nmid(p-1)!$, we see that $p!$ has $1$ zero in base $p$.

In the second case, let $n = p_1\ldots p_n$ where $p_1<p_2<\cdots<p_n$ are the prime factors of $n$. If $p_n^k\mid n!$, then $p_i^k\mid n!$ for every $n$, and this $k$ is maximal, so we only need to work out the number of times $p_n$ divides $n!$, and this will be $$\frac n {p_n}+\lfloor\frac n{p_n^2}\rfloor+\lfloor\frac n{p_n^3}\rfloor+\cdots.$$

This approach fails in the general case. For example, if $n=24 = 2^3 \cdot 3$, we now need three times as many twos as threes, and indeed, one can show that $$n! = 2^{22}3^{10}m = 24^7m'$$ so looking at the largest prime alone won't be enough. We will need to consider each of the primes dividing $n$. Suppose that $$n = p_1^{k_1}p_2^{k_2}\cdots p_n^{k_n}$$ and let $$m_i = \frac 1{k_i}\left(\frac n{p_i}+\lfloor\frac n{p_i^2}\rfloor+\lfloor\frac n{p_i^3}\rfloor+\cdots \right)$$

Then the number of zeros of $n!$ in base $n$ will be $$\min_i(\lfloor m_i\rfloor).$$

$\endgroup$
  • $\begingroup$ wonderfull !!!!! $\endgroup$ – Abr001am Dec 7 '15 at 11:51
  • $\begingroup$ The ratio between that and $n$ is at least $\max_i k_i(p_i-1)$ $\endgroup$ – Empy2 Dec 7 '15 at 13:43
2
$\begingroup$

For 10 we check the largest prime factor powers(powers of 5) of 10. So in any base we should find the number of largest prime factor exponent of 10(in that base). For example in base 26, it's 13.

$\endgroup$
  • 4
    $\begingroup$ But for $n =24$, you need three times as many $2$s as $3$s. $\endgroup$ – Empy2 Dec 7 '15 at 11:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.