Problem 20: Factorial digit sum

Problem:

Please find the problem here.

Solution:

It is well known that we can use Strling's approximation to approximate factorial, let see what we'll get from it. First of all, we have
$ \begin{eqnarray*} \sqrt{2 \pi} n^{n+\frac{1}{2}} e^{-n} \leq n! \leq e n^{n+\frac{1}{2}} e^{-n} \end{eqnarray*} $

Only the term $n^{n+\frac{1}{2}}e^{-n}$ matters, the rest are small. That gives us 100! is approximately $ 1.01 \times 10^{158} $.

This number is not small, but it is manageable to just compute 100! I don't have other solution to compute the sum of the digits anyway. Here is the code

namespace Euler
{
    using System;
    using System.Linq;
    using System.Numerics;

    internal static partial class Program
    {
        public static void Problem020()
        {
            BigInteger prod = new BigInteger(1);
            for (int i = 2; i <= 100; i++)
            {
                prod = BigInteger.Multiply(prod, new BigInteger(i));
            }
            Console.WriteLine(prod.ToString().Select(i => i - '0').Aggregate((x, y) => x + y));
        }
    }
}

Answer: 648

The value of 100! is actually
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

It has 159 digits, so the Stirling approximation above is pretty close.

Problem 19: Counting Sundays

Problem:

Please find the problem here.

Solution:

We might be able to compute it by the description, but it is much easier to use the built-in calendar. Here is the code:

namespace Problem019
{
    using System;

    class Program
    {
        static void Main(string[] args)
        {
            int sum = 0;
            for (int year = 1901; year <= 2000; year++)
            {
                for (int month = 1; month <= 12; month++)
                {
                    if (new DateTime(year, month, 1).DayOfWeek == DayOfWeek.Sunday)
                    {
                        sum++;
                    }
                }
            }
            Console.WriteLine(sum);
            
        }
    }
}

Answer: 171

Problem 18: Maximum Path Sum I

Problem:

Please find the problem here.

Solution:

Instead of solving it by brute force, I think it is easier to solve it with dynamic programming. First, let generalize the problem by asking the question - what is the maximum route from an arbitrary node to bottom? The base case is really simple. If you are trying to go from the bottom row to the bottom row, there is only one route with one node, and therefore the maximum total is the node value itself. Now, if we want to reach the node 2 (1st in the 3rd row) in the first triangle, we will pick the left route because 2 + 8 has a bigger sum than 2 + 5. The rule generally applies. If we want to go to 7 (the 1st in the 2nd row), we pick from its children the one with maximum total.

That translate to a dynamic programming algorithm as follow:

maximum_total_cost(last_row) = last_row value
maximum_total_cost(any node n ) = n + max(maximum_total_cost(left_child) + maximum_total_cost(right_child)).

Without further ado, here is the code for the problem:

namespace Euler
{
    using System;
    using System.Linq;
    using System.Numerics;

    internal static partial class Program
    {
        public static void Problem018()
        {
            string input = ReadResourceAsString("Euler.Problem018.txt");
            int[] inputParsed = input.Replace('\r', ' ').Replace('\n', ' ').Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(x => Int32.Parse(x)).ToArray();
            int numRows = 15;

            // answer(row, column) = data[row, column] + max(answer(row + 1, column), answer(row + 1, column + 1));

            int[,] answer = new int[numRows, numRows];
            for (int i = 1; i <= numRows; i++)
            {
                answer[i - 1, numRows - 1] = inputParsed[i + numRows * (numRows - 1) / 2 - 1];
            }
            for (int currentRow = numRows - 1; currentRow > 0; currentRow--)
            {
                for (int currentColumn = 1; currentColumn <= currentRow; currentColumn++)
                {
                    int currentValue = inputParsed[currentColumn + currentRow * (currentRow - 1) / 2 - 1];
                    answer[currentColumn - 1, currentRow - 1] = currentValue + Math.Max(answer[currentColumn - 1, currentRow + 1 - 1], answer[currentColumn + 1 - 1, currentRow + 1 - 1]);
                }
            }
            Console.WriteLine(answer[0, 0]);
        }
    }
}

Answer: 1074

Problem 17: Number letter counts

Problem:

Please find the problem here.

Solution:

Just implement the rules - nothing special about this problem, here is the code. Note that ToEnglishString() works only if the input is between 1 to 1000, which is enough for the purpose.

namespace Euler
{
    using System;
    using System.Linq;

    internal static partial class Program
    {
        public static void Problem017()
        {   
            Console.WriteLine(Enumerable.Range(1, 1000).Select(i => ToEnglishString(i).Replace(" ", string.Empty).Length).Aggregate((x, y) => x + y));
        }

        static string ToEnglishString(int i)
        {
            string ONE = "one";
            string TWO = "two";
            string THREE = "three";
            string FOUR = "four";
            string FIVE = "five";
            string SIX = "six";
            string SEVEN = "seven";
            string EIGHT = "eight";
            string NINE = "nine";
            string TEN = "ten";
            string ELEVEN = "eleven";
            string TWELVE = "twelve ";
            string THIRTEEN = "thirteen";
            string FOURTEEN = "fourteen";
            string FIFTEEN = "fifteen";
            string SIXTEEN = "sixteen";
            string SEVENTEEN = "seventeen";
            string EIGHTEEN = "eighteen";
            string NINETEEN = "nineteen";
            string TWENTY = "twenty";
            string THIRTY = "thirty";
            string FORTY = "forty";
            string FIFTY = "fifty";
            string SIXTY = "sixty";
            string SEVENTY = "seventy";
            string EIGHTY = "eighty";
            string NINETY = "ninety";
            string HUNDRED = "hundred";
            string THOUSAND = "thousand";
            switch (i)
            {
                case 1000: return ONE + " " + THOUSAND;
                case 1: return ONE;
                case 2: return TWO;
                case 3: return THREE;
                case 4: return FOUR;
                case 5: return FIVE;
                case 6: return SIX;
                case 7: return SEVEN;
                case 8: return EIGHT;
                case 9: return NINE;
                case 10: return TEN;
                case 11: return ELEVEN;
                case 12: return TWELVE;
                case 13: return THIRTEEN;
                case 14: return FOURTEEN;
                case 15: return FIFTEEN;
                case 16: return SIXTEEN;
                case 17: return SEVENTEEN;
                case 18: return EIGHTEEN;
                case 19: return NINETEEN;
                case 20: return TWENTY;
                default:
                    string result = string.Empty;
                    int remaining;
                    int hundredthDigit = i / 100;
                    remaining = i - hundredthDigit * 100;
                    if (hundredthDigit != 0)
                    {
                        result += ToEnglishString(hundredthDigit) + " " + HUNDRED;
                        if (remaining == 0)
                        {
                            return result;
                        }
                        else
                        {
                            result = result + " and ";
                        }
                    }

                    int tenthDigit = remaining / 10;
                    remaining = remaining - tenthDigit * 10;

                    switch (tenthDigit)
                    {
                        case 1:
                            switch (remaining)
                            {
                                case 0: result = result + TEN; break;
                                case 1: result = result + ELEVEN; break;
                                case 2: result = result + TWELVE; break;
                                case 3: result = result + THIRTEEN; break;
                                case 4: result = result + FOURTEEN; break;
                                case 5: result = result + FIFTEEN; break;
                                case 6: result = result + SIXTEEN; break;
                                case 7: result = result + SEVENTEEN; break;
                                case 8: result = result + EIGHTEEN; break;
                                case 9: result = result + NINETEEN; break;

                            };
                            remaining = 0;
                            break;
                        case 2: result = result + TWENTY; break;
                        case 3: result = result + THIRTY; break;
                        case 4: result = result + FORTY; break;
                        case 5: result = result + FIFTY; break;
                        case 6: result = result + SIXTY; break;
                        case 7: result = result + SEVENTY; break;
                        case 8: result = result + EIGHTY; break;
                        case 9: result = result + NINETY; break;
                    }
                    if (tenthDigit != 0)
                    {
                        result = result + " ";
                    }
                    if (remaining != 0)
                    {
                        result = result + ToEnglishString(remaining);
                    }
                    return result;
            }

        }
    }
}

Answer: 21224

Problem 16: Power Digit Sum

Problem:

Please find the problem here.

Solution:

Just compute it with BigInteger in C#. Here is the code:

namespace Euler
{
    using System;
    using System.Linq;
    using System.Numerics;

    internal static partial class Program
    {
        public static void Problem016()
        {
            BigInteger p = BigInteger.Pow(new BigInteger(2), 1000);
            Console.WriteLine(p.ToString().Select(x => x - '0').Aggregate((x, y) => (x + y)));
        }
    }
}

Answer: 1366

Problem 15: Lattice paths

Problem:

Please find the problem here.

Solution:

The key observation here is that the number of way to reach a particular point is the number of ways to reach the point above it plus the number of way to reach the point on the left of it.

If you rotate the diagram by 45 degree clockwise, the recursion will look familar, it is simply the pascal triangle. On the wiki, this problem is sited as one of the picture!

Computing a pascal triangle is trivial, here is the code!

namespace Euler
{
    using System;
    using System.Numerics;

    internal static partial class Program
    {
        public static void Problem015()
        {
            Console.WriteLine(BinomialCoefficient(40, 20));
        }

        public static BigInteger BinomialCoefficient(long n, long c)
        {
            return BinomialCoefficient(n, c, BuildPascalTriangle(n));
        }

        public static BigInteger BinomialCoefficient(long n, long c, BigInteger[,] pascalTriangle)
        {
            return pascalTriangle[n - 1, c];
        }

        public static BigInteger[,] BuildPascalTriangle(long n)
        {
            BigInteger[,] content = new BigInteger[n, n + 1];
            content[0, 0] = BigInteger.One;
            content[0, 1] = BigInteger.One;
            for (long i = 1; i < n; i++)
            {
                content[i, 0] = 1;
                for (long j = 1; j < i + 2; j++)
                {
                    content[i, j] = content[i - 1, j - 1] + content[i - 1, j];
                }
                content[i, i + 1] = 1;
            }
            return content;
        }
    }
}

Answer: 137846528820

An amazing large number of possibilities.

Problem 14: Longest Collatz sequence

Problem:

Please find the problem here.

Solution:

Given the sequence is so random, I am not hoping to be able to count it without going through it. Going through all sequences, however, is going to take long time. Therefore, we need to find a trick to improve it.

The key idea is after going through 1 chain, we will know the length of all elements in the chain. In the example, we know 13 has a length of 10, but we also know 40 has a length of 9, and so on.

Suppose we have another sequence that have k → 40 → ... , we know k is going to have a length 10. Optimization like that save a lot of time because repeated checking of the same sequences is eliminated, and in practice the problem involve many repeated sequences.

This trick is generally called memoization (NOTE: Don't be confused this work with memorization, they spell differently). The code is pretty simple.

namespace Euler
{
    using System;
    using System.Collections.Generic;
    using System.Linq;

    internal static partial class Program
    {
        public static void Problem014()
        {
            var lengths = new Dictionary<long, long>();
            for (long i = 1; i <= 1000000; i++)
            {
                Length(i, lengths);
            }
            var lengthSorted = lengths.ToList();
            lengthSorted.Sort((x, y) => (x.Value < y.Value) ? 1 : ((x.Value == y.Value) ? 0 : -1));


            Console.WriteLine(lengthSorted[0].Key);
        }

        private static long Length(long x, Dictionary<long, long> lengths)
        {
            if (x == 1)
            {
                return 1;
            }
            else
            {
                long result;
                if (lengths.TryGetValue(x, out result))
                {
                    return result;
                }
                else
                {
                    long next = x % 2 == 0 ? x / 2 : (3 * x + 1);
                    result = 1 + Length(next, lengths);
                    lengths.Add(x, result);
                    return result;
                }
            }
        }
    }
}

Answer: 837799