Infinite Sequences in Ruby Using Enumerator

The Enumerator class in Ruby allows us to generate some very smooth and useful infinite sequences. For example, in some Project Euler problems it is required to generate sequences without a specific limit. A good example of this is the Highly Divisible Triangular Number problem:

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th 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?

So first we would want to be able to generate a (infinite) sequence of triangular numbers that we can use to do many programming operations, such as iterating over the sequence.

In Ruby, we can use the Enumerator class precisely for this in very simple manner:

def triangle_numbers
  Enumerator.new do |y|
    a = 0
    i = 1
    loop do
      a += i
      y << a
      i += 1
    end
  end
end

In the code above, we are using the Enumerator.new with a block, and passing a yielder (which is an array) y. When the loop inside the block finishes executing, the array will contain the values of the sequence. That means that the logic to generate a particular sequence must be initialized inside the block, and performed inside the block’s loop.

Since I defined the sequence inside a triangle_numbers method, I can call and chain this method with other useful standard Ruby methods:

triangle_numbers.each { |i| puts i } # Will infinitely print triangle numbers

triangle_numbers.take(10) # Will return an array of the first 10 triangle numbers

triangle_numbers.take(100).select { |i| i > 30 } # Will return an array of the first 10 triangle numbers, and select only the ones greater than 30.

Very powerful!

Other examples of sequences can be found in the Triangular, Pentagonal, Hexagonal problem where we need to use the additional pentagonal and hexagonal sequences:

Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:

Triangle 	  	Tn=n(n+1)/2 	  	1, 3, 6, 10, 15, ...
Pentagonal 	  	Pn=n(3n−1)/2 	  	1, 5, 12, 22, 35, ...
Hexagonal 	  	Hn=n(2n−1) 	  	1, 6, 15, 28, 45, ...

It can be verified that T285 = P165 = H143 = 40755.

Find the next triangle number that is also pentagonal and hexagonal.

We can define the sequences in a similar way, and implement the logic according to the information above:

def pentagonal_numbers
  Enumerator.new do |y|
    a = 0
    i = 1
    loop do
      a = i * (3 * i - 1) / 2
      y << a
      i += 1
    end
  end
end

def hexagonal_numbers
  Enumerator.new do |y|
    a = 0
    i = 1
    loop do
      a = i * (2 * i - 1)
      y << a
      i += 1
    end
  end
end

Likewise, we can call and these methods in our Ruby code the same way we did with the triangle_numbers method.

ruby algorithms project euler programming mathematics

Comments

comments powered by Disqus