twitterで話題になってた算数のお題のやつですが、安直に探すとせいぜい9回程度の数(数千万～数億)しか見つけられません。(11回の数を見つけた小学生凄い!)

素因数に注目する

さてどうしたものかと考えると、"各桁の数字を掛ける"という事は1桁の数を掛けていくという事、つまり途中経過は全て1桁の素因数のみを持つ合成数になっているはず(表1)なので、これを探して行くのが速い気がします。

(表1) bruteforceで見つけた9回の数 26888999 を処理して行く様子

回	数値	素因数分解
0	26888999	51413 * 523
1	4478976	2^11 * 3^7
2	338688	2^8 * 3^3 * 7^2
3	27648	2^10 * 3^3
4	2688	2^7 * 3 * 7
5	768	2^8 * 3
6	336	2^4 * 3 * 7
7	54	2 * 3^3
8	20	2^2 * 5
9	0	0

1桁の素数は2,3,5,7の4つですが、5が混じると一瞬で積が0に収束してしまいがちなので、2,3,7の合成数を探してみる事にしましょう。
探せる範囲で最大回数となる合成数を見つけ出したら、その合成数の1桁の因数を並べてやる事で最大回数+1の数も見つけられる事になります。

実装

という訳で以下Rubyで書いた探索コード

# 回数算出
def count(n)
  c = 0
  while n >= 10
    m = 1
    while n > 0 && m > 0
      m *= n % 10
      n /= 10
    end
    n = m
    c += 1
  end
  c
end

# 2,3,7の合成数を探索
def search(e2, e3, e7)
  max = 0
  nums = []
  e7.times{|k|
    e3.times{|j|
      e2.times{|i|
        n = (2**i)*(3**j)*(7**k)
        c = count(n)
        if c == max
          nums << [n, i, j, k]
        elsif c > max
          max = c
          nums = [[n, i, j, k]]
        end
      }
    }
  }

  # 一番回数が多かった2,3,7の合成数から回数+1となる数を生成
  nums.sort.each{|n, c2, c3, c7|
    puts "#{max}: #{n} = 2^#{c2} * 3^#{c3} * 7^#{c7}"
    m = '2'*c2 + '3'*c3 + '7'*c7
    m = m.gsub(/222/,'8').gsub(/33/,'9').chars.sort.join.sub(/23/,'6').sub(/22/,'4')
    puts "#{max+1}: #{m}"
  }
end

require 'benchmark'
puts Benchmark::CAPTION, Benchmark.measure {
  # 2^29 * 3^29 * 7^9 までの合成数を探索 (てきとう)
  search(30, 30, 10)
}

結果

10: 4996238671872 = 2^19 * 3^4 * 7^6
11: 277777788888899
10: 937638166841712 = 2^4 * 3^20 * 7^5
11: 27777789999999999
      user     system      total        real
  0.031000   0.000000   0.031000 (  0.037331)

10回となる2,3,7の合成数がサクっと2つ見つかり、11回となる数を2つ生成できました。
(なお探索範囲を2^199 * 3^199 * 7^199まで広げてみても11回以上になる合成数は見つからず、10回の合成数もこの2つ以外は見つかりませんでした。)

他の解法

Pythonで幅優先探索 by @yutasth