Can You Figure the Factorial Numbers?

In the factorial number system, the $N$th digit from the right has base $N$: it can be anything from $0$ to $N - 1$, and its place value is $(N - 1)!$. So the rightmost digit is always $0$, the next is $0$ or $1$, the next $0$, $1$ or $2$, and so on. For example, $103210$ in this system is $$1 \cdot 5! + 0 \cdot 4! + 3 \cdot 3! + 2 \cdot 2! + 1 \cdot 1! + 0 \cdot 0! \;=\; 143 .$$ What is the smallest number that is divisible by every whole number from $1$ to $5$ and whose factorial-system digits include each of $0, 1, 2, 3, 4, 5$ (repeats allowed)?

The Fiddler, Zach Wissner-Gross, October 6, 2023(original post)

The official solution appeared in the post of October 13, 2023 and gives $134522000$ (that is, $58{,}980$) for the main puzzle and $1234569870000000$ for the Extra Credit. Both agree with the answers below.

Solution

Two facts about this number system do all the work. First, every number has exactly one representation, just as in ordinary bases: the digits are found by dividing by $1, 2, 3, \dots$ in turn and keeping the remainders. Second, the rightmost $k$ digits on their own can be worth anything from $0$ to $k! - 1$ (the largest is $(k - 1)\cdot(k - 1)! + \dots + 1 \cdot 1! = k! - 1$), and every digit further left has a place value that is a multiple of $k!$. So the rightmost $k$ digits are exactly the remainder of the number on division by $k!$.

Divisible by every number from $1$ to $5$ means divisible by their least common multiple, $60$. Since $60$ divides $5! = 120$, divisibility by $60$ depends only on the remainder on division by $120$, which is the last five digits. That remainder must be a multiple of $60$ below $120$, so it is $0$ or $60$, and the last five digits are $$00000 \quad\text{or}\quad 22000 \qquad (2 \cdot 4! + 2 \cdot 3! = 60).$$

The number must also show the digits $1, 3, 4, 5$, and with the ending $22000$ it already shows $0$ and $2$. Those four other digits need four more places, so the number has at least nine digits. With the ending $00000$ it would need five more places for $1, 2, 3, 4, 5$, making ten digits. A ten-digit number is at least $9! = 362{,}880$, larger than every nine-digit number, so the ending is $22000$.

With nine digits, the four leading places, of bases $9, 8, 7, 6$, hold $1, 3, 4, 5$ in some order, and every digit is allowed in each of them. The number is smallest with the smallest digit in front, so the order is $1, 3, 4, 5$, and its value is $1 \cdot 8! + 3 \cdot 7! + 4 \cdot 6! + 5 \cdot 5! + 2 \cdot 4! + 2 \cdot 3! = 58{,}980$: $$\boxed{\ 134522000, \text{ which is } 58{,}980 . \ }$$

The computation

The check is blunt: count upwards from $1$, convert each number to the factorial system, and stop at the first that is divisible by $1$ to $5$ and shows all of the digits $0$ to $5$.

from itertools import permutations
from math import factorial

def fact_digits(n):
    """Digits of n in the factorial number system, most
    significant first (the place of base b holds 0..b-1)."""
    digits, base = [], 1
    while True:
        n, d = divmod(n, base)
        digits.append(d)
        base += 1
        if n == 0:
            return digits[::-1]

def show(n):
    return "".join(map(str, fact_digits(n)))

n = 1
while not (all(n % k == 0 for k in range(1, 6))
           and set(range(6)) <= set(fact_digits(n))):
    n += 1
print("main:", show(n), "=", n)

It prints

main: 134522000 = 58980

Extra Credit

What is the smallest number, written in the factorial system, that contains each of the digits $1$ to $9$ exactly once (and any number of zeros) and is divisible by every whole number from $1$ to $9$?

Solution

The same idea, one size up. The least common multiple of $1, \dots, 9$ is $2{,}520$, which divides $7! = 5{,}040$. So divisibility depends only on the last seven digits, which must be worth $0$ or $2{,}520$. In the factorial system $2{,}520 = 3 \cdot 6! + 3 \cdot 5!$, so the last seven digits are $$0000000 \quad\text{or}\quad 3300000 .$$ The second repeats the digit $3$, which is not allowed. So the last seven digits are zeros, and the nine digits $1$ to $9$ all sit in places of base $8$ or more.

That needs at least nine such places, the places of bases $8$ to $16$, making sixteen digits. A longer number would be larger, so the answer fills exactly these nine places, with each digit used once. The leading place matters most, so make it as small as possible, then the next, and so on, while keeping the rest possible. The only obstacles are the top digits: $9$ needs a place of base at least $10$, and $8$ a place of base at least $9$.

• The places of bases $16$ down to $11$ take $1, 2, 3, 4, 5, 6$: each is the smallest digit left, and the digits still to come, $7, 8, 9$, still have room in the bases $10, 9, 8$.

• The place of base $10$ is the last that can hold $9$, so it must take $9$.

• The place of base $9$ could take $7$ or $8$, but the base-$8$ place below it can hold at most $7$. So base $9$ takes $8$ and base $8$ takes $7$.

$$\boxed{\ 1234569870000000 . \ }$$ It is about $1.5$ trillion in ordinary numbers.

The computation

Counting upwards would take too long here, so the program splits the search along the place values, using the conversion function from The computation above. It first confirms that $7!$ is divisible by every number from $1$ to $9$, so that only the last seven digits matter, and lists every possible last-seven-digit block, from $0$ to $7! - 1$, that is itself divisible by all of them. Then it tries all $9!$ ways to put the digits $1$ to $9$ into the places of bases $8$ to $16$, keeps those that respect each place’s limit, and takes the smallest.

# Places from 7! upward are multiples of 1..9, so divisibility
# depends only on the last seven digits (worth 0 to 7!-1).
print("7! divisible by 1..9:",
      all(factorial(7) % k == 0 for k in range(1, 10)))
ends = [b for b in range(factorial(7))
        if all(b % k == 0 for k in range(1, 10))]
print("possible last seven digits:",
      [show(b).zfill(7) for b in ends])

# 3300000 repeats a 3, so the last seven are zeros and 1..9
# fill the nine places of bases 8 to 16 (fewer cannot hold
# them; more makes a longer, larger number).
best = min(sum(d * factorial(b - 1) for d, b in zip(p, bases))
           for bases in [range(16, 7, -1)]
           for p in permutations(range(1, 10))
           if all(d < b for d, b in zip(p, bases)))
print("extra credit:", show(best))

It prints

7! divisible by 1..9: True
possible last seven digits: ['0000000', '3300000']
extra credit: 1234569870000000