How many positive integers below
400,000
can be expressed as a sum of distinct factorials?
Rem1: 0! not included.
Rem2: Please refrain from software solutions.
The factorials below 400,000 are the following:
1
2
6
24
120
720
5040
40320
362880
None of them is the sum of any other set of them, so any chosen set of them will have a unique sum.
There are 2^9 = 512 ways of choosing 0 through 9 out of these 9 numbers, but some exclusions need be made from among the 512 ways.
We want a positive sum, so we must definitely exclude the set that has zero members.
The two highest numbers add up to more than the 400,000 limit, so any set that includes both of them needs also to be excluded. There are 2^7 = 128 such sets, as any or all of the remaining 7 may be present or not along with those two.
That means we're down to 512  1  128 = 383 sets of addends, or resulting positive integers.
If one objects that an individual factorial is not the sum of distinct factorials, then we also need to subtract another 9, making 374 such positive sums.

Posted by Charlie
on 20150420 09:56:06 