12歳の娘の算数を、おっさんが解いてみる（Multiplicative Persistence）

この問題をpythonで組んでみる。

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">12歳の娘の算数の授業で、「任意の自然数の各桁を、一桁になるまで掛け算する回数の最大回数とその数を示せ。最大桁数を出した生徒には賞品が出ます」という自由課題があったそうだ。例えば、15なら1x5=5と1回。93なら9x3=27, 2x7=14, 1x4=3と３回という具合（続き）1/2</p>&mdash; Keiko Torii (@KeikoUTorii) <a href="https://twitter.com/KeikoUTorii/status/1161322092165337088?ref_src=twsrc%5Etfw">August 13, 2019</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

- 総当たり法よりももう少し良い方法はないかな？もうちょっと枝狩りたい。

各桁は交換法則が成り立つ。

> "123" = "132" = "312" = "321" = ...

- 各桁に0が入ったら、そこでおしまいになるので、0はダメ。

> "10" = 1*0 = 0
> "110" = 1*1*0 = 0

- 各桁に1が入ったら、それはノーカウントになるので、1もダメ

> "12" = 1*2 = 2
> "112" = 1*1*2 = 2
> "1112" = 1*1*1*2 = 2

ということは……

> "93" -> sortして"39" = 3*9 = 27
> "27" = 2*7 = 14
= "14" = 1*4 = 4

よし、実装が雑だけど、とりあえる結果がでたのでコードを乗せておこう。
無意味にonmemoryに結果残していたりするけど、そこらへんはご愛敬ということで！

```python
r = {}

def cal(v,p):
    t = 1
    c = int(v)
    if ( c <= 9 ) :
        return c,0;
    else :
        t = 1
        for c2 in v :
            t = t * int(c2)
        c3,p2 = cal( str(t) ,p+1)
        return c3,p2+1

def f(x):
    ret = list()
    if(len(x) == 0 ):
        s = 2
    else:
        s = int ( x[-1:] )
    for i in range(s,10) :
        v = x + str(i)
        ret.append(v)
    return ret

t = f("")
r = list()

for i in range(1,1000):
    pmax = 0
    rimax = 0
    for ti in t:
        r+= f(ti)

    for ri in r:
        dmy,p = cal(ri, 0)
        if ( p > pmax ) :
            rimax = int(ri)
            pmax = p

    print ( "rimax = " + str(rimax)+ " pmax = " + str(pmax) ) 
    t = r
    r = list()

print ( len(t) )
## print ( t[0:20])
```

で、結果の一部、まだまだ計算中（というかたぶん、宇宙が終わるまで、終わらない）

```text
rimax = 77 pmax = 4
rimax = 679 pmax = 5
rimax = 6788 pmax = 6
rimax = 68889 pmax = 7

rimax = 238889 pmax = 7
rimax = 2677889 pmax = 8
rimax = 26888999 pmax = 9
rimax = 223888999 pmax = 9
rimax = 3778888999 pmax = 10

rimax = 22677888999 pmax = 10
rimax = 222377888999 pmax = 10
rimax = 2222267788999 pmax = 10
rimax = 22222237788999 pmax = 10
rimax = 277777788888899 pmax = 11

rimax = 2247777778888899 pmax = 11
rimax = 22227777778888899 pmax = 11
rimax = 222224777777888899 pmax = 11
rimax = 2222222777777888899 pmax = 11
rimax = 22222222477777788899 pmax = 11

rimax = 222222222277777788899 pmax = 11
rimax = 2222222222247777778899 pmax = 11
rimax = 22222222222227777778899 pmax = 11
rimax = 222222222222224777777899 pmax = 11
rimax = 2222222222222222777777899 pmax = 11

rimax = 22222222222222222477777799 pmax = 11
rimax = 222222222222222222277777799 pmax = 11
rimax = 2222222222222222222337777779 pmax = 11
rimax = 22222222222222222223333777777 pmax = 11
rimax = 222222222222222222222222226889 pmax = 10

rimax = 2222222222222222222222222223889 pmax = 10
rimax = 22222222222222222222222222222689 pmax = 10
rimax = 222222222222222222222222222222389 pmax = 10
rimax = 2222222222222222222222222222222269 pmax = 10
rimax = 22222222222222222222222222222222239 pmax = 10

rimax = 222222222222222222222222222222222333 pmax = 10
rimax = 2222222222222222222222223333333399999 pmax = 8
rimax = 22222222222222222222222233333333339999 pmax = 8
rimax = 222222222222222222222222333333333333999 pmax = 8
```

22222222222222222223333777777 を並び替えても掛け算の結果は同じなので、

77777733332222222222222222222 が交換回数11回になりますかね…

検算

```text
(1) 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 3 * 3 * 3 * 3 * 7 * 7 * 7 * 7 * 7 * 7 = 4996238671872
(2) 4 * 9 * 9 * 6 * 2 * 3 * 8 * 6 * 7 * 1 * 8 * 7 * 2 = 438939648
(3) 4 * 3 * 8 * 9 * 3 * 9 * 6 * 4 * 8 = 4478976
(4) 4 * 4 * 7 * 8 * 9 * 7 * 6 = 338688
(5) 3 * 3 * 8 * 6 * 8 * 8 =27648
(6) 2 * 7 * 6 * 4 * 8 = 2688
(7) 2 * 6 * 8 * 8 = 768
(8) 7 * 6 * 8 = 336
(9) 3 * 3 * 6 = 54
(10) 5 * 4 = 20
(11) 2 * 0 = 0
```
# 考察
277777788888899 から、
8は2*2*2 に分解可能。9は3*3に分解可能…ということで、桁数を稼ぐのに使えるわけですな……

# 追記 ( 2019/8/15 15:22)

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">11以上は10^50まで存在しないので、おそらくスパコンでも無理かと思います。<a href="https://t.co/rR2TGIcZ4Z">https://t.co/rR2TGIcZ4Z</a></p>&mdash; Endo, Takaho (@caripso) <a href="https://twitter.com/caripso/status/1161447979321982976?ref_src=twsrc%5Etfw">August 14, 2019</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

ほほぉ……

（と、ここでこのプログラムで1を除外したけどこれ正しいかどうか微妙な気がしてきた…）

プログラムの結果は、「 77777733332222222222222222222 」であってますけどね…