Problem 22: Names scores

Problem:

Please find the problem here.

Solution:

Just compute all the scores and add them up. Nothing special, so I will just post the code.

namespace Euler
{
    using System;
    using System.Linq;

    internal static partial class Program
    {
        public static void Problem022()
        {
            string[] names = ReadResourceAsString("Euler.Problem022.txt").Split(new char[] { '"', ',' }, StringSplitOptions.RemoveEmptyEntries);
            Array.Sort(names);
            var nameValues = names.Select((s, i) => Tuple.Create(s, i + 1L)).Select(t => Tuple.Create(t.Item1, t.Item1.Select(c => c - 'A' + 1).Aggregate((x, y) => x + y), t.Item2));
            Console.WriteLine(nameValues.Select(t => t.Item2 * t.Item3).Aggregate((x, y) => x + y));
        }
    }
}

Answer: 871198282

Problem 21: Amicable numbers

Problem:

Please find the problem here.

Solution:

Finally, we got another problem that feel like more number theoretic. A straightforward implementation would be checking, for each number i under 10000, if the SumOfProperDivisor(SumOfProperDivisor(i)) == i, and if so, add it to the sum, and that's all.

Therefore the problem becomes computing sum of proper divisor, turn out it is easier to consider the sum of divisor first. The sum of divisor, like the divisor function we encountered in problem 12, is multiplicative. Just like in proving the divisor function is multiplicative, we use the one to one correspondence between the a divisor of pq and the divisor of p, divisor of q pair. Now group the pairs by the first component we can see the sum and be factorized and we can see the sum of divisor function is multiplicative. The sum of divisor function for a prime power is simply a geometric series and is easily evaluated. 

The last twist in the problem is the SumOfProperDivisor(SumOfProperDivisor(i)) part. Turn out SumOfProperDivisor(i) can be larger than i (which are called abundant numbers), so we need to evaluate more SumOfProperDivisor(i) to its max to make sure we don't index out of bound.

Without further ado, here is the code:

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

    internal static partial class Program
    {
        public static void Problem021()
        {
            Dictionary<int, int> d = new Dictionary<int, int>();
            d.Add(1, 0);
            for (int i = 2; i <= 10000; i++)
            {
                d.Add(i, SumOfProperDivisor(i));
            }
            long maxSumOfDivisorWithin10000 = d.Values.Max();
            for (int i = 10001; i <= maxSumOfDivisorWithin10000; i++)
            {
                d.Add(i, SumOfProperDivisor(i));
            }
            Console.WriteLine(AmicableNumbers(d).Aggregate((x, y) => x + y));
        }

        private static IEnumerable<int> AmicableNumbers(Dictionary<int, int> d)
        {
            for (int i = 2; i <= 10000; i++)
            {
                if (d[d[i]] == i & i != d[i])
                {
                    yield return i;
                }
            }
        }

        private static int SumOfProperDivisor(int i)
        {
            return SumOfDivisor(i) - i;
        }

        private static int SumOfDivisor(int i)
        {
            var groupedFactors = BruteForceFactor(i).ToList();
            return groupedFactors.Select(kvp => (Power(kvp.Item1, kvp.Item2 + 1) - 1) / (kvp.Item1 - 1)).Aggregate((x, y) => x * y);
        }

        private static int Power(int x, int y)
        {
            if (y == 0)
            {
                return 1;
            }
            else if (y == 1)
            {
                return x;
            }
            else
            {
                int r = Power(x, y / 2);
                return y % 2 == 0 ? r * r : r * r * x;
            }

        }
    }
}

We could have optimized the factoring by eliminating trials using the Sieve_of_Eratosthenes. The idea is, instead of crossing out the number, we compute the power and store the information along. So at the end of the sieve, we got all factorizations we will need. It don't bother me to optimize right now as the performance of the previous code is fine.

Note that we reused the BruteForceFactor routine from problem 12.

Answer: 31626

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