Multiplicative Persistence

Multiplicative Persistence 11を求めたという話題がありましたので、Pythonで実装してみました。自力で書いたあと、調べてさらに探索空間を減らして高速化しました。

自力で書いたもの

できるだけ大きなMultiplicative Persistence Nを持つ数（以下MP-N数と書く）を求めれば良いので、MP-N数の中で最小の数（以下最小MP-N数と書く）のN=11を求めることとした。このとき、各桁を掛け算するというMPの求め方から、桁の並べ方はどうでもよいので、各桁の数字が単調非減少になるような場合だけを対象として探索空間を減らした。
0, 1はN > 2では最小MP-N数には含まれない（0があるとMP-N=1になるため、1は単にその1を除いた数とMP-Nが同じでかつ除いたほうが小さい数であるため）として省略してある。

from collections import deque

N = 11    # MPが11回となる最小の数を求める
TGT = (1, 0)    # これまで発見した最大回数を持つ（最小の数、回数）
q = deque()
for i in range(2, 10):    # N > 1では0, 1は出てこない
    q.append(i)

# 幅優先探索
while True:
    t = q.popleft()
    c = 0
    tmp = t
    while True:
        tmp_ = 1
        while tmp > 0:
            tmp_ *= tmp % 10   # 小さい桁では文字列化するより速い
            tmp //= 10
        tmp = tmp_
        c += 1
        if tmp < 10:
            break
    if c == N:
        TGT = (t, c)
        break
    for j in range(t % 10, 10):   # 次の桁を重複しないように追加
        q.append(t * 10 + j)

print("%d has multiplicative persistence %d." % TGT)
# 277777788888899 has multiplicative persistence 11.

私のPCでPyPy使って0.43秒くらい。

さらに考察して探索空間を減らす

記事を参考に考察すると、最小MP-N数を求める場合は、各桁を掛け算するというMPの求め方から以下のように候補を絞ることができる；

• N > 1で、各桁の数字は必ず単調非減少（上の桁の数字は下の桁の数字より同じか小さい）
• N > 1で、0は含まれない（N=1になるため）
• N > 1で、1は含まれない（単に1を取り除いた数のほうが小さいため）
• 2と2とは同時に含まれない（4が1つのほうが小さいため）
• 2と3とは同時に含まれない（6が1つのほうが小さいため）
• 2と4とは同時に含まれない（8が1つのほうが小さいため）
• 3と3とは同時に含まれない（9が1つのほうが小さいため）
• 3と4とは同時に含まれない（2と6の2つのほうが小さいため）
• 3と6とは同時に含まれない（2と9の2つのほうが小さいため）
• 4と4とは同時に含まれない（2と8の2つのほうが小さいため）
• 4と6とは同時に含まれない（3と8の2つのほうが小さいため）
• 6と6とは同時に含まれない（4と9の2つのほうが小さいため）
• N > 2で、5と偶数とは同時に含まれない（0が発生してN=2になるため）

したがって、N > 2のとき以下の規則が導ける。

• 各桁の数字は必ず単調非減少（上の桁の数字は下の桁の数字より同じか小さい）
• 一番上の桁が0, 1はありえない
• 一番上の桁が2のとき、2, 3, 4, 5は含まれず、6はあるとしてもその次の桁に1つ
• 一番上の桁が3のとき、3, 4, 6は含まれない
• 一番上の桁が4のとき、4, 5, 6は含まれない
• 一番上の桁が5のとき、偶数は含まれない
• 一番上の桁が6のとき、6は含まれない

まとめると、**最小MP-N数は、N > 2のとき、以下のどちらかである。

1. 先頭が「2, 3, 4, 6, 7, 8, 9, 26」のどれかになり、その後ろに続く数には7, 8, 9しか含まれない。
2. 先頭が「5, 35」のどれかになり、その後ろに続く数には5, 7, 9しか含まれない。**
   ただし、5が含まれる場合、MPを計算する過程でどこか1桁でも偶数になればただちに0になるので、特に大きな桁の数では最小MP-N数に5が含まれることは起こりそうにない。今回はMP-N数を求めさえすれば良い（最小MP-N数である必要はない）ので、条件1だけで最小MP-N数候補を探索すればより高速に求めることができそうだ：

from collections import deque

N = 11
TGT = (1, 0)
q = deque()
for i in [2, 3, 4, 6, 7, 8, 9, 26]:
    q.append(i)

# 幅優先探索
while True:
    t = q.popleft()
    c = 0
    tmp = t
    while True:
        tmp_ = 1
        while tmp > 0:
            tmp_ = tmp_ * (tmp % 10)
            tmp = tmp // 10
        tmp = tmp_
        c = c + 1
        if tmp < 10:
            break
    if c == N:
        TGT = (t, c)
        break
    tm = t % 10
    tp = t * 10
    for j in range(max(tm, 7), 10):
        if j >= tm:
            q.append(tp + j)

print("%d has multiplicative persistence %d." % TGT)
# 277777788888899 has multiplicative persistence 11.

私のPCでPyPy使って約0.02秒くらい。かなり高速化した。

なお、記事では5(7|9)と35(5)+(7|9)...は除外できるように読めるが、理由がわからなかったので上の考察では条件2に入れてある。理由がわかる人がいたら教えてほしい。

N > 11について

12以上は10^233未満にはないらしい。上記改善版で10^100まで回してみたが（約2分）、見つからなかった。