= Solution to Google Treasure Hunt 2008 - Task 4 =

The program below can be used to solve a particular instance of the task presented at http://treasurehunt.appspot.com (Task 4, 2008). You are given few numbers, e.g. [1111, 137, 13, 3]. Your task is to find smallest prime that is a sum of 1111 consecutive primes, sum of 137 consecutive primes and so on.

The values are placed in limits array, but you can also pass them as arguments (in descending order!) from command line:
{{{
    ./TreasureHunt4 799 415 63 31
}}}

The code allows to compare [http://dsource.org/projects/tango/docs/current/tango.core.BitArray.html BitArray] with array of booleans. BitArray is a bit slower, but should occupy less memory. Implementation uses Atkin sieve.

Code can be compiled with debug option for additional informations.

{{{
#!d
/* Michal 'GiM' Spadliński             <gim913 & gmail * com >
 * 
 * Google TreasureHunt task 4 solution
 * http://treasurehunt.appspot.com/
 */
module TreasureHunt4;

//version = BitArray;

import tango.io.Stdout;
import tango.time.StopWatch;
import Integer = tango.text.convert.Integer;
version ( BitArray )
    import tango.core.BitArray;


static const int sqrt_val = 2500;
// descending order
int[] limits = [1111, 137, 13, 3];


ulong primes[];
static this()
{   
    StopWatch timer;
    timer.start;
    some_small_primes = atkin_sieve;
    foreach (k, a; some_small_primes)
        if (a)
            primes ~= k;
    auto temp = timer.stop;
    Stdout.formatln ("primes table generated in {} seconds with {} entries", temp, primes.length);
}

class PrimesSum
{
private:
        ulong _sum;
        int start;
        int limit;
public:
    this(int lim)
    {   
        limit = lim;
        for (int j=0; j<limit; ++j)
            _sum += primes[j];
    }
    
    void next()
    {   
        _sum -= primes[start];
        _sum += primes[start+limit];
        ++start;
    }
    void previous()
    {   
        --start;
        _sum -= primes[start+limit];
        _sum += primes[start];
    }

    int opCmp(PrimesSum b) { return _sum - b.sum; }
    int opEquals(PrimesSum b) { return _sum == b.sum; }

    uint sum() { return _sum; }

    char[] toString()
    {   
        char[100] tmp = void;
        return Integer.format (tmp, _sum, Integer.Style.Unsigned, Integer.Flags.None).dup;
    }
}

void main(char[][] argv)
{
    PrimesSum[] prSums;
    StopWatch timer;

    if (argv.length > 1)
    {   
        limits = [];
        foreach (char[] arg; argv[1..$])
            limits ~= Integer.toInt(arg);
        Stdout(limits).newline;
    }

    timer.start;

    prSums.length = limits.length;
    foreach (a, ref b; prSums)
        b = new PrimesSum(limits[a]);

OUTER_LOOP:
    for(;;)
    {   
        // Sum must be a prime
        try {
            while (1)
            {   
                if (some_small_primes[prSums[0].sum])
                    break;
                else
                    prSums[0].next;
            }
        } catch (Exception e) {
            assert (0, "Increase the value of sqrt_val in the source file");
        }
        debug Stdout.formatln ("0: {} {}", prSums[0].sum, prSums[0].start);

        // check if all the other, smaller sums, sum to the same number
        for (int idx=1; idx<prSums.length; ++idx)
        {   
            while (prSums[idx] < prSums[0])
                prSums[idx].next;
            debug Stdout.formatln ("{}: {} {}", idx, prSums[idx].sum, prSums[idx].start);
            if (prSums[idx] != prSums[0])
            {   
                debug Stdout ("differ2").newline;
                prSums[0].next;
                for (int i=1; i<=idx; ++i)
                    while (prSums[i] > prSums[0])
                        prSums[i].previous;
                continue OUTER_LOOP;
            }
        }
        // we got you
        break;
    }
    auto temp = timer.stop;
    Stdout ("The Answer to the Great Question ...")
        .formatln ("Of Life, the Universe and Everything: {}", prSums[0]);
    Stdout  ("input data: ") (limits).newline;
    Stdout.formatln ("Finding answer took {} seconds", temp);
}

T atkin(T, int sqrt_limit)()
{
    const long limit = sqrt_limit*sqrt_limit;
    T firstSet;
    firstSet.length = limit;
    
    firstSet[2] = 1;
    firstSet[3] = 1;
            
    for (auto x = 1; x<sqrt_limit; ++x)
    {
        for (auto y=1; y<sqrt_limit; ++y)
        {
            auto n = 4 * x*x + y*y;
            if (n < limit && ((n % 12) == 1 || (n % 12) == 5))
                firstSet[n] = cast(bool)1^firstSet[n];
            n = 3 * x*x + y*y;
            if (n < limit && ((n % 12) == 7))
                firstSet[n] = cast(bool)1^firstSet[n];
            n = 3 * x*x - y*y;
            if (n < limit && x > y && ((n % 12) == 11))
                firstSet[n] = cast(bool)1^firstSet[n];
        }
    }   
    for (int n=5; n<sqrt_limit; ++n)
    {   
        if (firstSet[n])
            for (int k=1, j=n*n; j*k<limit; ++k)
                firstSet[k*j] = 0;
    }   
    return firstSet;
}       
    
version ( BitArray )
{   
    static const BitArray some_small_primes;
    alias atkin!(BitArray, sqrt_val) atkin_sieve;
} else  {
    static const bool[] some_small_primes;
    alias atkin!(bool[], sqrt_val) atkin_sieve;
}   
}}}

Here is sample run of a program on Core Duo 1.7 with sqrt_val set to 2630, this also show how fast D is:

{{{
primes table generated in 1.07 seconds with 471342 entries
[ 799, 415, 63, 31 ]
The Answer to the Great Question ...Of Life, the Universe and Everything: 6814289
input data: [ 799, 415, 63, 31 ]
Finding answer took 0.00 seconds
}}}