Tao of Coding

Euler 077- First value that can be written as sum of more then x primes

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();
}

Euler 206- Concealed Square

Find the unique positive integer whose square has the form 1_2_3_4_5_6_7_8_9_0,
where each “_” is a single digit.

First thought was brute force by replacing blanks with numbers, and checking for a square root. This comes to a mere 10^9 possibilities, with a lot of parsing longs from string. After a bit of analysis though, you realize the last digit of the number we are looking for has to be 0. (0 being the only a*a to result in a 0 digit at the end). This also means the first blank is a 0, giving a mere 10^8 possibilities. Next is to realize that 9 can only be formed by a 3, or a 7 in the number. (Try not to forget the 7, as I did the first time through). So, we now know the target square ends in either 70 or 30.

We can move away a lot of parsing longs from strings, and sqrt’s, by just iterating over the possible answers, rather then the possible answers^2. This basically means iterating from 10^9+30 to something less then 10^10 (sqrt of 1929394959697989900; though I’m far too boring to plug that into a calculator). As already stated, we’re looking for something ending in 30 or 70, so we could start with 10^9+30 and increment by 100, then switch to +70, or alternatively alter increments of 40 and 60.

Probably the most complex thing is checking whether or not a square is of the desired format. For that I get the string representation of the square, and then in a for loop check that every other character is incrementing; with a special check for the 0 case. I envision there are better ways, but this was good enough for this problem.

Code:

static void Main(string[] args)
{
    long start = 1000000000;
    //add 100 to long on the off chance that there's a terrible loss
    //  of precision in the constant double
    long end = (long)(Math.Sqrt(1929394959697989900))+100;
    Test(start + 30, end, 100);
    Test(start + 70, end, 100);
}
static void Test(long start, long end, long incr)
{
    for (long current = start; current < end; current += incr)
    {
        string squareString = (current * current).ToString();
        bool isValid = true;
        for (int i = 1; i <= 9 && isValid; i++)
            if (squareString[2 * (i - 1)] != '0' + i)
                isValid = false;
        if (squareString[2 * (10 - 1)] != '0')
            isValid = false;
        if (isValid)
            Console.WriteLine("Solution: " + current);
    }
}

Euler 001- Starting out Easy

At least something to start the blog with.

Project Euler problem #1; sum all natural numbers less then 1000 that are multiples of 3 or 5. Natural numbers meaning positive integers. The simplest way to go about this is a for loop with a sum, something akin to:

int sum=0;
for(int i=1; i<1000; i++)  
    if(i%3==0 || i%5==0)
        sum+=i;
Console.WriteLine(sum);

Which gives us a nice and specific answer, which is correct. Fun optimization side of this:

You can consider the sum of all 3’s to be 3*sum(1..333), which can be computed as 3*(333*332/2 + 333), if math holds.

Similarly, sum of 5 is 5*sum(1..199) = 5*(199*198/2 + 199).

Next, you need to determine the sum of natural numbers divisible by 15: 15*sum(1..66)=15*67*66/2;

Finally, take the sum of the first two values, and subtract from that the last value. In this case: 166833 + 99500 – 33165 = the answer. This follows from a little too much math, and a bit of set theory: numbers divisible by 15 are counted in both the 3 and 5 cases, effectively double counted. We subtract one of these double counts to end up with a single count of all numbers; and, an O(1) solution.

Howdy

This is written far after the fact, in the balmy year of 2016.

I’m Matt Moss. At the time I started writing this blog, I was a Student and Software Developer at Texas A&M for the Energy Systems Lab (ESL). I graduated in 2011, and continued in Software Development for a local consultancy, as well as dabbling with Oilfield Electronics on the side.

This blog started out as a way to generate an excuse to practice for the ACM ICPC contest. To that effect I’d go through, look at past ACM problems or Project Euler problems, anything that struck my fancy, and go through and try to solve them. The goal being to both improve implementation time, and just improve problem solving/recognition skills. Eventually I also started learning electronics, and some of my early projects from that ended up here, as well as a few philosophical diatribes. Now that I’m out of college, I’m trying to maintain the blog mostly as a project repository. And/or a place to write when I feel like writing.

You might be curious about the name. Coder Tao is not a fascinating name based on the balance that should come from being able to solve complex problems semi-elegantly while also operating within the confine of project scope. Nor is it an endorsement of Asian religions. Nor is it a statement involving Torque and the coding folk. Tao is the name of a gnome sorcerer. A machine of unimaginable destruction and chaos (but mostly destruction). And now it is a name.