Solving Google Treasure Hunt Puzzle 4: Prime Numbers

Nice work! I solved this question using similar methods of scripting to you, but utilizing MySQL when performing the sums. Created a 2 column table where I was running the query:

SELECT p FROM primes WHERE p=(SELECT sum(p) from primes WHERE n>=$i AND n

where $i is the index of the prime (1 being 2, 2 being 3, 3 being 5, 4 being 7 etc) and $a being the number of consecutive primes to sum.

Here's some MySQL:

<pre>mysql> describe primes;
+-------+------------------+------+-----+---------+----------------+
| Field | Type             | Null | Key | Default | Extra          |
+-------+------------------+------+-----+---------+----------------+
| n     | int(10) unsigned | NO   | PRI | NULL    | auto_increment |
| p     | int(10) unsigned | NO   | MUL |         |                |
+-------+------------------+------+-----+---------+----------------+
2 rows in set (0.00 sec)

mysql> select * from primes limit 10;
+----+----+
| n  | p  |
+----+----+
|  1 |  2 |
|  2 |  3 |
|  3 |  5 |
|  4 |  7 |
|  5 | 11 |
|  6 | 13 |
|  7 | 17 |
|  8 | 19 |
|  9 | 23 |
| 10 | 29 |
+----+----+
10 rows in set (0.02 sec)

Had to create an index on column 'p' to speed up the summation of the primes (very slow otherwise!). In the end, once the actual table had been created and indexed by MySQL, the solution popped out in a few more minutes of PHP and BASH script.

Ended up with 4 text files, containing all possible potential numbers. Then used a final bit of scripting piped through ‘less’ to manually locate the final answer:

for i in `awk '{print $1}' 1151.txt`; do grep "^$i$" 1151.txt 775.txt 11.txt 5.txt; echo; done | less

…

1151.txt:8256109

1151.txt:8327513

1151.txt:8368331

1151.txt:8429539
775.txt:8429539
11.txt:8429539
5.txt:8429539

1151.txt:8480599

1151.txt:8501039

1151.txt:8582831

…

And there’s the answer: 8429539 (for problem 5, 11, 775 and 1151).

And this was all done on a small ITX Linux box with 384Mb of RAM running a VIA Nehemiah 1Ghz cpu. Who needs fast processors and gigs of RAM to solve this!! :-)