Michael Schubmehl (who won a 🎬 Best Picture Award 🎬 just two Fiddlers ago) poses a puzzle inspired by a recent xkcd comic:
Number systems like decimal, binary, and hexadecimal each have a fixed number of allowed digits in each place (10, 2, and 16, respectively), while “mixed-radix” systems like the 24-hour clock can have a different number of allowed digits in each place (24 hours, 60 minutes, and 60 seconds, for example). Counting works the same way in all of these systems: When incrementing the rightmost digit causes it to roll from its maximum value back to zero, we “carry” this overflow by incrementing the next digit to the left: 09 increments to 10 in base 10, and 00:00:59 increments to 00:01:00 on the clock.
In the factorial number system (not a prank), the Nth digit from the right has base N, and thus a maximum allowable digit of N−1. As a result, the rightmost digit is always 0 (don’t get me started on “base 1”), the digit to its left can be 0 or 1 (in good old base 2), the next digit can be 0, 1, or 2 (in base 3), and so on. This is called the factorial number system because the place value of the Nth digit is (N−1)!.
Let’s look at an example. Suppose a number is written 103210 in the factorial number system. What is this number in base 10? It’s 1(5!) + 0(4!) + 3(3!) + 2(2!) + 1(1!) + 0(0!), or 143. (Note that the numbers in bold are exactly the digits from the factorial number representation.)
What is the smallest number in the factorial number system that is divisible by the whole numbers from 1 through 5, while also containing all of the digits 0 through 5? (Note that this number can have more than one copy of any given digit.)
You can submit this number using the factorial number system or in base 10.
$LCM(1,2,3,4,5) = 60$. Every $N!$ for $N \ge 5$ is divisible by 60, so only the first five digits are important.
The first digit must be $0$. The second digit must be $0$ as well otherwise the number will have an odd value.
The remaining problem is determining $n_4 \cdot 4! + n_3 \cdot 3! + n_2 \cdot 2! = k \cdot 60$.
$n_2 = n_3 = n_4 = 0$. The resulting number is $1234500000$.
$n_2 = 0$, and $n_3 = n_4 = 2$. The resulting number is $134522000$.
Maximizing the value of each digit when $n_2 = 2$, $n_3 = 3$, and $n_4 = 4$ yields $118$, which is $\le 2 \cdot 60$.
$134522000$ is the smallest.
This week’s Extra Credit also comes courtesy of Michael Schubmehl:
What is the smallest number in the factorial number system that contains each of the digits 1 through 9 exactly once, and is also divisible by all of the whole numbers from 1 through 9? (Note that this number can contain any amount of zeros.)
This time around, please submit this number using the factorial number system.
$LCM(1,2,3,4,5,6,7,8,9) = 2520$. Every $N!$ for $N \ge 7$ is divisible by $2520$, so only the first seven digits are important.
Every $N!$ for $N \ge 5$ is divisible by $120$, thus, similar to before, the first five digits must be $0$.
The remaining problem is determining $n_6 \cdot 6! + n_5 \cdot 5! = k \cdot 2520$.
$n_5 = n_6 = 0$. The resulting number is $1234569870000000$.
$n_5 = n_6 = 3$. The resulting number is $124569873300000$.
Maximizing the value of each digit with $n_5 = 5$ and $n_6 = 6$ yields $4920$, which is $\le 2 \cdot 2520$.
$1234569870000000$ is the smallest where each of the digits 1 through 9 is used exactly once.