なんとな~くしあわせ?の日記

「そしてそれゆえ、知識そのものが力である」 (Nam et ipsa scientia potestas est.) 〜 フランシス・ベーコン

プロジェクトオイラーProblem 12を解いてみた

今回はほとんど自力では解けてないので、翻訳実装しただけです。

問題

   三角数の数列は自然数の和で表わされ, 7番目の三角数は 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 である. 三角数の最初の10項は:
    
   1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
   となる.
    
   最初の7項について, その約数を列挙すると, 以下のとおり.
    
    1: 1
    3: 1,3
    6: 1,2,3,6
   10: 1,2,5,10
   15: 1,3,5,15
   21: 1,3,7,21
   28: 1,2,4,7,14,28
    
   これから, 7番目の三角数である28は, 5個より多く約数をもつ最初の三角数であることが分かる.
    
   では, 500個より多く約数をもつ最初の三角数はいくつか.

解答

五角数を求めるのも、その約数を求めるのも至極簡単なのですが500を超える約数を愚直に求めるとプログラムの実行が終わりません。
結局私はそこの工夫の仕方が思いつかなかったので他者の回答を読むことにしました。

参考にした解答

解答の方法はリンク先の方々に任せるとして、ポイントを載せる。

問題のポイント

アルゴリズム上の工夫:
  • 一度計算した約数の個数は、保存しておいて再利用する
  • もし、nや(n+1)/2等の数が、再び m(m+1)のかたちで表せるなら、前出の式が再び適用できる(このパターンは意外に多い)
メモ
  • 約数F(n)F(m)は互いに素(!)なので、掛け算で求められる。
    • ここはマジで思いつかなかった、掛け算で求められるので約数自体を保存しておく必要はなく数だけ数えればよい。
  • nや(n+1)/2等の数が、再び m(m+1)のかたちで表せる
    • これを求める方法がわからなかったのだが、コードを見れば一目瞭然、nの平方根を求め+1で掛け算したときnになるか見ている

ソースコード

@fact = {1=>1,2=>2}

def num_factors(n)
  return @fact[n] if @fact.has_key?(n)

  r = Math.sqrt(n).to_i
  num = 0
  if r*(r+1)==n
    num = num_factors(r)*num_factors(r+1)
  else
    i=1
    while i<r
      if n % i==0
        num +=1
      end
      i+=1
    end
    num *= 2
    num += 1 if r*r==n
  end
  @fact[n] = num
  return num
end

n = 2
loop {
  if n.even?
    fn = num_factors(n/2) * num_factors(n+1)
  else
    fn = num_factors(n) * num_factors((n+1)/2)
  end

  if fn >= 500
    printf "%d = (%d * %d)/2, it has %d factors", n*(n+1)/2, n, n+1, fn
    break
  end

  @fact[n*(n+1)/2] = fn
  n+=1
}