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

各桁を一桁になるまで掛け算する回数の大きい数をRubyで探す

More than 1 year has passed since last update.

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

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
ユーザーは見つかりませんでした