Admin: Created page with "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. Her..."

2018-01-05T09:45:44Z

Created page with "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. Her..."

New page

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.

<pre>
$ 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()
</pre>

=Flags=

{{ProjectEulerFlag}}

Project Euler/254 - Revision history

Admin: Created page with "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. Her..."