Help us understand the problem. What is going on with this article?

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

More than 1 year has passed since last update.

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

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

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

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

ほほぉ……

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

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

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした