How to Implement an Amicable Number Algorithm in Ruby
In this lesson, we are going to find a solution in Ruby for a complex problem from Project Euler (problem #21) that asks: Evaluate the sum of all the amicable numbers under 10000. Clear as mud right? Essentially, you take a number, identify all its divisors and add them together to get a value. Next, take that final sum value, identify its divisors and add them together. If this second sum value is the same as the original number for which you found divisors in the first place, then both the original number and its final sum are considered as amicable numbers.
Guide Tasks
  • Read Tutorial
  • Watch Guide Video
Video locked
This video is viewable to users with a Bottega Bootcamp license

In this guide we are going to find a solution in Ruby the math problem that asks:

Evaluate the sum of all the amicable numbers under 10000..

So that made perfect sense, right? Just got knock that out... In case your amicable number knowledge is a little rusty like mine was, let's look at a definition for amicable numbers:

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n). If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers.

The full question is below:

Still unclear? Essentially, you take a number, identify all its divisors and add them together to get a value. Next, take that final sum value, identify its divisors and add them together. If this second sum value is the same as the original number for which you found divisors in the first place, then both the original number and its final sum are considered amicable numbers.

The question is asking us to find the sum of all such amicable numbers under 10,000.

Now, we are going to solve this problem in Ruby. We are going to include a gem called mathn and then do some metaprogramming by opening the Integer class. Inside this class, let's create a new method called dsum.

require 'mathn'

class Integer
  def dsum
    return 1 if self < 2
    pd = prime_division.flat_map{|n,p| [n] * p}
    ([1] + (1...pd.size).flat_map{ |e| pd.combination(e).map{ |f| f.reduce(:*) }}).uniq.inject(:+)
  end
end

First we are returning a value of 1 if the object value is less than 2. This makes sense because 1 has no divisor besides itself.

Next, we are creating a variable called pd to store the result of our prime division calculation. For this, we are calling a method called flat_map that takes two parameters, one being n and the other being p. Inside this block we are creating a block that will give us all the prime divisors that are provided.

Next we have a complicated line that sums all the prime divisors. Let's go over each part of that line.

In the first part, we are combining all the prime divisors value and adding 1 to that array. So this will combine all the prime divisors including 1 into a single array. Then we are creating once again using the flat_map method and passing a nested block to it. Inside this block we are calling a method called combination that will find all the combinations in our prime divisors and then it's passing the multiplication method to each element, creating a product. At the end of the line we are calling the uniq method since only want to grab the unique matches. Finally, inject will return the sum of all the values.

Next, we are going to create another method called find_d_sum that will call this dsum method. We'll call this method from outside where we've opened up the Integer class:

def find_d_sum(n)
  n.times.inject do |sum, cur| 
    other = cur.dsum
    (cur  != other && other.dsum == cur) ? sum + cur :sum
  end
end

The first line iterates over each of the n times provided by the method argument and it leverages the inject method to combine the values. The second line stores that value in a variable called other. Next is a conditional that checks if cur is not equal to other and also if the dsum value of other is equal to cur. If that's true, we are printing the value of sum and cur. Otherwise, we return only the value of sum.

Finally, we print the value returned by find_d_sum.

If you execute the code, the output is 31,626. And that's the right answer.

Since this is complicated, play around with this code and see what the effect is when you change isolated components and how that affects the final output. Also, explore some of these methods that are new to you.