We haven't cracked this one yet.

The naive implementation takes an astronomical amount of time, so this one, like many PE problems, requires some elegance and foresight.

Here is a brute force solution - useful for implementing and exploring the problem, but also showing just how hopeless it is to brute force the solution.

$ cat problem254_naive.py
"""
Project Euler Problem 254:
Sum of Digit Factorials

Naive solution: this is the most "obvious" way
to implement a solution, and accordingly, it will
take longer than the heat death of the universe.
"""

# Utility:

def split_to_digits(n):
    d = list(str(n))
    return [int(z) for z in d]



# Factorial:

def fact(n):
    if n>1:
        return n*fact_(n-1)
    else:
        return 1



# Sum of factorial digits

def f(n):
    return sum([fact(z) for z in split_to_digits(n)])



# Sum of digits of sum of factorial digits

def sf(n):
    return sum( split_to_digits(f(n)) )



# Minimum number such that sum of digits of sum of factorial digits is itself

def g(p):
    n = 1
    sf_val = sf(n)
    while sf_val != p:
        n+=1
        sf_val = sf(n)
    return n



# Sum of digits of minimum number, &c.

def sg(p):
    return sum( split_to_digits( g(p) ) )



# Main method:

def test():
    # These tests all behave as expected
    print(split_to_digits(342))
    print(f(342))
    print(sf(342))
    print(sf(25))
    print(g(25))
    print(g(20))

    # This test goes really fast
    print(sum([sg(i) for i in range(1,21)]))


def solve():
    # This gets bogged down at 40, and 44, and &c...
    summ = 0
    for i in range(41,44):
        print("Loop {i}".format(i=i))
        summ += sg(i)

    print("Final sum:")
    print(summ)

if __name__=="__main__":
    import cProfile
    pr = cProfile.Profile()
    pr.enable()
    solve()
    pr.disable()
    pr.print_stats()

Flags

Project Euler/254

From charlesreid1

Flags