Your code outperforms mine. I see you already cache the earlier results, which was my "trick" to make it run faster. I used a Python "generator" to implement the sequence generation and a "cache" class to do the caching of earlier results. My best guess is that your code's improved performance relative to mine is you have fewer calls as your code is more of an inline implementation where mine is perhaps more modular.
Once I got the runtime down to what I thought was an acceptable level, I stopped trying to improve it. I see from the other comments that various folks, including you, have done much better than I did on runtime.
I was using Cygwin python 2.7.3 for the tests.
problem14_nico.py - http://pastebin.com/bfDTte3p
- Your version
problem14.py - http://pastebin.com/AYYykyrj
- my version w/cache
problem14_nocache.py - http://pastebin.com/wTzCfcXr
- my version without cache
main_timer.py - http://pastebin.com/trk7E1n9
- Main program for all my project Euler programs.
problem14_results.txt - http://pastebin.com/ZUzeZjLW
- Timed test runs on my meager laptop PC.
I made one extra test run. I cranked my cache up to a full 1,000,000 slots and ran the program again. The CPU time came down, though not to your level of speed. I'm pretty sure the poor PC was paging heavily during that run.