extract amicable pair

amicable_pair.rb

=begin
두 수 220과 284는 약수를 통해 매우 친근한 관계를 맺고 있다.
220의 진약수(자신을 제외한 약수)는 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110인데, 이것들의 합은 284이다.
또 284의 진약수는 1, 2, 4, 71, 142인데, 이것들의 합은 220이다.
서로 다른 친구를 ‘또 다른 나’라고 역설한 피타고라스는 이 두 수에서 우정의 표상을 발견했으며, 이런 수들을 ‘우애수’의 쌍이라고 불렀다.
10000 이하의 숫자들 중에서 우애수 쌍의 목록을 구하라.
=end
require 'benchmark'

def amicable_pair(max_num)
  amicables = []
  (1..max_num).each do |n|
    next if amicables.include?(n)
    
    amicable_sum = refined_submultiple(n).reduce(0, :+)
    
    next if amicable_sum < n

    if amicable_sum <= max_num && 
      n == refined_submultiple(amicable_sum).reduce(0, :+) && 
      n != amicable_sum
      amicables.push(*[n, amicable_sum]) 
    end
  end

  amicables.each_slice(2).to_a
end

# return 약수
def submultiple(num)
  (1..num).select{|n| num%n==0 }
end

# return 진약수
def refined_submultiple(num)
  submultiple(num).tap{|n| n.delete num}
end



puts Benchmark.measure { puts amicable_pair(10000).inspect }
# => [[220, 284], [1184, 1210], [2620, 2924], [5020, 5564], [6232, 6368]]