Tao of Coding

From Euler 077–

The goal is to find the first number that can be written as a sum of primes in 5,000 different ways. As an example, 10 can be written as 7+3, 2+2+2+2+2, 5+5, 5+3+2, etc.

Going about this the slow way. The first and immediate thoughts is ‘gee, I can try brute force’. The maximum number that the answer can be is 10,000 (2+2+…+2=2*5000). It’s actually a fair amount less (2+2+2=3+3, but, my math skills are too terrible to figure out a better upper bound).

Now, I envision that determining all unique sums is quite slow for a single number. Can’t prove but envision. And slow being relative. To speed this up, we use an interesting property of these numbers.

Assume P(k) is the number of unique sums for k; P(k) <= P(k+2), as k+2 can be given simply by 2+(all solutions of k). Similar for P(k+3). I can’t prove it for P(k+1) though, sadly. This means that we could do one of two things: Either do a binary search on all even numbers, then all odd numbers to find the first number with P(k)==5000, (should be about 2*log2(10000)=26 checks, roughly); or, we can do a binary search down to a resolution of about 3, then check those final 3 numbers. It’d be about 16-19 comparisons. As the binary search across all evens then all odds is much simpler/less sticky, we’ll go that route.

Now, humorous fact: I went through all this thinking, and then did a test to see a. how slow finding unique sums is, and b. verify my ‘find unique sums’ algorithm works. The answer is less then 100, and can be found without any of the cool binary searching. I got to do precisely none of the cool things I was planning on. None of them. I feel like life is such a terrible waste, as I probably spent hours working out ways to solve the problem which would be equivalent to ‘find the first k such that P(k) is 10^(something huge)’… very disappointing. And also, P(k)<=P(k+1) for all observed points.

Edit: Slight explanation of how to find the number of unique sums.
What we do is attempt all summations using primes in decreasing value of the prime. This ensures that any summation found will be unique. We do this recursively, and it can actually be considered dynamic programming; but, alas, the answer is already found.

Code:

static List primes;
public static void Main()
{
    BuildPrimes(10000);
    for (int i = 2; i <= 100; i++)
        Console.WriteLine(i+" "+NumberOfUniqueSums(i, 0));
}
static int NumberOfUniqueSums(int k, int primeStartIndex)
{
    if(k<0) return 0;
    if (k == 0) return 1;
    int sum = 0;
    for (int primeIndex = primeStartIndex; primeIndex < primes.Count; primeIndex++)
        sum += NumberOfUniqueSums(k - primes[primeIndex], primeIndex);
    return sum;
}
static void BuildPrimes(int maxSquare)
{
    primes = new List { 2};
    int maxI=((int)Math.Sqrt(maxSquare))+1;
    for (int primeCandidate = 3; primeCandidate < maxI; primeCandidate += 2)
    {
        bool isPrime = true;
        for (int i = 0; i < primes.Count && isPrime; i++)
            if (primeCandidate % primes[i] == 0)
                isPrime = false;
        if (isPrime)
            primes.Add(primeCandidate);
    }
    //max prime is now at index 0
    primes.Reverse();
}

Tags: project euler

This entry was posted on Saturday, May 9th, 2009 at 21:42 by Matt and is filed under Contest Stuff. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.