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つ以外は見つかりませんでした。)