Base 12?

Disclaimer: I am relatively new in writing solutions, so I see myself as blind when it comes to telling the difference between pseudo-maths and maths-maths. If you happen to catch anything odd in this solution, please reply. If any of my "theories" are wrong, please reply as well so that everybody may benefit. :-)

Initial Thoughts of the Mind

$12$ can be prime factored into $2^2 \times 3$ . Furthermore, $N!$ can be factored into $12^a \times k$ where $a$ is the number of trailing zeroes and $12 \nmid k$ . From $12^a = 4^a \times 3^a = 2^{2a} \times 3^a$ , it follows that we need to find $\min(\left\lfloor{\frac{v_2(N)}{2}}\right\rfloor, v_3(N))$ where the function $v_p(n)$ is given as: $\begin{aligned} v_p(n) &= \sum_{i=1}^k \left\lfloor{\frac{n}{p^i}}\right\rfloor \\ \\ &= \left\lfloor{\frac{n}{p}}\right\rfloor+\left\lfloor{\frac{n}{p^2}}\right\rfloor+\left\lfloor{\frac{n}{p^3}}\right\rfloor+\dots+\left\lfloor{\frac{n}{p^k}}\right\rfloor, \end{aligned}$ where $k=\left\lfloor \log_p{n} \right\rfloor$ .

Note that we floor $\frac{v_2(N)}{2}$ to ignore any decimal points and remainders obtained from dividing by 2.

To simplify things, perhaps it might be possible to theorise which prime number (either $2$ or $3$ ) will be sparser throughout the product of the factorial $N!$ . When dealing with base $10$ , we could theorise that $5$ is sparser relative to $2$ and as such, we only counted the highest power of $5$ . With $2$ and $3$ however, it's rather difficult to tell. With base $10$ , $2^2 < 5$ , so we are reassured that the ratio of $2$ 's and $5$ ’s will eventually reach or exceed 2 : 1. With base $12$ , each $3$ has to be compensated with two $2$ 's. However, we aren't guaranteed that the growth will be entirely linear and keep a 2 : 1 ratio between the number of $2$ ’s and the number of $3$ ’s because $3 < 2^2$ . In this solution, I chose to count the number of 3's.

Developing a Fast Algorithm

Let's first obtain a rough estimate of our integer $N$ . We could do a linear search starting from $1$ all the way up to our integer $N$ but that would take much too long to test (for some, at least).

Instead, we can make use of the geometric-series-sum formula: $\begin{aligned} S = \frac{u_1 (1-r^n)}{1-r}, \end{aligned}$ where $u_1$ is the first term of the sequence, $r$ is the common ratio between consecutive terms, and $n$ is the number of terms in the geometric progression.

Now how can we apply this formula? Firstly, we can treat the summation of $v_p(n)$ as a sequence of integers $a_m \forall m \in Z$ . Treating this as a sequence, we can take $a_0 = N$ then iterate through all $a_i = \left\lfloor \frac{a_{i-1}}{p} \right\rfloor$ where $1 ≤ i ≤ k, k = \left\lfloor \log_p{n} \right\rfloor$ . Also from the theorem of $v_p(n)$ , we may observe each consecutive term experiencing a multiplicative factor of $\frac{1}{p}$ . We will use this multiplicative factor as our common ratio, $r$ .

We shall remove the mapping of the floor function for the simplicity of the geometric-series summation. (Note that, by waiving the floor function, we are subjecting our sum to an accumulation of continuous values. And this is the cause for the inaccuracy of this part of the algorithm, regardless of the fact that it's quick to use).

We can obtain an estimate for $v_p(n)$ by using the geometric-series-sum formula stated above and ignoring the floor function. (Mind though, that this will often lead to an estimate of $v_p(n)$ , and not its exact value.) By doing this, we have a convenient way of pinpointing the whereabouts of $N$ .

We shall state this function as $w_p(n)$ : $\begin{aligned} w_p(n) &= \sum_{i=1}^k \frac{n}{p^i} \\ \\ &= \frac{n (1 - \frac{1}{p^k})}{1-\frac{1}{p}} - n, \end{aligned}$ where $k=\left\lfloor \log_p{n} \right\rfloor$ .

To clarify the use of subtracting $n$ at the end, we need to acknowledge that $n$ itself is not supposedly part of our sum. We consider it the $a_0$ but our summation officially begins for $a_i$ when $i = 1$ .

Further simplification using algebra brings us to $\begin{aligned} w_p(n) &= \frac{n (p^k - 1)}{p^k (p - 1)} \end{aligned}$

To further simplify the equation, we could also treat the sequence from our previous theorems as an infinite geometric progression. By summing an infinite progression, smaller and smaller values will keep being added. As $i$ approaches zero, $a_i$ approaches 0. The series converges due to our common ratio, $r = \frac{1}{p}$ being in between $-1$ and $1$ (to be more precise, $0 < r < 1$ as we will never be getting a negative prime, $p$ ).

The sum of an infinite geometric progression goes: $\begin{aligned} S &= \frac{u_1}{1-r}, \end{aligned}$ where $u_1$ is the first term of the progression and $r$ is the common ratio.

Thus, we could restate $w_p(n)$ as $\begin{aligned} w_p(n) &= \sum_{i=1}^\infty \frac{n}{p^i} \\ \\ &= \frac{n}{1-\frac{1}{p}} - n \end{aligned}$ Further algebraic simplification leads us to $\begin{aligned} w_p(n) &= \frac{n}{p - 1} \end{aligned}$

Keep in mind that our current $w_p(n)$ is not entirely the same function as our previous $w_p(n)$ . Further consequences involve a less accurate value returned and a higher deviation from the exact value.

This, however, provides a straight-forward function to use since it is easy to manipulate and isolate variables.

Solving the Problem: Finding N

$w_p(n)$ will only provide us an estimate. We might possibly need to do a linear search and check every number after applying the formula for $w_3(n) = 121$ . $\begin{aligned} w_3(n) &= \frac{n}{3 - 1} \\ \\ 121 &= \frac{n}{2} \\ \\ 121 &= \frac{n}{2} \\ \\ n &= 242 \end{aligned}$

Using this estimate of $N$ , we can test this value (and possibly consecutive values) using $v_p(n)$ . First we count the number of $2$ 's using $v_2(242)$ : $\begin{aligned} v_2(242) &= \left\lfloor{\frac{242}{2^1}}\right\rfloor + \left\lfloor{\frac{242}{2^2}}\right\rfloor + \dots + \left\lfloor{\frac{242}{2^7}}\right\rfloor \\ \\ &= 237 \end{aligned}$ We stop at $2^7$ since $\left\lfloor{\log_2{242}}\right\rfloor = 7$ .

We also need to count the number of $3$ 's using $v_3(242)$ : $\begin{aligned} v_3(242) &= \left\lfloor{\frac{242}{3^1}}\right\rfloor + \left\lfloor{\frac{242}{3^2}}\right\rfloor + \dots + \left\lfloor{\frac{242}{3^4}}\right\rfloor \\ \\ &= 116 \end{aligned}$ Likewise, we stop at $3^4$ as $\left\lfloor{\log_3{242}}\right\rfloor = 4$ .

Computing $\min(\left\lfloor{\frac{v_2(N)}{2}}\right\rfloor, v_3(N))$ gives us $116$ which is only $5$ zeroes away from our goal. We shall now apply a linear search method and accumulate our zeroes starting from $N = 243$ by first prime factorising $N$ .

$243 = 3^5$

We can add five $3$ 's to our already existing one-hundred-(and)-sixteen $3$ 's, giving us (currently) a grand total of $2^{237}$ and $3^{121}$ . Yay, we reached 121!!! Indeed, that may be a cause for celebration, but computing $\min(\left\lfloor{\frac{v_2(N)}{2}}\right\rfloor, v_3(N))$ unfortunately gives us 118. This is due to $v_2(N)$ having a value of 237. Ah, so now we need to ensure that there will be at least 242 (or 243) $2$ 's and at least 121 $3$ 's. Let's keep this in mind now (if you already had this in mind, good on you).

$244 = 2^2 \times 61^1$ Grand Total: $2^{239}$ , $3^{121}$

$245 = 5^1 \times 7^2$ Grand Total: $2^{239}$ , $3^{121}$

$246 = 2^1 \times 3^1 \times 41^1$ Grand Total: $2^{240}$ , $3^{122}$

We have exceeded 121 $3$ 's, so now we are hoping that there will be 2 or 3 more $2$ 's in store for us.

$247$ ... skip this, no factors of 2 or 3 here.

$248 = 2^3 \times 31$ Grand Total: $2^{243}$ , $3^{122}$ .

We have reached a point where we have 243 $2$ 's and 122 $3$ 's. Going any further with higher values of $N$ will only give us more factors of 2 and 3 to worry about. 248 is our smallest integer $N$ such that when $N!$ is written in base 12 , it has 121 trailing zeroes (restating statement from question). 249 is also a possible candidate since $\min(\left\lfloor{\frac{v_2(N)}{2}}\right\rfloor, v_3(N))$ also equals $121$ . However, we shall hang on tight to 248 since it is our smallest candidate.

Solving the Problem: Converting to Base 6

A method of converting any number, $M_{10}$ from base $10$ to base $x$ is to find the highest power $i$ of $x$ such that $x^i ≤ M_{10}$ . A way to start off is to draw a 'T' table listing pairs of $i$ and $x^i$ . The table for $x = 6$ is listed below for values of $i$ up to $i = \left\lfloor{\log_6{248}}\right\rfloor = 3$ .

|| $3$ || $216$ ||

Now we shall iterate through values of $x^i$ starting from the largest value (i.e. $216$ ). As we iterate, we shall write $a_i$ in the form $a_i = b_i \times 6^i + a_{i-1}$ (as in $a = b \times q + r$ ) so that $a_{i-1} < 6^i$ . We shall then note down the value of $b_i$ then repeat for $a_{i-1}$ . Our numeric conversion terminates once $i = 0$ . (There is probably a neat algorithmic approach to notate this paragraph, but I couldn't get it right.) Keep in mind that $a_{max(i)} = M_{10}$ . In our current case, $a_3 = 248$ .

$\begin{aligned} 248 &= 1 \times 6^3 + 32 \\ \\ 32 &= 0 \times 6^2 + 32 \\ \\ 32 &= 5 \times 6^1 + 2 \\ \\ 2 &= 2 \times 6^0 + 0 \\ \\ \end{aligned}$

We may conclude that $248_{10} = 1052_{6}$ and $1052_6$ is the smallest integer in base 6 that when $1052_6!$ is written in base 12, it has 121 trailing zeroes $\square$ .