「任意の自然数の各桁を、一桁になるまで掛け算する回数の最大回数とその数を示せ」
という問題で、昨日からCore2 Q6600を動かし続けて電力を消費しまくっています。13回のパターンが存在しないことは数学的に証明されているらしく、一方で277777788888899が11回というのは容易に見つかりましたが、そこから先、12回が見つかりません。
で、高速化の手法を調べているうちに、桁数が多いほど回数が少なくなっていることに気づきました。で、こんなプログラムを作って動かしてみました。(concurrent.futuresを使っていますが、意味はありませんw)
import concurrent.futures
def check(m,n):
s = list(str(m**n))
return('0' in s)
def show(k):
r = [i for i in range(1,10001) if not check(k,i)]
print(k,':',r)
if __name__ == "__main__":
kl = [7,8,9]
with concurrent.futures.ProcessPoolExecutor(max_workers=4) as excuter:
result_list = list(excuter.map(show,kl))
結果は、
7 : [1, 2, 3, 6, 7, 10, 11, 19, 35]
8 : [1, 2, 3, 5, 6, 8, 9, 11, 12, 13, 17, 24, 27]
9 : [1, 2, 3, 4, 6, 7, 12, 13, 14, 17, 34]
こうなりましたが、こんなめんどくさいことしなくても、
>>> [i for i in range(1,10001) if not '0' in list(str(7**i))]
[1, 2, 3, 6, 7, 10, 11, 19, 35]
>>> [i for i in range(1,10001) if not '0' in list(str(8**i))]
[1, 2, 3, 5, 6, 8, 9, 11, 12, 13, 17, 24, 27]
>>> [i for i in range(1,10001) if not '0' in list(str(9**i))]
[1, 2, 3, 4, 6, 7, 12, 13, 14, 17, 34]
>>>
で十分ですね。
これは、7のみ36個以上(1万個以下)」、8のみ27個以上(1万個以下)、9のみ34個以上(1万個以下)の数値は各桁を乗算すると、出てきた数値の中に0の桁が含まれることを示します。
・・・ということはある桁数以上の検証は無意味かも、と思ったのですが、さらに他の数字をいくつか掛けたときに0の桁が残るかまではわからないのか・・・。
いずれにせよ、桁数がふえると、各桁の乗算結果に0だったり、5と2だったりという桁が出てくる確率が高くなりそうなので、桁数が増えるほど実は回数が少なくなりそうです。