Treasure hunt

Created 29th January, 2009 03:59 (UTC), last edited 29th January, 2009 04:47 (UTC)
Treasure hunt

This is the second Google puzzle that I discussed at BarCamp way back last year. You can get your own personalised question from Google at http://treasurehunt.appspot.com/.

The basis of the puzzle is to find sequences of prime numbers that sum to prime numbers. Copying the example from the Google page, if you have sequences of 3 and 6 prime numbers then the smallest prime sum you can have is 41 which is:

  • 11 + 13 + 17 = 41
  • 2 + 3 + 5 + 7 + 11 + 13 = 41

The sequence lengths are quite long, for example I've just been asked for the smallest prime sum for sequences of lengths 19, 21, 405 and 781.

My first Haskell version with a poor prime number test took about 8 hours to run, with a better test it took only about two minutes. JavaScript can solve the problem in less than fifteen minutes and C++ in around two seconds. So far I've not done a Python version, but I think it can be done very elegantly there (and in Ruby for that matter).


Categories:
Some rights reserved — by-nc-sa version 2 Attribution Non-commercial Share alike
© 2002-2019 Kirit & Tai Sælensminde. All forum posts are copyright their respective authors.
Licensed under a Creative Commons License. Non-commercial use is fine so long as you provide attribution.

kirit.com