Multiplicative Persistence の続きです。
12歳の娘の算数の授業で、「任意の自然数の各桁を、一桁になるまで掛け算する回数の最大回数とその数を示せ。最大桁数を出した生徒には賞品が出ます」という自由課題があったそうだ。例えば、15なら1x5=5と1回。93なら9x3=27, 2x7=14, 1x4=3と３回という具合（続き）1/2
— Keiko Torii (@KeikoUTorii) August 13, 2019
もう少し、枝刈りをまじめに考えてみよう。
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")
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])
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
検算してみるけど、あれもしかしてこれ…もう少し改良できる？
１段だけチェックすれば、もっと候補減らせそうな…
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
で、ここで、
を見ると・・・
- 2^X + 3^Y + 7^(n - X - Y ) と、
- 5^X + 3^Y + 7^(n - X - Y ) と
で、チェックすればよかったのかあ……確かになあ・・・と。