online advertising

Wednesday, August 28, 2013

Problem 15: Lattice paths

Problem:

Please find the problem here.

Solution:

The key observation here is that the number of way to reach a particular point is the number of ways to reach the point above it plus the number of way to reach the point on the left of it.

If you rotate the diagram by 45 degree clockwise, the recursion will look familar, it is simply the pascal triangle. On the wiki, this problem is sited as one of the picture!

Computing a pascal triangle is trivial, here is the code!


namespace Euler
{
    using System;
    using System.Numerics;

    internal static partial class Program
    {
        public static void Problem015()
        {
            Console.WriteLine(BinomialCoefficient(40, 20));
        }

        public static BigInteger BinomialCoefficient(long n, long c)
        {
            return BinomialCoefficient(n, c, BuildPascalTriangle(n));
        }

        public static BigInteger BinomialCoefficient(long n, long c, BigInteger[,] pascalTriangle)
        {
            return pascalTriangle[n - 1, c];
        }

        public static BigInteger[,] BuildPascalTriangle(long n)
        {
            BigInteger[,] content = new BigInteger[n, n + 1];
            content[0, 0] = BigInteger.One;
            content[0, 1] = BigInteger.One;
            for (long i = 1; i < n; i++)
            {
                content[i, 0] = 1;
                for (long j = 1; j < i + 2; j++)
                {
                    content[i, j] = content[i - 1, j - 1] + content[i - 1, j];
                }
                content[i, i + 1] = 1;
            }
            return content;
        }
    }
}

Answer: 137846528820

An amazing large number of possibilities.

Problem 14: Longest Collatz sequence

Problem:

Please find the problem here.

Solution:

Given the sequence is so random, I am not hoping to be able to count it without going through it. Going through all sequences, however, is going to take long time. Therefore, we need to find a trick to improve it.

The key idea is after going through 1 chain, we will know the length of all elements in the chain. In the example, we know 13 has a length of 10, but we also know 40 has a length of 9, and so on.

Suppose we have another sequence that have k → 40 → ... , we know k is going to have a length 10. Optimization like that save a lot of time because repeated checking of the same sequences is eliminated, and in practice the problem involve many repeated sequences.

This trick is generally called memoization (NOTE: Don't be confused this work with memorization, they spell differently). The code is pretty simple.

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

    internal static partial class Program
    {
        public static void Problem014()
        {
            var lengths = new Dictionary<long, long>();
            for (long i = 1; i <= 1000000; i++)
            {
                Length(i, lengths);
            }
            var lengthSorted = lengths.ToList();
            lengthSorted.Sort((x, y) => (x.Value < y.Value) ? 1 : ((x.Value == y.Value) ? 0 : -1));


            Console.WriteLine(lengthSorted[0].Key);
        }

        private static long Length(long x, Dictionary<long, long> lengths)
        {
            if (x == 1)
            {
                return 1;
            }
            else
            {
                long result;
                if (lengths.TryGetValue(x, out result))
                {
                    return result;
                }
                else
                {
                    long next = x % 2 == 0 ? x / 2 : (3 * x + 1);
                    result = 1 + Length(next, lengths);
                    lengths.Add(x, result);
                    return result;
                }
            }
        }
    }
}

Answer: 837799

Problem 13: Large sum

Problem:

Please find the problem here.

Solution:

Welcome to the world of BigInteger. With BigIntegers, you can do arbitrary precision arithmetic at ease. Here is the code, real no brainer, just computing sum.

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

    internal static partial class Program
    {
        public static void Problem013()
        {
            var text = ReadResourceAsString("Euler.Problem013.txt").Split(new char[] { '\r', '\n' }, StringSplitOptions.RemoveEmptyEntries);
            var data = text.Select(t => BigInteger.Parse(t));
            Console.WriteLine(data.Aggregate((a, b) => BigInteger.Add(a, b)).ToString().Substring(0, 10));
        }
    }
}

Answer: 5537376230

Problem 12: Highly divisible triangular number

Problem:

Please find the problem here.

Solution

It is easy to generate triangle number, what is not easy is to count the number of divisors. Here we should say something about the divisor function. Simply put, the divisor function, denoted by $ \sigma(n) $ of a positive integer $ n $ counts the number of positive factors (including 1 and n) a number has. For example, we have $ \sigma(3) = 2 $ because 1 and 3 are the only factors for 3.

A key property of the divisor function is that it is multiplicative. That is to say, if GCD(p, q) = 1, then $ \sigma(p \times q) = \sigma(p) \times \sigma(q) $. This can be proved by creating a bijection between a factor of $ p \times q $ and the pair of factors of $ p $ and $ q $.

The divisor function value of a prime power is particularly easy. Suppose $ p $ is prime, then $ \sigma(p^n) = n + 1$ because the only factors are 1, $ p $, $ p^2 $, ..., $ p^n $.

Now we know how to compute the divisor function by completely factorize the number into prime powers, and leverage the multiplicative property.

Last but not least, it is easy to see the nth triangular number is simply $ \frac{n(n+1)}{2} $. We will simply compute a factorization of it by brute force. The following is the code.


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

    internal static partial class Program
    {
        public static void Problem012()
        {
            long n = 1;
            while (true)
            {
                long t = n * (n + 1) / 2;
                int numberOfDivisors = BruteForceFactor(t).Select(p => p.Item2 + 1).Aggregate((x, y) => x * y);
                if (numberOfDivisors > 500)
                {
                    Console.WriteLine(t);
                    break;
                }
                n++;
            }
        }

        // Brute-force factoring 
        private static IEnumerable<Tuple<int, int>> BruteForceFactor(long n)
        {
            if (n == 1)
            {
                yield return Tuple.Create(1, 1);
            }
            else
            {
                int i = 2;
                while (n > 1)
                {
                    if (n % i == 0)
                    {
                        int index = 0;
                        while (n % i == 0)
                        {
                            index++;
                            n /= i;
                        }
                        yield return Tuple.Create(i, index);
                    }
                    i++;
                }
            }
        }
    }
}

Answer: 76576500

Problem 11: Largest product in a grid

Problem:

Please find the problem here.

Solution:

To find the maximum, we need to go through all of them, a simple set of for loop will do:

namespace Euler
{
    using System;
    using System.Linq;

    internal static partial class Program
    {
        public static void Problem011()
        {
            string input = ReadResourceAsString("Euler.Problem011.txt");
            int[] inputFlatten = input.Split(new char[] { ' ', '\r', 'n' }, StringSplitOptions.RemoveEmptyEntries).Select(s => Int32.Parse(s)).ToArray();
            int[,] inputArray = new int[20, 20];
            int p = 0;
            for (int i = 0; i < 20; i++)
            {
                for (int j = 0; j < 20; j++)
                {
                    inputArray[i, j] = inputFlatten[p++];
                }
            }

            int max = -1;

            // Try all horizontal lines
            for (int i = 0; i < 17; i++)
            {
                for (int j = 0; j < 20; j++)
                {
                    int prod = 1;
                    for (int k = i; k < i + 4; k++)
                    {
                        prod *= inputArray[k, j];
                    }
                    if (prod > max)
                    {
                        max = prod;
                    }
                }
            }

            // Vertical lines
            for (int i = 0; i < 20; i++)
            {
                for (int j = 0; j < 17; j++)
                {
                    int prod = 1;
                    for (int k = j; k < j + 4; k++)
                    {
                        prod *= inputArray[i, k];
                    }
                    if (prod > max)
                    {
                        max = prod;
                    }
                }
            }

            // Slash 
            for (int i = 0; i < 17; i++)
            {
                for (int j = 0; j < 17; j++)
                {
                    int prod = 1;
                    for (int k = 0; k < 4; k++)
                    {
                        prod *= inputArray[i + k, j + k];
                    }
                    if (prod > max)
                    {
                        max = prod;
                    }
                }
            }

            // Backslash
            for (int i = 3; i < 20; i++)
            {
                for (int j = 0; j < 17; j++)
                {
                    int prod = 1;
                    for (int k = 0; k < 4; k++)
                    {
                        prod *= inputArray[i - k, j + k];
                    }
                    if (prod > max)
                    {
                        max = prod;
                    }
                }
            }
            Console.WriteLine(max);
        }
    }
}

Answer: 70600674

Tuesday, August 27, 2013

Problem 10: Summation of primes

Problem:

Please find the problem here.

Solution:

To find all primes under a certain limit, Sieve of Eratosthenes is great. While the name of it sound foreign, this is probably one of the simplest algorithms for finding primes. The wiki have tons on information about the algorithm and I am not going to repeat it here.

The Devil is in the details! To scale this algorithm up, using the standard collection is going to limit the scalability quite significantly. Notice all you need is a single bit to represent whether a number is crossed out or not, one should use a Bitmap. Fortunately, we have BitArray in the .NET framework we can just use, and avoiding the even numbers altogether can give us a big memory saving. Here is the code for my sieve:


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

    internal static partial class Program
    {
        public static void Problem010()
        {
            Console.WriteLine(Primes(2000000).Select(t => (long)t).Sum());
        }

        private static IEnumerable<int> Primes(int max)
        {
            if (max >= 2)
            {
                yield return 2;
            }

            // sieve[i] represents 2i + 3; [So sieve[0] = 3, sieve[1] = 5] ...
            BitArray sieve = new BitArray(max / 2);
            int i = 0;
            while (true)
            {
                int num = (2 * i) + 3;
                int current_i = i;
                var indexes = Enumerable.Range(1, (sieve.Length - 1 - current_i) / num).Select(t => (t * num) + current_i).ToList();
                Parallel.ForEach<int>(indexes, delegate(int index) { sieve[index] = true; });
                sieve[i] = false;
                i++;
                while (i < sieve.Length && sieve[i])
                {
                    i++;
                }

                if (i >= sieve.Length)
                {
                    break;
                }
            }

            for (int j = 0; j < sieve.Length; j++)
            {
                if (!sieve[j])
                {
                    int num = (2 * j) + 3;
                    if (num <= max)
                    {
                        yield return num;
                    }
                }
            }
        }
    }
}

Note the use of Parallel.ForEach - that speed the crossing up significantly. A careful reader might notice this code is not cache friendly. Yes, it is not, and a cache friendly version can be found online here. The code is not really meant for blazing fast, but just good enough to get the problem solved.

Answer: 142913828922

Problem 9: Special Pythagorean triplet

Problem:

Please find the problem here.

Solution:

Along our usual line-of-thought, we would think about brute force again. But this time brute force is not so easy anymore since we need to find out a good pair that work. We can still try all possible pairs, but that will spend a lot of time on the unnecessary search. Turn out, iterating through the list of all Pythagorean triplet is not hard at all, as we can see shortly.

First, let's define primitive Pythagorean triplet be the Pythagorean triplet which is relatively prime. (i.e. GCD(a, b, c) = 1). Suppose we have a non-primitive Pythagorean triplet, we can divide every number by their GCD to obtain one. In some sense, primitive Pythagorean triplet spans the Pythagorean triplets.

The set of primitive Pythagorean triplet can be enumerated through the tree of primitive Pythagorean triplet found in wiki. What is not mentioned in the wiki is that the sum of the Pythagorean triplet must be increasing when we descend down the tree as we will show here:

The sum of the three numbers can be obtained by pre-multiplying the row vector (1, 1, 1). Thus the child node's sum can be obtained as:
(1,1,1)(d, e, f)' = (1,1,1)A(a,b,c) = 5a-5b+7c

Now we know a^2 + b^2 = c^2. Therefore c = sqrt(a^2 + b^2) > b. 5a - 5b + 7c > 5a - 5b + 6b + c = 5a + b + c>  a + b + c.

So we know the child sum is greater than the parent sum.

We can prove the other two matrices similarly. With that, we can be sure that we have found all primitive Pythagorean triples by doing a simple Breadth First Search on the tree and stop descending when sum exceed 1,000. With that we can check whether a particular triple works or not. The code will look like this.


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

    internal static partial class Program
    {
        public static void Problem009()
        {
            foreach (var triple in GetPrimitivePythTriples(1000))
            {
                int tripleSum = triple.Item1 + triple.Item2 + triple.Item3;
                if (1000 % tripleSum == 0)
                {
                    int scale = 1000 / tripleSum;
                    Console.WriteLine(scale * scale * scale * triple.Item1 * triple.Item2 * triple.Item3);
                    return;
                }
            }
        }


        public static IEnumerable<Tuple<int, int, int>> GetPrimitivePythTriples(int sumMax)
        {
            var root = new Tuple<int, int, int>(3, 4, 5);
            Queue<Tuple<int, int, int>> bfsQueue = new Queue<Tuple<int, int, int>>();
            bfsQueue.Enqueue(root);
            while (bfsQueue.Count > 0)
            {
                var visiting = bfsQueue.Dequeue();
                int a = visiting.Item1;
                int b = visiting.Item2;
                int c = visiting.Item3;

                if (a + b + c <= sumMax)
                {
                    yield return visiting;
                    bfsQueue.Enqueue(Tuple.Create(
                        1 * a - 2 * b + 2 * c,
                        2 * a - 1 * b + 2 * c,
                        2 * a - 2 * b + 3 * c));
                    bfsQueue.Enqueue(Tuple.Create(
                        1 * a + 2 * b + 2 * c,
                        2 * a + 1 * b + 2 * c,
                        2 * a + 2 * b + 3 * c));
                    bfsQueue.Enqueue(Tuple.Create(
                        -1 * a + 2 * b + 2 * c,
                        -2 * a + 1 * b + 2 * c,
                        -2 * a + 2 * b + 3 * c));
                }
            }
        }
    }
}

Note the use of yield return. This is a very powerful construct in C# that allow a method the sequence generating function a to become an iterator object with all the state keeping work done by the compiler. The best explanation of the yield feature (not necessarily the most precise, but the most understandable one) is found here.

Great feature comes with great responsibility when using it, you can trip yourselves up if you are not careful - typical mistake is iterating the sequence twice, you will do all the computation twice. Caching them in a list or array if you need to iterate more than once.

Answer: 31875000

Problem 8: Largest product in a series

Problem:

Please find the problem here.

Solution:

There are just 1000 - 5 + 1 = 996 cases to consider. The maximum possible value is $ 9 \times 9 \times 9 \times 9 \times 9 = 59049 $ so using a 32 bit integer is good enough.

Here is the code:


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

    internal static partial class Program
    {
        public static void Problem008()
        {
            string n = ReadResourceAsString("Euler.Problem008.txt");
            n = n.Replace("\n", string.Empty);
            n = n.Replace("\r", string.Empty);
            int[] d = n.ToCharArray().Select(c => c - '0').ToArray();
            int max = -1;
            for (int i = 0; i < 1000 - 5; i++)
            {
                int p = 1;
                for (int j = i; j < i + 5; j++)
                {
                    p *= d[j];
                }
                if (p > max)
                {
                    max = p;
                }
            }
            Console.WriteLine(max);
        }
    }
}

This problem is truly trivial, because it runs so quickly it doesn't worth to optimize it in any sense (one can imagine the next product can be obtained easily by division, or any product involve zero can quickly skip, ...)

Answer: 40824.

Wednesday, August 21, 2013

Problem 7: 10001st prime

Problem:

Please find the problem here.

Solution:
It seems that the number go a little larger from the previous problem at around 100, to now at around 10,000. With a computer, however, 10,000 is still a fairly small number, especially so if you have linear/quadratic algorithms. We will still brute force it. Let's first estimate how big would that prime be.

We know that prime density decreases and is governed by the prime number theorem. Let's use it to estimate how big would the 10001st prime be.

Assuming 10,000 is a large number (far from true), so we have
$
\begin{eqnarray*} \pi(x) &=& \frac{x}{\ln(x)} \\ 10001 &=& \frac{x}{\ln(x)} \end{eqnarray*} $

That is a non-linear equation to solve - in general - it is hard to solve non-linear equation - but we are just estimating, so let do some wild guess.

When $ x = 10000, \frac{x}{\ln(x)} = 1083 $
When $ x = 100000, \frac{x}{\ln(x)} = 8685 $
When $ x = 120000, \frac{x}{\ln(x)} = 10260 $

So we estimate the prime number to be around 100,000 - 120,000, this is fairly small and we will just try the numbers 1 by 1. Here is the code:


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

    internal static partial class Program
    {
        public static void Problem007()
        {
            List<int> primes = new List<int>();
            int primeCount = 0;
            int current = 2;
            while (true)
            {
                bool isPrime = true;
                foreach (int prime in primes)
                {
                    if (current % prime == 0)
                    {
                        isPrime = false;
                        break;
                    }
                }
                if (isPrime)
                {
                    primes.Add(current);
                    primeCount++;
                    if (primeCount == 10001)
                    {
                        Console.WriteLine(current);
                        return;
                    }
                }
                current++;
            }
        }
    }
}

The code is trivial - except it did a simple smart thing - to certify a number is prime, all we need to check is that any prime smaller than it is not a factor of it. That cut the number of trial division significantly.

Answer: 104743.

Note how close our estimate based on prime number theorem is.

Problem 6: Sum square difference

Problem:

Please find the problem here.

Solution:

Again, notice the size of the problem - it is just 100 numbers, brute force will work great. But let's be slightly advanced with computing sums. Here I introduce a method that we can compute sum of squares (in general, the method can go to sum of any powers) as follow:

When we want to compute sum of squares, let consider difference of cubes.

$
\begin{eqnarray*} (n+1)^3 - n^3 &=& n^3 + 3n^2 + 3n + 1 - n^3 \\ &=& 3n^2 + 3n + 1 \\ \sum\limits_{j=1}^{n} ((j+1)^3 - j^3) &=& \sum\limits_{j=1}^{n} (3j^2 + 3j + 1) \\ (n+1)^3 - 1 &=& 3\sum\limits_{j=1}^{n} j^2 + 3\sum\limits_{j=1}^{n} j + \sum\limits_{j=1}^{n} 1 \\ &=& 3\sum\limits_{j=1}^{n} j^2 + 3\frac{n(n+1)}{2} + n \\ 3\sum\limits_{j=1}^{n} j^2 &=& (n+1)^3 - 1 - 3\frac{n(n+1)}{2} - n \\ \sum\limits_{j=1}^{n} j^2 &=& \frac{(n+1)^3 - 1 - 3\frac{n(n+1)}{2} - n}{3} \\ &=& \frac{n(n+1)(2n+1)}{6} \end{eqnarray*}$

There are two things you should wonder in the proof. First - how on hell I know to consider the difference of cube. The truth is - I don't know - I learn it somewhere in my algebra textbook. But that useful technique can cover sum of any power by considering difference of a higher power, as you can imagine the first line will cancel out the higher power, and the fourth line will the higher power difference sum will telescope away.

The second thing is why we have the equality on the last line - that must have involve some serious expansion and factorization, which is tedious. Fortunately, we don't have to do that manually. The following Matlab command will do that for us instantly.

syms x
factor(((x+1)^3 - 1 - 3 *x*(x+1)/2 - x)/3)

It will yield 1/6*x*(x+1)*(2*x+1) right away. It is awesome to have Matlab.

With that, the code to compute is trivial, here it is:


namespace Euler
{
    using System;

    internal static partial class Program
    {
        public static void Problem006()
        {
            int n = 100;
            int sumOfSquares = n * (n + 1) * (2 * n + 1) / 6;
            int squareOfSum = n * n * (n + 1) * (n + 1) / 4;
            Console.WriteLine(squareOfSum - sumOfSquares);
        }
    }
}

Answer: 25164150 

Tuesday, August 20, 2013

Problem 5: Smallest multiple

Problem:

Please find the problem here.

Solution:

It is pretty obvious that the problem ask for the least common multiple of 1 to 20. What is not obvious is how to do it.

We first note that the least common multiple operator is associative. By that, we mean

Proposition: LCM(a, b, c)  = LCM(a, LCM(b, c)) = LCM(LCM(a, b), c))

Proof:
LCM(a, LCM(b, c)) is a multiple of a, LCM(b, c)
A multiple of LCM(b, c) is a multiple of b
A multiple of LCM(b, c) is a multiple of c
Therefore LCM(a, LCM(b, c)) is a multiple of a, b, and c.
Similarly, LCM(LCM(a, b), c) is also a multiple of a, b and c.
Suppose LCM(a, LCM(b, c)) $ \ne $ LCM(LCM(a, b), c), we can compute

d = GCD(LCM(a, LCM(b, c)), LCM(LCM(a, b), c)).

d must also be a multiple of a, b, and c.
Consider LCM(a, LCM(b, c)) = kd where k and d are both not 1.

d is a multiple of a, and d is NOT LCM(a, LCM(b, c)), therefore d must NOT be a multiple of LCM(b, c)
But d is a multiple of b, d is a multiple of c, therefore d is a multiple of LCM(b, c).

The contradictation leads to the conclusion that LCM(a, LCM(b, c)) = LCM(LCM(a, b), c)

So we reduced the problem of computing LCM of 20 numbers to compute the LCM of two number 20 times.

LCM(1, 2, ..., 20) = LCM(1, LCM(2, LCM(3, ..., LCM(19, 20))))))))

Now, we need to be able to compute LCM of two numbers. We will use this proposition to do this

Proposition: LCM(a, b) $ \times $ GCD(a, b) = ab

Proof:

Let c = GCD(a, b)/a, d = GCD(a,b)/b
We have a = c $ \times $ GCD(a, b), b = d $ \times $ GCD(a, b)
ab/GCD(a, b) = cdGCD(a, b).
Therefore ab/GCD(a, b) = cdGCD(a, b) is a multiple cGCD(a, b) = a.
Therefore ab/GCD(a, b) = cdGCD(a, b) is a multiple dGCD(a, b) = b.

Suppose e is LCM(a, b), e must be a factor of ab/GCD(a, b) = cdGCD(a, b).
Note that cdGCD(a, b) have only three prime factors and therefore 8 factors as follow:
1
c
d
GCD(a,b)
cGCD(a,b) = a
dGCD(a,b) = b
cd
cdGCD(a,b)

Since only the last one is a common multiple of a and b, this is the least common multiple of a and b.

With that, the code is almost trivial.

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

    internal static partial class Program
    {
        public static void Problem005()
        {
            IEnumerable<long> bases = Enumerable.Range(1, 20).Select(x => (long)x);
            Console.WriteLine(bases.Aggregate(CommonMultiple));
        }
    }
}

Note that the code use a method called CommonFactor described in Problem 3.

Note the use of the Linq function called Aggregate - it can be very handy when we have an operation to apply to a sequence of elements.

Answer: 232792560

Monday, August 19, 2013

Problem 4: Largest palindrome product

Problem: 

Please find the problem here.

Solution:

The problem size is just too small - consider the set of all pairs or 3 digits numbers = $ (999-100+1)^2 = 810000 $, any computer is going to find the answer very quickly. Here is the code:


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

    internal static partial class Program
    {
        public static void Problem004()
        {
            int max = 0;
            for (int i = 999; i >= 100; i--)
            {
                for (int j = 999; j >= 100; j--)
                {
                    int candidate = i * j;
                    if (candidate == Reverse(candidate)) 
                    {
                        if (candidate > max)
                        {
                            max = candidate;
                        }
                    }
                }
            }
            Console.WriteLine(max);
        }

        private static int Reverse(int i)
        {
            int j = 0;
            while (i > 0)
            {
                j = j * 10 + i % 10;
                i = i / 10;
            }
            return j;
        }
    }
}

At this point - don't you think Project Euler problem is really simple? All just brute force, isn't it. NO! Problems are getting harder and harder, you will see them soon.

Answer: 906609

Problem 3: Largest prime factor

Problem:

Please find the problem here.

Solution:

Again, brute force is going to work for this, just try different prime numbers and try. Note that $ 600851475143 > 2^{39} $, 32 bit integer will not work for the problem, we will need 64 bit integer.
C# compiler will give an error right away like this.

namespace Problem003
{
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using Common;

    class Program
    {
        static void Main(string[] args)
        {
            int x = 600851475143;
        }
    }
}
Error 1 Cannot implicitly convert type 'long' to 'int'. An explicit conversion exists (are you missing a cast?)

A nice feature of C# to avoid error. With that, all I have to do is to do trial division. Here is the code to do that:

namespace Problem003
{
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using Common;

    class Program
    {
        static void Main(string[] args)
        {
            long x = 600851475143;
            while (x != 1)
            {
                long d = 0;
                for (long c = 2; c < x; c++)
                {
                    if (x % c == 0)
                    {
                        d = c;
                        // Found a factor!
                        Console.WriteLine(d);
                        break;
                    }
                }
                if (d != 0)
                {
                    x = x / d;
                    
                }
                else
                {
                    // No factor found - this must be another prime factor
                    Console.WriteLine(x);
                    break;
                }
            }
        }
    }
}

This is run very quick - this tell us one basic principle with problem solving - be optimistic. Suppose we were pessimistic to believe the prime factor is going to be large, this is going to loop for long period of time and we spent time thinking about more advanced algorithm, which we really don't need.

Even if it does turn out to be bad, we can try something else soon. Trying this one doesn't hurt since it is really quick to code this up.

In fact, I myself learn a lesson here, since I coded the complicated one to start with. I used Pollard's rho algorithm to do the factoring. Here is the implementation of it.

public static int CommonFactor(int m, int n)
{
    while (true)
    {
        int r = m % n;
        if (r == 0)
        {
            return n;
        }

        m = n;
        n = r;
    }
}

// Pollard's rho algorithm for factoring (note that it does not factor 2^n)
public static List<long> PollardFactor(long n)
{
    List<long> factors = new List<long>();
    while (true)
    {
        // Factor it
        long x = 2;
        long y = 2;
        long d = 1;
        while (d == 1)
        {
            x = PollardSequence(x);
            y = PollardSequence(PollardSequence(y));
            long diff = x - y;
            if (diff < 0)
            {
                diff = -diff;
            }
            d = CommonFactor(diff, n);
            if (d == n)
            {
                factors.Add(n);
                break;
            }
        }
        if (d == n) { break; }
        factors.Add(d);
        n = n / d;
    }

    return factors;
}

private static long PollardSequence(long x)
{
    return (x % int.MaxValue) * (x % int.MaxValue) + 1;
}

The implementation is really just implementing the pseudocode on the wiki so it is trivial. It runs in more or less the same time as the brute force as they both are done without a blink. I learn the factoring algorithm there, and I hope you would go learn that too.

Answer: 6857

Friday, August 16, 2013

Problem 2: Even Fibonacci numbers

Problem:

Please find the problem here.

Solution:

Again, brute force worked great. Observe that Fibonacci numbers are growing exponentially, there are only a handful of terms before the sequence reach four million. Here is the code:


namespace Euler
{
    using System;

    internal static partial class Program
    {
        public static void Problem002()
        {
            int fib, fibLast, fibLastLast;
            fibLast = 1;
            fibLastLast = 1;
            int sum = 0;
            do
            {
                fib = fibLast + fibLastLast;
                if (fib % 2 == 0)
                {
                    sum += fib;
                }

                fibLastLast = fibLast;
                fibLast = fib;
            } while (fib < 4000000);
            Console.WriteLine(sum);
        }
    }
}

Again, we do have better method, which doesn't really worth the time. But for completeness sake, I will describe it here. First, observe that even valued Fibonacci numbers appear as every third element, there is an easy way to show this is exactly the case.

Proposition 1.1: $ F_n $ is even if and only if $ n = 2 \mod 3 $.
Prove: Apparently, the proposition is true for small $ n $, in particular, $ n \le 3 $. Assume the proposition is true for all $ n \le k $, for $ F_{k+1} = F_{k} + F_{k-1} $, we can deduce $ F_k $ is even if and only if both $ F_k $ and $ F_{k-1} $ are both odd or both even. But they cannot be both even (by assumption), so $ F_{k+1} $ is even if and only if $ F_k $ and $ F_{k-1} $ are both odd, that correspond to $ k = 1 \mod 2 $ and therefore the position also hold true for $ n = k + 1 $. By the principle of mathematical induction the proposition is true for all natural number $ n $.

With the proposition above, we could avoid the division and just do the sum as follow, and it is guaranteed to give the same result.


namespace Euler
{
    using System;

    internal static partial class Program
    {
        public static void Problem002()
        {
            int fib, fibLast, fibLastLast;
            fibLast = 1;
            fibLastLast = 1;
            int sum = 0;
            int i = 0;
            do
            {
                fib = fibLast + fibLastLast;

                if (i == 0)
                {
                    sum += fib;
                }

                i++;
                if (i == 3)
                {
                    i = 0;
                }

                fibLastLast = fibLast;
                fibLast = fib;
            } while (fib < 4000000);

            Console.WriteLine(sum);
        }
    }
}

Answer: 4613732.

Problem 1: Multiples of 3 and 5

Problem:

Please find the problem here.

Solution:

Hey, don't complicate it. You don't need any mathematics for this simple problem. Just brute force will get you answer in less than a second.

namespace Euler
{
    using System;

    internal static partial class Program
    {
        public static void Problem001()
        {
            int sum = 0;
            for (int i = 1; i < 1000; i++)
            {
                if (i % 3 == 0 || i % 5 == 0)
                {
                    sum += i;
                }
            }
            Console.WriteLine(sum);
        }
    }
}

Of course, there are better method. But in my humble opinion, it is not worth the effort, but it is a good learning exercise anyway. In order to compute the sum of the number that is either a multiple of 3 or multiple of 5, we could use the inclusion-exclusion principle simplified as follow:

The sum of the numbers in A union B is the sum of numbers in A + the sum of numbers in B - the sum of numbers in A intersect B.

Applying the rule to our case, we have:
The sum of multiples of 3 less than 1000 is $ \sum\limits_{i=1}^{\lfloor \frac{1000}{3} \rfloor}3i = 166833 $.
The sum of multiples of 5 less than 1000 is $ \sum\limits_{i=1}^{\lfloor \frac{1000}{5} \rfloor}5i = 99500 $.

The sum of multiples of 15 less than 1000 is $ \sum\limits_{i=1}^{\lfloor \frac{1000}{15} \rfloor}15i = 33165 $

The final answer is 166833 + 99500 - 33165 = 233168.

Answer: 233168

Starting of the blog

I have solving Project Euler problems for around an year, and I am really having fun with it. One of the problem I had is that there is no easy way for me to share my solutions to some friends. Typically I send them emails or DropBox. That's inefficient, I routinely forget to send solution over. Again, typically, I send source code, which is very often, inadequate to explain how I arrived at the solution.

So I decided to write this blog to share the solutions. The code is also shared on GitHub here.

My approach to Project Euler is pragmatic, focused on getting the solution, not the optimal way to code. So from time to time you see I am using non-optimal approach, and even low quality code. That doesn't mean I can write optimal or high quality code, that merely means that is unimportant for me. The same is also observed in various programming contests.

As I disclaimer, I don't want to deprive the fun of solving the problem from you, so please refrain yourself from reading the solution if you still want the fun.