Project Euler 34: Find the sum of all numbers which are equal to the sum of the factorial of their digits

Written by on 2 April 2011

Topics: Project Euler

The headline of Problem 34 of Project Euler triggered something in me and I found it oddly familiar. I didn’t quite know what it was until a few minutes later where it dawned on me that it was very similar to Problem 30. The problem description is short and reads:

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.

Where the solution to Problem 30 is about the sum of the fifth power of the digits, this is about the sum of factorials of the digits.

I could copy paste the text from the solution to problem 30, but let me change the focus a bit. We can establish an upper bound of the problem by figuring out that 9!*7 = 2540160 which is the upper limit. There is no possible higher value since 9!*8 also results in a 7 digit number. First I will make a solution almost similar to the aforementioned solution, and later on I will speed it up, by pre-calculating the factorial.

Calculating the factorial

The first thing I did was making an implementation of the factorial. We will never go higher than 9!, so we can easily store it in an integer with no special need for things like BigInteger or the like. The only catch is to note that 0! = 1. And once that case is treated it is easy.

The C# implementation of the factorial looks like this

private int factorial(int x) {
    if (x == 0) {
        return 1;
    }
    int y = x;
    for (int i = 1; i < x; i++) {
        y *= i;
    }
    return y;
}

Brute Force Solution

My first solution is once again a for loop where I chop off digits, add the factorial of the digits together and compare it with the original number. No magic there and it works plenty fast for all purposes.  It looks like the following

int result = 0;
for (int i = 10; i < 2540161; i++) {
    int sumOfFacts = 0;
    int number = i;
    while (number > 0) {
        int d = number % 10;
        number /= 10;
        sumOfFacts += factorial(d);
    }

    if (sumOfFacts == i) {
        result += i;
    }
}

And yields the result

The sum of numbers factorial to their digits 40730
Solution took 322 ms

Pre-calculating the Factorial

After solving a problem I usually sneak peak at other solutions before writing a post, since I want to learn as much as I can and to cover the topic from different approaches. The solution for problem 34 at Dreamshire used caching of the factorial. So by adding an array with pre-calculated factorials we can skip making the calculation 6! = 1*2*3*4*5*6 = 720 over and over and over again.

The small addition to the program changes the C# code to look like

int[] facts = new int[10];
int result = 0;
for (int i = 0; i < 10; i++) {
    facts[i] = factorial(i);
}
for (int i = 10; i < 2540161; i++) {
    int sumOfFacts = 0;
    int number = i;
    while (number > 0) {
        int d = number % 10;
        number /= 10;
        sumOfFacts += facts[d];
    }

    if (sumOfFacts == i) {
        result += i;
    }
}

Not exactly rocket science, but it make the code execute within 176ms and this yields a speed-up of approximately a factor 2. So nothing big.

Wrapping up on Problem 34

The reason the time difference is so big in this problem and problem 30 is that the upper bound is so much higher, and thus we need to investigate more numbers.

I think this is a simple straight forward solution to something which is a fairly straight forward problem. The only thing I noted when I developed the code is that only two numbers fulfils the conditions and one is given by the problem description, the other number is 40585, so we could lower the upper limit significantly, but I don’t know how to find this lower upper bound ahead of time.  If you can elaborate on how to lower the upper bound I would very much like your input through comments on the blog. Also if you can come up with implementations that speed up the process I would be very happy to hear about it.

Here is the source code for you to peek at if you like the full implementation.

24 Comments For This Post I'd Love to Hear Yours!

  1. SuprDewd says:

    You can also scrap the factorial function and use Dynamic Programming when you calculate the factorials of 0 to 9.

    int[] facts = new int[10];
    facts[0] = facts[1] = 1;
    
    for (int i = 2; i < 10; i++) {
        facts[i] = facts[i - 2] + facts[i - 1];
    }
    
  2. Kristian says:

    Hi SuprDewd

    You are right, I could change the factorial function. But what you made there is the Fibonacci sequence which is not the same. I could write a piece of code such as

    int[] facts = new int[10];
    facts[0] = facts[1] = 1;
    
    for (int i = 2; i < 10; i++) {
        facts[i] = i*facts[i - 1];
    }
    

    I doubt it will change the performance anything significantly though, since it is such a small change. But it saves calculations and it would save a few function calls as well.

    Have you tried it?

    /Kristian

  3. SuprDewd says:

    Haha, I meant to do factorial, not fibonacci.
    But I tried it, and the execution time is exactly the same.

  4. Mike Housky says:

    On a modern processor, the divisions will dominate the compute time. You can eliminate most of them by precomputing the digits of the numbers 0 through 9,999. That’s four arrays of 10,000 elements. Since the elements are digits 0..9, bytes will do. You can even build the table without multiplication or division by:

    d0tab = new char[10000];
    d1tab = new char[10000];
    d2tab = new char[10000];
    d3tab = new char[10000];
    int d0=0, d1=0, d2=0, d3=0;
    for (int i=0; i 9)
    { d0 = 0;
    if (++d1 > 9)
    { d1 = 0;
    if (++d2 > 9)
    { d2 = 0;
    ++d3;
    }
    }
    }
    d0tab[i] = d0;
    d1tab[i] = d1;
    d2tab[i] = d2;
    d3tab[i] = d3;
    }

    Then you get the digits in either (one division instead of 6) or (two divisions instead of 12) depending on whether the optimizer is smart enough to get a/b and a%b in one division operation. That’s for up to 8 digits.

    I haven’t done this problem yet, though. I just got to 32 tonight.

  5. Kristian says:

    Interesting approach to speed it up even more. I would be curious to know if this strategy speeds things up in practice as well as in theory. So please post the solution once you have solved it.

    /Kristian

  6. Bjarki Ágúst says:

    That’s actually really interesting. I copied Kristian’s code and it ran in ~170 ms. I then did what Mike proposed (and even got rid of all divisions) and amazingly it ran in only ~70ms. Both execution times are averages of a couple of runs.

    The code, for those who are interested: (C++)

    #include <cstdio>
    #include <cstring>
    using namespace std;
    
    int main()
    {
    	// calculate the factorials
    	int facts[10];
    	facts[0] = 1;
    
    	for (int i = 1; i < 10; i++) {
    	    facts[i] = i * facts[i - 1];
    	}
    
    	// calculate the factorial number sums (zeros in front of number are also summed)
    	int* sum = new int[10000];
    	sum[0] = 4;
    
    	char number[4];
    	memset(number, 0, 4);
    
    	int cursum = 4,
    		curnumber = 1;
    
    	while (true)
    	{
    		bool carry = 1;
    		int i = 0;
    
    		while (carry && i < 4)
    		{
    			cursum -= facts[number[i] + 0];
    
    			if (++number[i] == 10)
    				number[i] = 0;
    			else
    				carry = false;
    
    			cursum += facts[number[i] + 0];
    			i++;
    		}
    
    		if (carry) break;
    		sum[curnumber++] = cursum;
    	}
    
    	// calculate the result
    	int result = 0;
    	for (int i = 10, x = 0, y = 10; i < 2540161; i++) {
    
           	int sumOfFacts = sum[x] + sum[y];
    
           	// because the sums contain the zeros in front
           	if (x < 1000) {
           		sumOfFacts--;
           		if (x < 100) {
    	       		sumOfFacts--;
    	       		if (x < 10) {
    	       			sumOfFacts--;
    	       			if (x < 1) {
    	       				sumOfFacts--;
    	       				if (y < 1000) {
    	       					sumOfFacts--;
    	       					if (y < 100) {
    	       						sumOfFacts--;
    	       						if (y < 10) {
    	       							sumOfFacts--;
    	       							if (y < 1) {
    	       								sumOfFacts--;
    	       							}
    	       						}
    	       					}
    	       				}
    	       			}
    	       		}
           		}
           	}
    
    	    if (sumOfFacts == i) {
    	        result += i;
    	    }
    
    	    if (++y == 10000) {
    	    	y = 0;
    	    	x++;
    	    }
    	}
    
    	printf("%d\n", result);
    	return 0;
    }
  7. Mike Housky says:

    Okay, I got it down to no divisions at all and 15 ms on one core of a Core 2 Duo (3.0GHz) with Visual C++ Express 2008. Rather than decompose the current number into digits, I manually incremented and performed carries to a digit array.

    I also used the obvious precomputation of 0!-9!, and computed the sum in a for loop. At this runtime (15 ms is the smallest interval that Windows clock() will measure…I see no difference between 2,000,000 iterations and 3,000,000 iterations, for example) I didn’t follow up with the C trick of using switch to unroll the sum-of-factorials loop. If you have a finder grained timer, you could take a look at:

    sum = 0;
    switch (ndigits)
    {
    default: assert(ndigits<0); // always false. force error
    break;
    case 7: sum += facts[digits[6]];
    case 6: sum += facts[digits[5]];
    case 5: sum += facts[digits[4]];
    case 4: sum += facts[digits[3]];
    case 3: sum += facts[digits[2]];
    case 2: sum += facts[digits[1]] + facts[digits[0]];
    break;
    }

    So, here's the actual code:

    #include <iostream>
    #include <cassert>
    #include <ctime>
    
    using namespace std;
    
    int main()
    {
        int target = 3000000;
        int digitsOfN[] = {0, 1, 0, 0, 0, 0, 0, 0, 0};
        int n=10;
        int ndigits = 2;
        const int facts[10] = 
        { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880 };
    
        // super brute force:
        clock_t t0 = clock();
        int nfound = 0;
        int sumfound = 0;
    
        while (n<=target)
        {
    	int sumpow = 0;
    	for (int i=0; i<ndigits; ++i)
    	    sumpow+=facts[digitsOfN[i]];
    	if (sumpow == n)
    	{
    	    cout << "found n=" << n << endl;
    	    ++nfound;
    	    sumfound += n;
    	}
    	++n;
    	if (++digitsOfN[0] > 9)
    	{
    	    digitsOfN[0] = 0;
    	    if (++digitsOfN[1] > 9)
    	    {
    		digitsOfN[1] = 0;
    		int k=2;
    		while (++digitsOfN[k] > 9)
    		{
    		    digitsOfN[k++] = 0;
    		}
    		if (k >= ndigits)
    		    ndigits = k+1;
    	    }
    	}
    #ifdef _DEBUG
    	int ncalc=0;
    	for (int i=ndigits-1; i>=0; --i)
    	    ncalc = ncalc*10 + digitsOfN[i];
    	assert(n==ncalc);
    #endif
        }
        clock_t t1 = clock();
        cout << "Searched " << target << " numbers in "
    	<< ((t1-t0)*1000.0/CLOCKS_PER_SEC) << "ms." << endl;
        cout << "Found " << nfound << " numbers, sum=" << sumfound << endl;
        return 0;
    }
    

    By the way, on the upper bound, it's a bit fuzzy, but you can probably switch methods for really large numbers, because the composition is limited. A 7-digit solution must be mostly 8s and 9s, since 6*7! is only 30240. So, maybe use the brute loop for up to 99,999 and then use a strategy that composes sums of 6 or 7 factorials. That won't be the full 10^6 or 10^7 possibilities, because order doesn't matter. If a solution exists, the sum tells you what order the digits are in. Plus, there's still the minimum number of 8s and 9s to get a sum in range.

  8. Bjarki Ágúst says:

    Good job, Mike.

  9. safeside says:

    sum_factorials((digits(40585)) == 40584. So what are you all talking about?

  10. Kristian says:

    Nope, because 0! = 1. So I do believe we are right.

  11. Guest says:

    The fact that 0!=1 invalidates some methods which work for the 5th-power case. This caught me — I was caching the sum-of-all-but-leading-digit.

  12. Babak Sairafi says:

    Hello
    I think if fact function implementation once than these
    1-

    int fact(int n)
    {
    int f = 1;
    for (int i = 1; i <= n; i++)
    f *= i;
    return f;
    }

    2-

    int fact(int n)
    {
    return n == 0 ? 1 : n * fact(n – 1);
    }

  13. Kraay89 says:

    To establish an upper bound i figured 9! = 362880;
    the digit factorial sum of this number is 3! +6! +2! +8! +8! +0! = 6+720+2+40320+40320+1 = 81369

    Now this (by accident?) provides me with a sufficient upper limit(40585 is far below that), but is it mathematically solid? are can it be made so?

  14. Kristian says:

    I don’t think that is a solid bound. After all you are looking for any number which fits the property. I am not saying you are wrong, but I think so, and I can’t prove either way.

  15. oursinblanc says:

    You can lower the upper bound. I mean to get 2540161 you 7*9!=2540161 so we can calculate 2+6*9!=2177282 and then 2+2+5*9!<2000000 this way I reduce 20% of the cases to evaluate not really a big deal 🙂

  16. zakariae says:

    many thanks, i want to go through all the problems and learn from you.
    but i have a request if you can post what kind of books you have read to reach this level.i hope one day i can became like you or like Bjarki Ágúst , you are awesome, any tips , tutoriels , methods you find it wil be useful to me. because i found dificulty to solve problems in deadline.

  17. Kristian says:

    I don’t know how much it is about reading books. I think a lot of it comes from practice. In my case I picked up a lot of the prerequisites for solving these during my university time.

    Maybe Bjarki has some more explicit ideas as it seems he has read a lot of good books about the subject.

  18. MartinP says:

    A slight, but rather obvious improvement is breaking the loop when sumOfFacts>i .

  19. SpivakA says:

    My thinking about how to find the upper bound is to find how much nines in the number gives a factorial digit sum that is larger from the number.
    I’ve got 99999999, 8 nines that is bigger then 2903040, which is 8*9!.
    After it, you can be sure that any number factorial digits sum is lower then the number itself.
    I don’t understand why 7*9! is a large enough number, as claimed earlier.

  20. Mike Housky says:

    @SpivakA: The reason that 7*9! is the upper bound is in the number you posted. An 8-digit solution is impossible, since the largest possible sum of 8 factorials is 8*9! = 2903040, a 7 digit number. So every 8-digit number must be greater than it’s sum of factorials.

    The same holds for 9 or more digits, too, so 7 digits is the maximum and 7*9! is an upper bound because every larger 7-digit number has a sum of factorials less than itself.

  21. Jean-Marie Hachey says:

    More on factorions …
    The base b factorions are integers that are equal to the sum of the factorials of their base b digits. For example, 145 is a factorion in decimal, since 1! + 4! + 5! = 1 + 24 + 120 = 145. […] (1)
    ___

    Sources:
    1) Irregular table read by rows, in which row n lists the factorions in base n, for 2 <= n.
    http://oeis.org/A193163
    2) Factorion.
    http://mathworld.wolfram.com/Factorion.html
    3) Factorions: equal to the sum of the factorials of their digits in base 10.
    http://oeis.org/A014080

  22. You say “this yields a speed-up of approximately a factor 2. So nothing big.” But in real life even a speed up of is highly appreciated by programmers. Nice post though. 🙂 I presume the upper bound is obtained by trial-and-error?

  23. Bhoszx says:

    Hi! I am new to programming and I’m trying to learn c++, how do I convert this to c++? Thanks

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

This site uses cookies.