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.

I can't figure out a fair way to optimize the upper bound from the information given in the question. I went on the PE forum and found many people setting the upper bound to 50000 because they knew that would be large enough after testing. This doesn't seem fair to me; I want to set the bound based on the information in the question. Right now it runs in around 20 seconds.

EDIT: I'm not looking for a mathematical algorithm. I'm looking for ways to make this code faster.

from math import factorial as fact
from timeit import default_timer as timer

start = timer()
def findFactorialSum():
    factorials = [fact(x) for x in range(0, 10)] # pre-calculate products
    total_sum = 0
    for k in range(10, fact(9) * 7): # 9999999 is way more than its fact-sum
        if sum([factorials[int(x)] for x in str(k)]) == k:
            total_sum += k

    return total_sum

ans = findFactorialSum()
elapsed_time = (timer() - start) * 1000 # s --> ms

print "Found %d in %r ms." % (ans, elapsed_time)
\$\endgroup\$
  • \$\begingroup\$ Please remember to tag these questions with [programming-challenge] and [optimization]. \$\endgroup\$ – Jamal Apr 25 '14 at 23:58
  • \$\begingroup\$ Are you hoping to mathematically determine the upper bound on the largest number which is equal to the sum of the factorials of its digits? If so that sounds like a question for Mathematics. \$\endgroup\$ – David Z Apr 26 '14 at 4:23
  • \$\begingroup\$ Further to @DavidZ comment, finding the upper bound is a topic you can find using Google. It seems as if you're asking for an algorithm, not a code review. \$\endgroup\$ – ChrisW Apr 26 '14 at 4:25
  • 1
    \$\begingroup\$ The upper bound is the topic of a Mathematics question \$\endgroup\$ – Janne Karila Apr 27 '14 at 8:45
4
\$\begingroup\$

I'm not aware of any mathematical way to establish the upper bound for the search space (I used the same upper limit as you did). However, there are some optimizations you can make:

  1. Use integer math throughout instead of converting to a string, extracting the digits, then converting back to an integer. On my PC, your algorithm ran in approximately 6200ms. Using integer math as follows (there may be a more Pythonic way to do this; my code is a direct transliteration of C++ that I used), it ran in approximately 1600ms -- almost 4 times as fast:

    def findFactorialSum():
        factorials = [fact(x) for x in range(0, 10)] # pre-calculate products
        total_sum = 0
        for k in range(10, fact(9) * 7): # 9999999 is way more than its fact-sum
            tmp = k
            total = 0
            while tmp > 0:
                total += factorials[tmp % 10]
                tmp //= 10
    
            if total == k:
                total_sum += k
    
        return total_sum
    

    (For my curiosity, I also tried it with the '/' operator instead of the '//' operator, and consistently got 100ms longer run times with the former.)

  2. You're doing an exhaustive search of the numbers from [10...7*9!] to see which ones meet the problem criteria. You can eliminate a large proportion of those numbers:

    Hint 1:

    No 2-digit number can have a digit >= 5. This is because 5! == 120, so any 2-digit number with a 5 (or higher) in it will automatically have a 3-digit (or longer) sum. You can extend this rule for 3-, 4- and 5- digit numbers.

    Hint 2:

    Extending Hint 1: No 3-digit number can have more than one 7 in it. 7! is 720, so if you have two 7s, you have 1440, a 4-digit number. There are a few more opportunities like this to eliminate numbers to check

    Hint 3:

    Think of the number 145 given in the problem; since you know that this works, there's no need to check numbers that are a permutations of its digits: 154, 415, 451, 514, 541. The trick here is to look at the problem the other way around: instead of finding numbers whose Sum of Factorials of Digits equals the original number, find an ordered sequence of digits whose Sum of Factorials can be split into a sequence of digits, sorted, and that compares equal to the original sequence.

\$\endgroup\$
  • \$\begingroup\$ Your code returned zero when I ran it on my machine. \$\endgroup\$ – Joshua Apr 27 '14 at 22:53
  • \$\begingroup\$ @jshuaf ... Hmm, when I ran the code on my machine, it returned Found 40730 in 2611.125946044922 ms. Ran the code on ideone too: ideone.com/qZqPIW \$\endgroup\$ – rolfl Apr 27 '14 at 23:43
  • \$\begingroup\$ On this machine I get Found 40730 in 8652.6780128479 ms. under Python 2.7 and Found 40730 in 11760.103859938681 ms. under Python 3.3 (when I fix the print statement). The original code gives Found 40730 in 26423.507928848267 ms. on the same machine. \$\endgroup\$ – Edward Apr 27 '14 at 23:49
1
\$\begingroup\$

This is much faster than both of your solutions(~50 ms compared to 5 and 13 seconds) jshuaf when you initialized the factorial values try using a dictionary instead of a list also allows me to use str keys and get int values,

import math

def problem34():
    total=0
    factorials={}
    for i in xrange(10):
        factorials[str(i)]=math.factorial(i)    
    for i in xrange(3,50000):
        factorial_sum=0
        for j in str(i):
            factorial_sum+=factorials[j]
        if factorial_sum==i:
            total+=factorial_sum
    return total
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.