Coastal Vectors

I recently (2 years ago) purchased a Raspberry Pi (The original model). I bought it off a friend who never ended up using it for anything useful. My intent was to run a small web server with it, and enjoy some savings over the old computer I use for a server that was eating up more than 100 watts of energy.

I also didn’t care for the case it came with. I also happened to have a first generation Airport Extreme that I also got second hand. It served it’s purpose, but had since died. I thought these two might be a match-made in heaven.

I gutted the poor airport extreme and inspected it.

It didn’t know what hit him.

I was going to throw out the PCB entirely, until I noticed that the Raspberry Pi had two holes that matched up perfectly with two holes on the Airport’s main board. I decided to keep the circuit board for mounting purposes, and reuse it’s input jacks since they line up so nicely with the enclosure.

I desoldered all the parts I could near the connectors, and then marked off the part of the PCB I could remove. The intent was to remove all the circuitry that would be difficult to desolder. The result was a completely bare, partial PCB to work with.

I then soldered power, USB and ethernet cables to the circuit board that would then connect to the Pi (so it’s not hardwired in, and can be swapped).

Now I have a low power web server in a cute, unassuming box.

I also wanted to have the filesystem accessible over AFP so I could access it on my desktop. this was easily achieved by installing netatalk using the command:

sudo apt-get install netatalk

Now that I have the server’s disk mounted on my Mac’s desktop, naturally I need a representative icon.

Using a reference picture, I was able to throw this icon together in Illustrator in about a half-hour’s time.

I recently completed Project Euler 357 after working on it here and there over the course of a couple of days. I decided to do this one out of order because it seemed like a fairly straight foward problem.

Consider the divisors of 30: 1,2,3,5,6,10,15,30.
It can be seen that for every divisor d of 30, d+30/d is prime.

Find the sum of all positive integers n not exceeding 100 000 000
such that for every divisor d of n, d+n/d is prime.

This shouldn’t be hard. Just find the divisors of every number, and see if n+1 is prime. Heck, I already have an isPrime() function written! The brute force approach will be easy to code.

I started off with code resembing this:

bool isPrimeGen(int n, bool *primes)
{
    for (int d=1; d<=n; d++)
        if (n % d == 0)
            if (primes[d+n/d] != true)
                return false;
    return true;
}
int main()
{
    int limit = 100000000;
    unsigned long long sum = 1;
    for (int i=2; i<limit; i++)
        if (isPrimeGen(i))
            sum += i;
    printf("%d", sum)
}

Well, this worked… But it took far too long. It took over 4 hours to complete. Obviously this doesn’t fit in with the guidlines that solutions should take less than a minute to complete.

I was able to make a single optimization that got the time down from 4 hours to 12 minutes. A single, tiny change. (It’s actually a similar optimization I made to my prime function when I first started doing these Euler problems…) Instead of looking for every divisor up to the size of n, our number, I put in a square root n, sqrt(n), as the limit for divisor checking.

Another optimization was to make use of looking for patterns in the qualifying numbers.

n is always even
n is always 1 less than a prime number
n/2+2 is always a prime number

Filtering down the potential numbers by using these patterns further reduced the time, but it was still taking longer than I would have liked. I decided to take drastic measures… I pre-computed a ton of primes using a Seive of Eratosthenes.

I made a giant boolean array where any number is marked as a prime or not. This made looking up whether or not primes are numbers super trivial. I’m not sure this is the most elegant solution, but it seemed simple and fast.

// Generate primes using sieve
bool *primes = malloc(limit*sizeof(bool));
for (int i=2; i<limit; i++)
    primes[i] = true;
primes[0] = false;
primes[1] = false;
for (int i=2; i<limit; i++)
    if (primes[i] == true)
    {
        int n = 2;
        while (n*i < limit)
            primes[i*n++] = false;
    }

So, this generates an array, and I pre-load the value for each number as ‘true’ (excepting for 0 and 1 of course). I then go through sequentially, and if I hit a number that is ‘true,’ or prime, every multiple of that number gets marked as ‘false,’ or not prime, until we reach the limit of the array. This is a super fast method for calculating an obscene number of primes very quickly because it doesn’t require any division.

With this pre-loaded table of primes, the code was then refactored to make use of this table rather than my standard isPrime() function.

Putting all these changes together allowed the problem to be solved in under 5 seconds, which is just a tad better than my original 4 hours.

Of course, I won’t reveal the answer here. You’ll need to figure that out on your own. You can, however, check out my full solution on my GitHub account.

Author: Michael Caldwell

Apple Pi

Project Euler 357