Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.