nの倍数が0,1,2で構成される最小の値をf(n)の値をとして、10000までのf(n)/nの値の和を求めようという問題
なかなか計算量が多いのですが、うまくやれば、計算量が減らせそうな感じになってきました。
今のところ、pythonでプログラムを書いてみて、11秒ぐらいかかってます。
(ずいぶん昔のPCではありますが・・)
基本的には、f(n･m)≧f(n)の関係が成り立っているはずです。
・・・f(n･m)がf(n)より小さいとしたら、n･mもnの倍数なので、f(n･m)がf(n)でなければならないのでこうなるはず・・・
それで、過去の値からf(n)を推測できるものがでてきます。
まず、
f(10n)＝10f(n)
f(5m)=10f(m) (mは奇数)
です。
g(n)=f(n)/nとすると
g(10n)=g(n)
g(5m)= 2g(m) (mは奇数)
ということになります。
g(n)が偶数であれば、
f(2n)=f(n)で、
g(2n)=g(n)/2 が成立します。
これだけで約4割程度の数字が簡単な計算で求まります。
ただし、f(n･m)=k･f(n)が成り立つかというとそうでもないようです。
さて、f(n)が大きい数字になるのは、nが9で構成されるときなのですが、f(9)を考えてみます。
1桁目で一番大きな数は2なので、2桁目が必要です。
10を9で割った時の余りは1なので、2桁目が2になっても合計は4で3桁目が必要
100を9で割ったあまりは1なので、3桁目が2になったとき合計は6
1000を9で割ったあまりは1なので、4桁目が2になった時合計は8
10000を9で割ったあまりは1で、5桁目が1の時に合計が9になります。
ということでf(9)=12222です。
99の場合も同様に考えることができ、99の場合は100単位で考えます。
そうするとf(99)=1122222222です。
つまり、nの桁数で{0,1,2}で作ることができる数字を1blockとすると５blockが最大です。
しかも9,99,999・・・といった、9のみで構成される数字以外に5blockになるものは存在しないため、
4blockまでの検査で見つかることになります。
nの桁数をdとして、10^d ー n ＝ 1となるもののルールがわかることで、計算量を大きく減らすことができます
それなら10^d ー n ＝ 2,3,4となるものを順に見つけていったら、と考えることもできるのですが、2、5については過去の値から求まりますし、いろんな場合を考えるのもあまり得策ではなさそうです。考えるとしたら11です。しかしルールがわかりません。