The Factorial Base II

After my factorial base post, a commenter asked about multiplication and it turns out multiplication is hard in factoradix, as far as I know. A natural question is, what does factoradix make easy? Here's an example: testing for divisibility.

In fact, this can be downright awesome by comparison. In decimal, testing if a number n divides into m takes time about equal to the length of m. Checking if 3 divides into a billion digit decimal number will take your computer about one billion cycles, within some constant factor of time spent.

Checking if m divides n in factoradix takes time proportional only to m. Checking if 3 divides a billion digit number in factoradix (which would be about a 9 billion digit number in decimal because of decimal's less efficient use of digits), only requires looking at the last 2 places!

Let me give an example. Does 3 divide into 9a0a4023220011?

Recall that each of the places corresponds to a certain number of factorials. Well, every factorial greater than 2! contains 3 as a factor, by definition. Therefore, the values of any digit other that the two rightmost, is irrelevant, because it could only change the value of the number by a multiple of three. This is sort of like how you can tell if a decimal number is divisible by ten only by looking at the last digit (all the other digits cannot affect the divisibility by ten).

Getting back to 9a0a4023220011, we need only check 11. Sure enough 11(factoradix) = 1 * 2! + 1 * 1! = 3. So yes, 3 does divide 9a0a4023220011.