Project Euler-Problem 12

Description

From Project Euler:

The sequence of triangle numbers is generated by adding the natural numbers. So the 7^th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

Solution

There are two basic parts of this problem that we need to be concerned with. The first is generating the sequence of triangle numbers, and the second is counting how many divisors a given number has.

The first part is relatively trivial. We will just create an Enumerable that returns the proper sequence of numbers:

class Problem012
  include Enumerable

  def each
    counter = 1; result = 1
    while true
      yield result
      result += (counter += 1)
    end
  end
end

The next part of the problem is to count the number of divisors for a given number. Note that we don't actually need to compute the divisors, just count how many there are. The first observation that we can make is that the number of divisors will always be even except for the case of a perfect square. Why? Because if the number n is evenly divisible by a number d (and hence it is a divisor), then it is also divisible by n/d. So in finding divisor d, we have also found n/d. For perfect squares, however, this rule works until you reach the square root of n. In that case d = n/d, so there is only one divisor. In addition, we also know that every number greater than one will have at least two divisors - one and itself. Given all of this, we come up with:

class Integer
  def divisor_count
    return 1 if self == 1
    limit = Math.sqrt(self)
    (2..limit).inject(limit == limit.floor ? 1 : 2) do |count,d|
      count + (self % d == 0 ? 2 : 0)
    end
  end
end

We are now in a position to find the first triangle number with greater than 500 divisors:

Problem012.new.find { |n| n.divisor_count > 500 }

The full source and specifications can be seen on github. Next time, finding the first ten digits of the sum of one-hundred 50-digit numbers.