150315

Ruby


不思議数

minからmaxまでの不思議数を出力するコードを書いてみた。
オンライン整数列大辞典の
A006037（http://oeis.org/A006037/list）
と比較し、答え合わせしてみる。

N0 = 19700

def sum_of_divisors(p)

  sum = 0

  q = Math.sqrt(p).to_i

  for i in (1..q - 1)

    if p % i == 0

      sum += i + p / i

    end

  end

  if p % q == 0

    if p == q * q

      sum += q

    else

      sum += q + p / q

    end

  end

  return sum

end

def divisors(p)

  ary = []

  q = Math.sqrt(p).to_i

  for i in (1..q - 1)

    if p % i == 0

      ary << i

      ary << p / i

    end

  end

  if p % q == 0

    if p == q * q

      ary << q

    else

      ary << q

      ary << p / q

    end

  end

  return ary

end

def weird?(i, j)

  # weirdなら、「sum_of_divisors(i)からj分だけ引ける」ということは起こらない

  ary1 = divisors(i).select{|n| n <= j}

  ary2 = [0]

  for k in (0..ary1.size - 1)

    ary3 = []

    for l in (0..ary2.size - 1)

      m = ary2[l] + ary1[k]

      if m == j

        return false

      elsif m < j

        ary3 << m

      else

      end

    end

    ary2 |= ary3

  end

  return true

end

def weird_numbers(min, max)

  ary = []

  for i in (min..max)

    j = sum_of_divisors(i) - i * 2

    # 過剰数か？

    if j > 0

      ary << i if weird?(i, j)

    end

  end

  return ary

end

ary = weird_numbers(1, N0)

# OEIS A006037のデータ

ary0 =

[70,836,4030,5830,7192,7912,9272,10430,10570,

 10792,10990,11410,11690,12110,12530,12670,13370,

 13510,13790,13930,14770,15610,15890,16030,16310,

 16730,16870,17272,17570,17990,18410,18830,18970,

 19390,19670]

# 一致の確認

p ary == ary0