Project Euler 475

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

76着。3分。
日曜日、ナイーブな実装はすぐに思いついた。しかし、これでは答えは出ない。ほかにやりたいこともある。スルーする。
翌日、電車の中で考える。しかし何も出てこない。帰ってからナイーブな実装に手を付ける。なぜか答えが合わない。
今日、帰りに電車の中でなにやら思いついた。しかしn = 2で答えが合わない。どれくらい合わないか調べるためにナイーブな実装をなんとかしようとする。がんばっていたらn = 2が合った。nを大きくしていくと、意外と時間を食わない。n = 35で48秒で、40だと1分超えそう。あれ、っと思って問題を見直してみる。n = 50を出せばいいんじゃないか。これならこのまま押せそう。少しメモリ対策して回してみる。3分をちょっと切るくらいだった。
明日、4と3を3と2に直して今日思いついた方法を考えてみる。