Project Euler #34 Digit factorials

Question

I'm having trouble improving the performance of the solution to the Project Euler problem #34

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.

I've done the following :

    private static readonly int max = (int)Factorial(9)*7;
    private static void Main()
    {
        long sum = 0;
        Stopwatch sw = new Stopwatch();
        sw.Start();
        for (int i = 3; i <= max; i++)
        {
            if (IsCuriousNumber(i))
            {
                sum += i;
            }
        }
        sw.Stop();
        Console.WriteLine(sum);
        Console.WriteLine("Time to calculate in milliseconds : {0}", sw.ElapsedMilliseconds);
        Console.ReadKey();
    }

    private static long Factorial(int input)
    {
        int sum = 1;
        for (int i = 1; i <= input; i++)
        {
            sum *= i;
        }
        return sum;
    }

    private static bool IsCuriousNumber(long input)
    {
        char[] digits = input.ToString().ToCharArray();
        long sum = digits.Sum(t => Factorial((int) char.GetNumericValue(t)));
        return sum == input;
    }

It's pretty much self-explanatory .. We have a method to find the factorial of specific number and one more method that checks if a number is "curious" as described in the problem above. We do this by simply converting the input to a char array than we have a variable that just sum's up all the factorials of the digits in the number.

Answer 1

I ran your code and it ran in 1397 milliseconds, so that's not something to worry about. However, there is something very inefficient about your code: you calculate Factorial for every digit you encounter.
Calculate them in advance.

You have declared your sum variable inside the Factorial(i) method as an int, while the return type is long. However, you are never dealing with a long value, so you can just change the return type to int.
(You're only calculating up to 9!, which fits well within the range for int)

Also, converting each number to a string and back again is kinda slow too.

class Euler034
{
    //Calculate the factorials in advance and just look them up.
    private static readonly int[] fact = Enumerable.Range(0, 10).Select(Factorial).ToArray();
    private static readonly int max = fact[9] * 7;

    public static void Main()
    {
        //Convenient method for creating and starting a Stopwatch
        Stopwatch watch = Stopwatch.StartNew();
        int sum = 0;
        for (int i = 4; i <= max; i++) {
            if (IsCuriousNumber(i)) sum += i;
        }
        watch.Stop();
        Console.WriteLine(sum);
        Console.WriteLine("Time to calculate in milliseconds : {0}", sw.ElapsedMilliseconds);
        Console.ReadKey();
    }

    private bool IsCuriousNumber(int number) {
        return number == Digits(number).Select(i => fact[i]).Sum();
    }

    private static int Factorial(int number)
    {
        int sum = 1;
        for (int i = 1; i <= number; i++) {
            sum *= i;
        }
        return sum;
    }

    private static IEnumerable<int> Digits(int number)
    {
        while (number > 0) {
            yield return number % 10;
            number /= 10;
        }
    }
}

Answer 2

I'd prefer to get digits of a number using integer math:

private static IEnumerable<int> GetDigits(int number)
{
    while (number != 0)
    {
        yield return number % 10;
        number /= 10;
    }
}

In this method digits are enumerated in reverse order, but it doesn't matter. Moreover, we can take an advantage of it.

private static bool IsCuriousNumber(int input)
{
    var digits = GetDigits(input);
    int sum = 0;
    foreach (int i in digits)
    {
        sum += Factorial(i);
        if (sum > input)
            return false;
    }
    return sum == input;
}

I've replaced the long sum = digits.Sum(t => Factorial(t)); with foreach loop to be able break the loop as soon as a current sum value exceeds the input. Reverse digits order is an opportune moment here.

---

Also, you could store an array of calculated factorials for digits and eliminate the Factorial method:

private static readonly int[] Factorials;

static Program()
{
    Factorials = new int[10];
    Factorials[0] = 1;
    for (int i = 1; i < Factorials.Length; i++)
    {
        Factorials[i] = Factorials[i - 1] * i;
    }
}

In this case the IsCuriousNumber method looks like:

private static bool IsCuriousNumber(int input)
{
    var digits = GetDigits(input);
    int sum = 0;
    foreach (int i in digits)
    {
        sum += Factorials[i]; // The only changed line
        if (sum > input)
            return false;
    }
    return sum == input;
}

---

You could also use the Paraller.For instead of for:

int sum = 0;
Parallel.For(3, max + 1, i =>
    {
        if (IsCuriousNumber(i))
        {
            Interlocked.Add(ref sum, i);
        }
    });

Replacing long with int also speeds up the solution. Please revise.

Answer 3

An easy way to speed this up is to calculate the factorial of 1..9 and storing the values including 0, 0 e.g in a Dictionary<TKey, TValue> once.

Looking up the values in the dictionary will take less time then calculating the factorials each time.