online advertising

Monday, November 3, 2014

Problem 32 - Pandigital products

Problem: 

Please find the problem here.

Solution:

My current solution is kind of slow - it runs through all permutations and all possible splits to check for the product formula, and when it does accumulate the results, it is that simple.

It would be great if we could speed this up using some more constraints, but for now, this is good enough to produce and answer.

It would be an interesting detour to discuss the permutation generating algorithm. In some sense it is simple, pick the head, recursively compute the permutation of remaining elements, and concat with the head. Note that we could have been faster if we optimize the permutation method to reuse the same buffer instead of creating new list for each recursive result!

Code:

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

    internal static partial class Program
    {
        public static IEnumerable<IEnumerable<T>> Permutations<T>(IEnumerable<T> available)
        {
            List<T> availableList = available.ToList();
            return Permutations(availableList.Select(t => Pair<bool, T>.Create(true, t)).ToArray(), availableList.Count);
        }

        private static IEnumerable<IEnumerable<T>> Permutations<T>(Pair<bool, T>[] available, int count)
        {
            if (count == 0)
            {
                yield return new List<T> { };
            }

            for (int i = 0; i < available.Length; i++)
            {
                if (available[i].Item1)
                {
                    available[i].Item1 = false;
                    foreach (IEnumerable<T> recursiveResult in Permutations(available, count - 1))
                    {
                        yield return new List<T> { available[i].Item2 }.Concat(recursiveResult);
                    }

                    available[i].Item1 = true;
                }
            }
        }

        private class Pair<T, U>
        {
            public static Pair<T, U> Create(T item1, U item2)
            {
                return new Pair<T, U>(item1, item2);
            }

            private Pair(T item1, U item2)
            {
                this.Item1 = item1;
                this.Item2 = item2;
            }

            public T Item1 { get; set; }

            public U Item2 { get; set; }

        }

        public static void Problem032()
        {
            HashSet<int> results = new HashSet<int>();
            foreach (var permutation in Permutations(Enumerable.Range(1, 9).ToArray()))
            {
                // Break down the permutation into list of different partitions and check product formula
                for (int firstPart = 1; firstPart < 9; firstPart++)
                {
                    for (int secondPart = 1; secondPart < 9; secondPart++)
                    {
                        int thirdPart = 9 - firstPart - secondPart;
                        if (thirdPart > 0)
                        {
                            string permutationString = permutation.Aggregate("", (s, x) => s + x);
                            int firstPartValue = int.Parse(permutationString.Substring(0, firstPart));
                            int secondPartValue = int.Parse(permutationString.Substring(firstPart, secondPart));
                            int thirdPartValue = int.Parse(permutationString.Substring(9 - thirdPart));
                            if (firstPartValue == secondPartValue * thirdPartValue)
                            {
                                results.Add(firstPartValue);
                                //Console.WriteLine("{0} = {1} x {2}", firstPartValue, secondPartValue, thirdPartValue);
                            }
                        }
                    }
                }
            }
            Console.WriteLine(results.Aggregate((x, y) => x + y));
        }
    }
}

Problem 31 - Coin Sum

Problem:

Please find the problem here.

Solution:

It is easier to think when the number is smaller.

The number of ways to represent 15 using any number of coin is:

number of ways to represent 15 using coins (1, 2, 5) [by choosing using 0 10 coin]
+
number of ways to represent 5 using coins (1, 2, 5) [by choosing using 1 10 coin]

Similarly, the number of ways to represent 15 using coin (1, 2, 5) is:

number of ways to represent 15 using coins (1, 2, 5) [by choosing using 0 5 coin]
+
number of ways to represent 10 using coins (1, 2) [by choosing using 1 5 coin]
+
number of ways to represent 5 using coins (1, 2) [by choosing using 2 5 coin]
+
number of ways to represent 0 using coins (1, 2) [by choosing using 3 5 coin]

Of course the last term is 1, and now you get the idea how to use recursion to find the number of ways. The code do exactly that.

Code:

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

    internal static partial class Program
    {
        public static void Problem031()
        {
            // Count the number of using different coins
            int[] coinValues = new int[] { 1, 2, 5, 10, 20, 50, 100, 200 };
            Console.WriteLine(Way(200, coinValues, coinValues.Length - 1));
        }

        private static int Way(int value, int[] coinValues, int maxIndex)
        {
            // This is special because we know it is 1, the value is can always be represented as sum of 1 in only 1 way.
            if (maxIndex == 0)
            {
                return 1;
            }
            int maxValue = coinValues[maxIndex];
            return Enumerable.Range(0, value / maxValue + 1).Select(t => Way(value - maxValue * t, coinValues, maxIndex - 1)).Aggregate((x, y) => x + y);
        }
    }
}

Thursday, October 2, 2014

Problem 30 - Digit fifth powers

Problem:

Please find the problem here.

Solution:

The problem can be solved with brute force, just testing if the number matches the digit sum. The only problem is when do we stop the search.

Observe that the right hand side, despite raised to high power, are relatively small in magnitude since it got broken down into digits. For a six digit number, the maximum possible right hand side is
6x95 =354294, which is a 6 digit number, but 7x95 = 413343 is not a seven digit number. So all we need to do is to test the 6 digit numbers, in fact, only those less than 354294.

The rest is trivial. Caching the fifth powers of the digit can help quite a bit.

Code:

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

    internal static partial class Program
    {
        private class Solution030
        {
            public void Run()
            {
                Console.WriteLine(GetPowers().Aggregate((x, y) => x + y));
            }

            private IEnumerable<int> GetPowers()
            {
                int max = 9 * 9 * 9 * 9 * 9 * 6;
                int[] powers = Enumerable.Range(0, 10).Select(x => x * x * x * x * x).ToArray();
                for (int i = 1; i <= max; i++)
                {
                    IEnumerable<int> digits = i.ToString().Select(c => c - '0');
                    int digitPowerSum = digits.Select(d => powers[d]).Aggregate((x, y) => x + y);
                    if (digitPowerSum == i && i != 1)
                    {
                        yield return i;
                    }
                }
            }
        }

        public static void Problem030()
        {
            new Solution030().Run();
        }
    }
}

In fact, listing the found sums numbers is also fun:

4150 = 45 + 15 + 55 + 05
4151 = 45 + 15 + 55 + 15
54748 = 55 + 45 + 75 + 45 + 85
92727 = 95 + 25 + 75 + 25 + 75
93084 = 95 + 35 + 05 + 85 + 45
194979 = 15 + 95 + 45 + 95 + 75 + 95

Answer: 443839

Problem 29: Distinct Powers

Problem:

Please find the problem here.

Solution:

This is a counting problem. The elements can be big (e.g. 100100), but the number of elements is small, just at most 10,000 of them.

First, note that the set of powers can intersect only if they have the same prime factors with same ratios. For example, power of 2 will intersect with power of 4, but it will never intersect with power of 6. Similarly, power of 6 will never intersect with power of 12.

So we break the problem down to computing the count of union of some complicated disjoint sets.

{power of 2 union power of 4 union .. } union ... union { power of 6 union power of 36 union ... } union ...

As those sets are disjoint, the count of union is just the sum of counts. Now we focus on the compute the count of a particular term.

To compute the size of a union of a set of sets, we can use the inclusion-exclusion principle. In problem 1, we already applied the principle to compute the sum. This one is more complicated.

The hard part is to compute the size of an arbitrary intersection. For example, what is the size of {power of 2 union power of 4}?

Taking logarithm (to base 2 in this case) on the values will make the problem look simpler. Now we have the compute the size of {2, 3, ..., 100}, {4, 6, ..., 200}, so that is just {4, 6, ... 100}, which is 49, easy to compute in this case, but what is the general rule?

Abstractly, we are given sets of multiples and we wanted to find intersection. They are simply the common multiples. To compute the number of common multiples. We simply find the least common multiple, and then count how many multiple of that least common multiple can stay within the set.

Last but not least, we have to apply the inclusion-exclusion principle formula. The formula itself look daunting when applied with arbitrary number of sets, but fortunately, the formula can be implemented using gray code enumeration.

Gray code is a specific sequence of binary strings such that adjacent element of the sequence differ by only one bit. A sample sequence of 3 element is shown below:

000
001
011
010
110
111
101
100

By definition, the gray code flip one bit every time, so the parity of the sequence alternates (number of 1 is even -> number of 1 is odd -> ...) This is exactly what we need in the inclusion exclusion sum! So I simply adopted the gray code generation algorithm from The Art of Computer Programming, and coded the formula.

As an aside - reverse engineering this piece of code (written two years ago) to the description above isn't easy at all. I should really have written the blog by the time I coded it.

Code:


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

    internal static partial class Program
    {

        class Solution029
        {
            public void Run()
            {
                int A = 100;
                int B = 100;
                long sum = 0;
                bool[] processed = new bool[A + 1];
                for (int a = 2; a <= A; a++)
                {
                    if (!processed[a])
                    {
                        int numberOfSets = (int)Math.Log(B, a);
                        int c = a;
                        for (int i = 1; i <= numberOfSets; i++)
                        {
                            processed[c] = true;
                            c *= a;
                        }
                        IEnumerable<long> allPowers = Enumerable.Range(1, numberOfSets).Select(t => (long)t);
                        foreach (var code in Gray(numberOfSets))
                        {
                            var joined = Enumerable.Zip(allPowers, code.Item1, (x, y) => Tuple.Create(x, y));
                            var powers = joined.Where(t => t.Item2).Select(t => t.Item1);
                            if (powers.Count() == 0)
                            {
                                // Gray code generate this sequence - but this should simply be discarded since it make
                                // no sense for having an intersection of no sets.
                                // One could argue this is simply empty set and contribute 0 to sum, that's fine too.
                                continue;
                            }
                            // The size of the intersection of a particular subset can be computed using this formula
                            // min(powers) * B / lcm
                            var lcm = powers.Aggregate((x, y) => CommonMultiple(x, y));
                            var min = powers.Min();
                            var intersectionSize = min * B / lcm;
                            if (powers.Contains(lcm))
                            {
                                intersectionSize--;
                            }
                            sum = sum + (code.Item2 ? -1 : 1) * intersectionSize;
                        }
                    }
                }
                Console.WriteLine(sum);
            }

            // From "The Art of Computer Programming, book 4"
            private IEnumerable<Tuple<List<bool>, bool>> Gray(int n)
            {
                int parity = 0;
                bool[] bits = new bool[n];
                int j = 0;
                while (true)
                {
                    // Iterating gray code and present the inclusion-exclusion sum
                    yield return Tuple.Create(bits.ToList(), parity == 0);
                    parity = 1 - parity;
                    if (parity == 1)
                    {
                        j = 0;
                    }
                    else
                    {
                        int k = 0;
                        while (true)
                        {
                            if (bits[k])
                            {
                                break;
                            }
                            else
                            {
                                k++;
                            }
                        }
                        // Now we know bits[k] is true, and the minimal such k, then 
                        j = k + 1;
                    }
                    if (j == n)
                    {
                        yield break;
                    }
                    else
                    {
                        bits[j] = !bits[j];
                    }
                }
            }
        }
        public static void Problem029()
        {
            new Solution029().Run();
        }
    }
}

Answer: 9183

Tuesday, September 23, 2014

Problem 28: Number spiral diagonals

Problem:

Please find the problem here.

Solution:

Since 10012 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 = 16i2+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

Friday, September 5, 2014

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