<?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_4.sqlite');
define('DATABASE_READSTEP', 10000);
define('PRIMES_CONSEC_SEQ', '25, 129, 139, 1087, 1199');

/*
 * Program implementation
 */

$db = new SQLiteDatabase(DATABASE_FILENAME, 0660, $error);
if(!$db) {
    die("Could not create database file: {$error}");
}

$data = array(
    'offset' => 0,
    'offset_step' => 0,
    'stack' => array(),
    'stack_size' => 0,
    );

function readAhead() {
    $res = $GLOBALS['db']->unbufferedQuery(
        'SELECT * FROM t_primes LIMIT '.
        DATABASE_READSTEP.' OFFSET '.
        ($GLOBALS['data']['offset'] + $GLOBALS['data']['stack_size']).';');

    $rows = $res->fetchAll(SQLITE_NUM);
    if(!($rows_count = count($rows))) {
        return false;
    }

    for($i = 9; $i < $rows_count; $i++) {
        $GLOBALS['data']['stack'][] = $rows[$i][0];
    }
    $GLOBALS['data']['stack_size'] = count($GLOBALS['data']['stack']);

    return true;
}

function isPrime($number) {
    $res = $GLOBALS['db']->query("SELECT * FROM t_primes WHERE number = $number LIMIT 1;");
    return $res->numRows() != 0;
}

echo "\nSolving for inputs ".PRIMES_CONSEC_SEQ."...\n";

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

$sets = array();
for($i = 0; $i < $clevels; $i++) {
    $size = $levels[$i] * 1;
    $sets[] = array(
        'shifter' => !$i,
        'offset' => -$size,
        'size' => $size,
        'summed' => 0,
        );
}

$result = 0;
$max_sum = 0;
while(true) {
    $found = true;
    for($i = 0; $i < $clevels; $i++) {
        $s =& $sets[$i];
        $si = $s['offset'] < 0 ? 0 : $s['sum'];
        if($si < $max_sum || !$si) {
            $found = false;

            $pos= $s['offset'];
            $s['sum'] -= $pos < 0 ? 0 : $data['stack'][$pos - $data['offset']];

            $pos= $s['offset'] + $s['size'];
            $pos_data = $pos - $data['offset'];
            if($pos_data >= $data['stack_size']) {
                if(!readAhead()) {
                    die("Could not find a compatible prime number in the available list!\n\n");
                }
            }
            $s['sum'] += $pos < 0 ? 0 : $data['stack'][$pos_data];

            $s['offset']++;

            if($s['shifter'] && $s['offset'] > 0) {
                $data['offset_step']++;
                $data['stack_size']--;
                if($data['offset_step'] >= DATABASE_READSTEP) {
                    $data['offset'] += $data['offset_step'];
                    $data['stack'] = array_slice($data['stack'], $data['offset_step']);
                    $data['offset_step'] = 0;
                    $data['stack_size'] = count($data['stack']);
                }
            }

            if($s['sum'] > $max_sum) {
                $max_sum = $s['sum'];
            }
        }
    }
    if($found && isPrime($max_sum)) {
        echo "Found prime number: $max_sum\n";
        break;
    }
}

?>