Problem 28: Number spiral diagonals

Problem:

Please find the problem here.

Solution:

Since 1001² is small, I could have just fill the spiral and compute the sum. In fact, that is how I got the answer accepted for the first time. But I decide this is a chance for me to do some math, and so I do.

First notice the spiral (except the initial 1) can be decomposed into "Shells", each shell starts with the upper right corner and ends with a perfect square at the upper left corner. The values at the corners forms an arithmetic progression with common difference 2 * i, where i is the shell number, starting from 1.

With that observation, it is easy to translate that to the code below.

Apparently, the code can be further simplified, but I am not doing that in the code for simplicity.

Using Matlab, we can simplify this quickly using the commands below

clear
syms i
e = (2 * i + 1)^2
d = 2 * i
s = e - 3 * d
t = (s + e) * 4 / 2
expand(t)

Now t = 16i²+4i+4 is the term for summation, given the summation formula, we can even sum them up directly as follow

clear
syms n
q = n * (n + 1) * (2 * n + 1) / 6
l = n * (n + 1) / 2
o = 16 * q + 4 * l + 4 * n + 1
expand(o)

That gives the overall sum formula to be 16/3*n^3+10*n^2+26/3*n+1, an amazing simple cubic equation.

Code:

namespace Euler

{
    using System;

    internal static partial class Program
    {
        public static void Problem028()
        {
            long sum = 1;
            for (int i = 1; i < (1001 + 1) / 2; i++)
            {
                long end = (2 * i + 1) * (2 * i + 1);
                long diff = 2 * i;
                long start = end - 3 * diff;
                sum += (start + end) * 4 / 2;
            }
            Console.WriteLine(sum);
        }
    }
}

Answer: 669171001

Problem 27: Quadratic primes

Problem:

Please find the problem here.

Solution:

There isn't much we could do with this one, just try them all and find the best. The only optimization I have done is cache the is prime check, and it is quick enough for now.

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

    internal static partial class Program
    {
        private static Dictionary<long, bool> primeCache = new Dictionary<long, bool>();

        public static void Problem027()
        {
            Tuple<int, int> best = Tuple.Create(-1, -1);
            for (int a = -1000; a <= 1000; a++)
            {
                for (int b = -1000; b <= 1000; b++)
                {

                    long current = 0;
                    int length = 0;
                    while (true)
                    {
                        long value = current * current + a * current + b;
                        if (!IsPrime(value))
                        {
                            break;
                        }

                        length++;
                        current++;
                    }
                    if (length > best.Item1)
                    {
                        best = Tuple.Create(length, a * b);
                    }
                };
            };
            Console.WriteLine(best.Item1);
            Console.WriteLine(best.Item2);
        }

        private static bool IsPrime(long x)
        {
            if (x < 0)
            {
                x = -x;
            }
            bool result;
            if (primeCache.TryGetValue(x, out result))
            {
                return result;
            }
            for (long y = 2; y < x; y++)
            {
                if (x % y == 0)
                {
                    primeCache.Add(x, false);
                    return false;
                }
            }
            primeCache.Add(x, true);
            return true;
        }
    }
}

Answer: -59231

Given the restriction - the best quadratic formula can only output 71 primes.

Problem 26:Reciprocal cycles

Problem:

Please find the problem here.

Solution:

The key for this problem is to find the recurring cycle. For human, finding the recurring cycle involve long division and finding repeating dividend. We can code exactly that by dividing, multiply the remainder by 10 (much like adding zero in long division), and divide again, until we see the same dividend again.

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

    internal static partial class Program
    {
        public static void Problem026()
        {
            IEnumerable<Tuple<int, int>> recurringPartLength = GetRecurringPartLengths();
            int maxLength = recurringPartLength.Select(t => t.Item2).Max();
            Console.WriteLine(recurringPartLength.Single(t => t.Item2 == maxLength).Item1);
        }

        private static IEnumerable<Tuple<int, int>> GetRecurringPartLengths()
        {
            for (int d = 2; d < 1000; d++)
            {
                Tuple<List<int>, int> decimalRepresentation = GetDecimalRepresentation(d);
                if (decimalRepresentation != null)
                {
                    IEnumerable<int> recurringPart = decimalRepresentation.Item1.Skip(decimalRepresentation.Item2 - 1);
                    yield return Tuple.Create(d, recurringPart.Count());
                }
            }
        }

        private static Tuple<List<int>, int> GetDecimalRepresentation(int d)
        {
            int n = 1;
            List<int> quotients = new List<int>();
            // We need to stop when we see the same number to divide - we already know what would happen
            Dictionary<int, int> seen = new Dictionary<int, int>();
            int position = 0;
            while (true)
            {
                n = n * 10;
                position++;
                int previousIndex;

                if (seen.TryGetValue(n, out previousIndex))
                {
                    return Tuple.Create(quotients, previousIndex);
                }
                else
                {
                    seen.Add(n, position);
                    int quotient = n / d;
                    quotients.Add(quotient);
                }
                n = n % d;
                if (n == 0)
                {
                    return null;
                }
            }
        }
    }
}

Answer: 983

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