6
$\begingroup$

145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.
Find the sum of all numbers which are equal to the sum of the factorial of their digits.
Note: as 1! = 1 and 2! = 2 are not sums they are not included.

So I tried a random enough large upper bound (100000) in my program and it worked.

I deleted this part to not spoil the answer

My question is : How to find the closest upper bound using a mathematical approach ?

$\endgroup$
17
  • 1
    $\begingroup$ by "closest upper bound", do you mean $40585$? $\endgroup$
    – Jonathan
    Dec 29, 2013 at 0:13
  • 1
    $\begingroup$ Is it really viewed as appropriate to come here with PE questions? Include me out. $\endgroup$
    – Igor Rivin
    Dec 29, 2013 at 0:14
  • 6
    $\begingroup$ This question appears to be off-topic because it is about Project Euler $\endgroup$
    – Igor Rivin
    Dec 29, 2013 at 0:14
  • 1
    $\begingroup$ @IgorRivin Since I ALREADY find the solution, I don't see where is the problem. I just want to know how to find an upper bound mathematically, not by trying some bounds randomly. Finding an upper bound won't solve the problem for the others (and if you're too lazy to find the solution yourself, googling project euler problem 34 and you'll find plenty of answer in blogs). $\endgroup$
    – user2336315
    Dec 29, 2013 at 0:16
  • 1
    $\begingroup$ @IgorRivin, see my answer, correspondence with Project Euler moderator. They really do not want this. People put all sorts of variations, leave out parts, whatever. The part about experimenting on your own has not sunk in... $\endgroup$
    – Will Jagy
    Dec 29, 2013 at 1:46

2 Answers 2

Reset to default
6
$\begingroup$

Let $P(n)$ be the sum of the factorials of the digits of $n$. I apologize that this answer is not mathematically rigorous; the purpose is more to give my ideas rather than to prove.

Since $9!=362880$ is six digits, we can expect a seven digit number to have $P(n)$ at most seven digits (Note: $P(9999999) = 2540160$ is seven digits).

Similarly, An eight digit number will yield at most a seven digit $P(n)$. So once we reach eight digits, it is no longer possible. More precisely, anything above $2540160$ is impossible, since this is the highest $P(n)$ we can get with seven digits.

The highest $P(n)$ we can get with $n < 2540160$ is $2177281$ with $n = 1999999$. So we can use $2177281$ as our best bound. We can use this strategy again by checking the second highest $P(n)$ with $n$ under the bound, and so on. But the presented bound, $2177281$, is not out of the realm of computation by any means.

Perhaps more clever arguments yield better bounds. My method turns into raw computation fairly quickly. On the other hand, some of the numbers just under two million seem fairly valid guesses. This leads me to believe there is not an obvious way to reduce my bound below two million.

edit: I am looking at it further, and it seems like an argument could reasonably reduce my bound under a million. It seems that in order to get $P(n)$ close to two million while using numbers just under two million, we need a lot of $9$s as digits. So it seems that there are very few candidates, few enough to reasonably check by hand, just under two million.

$\endgroup$
1
$\begingroup$

The wikipedia article explains how to get some trivial bounds.

The most trivial one is to note that if the number $n$ has $d$ digits, we have

$$10^{d-1}<n<9!d$$ which yields that $d\leq7$ and thus gives an upper bound of $10^7=10000000$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .