Project Euler 306(3)

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


この問題はまともに解くとDPで2つ前の項を使うのでパッと見は並列化できないように思えるが、少し工夫すればほぼ並列化できる。
4分20秒くらいだったのが、4コアで並列化して69秒になった。4分切っていないのに、4コアで1分切れるはずがない。