Sure, and in this case memoization is crazy fast, but what I don't understand is how other solutions work at all.

As an example, your solution takes 13 seconds to generate the first 5000 numbers on my computer, much larger than the 5,000 msec limit on the server. Has the timeout value changed, or do I miss something? My own code without memoization runs in around 30 seconds for the same test and goes to around test case 1700 on the server, but the running time increases with n, so it seems borderline for other tests to match the timeout value. With memoization, this goes down to 30 msec on my machine :-)

I have a functionally correct solution, but it fails the test because of the time limit. Doing a local test shows that it indeed takes around 30 seconds to generate all numbers to 5000. At the other hand, each invocation of the function calculates all numbers below n, so all numbers below 5000 are calculated when calculating hamming(5000) and that takes less than 100 ms on the test machine. I compared my code against the fastest python code for that problem mentioned on Rosetta Stone, and I am only about a factor 2 slower, so I am a little stuck at this time.

I am wondering if we can use memoization to make the test faster and/or if we can use psyco or similar to accelerate the execution.