Project Euler 21

思い出したようにProject EulerのProblem 21。aとb、2つの数があるとき、これらの約数の合計が等しく、a!=bであるとき、aとbの組み合わせをamicable numbers(友愛数)と呼ぶ。10000以下のamicable numbersの合計を求めよ。

例えば220と284はamicable numbers。220の約数は1、2、4、5、10、11、20、22、44、55、110だから合計すると284。そして284の約数を足すと220ともとの数になる 。

class Integer
  @@memo = {}

  def divisors
    return @@memo[self] if @@memo[self]
    d = []
    1.upto(self / 2) do |i|
      d << i if (self % i) == 0
    end
    @@memo[self] = d
  end
end

ami = []

2.upto(100000) do |a|
  b = a.divisors.inject(:+)
  c = b.divisors.inject(:+)

  if c == a && a != b then
#    print "#{a}, #{b}: #{a.divisors}, #{b.divisors}\n"
    ami << [a, b].sort
  end
end

p ami.uniq

# [[220, 284], [1184, 1210], [2620, 2924], [5020, 5564], [6232, 6368], [10744, 10856], [12285, 14595], [17296, 18416], [63020, 76084], [66928, 66992], [67095, 71145], [69615, 87633], [79750, 88730]]

EulerのサイトでHaskellのコード例をみてちょっと感動。美しい。

p21 = sum $ filter isAmicable [1..9999]
 
isAmicable a = a==a' && a/=b
	where
		b = sum $ divisors a
		a' = sum $ divisors b
 
divisors n = filter ((==0).(n`mod`)) [1..n-1]

amicable numbersはどんな分布になってるのかなと思ってプロットしてみた。amicable numbersは無限に存在するのかどうか分かっていないらしい。