Twitterで見かけた
を考えてみました。
最初はPython3で力ずくで試してみて、９回の34888999まではすぐに見つかりました。しかし、ここからは時間がかかります。傾向をみると、８と９がたくさん含まれる数値ということで、そこにターゲットを絞ってみたところ、277777788888899が１１回というのも比較的短時間でわかりました。１３回のものは存在しないことが証明されているらしいので、残りは１２回のものということになります。
これを効率よく探す方法を考えてみました。
数値の並び順が結果には影響しないのはすぐにわかるので、個々の数値がどんな意味があるか考えてみました。もちろん、探すのは最短桁数のものです。
- ０は乗算するといきなり０になってしまうので、候補になりえません。
- １は桁数を増やす効果しかないので、最小桁数のものを考える上では探索不要です。
- ４は２ｘ２、６は２ｘ３、８は２ｘ２ｘ２、９は３ｘ３なので、桁数を短縮する効果があります。
- ７は素数ですから、桁数を短縮する効果はありません。
- ５は２が出てこないケースにおいてのみ意味があります。２があると、結果に０が含まれてしまい、２回で終わってしまいます。
- ２と３は素数ですから、これ以上桁数を短縮する効果はありません。
これらのことから、候補となる数値は７がｘ個、８がｙ個、９がｚ個とそれに付加して２が０〜２個、３が０〜１個、５が０〜１個登場するパターンと思われます。
５は２が０個のときのみ意味があるので、２３５６で構成される桁は最大３桁、４が２ｘ２であることを考えると、２３４５６で構成される最大２桁の範囲で探索すればよいということがわかります。
「２３４５６で構成される最大２桁」＋「７がｘ桁、８がｙ桁、９がｚ桁の組み合わせ」で、２桁の部分をさらに候補を絞ります。２が０〜２桁、３が０〜１桁、５が０〜１桁登場するパターンで、２が２桁＝４が１桁であることを考えると、２が１桁＝２、２が２桁＝２２＝４と同じ、３が１桁＝３、５が１桁＝５、２が１桁＋３が１桁＝６と同じ、２が２桁＋３が１桁＝３４と同じ、３が１桁＋５が１桁＝３５と同じ、ということから、探索するのは[２，４，３，５，６，３４，３５］だけで良いと思われます。
そこで、[２，４，３，５，６，３４，３５］＋（７，８，９の組み合わせからなる多数桁）をチェックするPython3プログラムを作成しました。（見直すと、もっときれいに書けそうですが・・・）
import datetime
keta2 = [2,3,4,5,6,34,35]
maxk = 1 # 桁数を保持
maxn = None # 数値を保持
def once(n): # １回の計算を行う
t = 1
for i in list(str(n)) :
t = t * int(i)
return(t)
def check(n): # 引数の数値が何回かチェックする
global maxk,maxn
k = 1 # ループした回数を保持
t = n # 検査する対象をセット
while True:
r = once(t)
if r < 10 :
break
t = r
k += 1
if k == maxk :
print('同等 ',n,k)
if k > maxk :
maxk = k
maxn = n
print('更新 ',n,k)
def check_print(n): # 引数の数値が何回か出力しながらチェックする
global maxk,maxn
k = 1 # ループした回数を保持
t = n # 検査する対象をセット
while True:
r = once(t)
if r < 10 :
break
t = r
k += 1
print(t,' ',end='')
def kensho(keta): # その桁数の数値の検証を行う
keta789 = keta - 2 #
for i in range(0,keta789+1):
s1 = '7'*i
keta89 = keta789 - i;
for j in range(0,keta89+1):
s2 = '8'*j + '9'*(keta89-j)
for k in keta2: # ２３４５６で構成される数値
s3=str(k)
n = int(s3+s1+s2)
check(n)
if __name__ == "__main__":
start = datetime.datetime.now()
print('start: ',start)
# for keta in range(2,100+1) :
keta = 2
while True:
now = datetime.datetime.now()
print("keta: ",keta," / time: ",now-start," / record: ",maxn,maxk)
kensho(keta)
keta += 1
print("result ",maxn,maxk)
check_print(maxn)
これを Core2 Q6600（古い・・）で実行すると、
keta: 2 / time: 0:00:00.000048 / record: None 1 同等 2 1 同等 3 1 同等 4 1 同等 5 1 同等 6 1 更新 34 2 同等 35 2 keta: 3 / time: 0:00:00.000200 / record: 34 2 同等 29 2 更新 39 3 同等 49 3 同等 59 3 同等 69 3 同等 359 3 同等 68 3 更新 348 4 keta: 4 / time: 0:00:00.000449 / record: 348 4 同等 699 4 同等 3499 4 同等 489 4 同等 3489 4 更新 688 5 同等 3488 5 同等 679 5 keta: 5 / time: 0:00:00.000870 / record: 688 5 同等 6999 5 同等 34999 5 同等 34888 5 更新 6788 6 keta: 6 / time: 0:00:00.001480 / record: 6788 6 同等 49999 6 更新 68889 7 同等 347799 7 keta: 7 / time: 0:00:00.002459 / record: 68889 7 同等 377889 7 更新 3477889 8 keta: 8 / time: 0:00:00.003920 / record: 3477889 8 同等 6999999 8 同等 6888999 8 更新 34888999 9 keta: 9 / time: 0:00:00.005924 / record: 34888999 9 keta: 10 / time: 0:00:00.008575 / record: 34888999 9 keta: 11 / time: 0:00:00.011963 / record: 34888999 9 更新 3778888999 10 keta: 12 / time: 0:00:00.016466 / record: 3778888999 10 keta: 13 / time: 0:00:00.022207 / record: 3778888999 10 keta: 14 / time: 0:00:00.029282 / record: 3778888999 10 同等 3888888888889 10 keta: 15 / time: 0:00:00.037926 / record: 3778888999 10 keta: 16 / time: 0:00:00.048363 / record: 3778888999 10 更新 277777788888899 11 keta: 17 / time: 0:00:00.060824 / record: 277777788888899 11 keta: 18 / time: 0:00:00.075424 / record: 277777788888899 11 同等 27777789999999999 11 keta: 19 / time: 0:00:00.092772 / record: 277777788888899 11 keta: 20 / time: 0:00:00.112918 / record: 277777788888899 11
ということで、60msほどで11回のものまで見つかりました。
これをひたすら回して、現在１１時間で470桁くらいまで到達しているのですが、今の所１２回のパターンは見つかっていません。横軸に桁数、縦軸にその桁数までの所要時間（秒）を取ると、
という感じで、概ね所要時間は ７．７×桁数^4×10^(-7) （秒）で近似できそうです。となると、１０００桁までチェックすると９日くらいかかりそうです。