2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ For the record, these numbers are known as Factorions. The series can be found at A014080. As there are only 4 of them (in base 10 anyhow), your function could simply look them up from an array instead of calculating it, which would be much faster, though that's kind of cheating a bit... \$\endgroup\$ – Darrel Hoffman Apr 12 '16 at 19:45
3
\$\begingroup\$

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;
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ Mine runs for ~1120, yours for ~800 it is improvement thanks, but I will still wait for more answer to come.. eventually with even greater performance increase. \$\endgroup\$ – Denis Apr 12 '16 at 16:42
  • \$\begingroup\$ Turning the Select(...) statement in IsCuriousNumber into a for-loop would improve it a bit, I guess. \$\endgroup\$ – Dennis_E Apr 12 '16 at 16:45
  • \$\begingroup\$ It's actually working for ~500 ms when I changed it to foreach loop now that's much better almost halved your initial time. \$\endgroup\$ – Denis Apr 12 '16 at 16:48
  • \$\begingroup\$ It seems still needless complicated ... enumerable.range.select.toArray ... why not{1,1,2,6,24,120,720,5040,40320,362880,3628800} \$\endgroup\$ – edc65 Apr 12 '16 at 19:34
  • \$\begingroup\$ @edc65 That's actually what I did in my original code... If you don't know the numbers you need from the top of your head, you can always calculate them. \$\endgroup\$ – Dennis_E Apr 13 '16 at 8:00
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I forgot to change the sum to long thanks for noting that however this doesn't improve the performance it works just 10-20 ms faster if not even none. I added the performance tag now. \$\endgroup\$ – Denis Apr 12 '16 at 16:29
  • \$\begingroup\$ @denis I've updated the answer. Please revise. \$\endgroup\$ – Dmitry Apr 12 '16 at 16:53
  • \$\begingroup\$ I tested the updated answer, it runs in ~640 ms Dennis_E's answer take's ~500 ms \$\endgroup\$ – Denis Apr 12 '16 at 16:59
  • \$\begingroup\$ @denis Probably it's because I use longs while in Dennis_E's answer ints are used. I've updated the answer. \$\endgroup\$ – Dmitry Apr 12 '16 at 19:21
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.