How to solve project euler #21 faster?

Question

Original Problem

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.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.

I solved the problem by generating a hash of all the numbers between 1 - 10000 and their corresponding divisors sum (ie hash[220] = 284). I then compared the items in the hash with a copy of the hash... anyways, it works, but it takes a long time. How can I make this faster?

def proper_divs_sum num
  divs = [1]
  for i in 2..((num/2) + 1)
    if num % i == 0
      divs.push i
    end
  end

  divs_sum = 0
  divs.each do |div|
    divs_sum += div
  end
  return divs_sum
end

def n_d_hash_gen num
  nd_hash = {}
  for i in 1..num
    nd_hash[i] = proper_divs_sum(i)
  end
  return nd_hash
end

def amicables num
  amicable_list = []
  hash1 = n_d_hash_gen(num)
  hash2 = n_d_hash_gen(num)

  hash1.each do |item1|
    hash2.each do |item2|
      if item1 != item2 && (item1[0] == item2[1] && item2[0] == item1[1])
        amicable_list.push item1
      end
    end
  end
  return amicable_list
end

Also, I am new to Ruby, so any tips on how to make this more Ruby-like would also be much appreciated.

Answer 1

The function d(n) (more commonly known as σ(n)) is a variant of the divisor function, and it has an important property which lets you calculate it much more efficiently. It is a multiplicative function, which means that if n = ab, where a and b are coprime, then d(n) = d(a) d(b).

This means that if you can calculate d(p^k) where p is prime, then d(n) = d(p₁^k₁) ... d(p_r^k_r), where n = p₁^k₁...p_r^k_r is the prime factorization of n. In fact, it turns out that d(p^k) = (p^k+1 - 1) / (p - 1), so d(n) = ∏_i (p_i^k_i+1 - 1) / (p_i - 1).

So to calculate d(n) efficiently for all 1 ≤ n ≤ 10000, you can use a sieve to calculate the prime factorizations of all n, and then use the formula above to calculate d(n) using the prime factorization.

Once you've done that, all you need is a simple loop to calculate the sum of all n for which d(d(n)) = n.

This can even be optimized further, by combining the sieving step with the calculation of d(n), but I'll leave that as an exercise for the interested. It is not necessary for the size of this particular problem.

Answer 2

There are a couple of things you can do to improve your algorithm:

1) There is no need to loop to n/2 when you compute the divisors. Stop at sqrt(2) instead. By that point you have found half the divisors; the other half are computed as n divided by the first half.

2) When you enter a number in the hash table, you can immediately check if its amicable twin is already in the hash table. No need for two hash tables, or for two nested loops comparing them.

Answer 3

Analysis of your approach

The approach you are taking is to start with a dividing, find its divisors, sum them up, and store them. You'll notice that the method you are using to find the divisors is a naïve one—I don't say this as an insult; it's only to say that your approach doesn't use any information it may have available, and only tries every number to see if it is a divisor. It does this by using modular division, and, in almost every case, the majority of candidates fail the test.

Something more constructive

Consider if you never had to try numbers that could fail a test like this. In fact, starting with the divisors and building up the dividends from there would skirt the issue altogether.

You can do this by looping through every number <= 5000. These are your divisors, the multiples of which are your dividends. Then add the divisor to the sum of divisors for each multiple.

This approach works up the sums bit-by-bit; by the time you've worked through every divisor, you'll have an array mapping dividend to divisor. From there, you can use a method like you already have to search for amicable numbers in this list.

Answer 4

Division is a slow process. In your approach you are doing a lot of it, therefor your program is slow.

First of all in trying to find all divisors of a number you are trying all divisors not larger than half that number as potential divisors. You can improve on that by not going further than the square root of the number. If a number is divisible by a number larger than it's square root, the result of the division will be smaller than the square root. This will eliminate some unnecessary divisions.

Also if a number is not divisble by 2 it will also be not divisble by 4, 6, 8 etc. It is better to just divide by primes and build the possible divisors from those.

However, the problem can be solved by doing no divisions at all.