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

Multiplicative Persistence の続きです。

<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>


もう少し、枝刈りをまじめに考えてみよう。

> 0,1,2,3,4,5,6,7,8,9

* 0が含まれると積が0になるので除外。
* 1が含まれると桁数が膨れ上がるので除外。
* 4,8 は、2*2, 2*2*2の代替となるのでなるべく使う。
* 6は、2*3の代替となるのでなるべく使う。
* 9は、3*3の代替となるのでなるべく使う。
* 1つでも2,4,8が含まれているときに、5が含まれると次々回の積で0になるので、なるべく使わない。
* 4が3以上含まれた、(2*2)*(2*2)*(2*2)* = (2*2*2)*(2*2*2) = 8*8 を冗長に表現しているので、使わない。
* 6が2以上含まれているとき、(2*3)*(2*3)=4*9を冗長に表現しているので、使わない。

つまり、

* 0が1個以上含まれたらスキップ。
* 1が1個以上含まれたらスキップ。
* 2が2個以上含まれたらスキップ。("22" = "4")
* 3が2個以上含まれたらスキップ。("33" = "6")
* 4が3個以上含まれたらスキップ。("444" = "88")
* 6が2個以上含まれたらスキップ。("66" = "49")
* 2が1個以上、かつ、3が1個以上含まれたらスキップ。("23"="6")
* 2が1個以上、かつ、4が1個以上含まれたらスキップ。("24"="8")
* 2が1個以上、かつ、5が1個以上含まれたらスキップ。("25"->"*0"-> "0")
* 2が1個以上、かつ、6が1個以上含まれたらスキップ。("26" = "34")

``` python

def calMultiplicativePersistence(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 = calMultiplicativePersistence( str(t) ,p+1)
        return c3,p2+1

def func(v):
    countList = [ 0,0,0,0,0,0,0,0,0,0 ]
    for c in v:
        idx = int(c)
        countList[idx] = countList[idx] + 1

    if ( countList[2] >= 2 ) : return False 
    if ( countList[3] >= 2 ) : return False 
    if ( countList[4] >= 3 ) : return False 
    if ( countList[6] >= 2 ) : return False 
    if ( (countList[2] >= 1) and ( countList[3] >= 1) ) : return False 
    if ( (countList[2] >= 1) and ( countList[4] >= 1) ) : return False 
    if ( (countList[2] >= 1) and ( countList[5] >= 1) ) : return False 

    return True

def makeCandidateList(x):
    ret = list()
    if(len(x) == 0 ):
        s = 2
    else:
        s = int ( x[-1:] )

    for i in range(s,10) :
        v = x + str(i)
        if ( func(v) == True ) :
            ret.append(v)
    return ret

## 初期値
t = makeCandidateList("")

for i in range(1,100):
    r = list()
    pmax = 0
    rimax = 0
    for ti in t:
        ri = makeCandidateList(ti)
        for r2 in ri:
            dmy,p = calMultiplicativePersistence(r2, 0)
            if ( p > pmax ) :
                rimax = int(r2)
                pmax = p
        r.extend ( ri )

    print ( "rimax = " + str(rimax)+ " pmax = " + str(pmax) + " candidate = " + str( len(t) ) )
    t = r

## print ( t[0:20])


```

```text
rimax = 77 pmax = 4 candidate = 8
rimax = 679 pmax = 5 candidate = 29
rimax = 6788 pmax = 6 candidate = 75
rimax = 68889 pmax = 7 candidate = 158
rimax = 344889 pmax = 7 candidate = 290
rimax = 2799999 pmax = 8 candidate = 483
rimax = 34888999 pmax = 9 candidate = 749
rimax = 346777889 pmax = 8 candidate = 1100
rimax = 3778888999 pmax = 10 candidate = 1548
rimax = 34677777899 pmax = 9 candidate = 2105
rimax = 377788888889 pmax = 9 candidate = 2783
rimax = 3888888888889 pmax = 10 candidate = 3594
rimax = 27777777777779 pmax = 9 candidate = 4550
rimax = 277777788888899 pmax = 11 candidate = 5663
rimax = 3477777777778888 pmax = 6 candidate = 6945
rimax = 27777789999999999 pmax = 11 candidate = 8408
rimax = 346888888899999999 pmax = 8 candidate = 10064
rimax = 4777777888888888889 pmax = 6 candidate = 11925
rimax = 34467777778888888888 pmax = 6 candidate = 14003
rimax = 278888888888888888889 pmax = 5 candidate = 16310
rimax = 2777778888888888999999 pmax = 5 candidate = 18858
rimax = 34677777888888888889999 pmax = 4 candidate = 21659
rimax = 777777777777777777788899 pmax = 5 candidate = 24725
rimax = 3467777777777777777777889 pmax = 5 candidate = 28068
rimax = 34477777777777788888888899 pmax = 4 candidate = 31700
rimax = 277777777777777777789999999 pmax = 4 candidate = 35633
rimax = 2777777888889999999999999999 pmax = 4 candidate = 39879
rimax = 27777788888888999999999999999 pmax = 4 candidate = 44450
rimax = 677777888888888888899999999999 pmax = 4 candidate = 49358
rimax = 2777777777777888888888888899999 pmax = 4 candidate = 54615
rimax = 34467777777777777777777777777799 pmax = 4 candidate = 60233
rimax = 277777777777777777777788888899999 pmax = 3 candidate = 66224
rimax = 4777777777788888888888999999999999 pmax = 4 candidate = 72600
rimax = 34467777777777888888888899999999999 pmax = 4 candidate = 79373
rimax = 277777777777777777777777777777777777 pmax = 3 candidate = 86555
rimax = 2777777777777777777777777777788899999 pmax = 3 candidate = 94158
rimax = 47777888888888888888888888889999999999 pmax = 4 candidate = 102194
rimax = 344677778888888888888888888888999999999 pmax = 4 candidate = 110675
rimax = 2777777777777777777777777777777778888899 pmax = 3 candidate = 119613
rimax = 37777777777777777777777888999999999999999 pmax = 4 candidate = 129020
rimax = 277777777777777777777777777788888999999999 pmax = 3 candidate = 138908
rimax = 2777777777777777777777777777777788899999999 pmax = 3 candidate = 149289
rimax = 47777777777777777777777777777778888888899999 pmax = 4 candidate = 160175
rimax = 344677777777777777777777777777777788888889999 pmax = 4 candidate = 171578
rimax = 2777777777777777777777777777777777788888888888 pmax = 3 candidate = 183510
rimax = 27777777777777777777777777777777777777777777889 pmax = 3 candidate = 195983
rimax = 677777777777777777777777777777777777777899999999 pmax = 4 candidate = 209009
rimax = 3447777777777777777777777777777777777777799999999 pmax = 4 candidate = 222600
rimax = 27777777777777777777777777777777777777777777778889 pmax = 3 candidate = 236768
rimax = 277777777777777777777777777777777777777777778889999 pmax = 3 candidate = 251525
rimax = 2777777777777777777777777777777777777777777778999999 pmax = 3 candidate = 266883
rimax = 27777777777777777777777777777777777777777778888888888 pmax = 3 candidate = 282854
rimax = 277777777777777777777777777777777777777777777777789999 pmax = 3 candidate = 299450
rimax = 2777777777777777777777777777777779999999999999999999999 pmax = 3 candidate = 316683
rimax = 27777777777777777777777777777777777777777888899999999999 pmax = 3 candidate = 334565
rimax = 277777777777777777777777777777778899999999999999999999999 pmax = 3 candidate = 353108
rimax = 2777777777777777777777788888888888888899999999999999999999 pmax = 3 candidate = 372324
rimax = 27777777777777777777777777777777777777777777777777777999999 pmax = 3 candidate = 392225
rimax = 277777777777777777777777777777777777777888888888888889999999 pmax = 3 candidate = 412823
rimax = 2777777777777777777777777788888999999999999999999999999999999 pmax = 3 candidate = 434130
rimax = 27777777777777777777777777777777777777788888888999999999999999 pmax = 3 candidate = 456158
rimax = 277777777777777777777777777777777777777777777777888888888888888 pmax = 3 candidate = 478919
rimax = 2777777777777777777777777777777777777777777777777777777777777778 pmax = 3 candidate = 502425
rimax = 27777777777777777777777777777777777777777777777799999999999999999 pmax = 3 candidate = 526688
rimax = 277777777777777777777777777777777777777777778888888888999999999999 pmax = 3 candidate = 551720
rimax = 2777777777777777777777777777777777777777777777778888888888888899999 pmax = 3 candidate = 577533
rimax = 27777777777777777777777777777777777777777777777888888899999999999999 pmax = 3 candidate = 604139
rimax = 277777777777777777777777777777777777777777777777788888888888888999999 pmax = 3 candidate = 631550
rimax = 2777777777777777777777777777777777777788888888899999999999999999999999 pmax = 3 candidate = 659778
rimax = 27777777777777777777777777777888888899999999999999999999999999999999999 pmax = 3 candidate = 688835
rimax = 277777777777777777777777777777777777777777777777777778888899999999999999 pmax = 3 candidate = 718733
rimax = 2777777777777777777777777777777777777777777777777777777777777777788899999 pmax = 3 candidate = 749484
rimax = 27777777777777777777777777777777777777777777777777777778899999999999999999 pmax = 3 candidate = 781100
rimax = 344677777777777777777888889999999999999999999999999999999999999999999999999 pmax = 3 candidate = 813593
rimax = 2777777777777777777777777777777777777777777777777777777777777777788888888899 pmax = 3 candidate = 846975
rimax = 27777777777777777777777777777777777777777777778888888888888889999999999999999 pmax = 3 candidate = 881258
rimax = 277777777777777777777777777777777777777777777777777777777777777777777788899999 pmax = 3 candidate = 916454
rimax = 2777777777777777777777777777777777777788888888888888888888888888888888888889999 pmax = 3 candidate = 952575
rimax = 27777777777777777777777788889999999999999999999999999999999999999999999999999999 pmax = 3 candidate = 989633
rimax = 277777777777777777777777888888888889999999999999999999999999999999999999999999999 pmax = 3 candidate = 1027640
rimax = 2777777777777777777777777777777777777777778888888888888888888899999999999999999999 pmax = 3 candidate = 1066608
rimax = 27777777777777777999999999999999999999999999999999999999999999999999999999999999999 pmax = 3 candidate = 1106549
rimax = 277777777777777777777777777777777777777777777777777777777777777888888888889999999999 pmax = 3 candidate = 1147475
rimax = 3446777777777777777777777777777777777777777777777777777777777777777778888888888888888 pmax = 3 candidate = 1189398
rimax = 27777777777777788888888888888888888888888888888888888888888888888888888888888888899999 pmax = 3 candidate = 1232330
rimax = 346777777777777777777777777777777777777778888888888888888888888888888888888888888888999 pmax = 3 candidate = 1276283
rimax = 2777777777777777777777777777888888888888888899999999999999999999999999999999999999999999 pmax = 3 candidate = 1321269
rimax = 27777777777777777777777777777777777777777777777888888888888888888888888888888888999999999 pmax = 3 candidate = 1367300
rimax = 277777777777777777777777777888888888889999999999999999999999999999999999999999999999999999 pmax = 3 candidate = 1414388
rimax = 2777777777777777777788888888888888899999999999999999999999999999999999999999999999999999999 pmax = 3 candidate = 1462545
rimax = 34477777777777777788888888888888888888888899999999999999999999999999999999999999999999999999 pmax = 3 candidate = 1511783
rimax = 344777777777777777777777777777778888888888888888888888888999999999999999999999999999999999999 pmax = 3 candidate = 1562114
rimax = 2777777777777777777777777777777777777777777777777777778888888888888888888888888888888888888889 pmax = 3 candidate = 1613550
rimax = 27777777777777777777777777777777777777777777777777777777777777777777778888888888888888899999999 pmax = 3 candidate = 1666103
rimax = 347777777777777777777777777777777777777777788888888888888888899999999999999999999999999999999999 pmax = 3 candidate = 1719785
rimax = 2777777777777777778888888888888888888888888888888888888888888888888888888888888999999999999999999 pmax = 3 candidate = 1774608
rimax = 27777777777777777777777788888888888888888888888888888888888888888888888888888888888888888888888888 pmax = 3 candidate = 1830584
rimax = 344777777777777777777777777777777777777777778888888888888888888888888888899999999999999999999999999 pmax = 3 candidate = 1887725
rimax = 3477777777777788888888888888888888888888888888888888888888888888888888888888888888888888888888888889 pmax = 3 candidate = 1946043
```

検算してみるけど、あれもしかしてこれ…もう少し改良できる？
１段だけチェックすれば、もっと候補減らせそうな…

```text

3477777777777788888888888888888888888888888888888888888888888888888888888888888888888888888888888889

print ( 3 * 4 * 7 * 7 * 7 * 7 * 7 * 7 * 7 * 7 * 7 * 7 * 7 * 7 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 8 * 9 = 
86546424387825783394539543819848599889738394136499838189311316291599955336275394343993344

print ( 8 * 6 * 5 * 4 * 6 * 4 * 2 * 4 * 3 * 8 * 7 * 8 * 2 * 5 * 7 * 8 * 3 * 3 * 9 * 4 * 5 * 3 * 9 * 5 * 4 * 3 * 8 * 1 * 9 * 8 * 4 * 8 * 5 * 9 * 9 * 8 * 8 * 9 * 7 * 3 * 8 * 3 * 9 * 4 * 1 * 3 * 6 * 4 * 9 * 9 * 8 * 3 * 8 * 1 * 8 * 9 * 3 * 1 * 1 * 3 * 1 * 6 * 2 * 9 * 1 * 5 * 9 * 9 * 9 * 5 * 5 * 3 * 3 * 6 * 2 * 7 * 5 * 3 * 9 * 4 * 3 * 4 * 3 * 9 * 9 * 3 * 3 * 4 * 4 ) = 
34769096542706639179811534284246762631541244821504000000000
``` 


で、ここで、

https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0107&L=NMBRTHRY&P=R1036&I=-3

を見ると・・・

* 2^X + 3^Y + 7^(n - X - Y ) と、
* 5^X + 3^Y + 7^(n - X - Y ) と

で、チェックすればよかったのかあ……確かになあ・・・と。