Iterate over an infinite sequence in Ruby

Question

I am trying to solve Project Euler problem #12:

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?

Here's the solution that I came up with using Ruby:

triangle_number = 1
(2..9_999_999_999_999_999).each do |i|
  triangle_number += i
  num_divisors = 2 # 1 and the number divide the number always so we don't iterate over the entire sequence
  (2..( i/2 + 1 )).each do |j|
    num_divisors += 1 if i % j == 0
  end
  if num_divisors == 500 then
    puts i
    break
  end
end

I shouldn't be using an arbitrary huge number like 9_999_999_999_999_999. It would be better if we had a Math.INFINITY sequence like some functional languages. How can I generate a lazy infinite sequence in Ruby?

Answer 1

Currrent versions of Ruby support generators heavily:

sequence = 1.step

Answer 2

On Christmas Day 2018, Ruby introduced the endless range, providing a simple new approach to this problem.

This is implemented by ommitting the final character from the range, for example:

(1..)
(1...)
(10..)
(Time.now..)

Or to update using Jonas Elfström's solution:

(2..).find { |i| ((2..( i / 2 + 1 )).select { |j| i % j == 0 }.count + 2) == 42 }

Hope this proves useful to someone!

Answer 3

In Ruby 2.6 this becomes much easier:

(1..).each {|n| ... }

Source: https://bugs.ruby-lang.org/issues/12912

Answer 4

Several answers are close but I don't actually see anyone using infinite ranges. Ruby supports them just fine.

Inf = Float::INFINITY # Ruby 1.9
Inf = 1.0/0 # Ruby before 1.9
(1..Inf).include?(2305843009213693951)
# => true
(1..Inf).step(7).take(3).inject(&:+)
# => 24.0

In your case

(2..Inf).find {|i| ((2..( i/2 + 1 )).select{|j| i % j == 0}.count+2)==42 }
=> 2880

Your brute force method is crude and can, potentially, take a very long time to finish.