<?php

/*
 * To run, type:
 * php -f google_th_4.php
 */

/*
 * Find the smallest number that can be expressed as
 * the sum of 3 consecutive prime numbers,
 * the sum of 7 consecutive prime numbers,
 * the sum of 45 consecutive prime numbers,
 * the sum of 611 consecutive prime numbers,
 * and is itself a prime number.
 *
 * For example, 41 is the smallest prime number that can be expressed as
 * the sum of 3 consecutive primes (11 + 13 + 17 = 41) and
 * the sum of 6 consecutive primes (2 + 3 + 5 + 7 + 11 + 13 = 41).
 */

/*
 * Configuration options
 */

define('DATABASE_FILENAME', 'google_th_4b.serial');

//define('PRIMES_CONSEC_SEQ', '25, 129, 139, 1087, 1199'); //4ed05e
//define('PRIMES_CONSEC_SEQ', '3, 25, 77, 953'); //9b1e44
//define('PRIMES_CONSEC_SEQ', '23, 63, 897, 965'); //0d1a89
//define('PRIMES_CONSEC_SEQ', '3, 35, 553, 829'); //http://ciju.wordpress.com/2008/06/03/google-treasure-hunt/
define('PRIMES_CONSEC_SEQ', '7, 17, 41, 541'); //0d1a89

/*
 * Program implementation
 */

// Increase memory limit
ini_set('memory_limit', '256M');

echo "\nLoading primes... ";

// Read data
$data = file(DATABASE_FILENAME, FILE_IGNORE_NEW_LINES);
$data_size = count($data);

echo "done.\n";
echo "Solving for inputs ".PRIMES_CONSEC_SEQ."...\n";

$time_start = explode(' ', microtime());
$time_start = $time_start[1].substr($time_start[0], 1);

$levels = explode(',', str_replace(' ', '', PRIMES_CONSEC_SEQ));
rsort($levels, SORT_NUMERIC);
$clevels = count($levels);

define('S_OFFSET', 0);
define('S_SIZE', 1);
define('S_SUM', 2);

$sets = array();
for($i = 0; $i < $clevels; $i++) {
    $size = $levels[$i] * 1;
    $sets[] = array(S_OFFSET => -$size,
                    S_SIZE => $size,
                    S_SUM => 0);
}

$result = 0;
$max_sum = 0;
while(true) {
    $found = true;
    for($i = 0; $i < $clevels; $i++) {
        $s =& $sets[$i];
        $si =& $s[S_SUM];
        if($si < $max_sum || $s[S_OFFSET] < 0) {
            $found = false;

            $pos = $s[S_OFFSET];
            $si -= $pos < 0 ? 0 : $data[$pos];

            $pos = $s[S_OFFSET] + $s[S_SIZE];
            if($pos >= $data_size) {
                die("Could not find a compatible prime number in the available list!\n\n");
            }
            $si += $pos < 0 ? 0 : $data[$pos];
            $s[S_OFFSET]++;

            if($si > $max_sum) {
                $max_sum = $si;
            }
        }
    }
    if($found && in_array($max_sum, $data)) {
        echo "Found prime number $max_sum";
        break;
    }
}

$time_stop = explode(' ', microtime());
$time_stop = $time_stop[1].substr($time_stop[0], 1);
$time_stop -= $time_start;
echo " in $time_stop seconds.\n\n";

?>