RubyでProject Euler - Problem 34

Problem 34 (Project Euler) [原文]

145は面白い数である. 1! + 4! + 5! = 1 + 24 + 120 = 145となる.

各桁の数の階乗の和が自分自身と一致するような数の総和を求めよ.

注: 1! = 1 と 2! = 2 は総和に含めてはならない.

いったいいくつまでの数を調べればいいのかというと、9!の9倍。ざっと326万です。

やることは単純ですので、何も工夫をしないでも答えにはたどり着きますが、やはりここでも時間がかかります。

で、掲示板には2桁の数の階乗和を配列で持つこととして、ループ内の計算を軽減した回答がありました。そのヒントだけを頼りに書いてみたのが以下のコードです。これでもあまり速くなっていませんけど…。

  fact = [1,1,2,6,24,120,720,5040,40320,362880]

  (10..99).each do |i|
    fact << fact[i/10] + fact[i%10]
  end

  limit = fact[9] * 9
  seq = []
  (10..limit).each do |i|
    str = i.to_s
    s = 0
    0.step(str.length-1, 2) do |j|
      s += fact[str[j,2].to_i]
    end
    if i == s
      seq << i
    end
  end

  p seq.inject(0){|s,v|s+v}

ご注意

当分の間、トラックバックの受信を行わないことといたしました。過去に戴いたトラックバックのリストについてはそのまま保持いたします。

トラックバックはありません

コメントはありません。

ご注意

当分の間、JavaScript が有効でないとコメント投稿できないようにします。スパム対策であって、投稿される方の個人情報を取得する目的ではありません。悪しからずご了承ください。