Euler Solution 34

From ProgSoc Wiki

Jump to: navigation, search

Solutions for Problem 34

Find the sum of all the numbers whose sum of the factorial of their digits is equal to the initial number, e.g. 145 = 1! + 4! + 5!.

Lisp by SanguineV

Runtime (script mode): 5.293 seconds

; Factorial function, needs to be able to handle (fact 0) case.
(define (fact n)
  (if (> 2 n)
    1
    (* n (fact (- n 1)))))

; Factorial of the digits of a number
(define (factdigits n)
  (if (> 10 n)
    (fact n)
    (+ (fact (modulo n 10)) (factdigits (floor (/ n 10))))))

; Search up to a limit and calculate the sum of all numbers n where n = (factdigit n)
(define (search n lim)
  (if (> lim n)
    ((lambda (fn) (
      if (= n fn)
      (cons n (search (+ n 1) lim))
      (search (+ n 1) lim)))
    (factdigits n))
    ()))

; Calculate the sum up to 500000, my first guess. Can be done faster once you know
; the lower limit... but I haven't proven there is a known limit (yet).
(begin (display (eval (cons + (search 3 500000)))) (newline))
(exit)


Python by Althalus

Runtime: 1.15 seconds

import time

start_time = time.time()

def f(n):
        if n > 0:
                return n * f(n-1)
        return 1

def fs(n):
        total = 0
        for c in str(n):
                total += f(int(c))
        return total

total = 0
for n in range (3,50000):
        if n == fs(n):
                total+=n
print n

run_time = time.time() - start_time
print run_time
Personal tools