Project Euler 320

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

S(1000)を出すのに1時間かかった。もう心が折れそう。実行時間30秒。
1.6秒になった。
結局47分かかった。14着。どうやったら速くなるんだ。
二分探索の範囲がいい加減だったのをちゃんとしたら10倍速くなった。そもそも二分探索しているのが間違っているのだろうか。