multiplicative persistence

しばらく前，TwitterでUniversity of WashingtonのKeiko Toriiさんの12歳の娘さん（gifted class）の算数の自由課題が話題になっていた。任意の自然数の各桁の積を計算して新たな自然数を求める。答えの自然数に対してさらにこの計算を反復しする。これを繰り返すと最後には１桁の自然数が得られる。１桁の自然数に到達するまでの反復回数がなるべく大きくなるもとの自然数を探せというのが賞品付きの課題だ。8th grade にも関らず，pythonでプログラムを組んで反復数11の数を見つけたとのこと。

飛び級小学生（＝中学生相当）には負けてられませんと，Brute Forceで計算してみた。残念ながら時間ばかりかかって反復数が10にしかとどかなかず老人は小学生に完敗だ。調べてみると，Persistence of a NumberというWikipediaの項目が見つかった。日本語版はない。自然数に一定のアルゴリズムでの操作を行って不変になるものを探すという問題群らしい。OEIS（On Line Encyclopedia of Integer Sequences ）A003001 にもある。

さらに調べると，Rubyで効率的な探索をしている人がいたので，この方法を Juliaにあてはめてみた。考え方としては，２と３と７のベキからなる数の集合から，反復数が最も大きいものを探し，その数を構成する因子の２と３と７の数字が並んだ数が，反復数＋１の数を与えるというものだ。反復回数11回の数が２つ見つかった。

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
function pcount(n::Int128)
  local m::Int128
  println(n)
  c = 0
  while n >= 10
    m = 1
    while n>0 && m>0
      m *= n%10
      n ÷= 10
    end
    n = m
    c += 1
    println(n)
  end
end

function count(n::Int128)
  local m::Int128
  c = 0
  while n >= 10
    m = 1
    while n>0 && m>0
      m *= n%10
      n ÷= 10
    end
    n = m
    c += 1
  end
  return c
end

function search(n2,n3,n7)
  local n,m3,m7::Int128
  d = (0,0,0,0,0)
  max = 0
  for k in 1:n7
    m7 = 7^k
    for j in 1:n3
      m3 = 3^j
      for i in 1:n2
        n = 2^i*m3*m7
        c = count(n)
        if c > max
          d = (i,j,k,c,n)
          max = c
        end
      end
    end
  end
  println(d)
  return d
end

function next(p)
  s="23789"
  m=[0,0,0,0,0]
  m[1]=p[1]%3
  m[2]=p[2]%2
  m[3]=p[3]
  m[4]=p[1]÷3
  m[5]=p[2]÷2
  c=""
  for i in 1:5
    for j in 1:m[i]
      c=c*s[i]
    end
  end
  return parse(Int128,c)
end

a=search(20,10,10)
pcount(next(a))
b=search(10,20,10)
pcount(next(b))
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
(19, 4, 6, 10, 4996238671872)
277777788888899
4996238671872
438939648
4478976
338688
27648
2688
768
336
54
20
0
(4, 20, 5, 10, 937638166841712)
27777789999999999
937638166841712
438939648
4478976
338688
27648
2688
768
336
54
20
0