この問題をpythonで組んでみる。
12歳の娘の算数の授業で、「任意の自然数の各桁を、一桁になるまで掛け算する回数の最大回数とその数を示せ。最大桁数を出した生徒には賞品が出ます」という自由課題があったそうだ。例えば、15なら1x5=5と1回。93なら9x3=27, 2x7=14, 1x4=3と3回という具合(続き)1/2
— Keiko Torii (@KeikoUTorii) August 13, 2019
- 総当たり法よりももう少し良い方法はないかな?もうちょっと枝狩りたい。
各桁は交換法則が成り立つ。
"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に結果残していたりするけど、そこらへんはご愛敬ということで!
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])
で、結果の一部、まだまだ計算中(というかたぶん、宇宙が終わるまで、終わらない)
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回になりますかね…
検算
(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)
11以上は10^50まで存在しないので、おそらくスパコンでも無理かと思います。https://t.co/rR2TGIcZ4Z
— Endo, Takaho (@caripso) August 14, 2019
ほほぉ……
(と、ここでこのプログラムで1を除外したけどこれ正しいかどうか微妙な気がしてきた…)
プログラムの結果は、「 77777733332222222222222222222 」であってますけどね…