Project Euler Problem 34 Solution

Project Euler Problem 34 Solution

Digit factorials

by {BetaProjects} | Project Euler & HackerRank

Project Euler Problem 34 Statement

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.

Solution

factorionsAt first read this problem appears to describe a boundless search for numbers which sum to the factorial of their digits. But, after some quick research, it appears that these type of numbers are referred to as factorions and that only 4 exist: 1, 2, 145 & 40585. The problem asks us to ignore 1 & 2 so the answer to this problem should be obvious.

But, let’s write a program anyway to search for factorions. As usual, when writing a brute force search algorithm, we must first determine our bounds. The lower bound is 10 because single digit candidates are to be ignored. The upper bound we discover as follows (from an archived discussion on Wikipedia: Factorion):

If n is a natural number of d digits that is a factorion, then 10d−1n ≤ 9!d. This fails to hold for d ≥ 8 thus n has at most seven digits, and the first upper bound is 9,999,999. But the maximum sum of factorials of digits for a seven–digit number is 9!*7 = 2,540,160 establishing the second upper bound.

Going further, since no number bigger than 2,540,160 is possible, the first digit of a seven-digit number can be at most 2. Thus, only six positions can range up until 9 and 2!+6*9!= 2,177,282 becomes a third upper bound. This implies, if n is a seven-digit number, either the second digit is 0 or 1 or the first digit is 1. If the first digit is 2 and thus the second digit is 0 or 1, the numbers are limited by 2!+1!+5*9! = 1,814,403—a contradiction to the first digit being 2. Thus, a seven-digit number can be at most 1,999,999, establishing our fourth upper bound.

Simple solution

Having a list of factorials of the numbers 1 through 9 saved having to calculate the factorials of the individual digits each time.

fact = {'0':1, '1':1, '2':2, '3':6, '4':24, '5':120, '6':720, '7':5040, '8':40320, '9':362880}

A lambda function calculates the sum of the factorial digits quickly.

sfd = lambda n: sum(fact[c] for c in str(n))

These two Python statements setup the requirements to solve this problem and the HackerRank problem.

Project Euler
print sum(n for n in range(10, 2000000) if n == sfd(n))
HackerRank
print sum(i for i in range(10, int(input())) if sfd(i)%i == 0)

HackerRank version

HackerRank didn’t have much liberty in expanding this problem, so they created a version still requiring the sum of the factorial–digits, but with a twist. They provide a query, 10 ≤ N ≤ 105, and we find the total of all numbers less than N that divide the sum of the factorial of their digits.

Python Source Code

fact = {'0':1, '1':1, '2':2, '3':6, '4':24, '5':120, '6':720, '7':5040, '8':40320, '9':362880}
sfd = lambda n: sum(fact[c] for c in str(n))
print (sum(i for i in range(10, int(input("Find the sum of factorions below N that divide N? "))) if sfd(i)%i == 0))	

Last Word