Danns.co.ukGoogle Treasure Hunt 2008
Google appear to be running a Treasure Hunt (for geeks). I was interested in the Prime Numbers Challenge. It's different every time, but it looks something like this:
Find the smallest number that can be expressed as
the sum of 11 consecutive prime numbers,
the sum of 25 consecutive prime numbers,
the sum of 513 consecutive prime numbers,
the sum of 1001 consecutive prime numbers,
the sum of 1129 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).
I was intrigued, so I decided to hack out a solution in C++. I've attached the file. It relies on a file containing a list of primes, which you can get from this website. All the solutions seem to fall well within the 1st million primes, so only the first file is required. Set "DEBUG" to true to see it working :)
Oh, and the solution to the above puzzle is: 4910371 :)
Update: OK, my bad: my solution was wrong :D I missed one small if, and the fixed solution is attached. The real solution is: 6409607.
Update: I changed a load of [] calls to iterators and shaved off 55.4% off the running time.
Update: And now I've discovered that generating the primes is pretty much just as fast...
Update: I finally got around to writing the obvious summing optimisation. This implementation solves the above puzzle in 0.48s on my machine. Drupal is being stupid, so the attachments are out of order. You'll just have to follow the number :s
Comments
Google treasure hunt
Wow, that's pretty cool! Not heard of the Google treasure hunt before this. I like your solution, although I haven't had time to fully work it out yet!
I wish I had time to spend developing cool things like this after work. My job seems to take over my life at the moment, which isn't good :-/
Thanks. The solution
Thanks. The solution probably isn't all that easy to follow, but it's certainly pretty efficient in complexity, memory usage, and disk usage. It uses a collection of sliding windows on the list of primes to maintain the sums. Before I wrote this, I've always used either pure C or the Qt toolkit, so this is the first time I decided to use the middle ground and get to grips with the C++ STL. I really like it :)
What do you use most at work Mark? I'm unfortunately stuck with JS most of the time, and I'm rather sick of it.
JS? You poor thing! I tend
JS? You poor thing! I tend to use equal amounts of Java and MATLAB (Java when producing customer-facing software products, MATLAB when knocking something up quickly to prove something).
I've actually come to quite like Java in recent years, whereas MATLAB (once a firm favourite af mine) is starting to get on my nerves. I just want a compiler and some decent type-checking, is that too much to ask?! A fair few people here use C/C++, although I still haven't got past the basics personally. Python is starting to become more popular, and I like the look of what I've seen so far.
Javascript is actually a
Javascript is actually a decent full-featured language. Firefox uses JS for its entire UI, so it's somewhat more involved JS that the type used to AJAXify websites. It's done amazingly well for a language that was slapped together in a month or two out of necessity back in the day, but it is starting to show its age.
As high-level scripting languages go, I'm a Ruby fan, and I'd say it beats Python hands down on style -- the "everything is an object" syntax makes for some incredibly neat and readable code, and I prefer using the "end" keyword to obsessing with line indents. Python's been around longer though, and I think it still has the edge on speed. Have you checked out Ruby on Rails? Definitely a stroke of genius.
I'm afraid I still don't see eye-to-eye with Java. It has portability on its side, but Java apps are painful to launch, slow, and Swing sticks out like a sore thumb in any OS. It is easier to pick up though. Personally, I'm a huge fan of the Qt toolkit (pronounced "cute"), which gives you pretty much all the ease-of-use the Java API provides and integrates seamlessly with the host system. It's a C++ toolkit natively, but there are bindings for Java, Python, and Ruby (at least). Unfortunately, although it's open-source, it's not free for commercial use.