Problem 25: 1000-digit Fibonacci number

Problem:

Please find the problem here.

Solution:

It is not hard to find online the Binet formula to compute Fibonacci number.
$ F_n = (\frac{\sqrt{5} + 1}{2})^n + (\frac{\sqrt{5} - 1}{2})^n $

Note that the second term is an exponential of a number less than 1, that goes to 0 quickly, so let's just ignore that and we get a good approximation

$ \begin{eqnarray*} F_n & \simeq & (\frac{\sqrt{5} + 1}{2})^n \\ \log(F_n) & \simeq & n \log (\frac{\sqrt{5} + 1}{2}) \end{eqnarray*} $

This gives us $ n \simeq 4785 $ when $ \log(F_n) \simeq 1000 $. That means if we use the trivial algorithm for computing Fibonacci number, it takes around 4785 additions and we will get the answer. However, since we know the answer will be approximately 4785, we have a much faster algorithm that allow us to compute $ F_{4785} $.

The algorithm start with observing the matrix

$ \begin{eqnarray*} \left(\begin{matrix}1 & 1 \\ 1 & 0\end{matrix}\right)^n = \left(\begin{matrix}F_{n+1} & F_{n} \\ F_{n} & 0\end{matrix}\right) \end{eqnarray*} $

With that, we can easily compute $ F_n $ by repeated squaring. Observing the matrix is symmetric we can reduce some arithmetic operations as well.

Once we get to the approximate solution, we need to walk to the solution. By some computation I know $ F_{4785} $ has 1,000 digits, so we need to walk backwards to see when it get started to become 999 digits, and that's when we can stop.

namespace Euler
{
    using System;
    using System.Numerics;

    internal static partial class Program
    {
        public static void Problem025()
        {
            new Solution025().Execute();
        }

        private class Solution025
        {
            public void Execute()
            {
                FibMatrix one = new FibMatrix
                {
                    a = 1,
                    b = 1,
                    d = 0
                };

                // By Binet formula approximation, we know the solution is around this
                int n = 4784;
                FibMatrix m = Power(one, n, one, Multiply);

                BigInteger big = m.a;
                BigInteger small = m.b;
                // small is the nth Fibonacci number

                // I already know small has 1000 digits by debugging, so I know I need to going backwards
                // in full generality I need to check if I need forward as well
                while (small.ToString().Length >= 1000)
                {
                    BigInteger prev = big - small;
                    big = small;
                    small = prev;
                    n--;
                    // small is still the nth Fibonacci number after the line
                }

                // Small has 999 digits, big has 1000 digit, so the answer is n + 1
                Console.WriteLine(n + 1);
            }

            private FibMatrix Multiply(FibMatrix p, FibMatrix q)
            {
                FibMatrix result = new FibMatrix();
                result.a = p.a * q.a + p.b * q.b;
                result.b = p.a * q.b + p.b * q.d;
                result.d = p.b * q.b + p.d * q.d;
                return result;
            }

            private class FibMatrix
            {
                public BigInteger a;
                public BigInteger b;
                public BigInteger d;
            }
        }
    }
}

Answer: 4782

Note how close is it for our analytic approximation.

Problem 24: Lexicographic permutations

Problem:

Please find the problem here.

Solution:

By dividing the set of permutations by the first digit into partitions, the set of all permutation of n digits can be divided into n partitions of size (n-1)!. The first thing to do is to determine which partition the kth permutation belongs to, it can easily computed to be floor((k - 1)/(n-1)!), that determine the first digit. Then, we know it is the (k-1) % (n-1)! permutation in the remaining digits, so we can just compute that recursively.

Once we have the analysis, the code came by really easily.

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

    internal static partial class Program
    {
        public static void Problem024()
        {
            int[] factorials = new int[11];
            factorials[0] = 1;
            for (int i = 1; i <= 10; i++)
            {
                factorials[i] = factorials[i - 1] * i;
            }

            // There are nine factorials number starts with 0
            // There are nine factorials number starts with 1, 
            // ...

            int current = 1000000 - 1;
            List<int> availableDigits = Enumerable.Range(0, 10).ToList();
            while (availableDigits.Count > 0)
            {
                int partitionSize = factorials[availableDigits.Count - 1];
                int quotient = current / partitionSize;
                int remainder = current % partitionSize;
                int partitionNumber = quotient + 1;
                current = remainder;
                Console.Write(availableDigits[partitionNumber - 1]);
                availableDigits.RemoveAt(partitionNumber - 1);
            }
            Console.WriteLine();
        }
    }
}

Answer: 2783915460

Problem 23: Non-abundant sums

Problem:

Please find the problem here.

Solution:

As we have already explained in Problem 21, it is easy to tell if a number is abundant by computing the sum of proper divisor function. Since we are given that every number larger than 28123 can be written as sum of two abundant numbers, so we don't have to consider any of the abundant numbers larger than that.

So we first creating a set of all abundant numbers less than 28124 (turn out there are around 7,000 of them), then we create the set of all abundant number sums. Finally, we evaluate all the number below 28124 and test if they're sum of abundant number, that's all.

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

    internal static partial class Program
    {
        public static void Problem023()
        {
            List<int> abundantNumbers = new List<int>();
            for (int i = 2; i <= 28124; i++)
            {
                if (IsAbundantNumbers(i))
                {
                    abundantNumbers.Add(i);
                }
            }

            HashSet<int> abundantSums = new HashSet<int>();
            foreach (int abundantNumber1 in abundantNumbers)
            {
                foreach (int abundantNumber2 in abundantNumbers)
                {
                    abundantSums.Add(abundantNumber1 + abundantNumber2);
                }
            }

            long answer = (1 + 23) * 23 / 2;
            for (int i = 24; i < 28124; i++)
            {
                if (!abundantSums.Contains(i))
                {
                    answer += i;
                }
            }
            Console.WriteLine(answer);
        }

        private static bool IsAbundantNumbers(int i)
        {
            return SumOfProperDivisor(i) > i;
        }
    }
}

Note that the code reused the SumOfProperDivisor function in Problem 21.

Answer: 4179871

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