Project Euler 495

http://projecteuler.net/index.php?section=problems&id=482

90着。
正月明けくらいから考え始めた。
すぐに一つ方法を思いついたが、よく考えるとどうもうまくいかない。もう一つ思いついたが、これもうまくいかない。かわりばんこに考えていたら、どうも後者がうまくいく可能性があるように思えてきた。そこから少しずつ頭の中で高速化していった。これは必ず速くなるはずだというところを1週間かけて速くしたりした。ここで少しずつというのは数桁速くすることを意味する。
十分に実行可能な速度になったあとはメモリの問題になった。とにかく2GB以内に収めなければならないのだ。Pythonならその壁を突破できるが、PyPyに比べてPythonはメモリを食いすぎて論外。PyPyだとintのリストが1要素8Byteずつ食うので、だいたいいくつリストに入れられるかわかる。今思うと、NumPyPyを使えばメモリを節約できるのかもしれない。その限界があるため、同じ処理を何度も行わなければならなかった。その調整がうまくいかなくてメモリエラーになった。メモリの解放がうまくいかないのだ。以前から考えてはいたが、そうなったあとで、繰り返しする前にファイルに途中結果を書くようにして、またスクリプトを立ち上げるようにした。これで約30時間。かなり頑張ったと思う。

残りあと1問。