Menu

Subscribe

Project Euler problem 34

on project euler, erlang, perl, python

Digit factorials.

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.
Link to original description
Source code examples on Github

Erlang version

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#!/usr/bin/env escript
%% -*- erlang -*-
%%! -smp enable -sname p34
% vim:syn=erlang

-mode(compile).

main(_) ->
    L = limit(),
    F = [fact(N)||N<-lists:seq(0,9)],
    put(fact, F),
    R = calc(10,L,0),
    io:format("Answer ~p ~n",[R]),
    ok.

limit() -> fact(9)*7.

fact(0) -> 1;
fact(N) -> N*fact(N-1).

is_ok(Num) ->
    Num =:= lists:sum([lists:nth(N+1,get(fact)) || N <- list_of_digs(Num)]).


calc(N, M, A) when N =< M ->
    case is_ok(N) of
        true -> calc(N+1,M,A+N)
        ;_   -> calc(N+1,M,A)
    end;
calc(_, _, A) -> A.

list_of_digs(Num) -> lod(Num, []).
lod(0, A) -> A;
lod(N, A) -> lod(N div 10, [N rem 10]++A).

Perl version

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#!/usr/bin/perl -w
use strict;

my %f = ();

sub main(){
    my $limit = 7*fact(9);
    my $sum = 0;
    %f = map{ $_ => fact($_)} 0..9;
    for(my $i=10;$i<$limit;$i++){
        $sum += $i if $i == sumofd($i)    
    }
    print "Answer: $sum \n";
}

sub fact{
    my $num = shift;
    if($num == 0){ 1 }
    else{ 
        my ($f,$i) = (1, 1);
        $f *= ++$i while $i < $num;
        $f
    }
}

sub sumofd{
    my $s = 0;
    map { $s += $f{$_} } split(//, shift);
    $s
}

main();

Python version

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#!/usr/bin/python
import math

def main():
    l = limit()
    print "limit: %d" % l
    s = 0
    f = {}
    for x in range(0, 10): f[str(x)] = math.factorial(x)
    for x in range(10, l):
        if x == sum(map(lambda y: f[y], str(x))): s += x
    print "Answer: %d" % s

def limit():
    return math.factorial(9)*7

main()

Performance

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
mkh@mkh-xps:~/work/mblog/pr_euler/p34$ time ./p34.pl
Answer: 40730 

real    0m9.628s
user    0m9.628s
sys     0m0.004s
mkh@mkh-xps:~/work/mblog/pr_euler/p34$ time ./p34.py
limit: 2540160
Answer: 40730

real    0m7.938s
user    0m7.854s
sys     0m0.080s
mkh@mkh-xps:~/work/mblog/pr_euler/p34$ time ./p34.escript 
Answer 40730 

real    0m7.369s
user    0m7.115s
sys     0m0.160s
mkh@mkh-xps:~/work/mblog/pr_euler/p34$