online advertising

Thursday, October 2, 2014

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

No comments :

Post a Comment