# Efficient factorion search in arbitrary base

A factorion in base $N$ is a natural number equal to the sum of the factorials of its digits in base $N$. So, the decimal factorions are:

$1 = 1!$
$2 = 2!$
$145 = 1! + 4! + 5!$
$40585 = 4! + 0! + 5! + 8! + 5!$

It's easy to prove that, in any base $N$, there is no factorion $> d \centerdot (N-1)!$ where $d$ is the maximum number (of digits) such that $N^{d-1} \leq d \centerdot (N-1)!$ In other words, beyond $d$ digits, the number will grow faster than the sum of its digit factorials. Thus, any base can be exhaustively searched in a time proportional to this upper limit, at worst.

However, I'm trying to find an algorithm more efficient than iterating that many times. I feel like there must be a way to eliminate large branches of the search, perhaps by searching in non-numerical order, but I haven't found any yet.

Any reasonable pre-calculations are allowed, including a table of the factorials of the digits.

-
Sum the factorials of a combination of digits then check that the result is not equal to any permutation of them, so that the factorial sum is not recomputed for different permutation. Also, if, for example, 555<5!+5!+5! then 1111,1112,11111,3444,4444,3241 etc must also be less than their factorial sums since they are larger and all their digits are smaller. – Angela Richardson Dec 26 '11 at 6:22