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?

Jaipur

num_divisors == 500 should be changed to num_divisors > 500. You don't have proof that there is one that has exactly 500 divisors. Actually, that may be the reason your program is running forever. Furthuremore, the question is not asking for one with 500, but the first one over 500. Read the question carefully. – Agaric

(side node) get triangle numbers with n*(n+1)/2 and you won't need to accumulate values... – Selfpreservation

Side note: n * (n + 1) / 2 factors cleanly into two mutually prime numbers... – Kirsten

Answer 1

In Ruby >= 1.9, you can create an Enumerator object that yields whatever sequence you like. Here's one that yields an infinite sequence of integers:

#!/usr/bin/ruby1.9

sequence = Enumerator.new do |yielder|
  number = 0
  loop do
    number += 1
    yielder.yield number
  end
end

5.times do
  puts sequence.next
end

# => 1
# => 2
# => 3
# => 4
# => 5

Or:

sequence.each do |i|
  puts i
  break if i >= 5
end

Or:

sequence.take(5).each { |i| puts i }

Programming Ruby 1.9 (aka "The Pickaxe Book"), 3rd. ed., p. 83, has an example of an Enumerator for triangular numbers. It should be easy to modify the Enumerator above to generate triangular numbers. I'd do it here, but that would reproduce the example verbatim, probably more than "fair use" allows.

Gerick

This seems to be closer to what i wanted, Thanks. Is there any way that I can use that in my loop above. Or can i use something like [code] while sequence [/code] to achieve this infinite looping untill the break condition is satisfied. – Jaipur

@nikhil, You can use each with the enumerator. Example added. You probably want to modify the enumerator to generate triangular numbers, which ought to be easy. – Gerick

Answer 2

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 < 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.

Schmitz

Could You suggest what approach I should use instead, I can only think of this brute force method. Is there some mathematical property of the divisors that can help instead? – Jaipur

You might find something at mathworld.wolfram.com/Divisor.html but it seems that there's no "magic" formula. – Yamauchi

Come to think of it, it feels pretty clear that there is no known easy way since that would identify prime numbers. – Yamauchi

This problem continues to elude me. I have all but given up on coming up with a solution to this. – Jaipur

"If you factor a number into its prime power factors, then the total number of factors is found by adding one to all the exponents and multiplying those results together. Example: 108 = 2^2*3^3, so the total number of factors is (2+1)*(3+1) = 3*4 = 12. Sure enough, the factors of 108 are 1, 2, 3, 4, 6, 9, 12, 18, 27, 36, 54, and 108." - mathforum.org/library/drmath/view/57151.html – Yamauchi

Answer 3

Infinity is defined on Float (Ruby 1.9)

a = Float::INFINITY
puts a #=> Infinity
b = -a
puts a*b #=> -Infinity, just toying

1.upto(a) {|x| break if x >10; puts x}

Longdistance

I think that this is what I wanted here, This is really cool any ideas on how something is actually implemented? – Jaipur

Matz Ruby is written in C, which supports Infinity (and Nan). I guess Ruby just uses the C routines. – Longdistance

in Ruby < 1.9 create your own infinity: 1.0/0 – Selfpreservation

Answer 4

Currrent versions of Ruby support generators heavily:

sequence = 1.step

Longdistance

To expand on this, 1.step returns an Enumerator, which can then be chained, like this: 1.step.each { |i| puts i; break if i > 10 }. You can also use take to just get the first n numbers: 1.step.take(n) => [1, 2, 3, 4, 5]. – Gen

@Gen 1.step { |i| puts i; break if i > 10 } is the same (no each). – Longdistance

Answer 5

In Ruby 2.6 this becomes much easier:

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

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

Minimalist

Answer 6

This would be best as a simple loop.

triangle_number = 1
i  = 1
while num_divisors < 500
  i += 1
  triangle_number += i
  # ...
end
puts i

Kirsten

Thats not what i'm looking for exactly, I was looking for a more rubyish solution not C++ like. I'd really like to know how I can generate an infinite series. – Jaipur

Ruby does not really have lazy evaluation unless you simulate it with closures, and I believe that would be very slow (Haskell is optimised for that kind of thing). Without lazy evaluation, you don't get infinite streams. I don't think there is anything particularly unRubylike here - use the tool appropriate for the job. But if you really want those, here's one implementation: chneukirchen.org/blog/archive/2005/05/… – Kirsten

This is a perfectly valid ruby solution and not at all "C++ish". I do understand what you are after, of course, you'd like to know if you can make it look prettier - nothing wrong with that - and it lets you learn a bit about Ruby Iterators... but I'll give you a hint for future Project Euler solutions: sometimes the only way to make it run within the minute is to use local variables as above, because the "rubyish" way is actually much slower. ;) – Defence

Answer 7

As Amadan mentioned you can use closures:

triangle = lambda { t = 0; n = 1; lambda{ t += n; n += 1; t } }[]
10.times { puts triangle[] }

Don't really think it is much slower than a loop. You can save state in class object too, but you will need more typing:

class Tri
  def initialize
    @t = 0
    @n = 1
  end

  def next
    @t += n
    @n += 1
    @t
  end
end

t = Tri.new
10.times{ puts t.next }

Added:

For those who like longjmps:

require "generator"

tri =
  Generator.new do |g|
    t, n = 0, 1
    loop do
      t += n
      n += 1
      g.yield t
    end
  end

puts (0..19).map{ tri.next }.inspect

Freya

I've just started with ruby and this doesn't make too much sense to me, could you put it in a somewhat simpler manner. – Jaipur

First method is a simple closure. You can check this link joeybutler.net/ruby/what-is-a-closure (first thing I found using google). Second method is a classic OOP. – Freya

+1 Smullyan points for the triangle = lambda... example, which is beautifully functional. It gives me the same sense of beauty I got when reading "To Mock a Mockingbird." – Gerick

Answer 8

Building on Wayne's excellent answer and in the Ruby spirit of doing things with the least number of characters here is a slightly updated version:

sequence = Enumerator.new { |yielder| 1.step { |num| yielder.yield num } }

Obviously, doesn't solve the original Euler problem but is good for generating an infinite sequence of integers. Definitely works for Ruby > 2.0. Enjoy!

Cutis

Answer 9

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!

Jakob

Answer 10

I believe that fibers (added in Ruby 1.9 I believe) may be close to what you want. See here for some information or just search for Ruby Fibers

Justus

I've always hated longjmps. You can use generators in R 1.8.7 with similar effect. – Freya