The number of zeros in the expansion of $n!$ in base $12$

128 Views Asked by At

During an interview last year I was asked the following question:

How many zeros appear at the end of $n!$ in base $12$, where $n$ is a positive integer?

I applied the known Legendre formula for $p=3$ and then for $p=2$ (in the last case followed by a division by $2$). Then I realised that I couldn't compare the two series produced.

It turned out that the interviewer was an applied mathematician and considered the two series to be "equal".

So the question remained unanswered:

Which of the produced series is greater for each value of $n$?

1

There are 1 best solutions below

4
On

This is quite a nice problem, though a proper solution is pretty involved for a job interview.

Here's a compact way to repackage this: The largest power $k$ of a prime $p$ that divides $n!$ is the $p$-adic valuation $$v_p(n!) := \sum_{k = 1}^{\infty} \left\lfloor \frac{n}{p^k} \right\rfloor$$ of $n!$. Expanding this necessarily finite sum and applying a little middle school algebra shows that we can rewrite this as $$v_p(n!) = \frac{n - S_p(n)}{p - 1},$$ where $S_p(n)$ is the sum of digits of $n$ in base $p$. (So, if one already has access to the base-$2$ and -$3$ representations of $n$, this computation is very fast.)

Now, the largest power of $3$ that divides $n$ is $$\boxed{v_3(n!) = \tfrac{1}{2}(n - S_3(n))} ,$$ and the largest power of $4$ that divides $n$ is $$\boxed{\left\lfloor \tfrac{1}{2} v_2(n!)\right\rfloor = \left\lfloor \tfrac{1}{2} (n - S_2(n))\right\rfloor}$$ (note that $S_2(n)$ is just the number of $1$'s in the binary expansion of $n$). Thus, the largest power of $12$ that divides $n!$ (and therefore the number of $0$'s at the end of the base-$12$ representation of $n!$) is $$\color{#bf0000}{\boxed{Z_{12}(n) := \min \left\{\tfrac{1}{2}(n - S_3(n)), \tfrac{1}{2} (n - S_2(n))\right\}}} .$$

If $n$ is a power $2^a$ of $2$, $a \geq 3$, then $S_2(n) = 1$, and so $$\left\lfloor \tfrac{1}{2} (n - S_2(n))\right\rfloor = \left\lfloor \tfrac{1}{2} (n - 1)\right\rfloor = \tfrac{1}{2} n - 1 > \left\lfloor \tfrac{1}{2} (n - S_3(n))\right\rfloor ,$$ that is, the number of factors of $3$ in $n!$ is smaller than the number of factors of $4$. On the other hand, if $n$ is a power of $3$, the reverse is true, so it is not the case that one factor or the other always dominates for sufficiently large $n$.

Remark This last fact is not equivalent to saying that each dominates the other with equal probability; it could be an interesting problem to compute, e.g., how often factors of $3$ dominate, asymptotically, i.e., the limit $$\lim_{n \to \infty}\frac{\#\left\{\tfrac{1}{2}(n - S_3(n)) > \tfrac{1}{2} (n - S_2(n)) : 1 \leq n \leq N\right\}}{N} .$$

From the above analysis, we can see immediately how to choose bases that have this critical behavior wherein some powers of the prime factors of the base are on even footing; the next smallest after $12$ is $45 = 3^2 \cdot 5$. The smallest base in which three prime factors are on mutually equal footing is $2^6 \cdot 3^3 \cdot 7 = 12096$.