12回は存在しない気がします

「任意の自然数の各桁を、一桁になるまで掛け算する回数の最大回数とその数を示せ」

という問題で、昨日からCore2 Q6600を動かし続けて電力を消費しまくっています。１３回のパターンが存在しないことは数学的に証明されているらしく、一方で277777788888899が１１回というのは容易に見つかりましたが、そこから先、12回が見つかりません。

で、高速化の手法を調べているうちに、桁数が多いほど回数が少なくなっていることに気づきました。で、こんなプログラムを作って動かしてみました。（concurrent.futuresを使っていますが、意味はありませんｗ）

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個以上（１万個以下）」、8のみ27個以上（１万個以下）、9のみ34個以上（１万個以下）の数値は各桁を乗算すると、出てきた数値の中に０の桁が含まれることを示します。

・・・ということはある桁数以上の検証は無意味かも、と思ったのですが、さらに他の数字をいくつか掛けたときに０の桁が残るかまではわからないのか・・・。

いずれにせよ、桁数がふえると、各桁の乗算結果に０だったり、５と２だったりという桁が出てくる確率が高くなりそうなので、桁数が増えるほど実は回数が少なくなりそうです。