CODEWITHSUNDEEP
rubyrangeinfinite-sequence
nikhil
nikhil

Reputation: 9385

Iterate over an infinite sequence in Ruby

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?

Upvotes: 10

Views: 6376

Answers (10)

Jonas Elfström
Jonas Elfström

Reputation: 31428

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.

Upvotes: 13

Wayne Conrad
Wayne Conrad

Reputation: 107989

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.

Upvotes: 10

SRack
SRack

Reputation: 12203

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!

Upvotes: 2

Mario P&#233;rez Alarc&#243;n
Mario P&#233;rez Alarc&#243;n

Reputation: 3638

In Ruby 2.6 this becomes much easier:

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

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

Upvotes: 4

steenslag
steenslag

Reputation: 80065

Currrent versions of Ruby support generators heavily:

sequence = 1.step

Upvotes: 6

cpt_peter
cpt_peter

Reputation: 429

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!

Upvotes: 2

Victor Moroz
Victor Moroz

Reputation: 9225

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

Upvotes: 3

Jackson
Jackson

Reputation: 5657

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

Upvotes: 1

steenslag
steenslag

Reputation: 80065

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}

Upvotes: 7

Amadan
Amadan

Reputation: 198324

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

Upvotes: 3

Related Questions