Take the 2-minute tour ×

I am trying to solve Project Euler problem #12:



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
  if num_divisors == 500 then
    puts i

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?

share|improve this question
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. –  sawa Jun 16 '11 at 14:42
(side node) get triangle numbers with n*(n+1)/2 and you won't need to accumulate values... –  tokland Jun 16 '11 at 15:00
Side note: n * (n + 1) / 2 factors cleanly into two mutually prime numbers... –  Amadan Jun 16 '11 at 21:18

6 Answers 6

up vote 5 down vote accepted

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:


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

5.times do
  puts sequence.next

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


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

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.

share|improve this answer
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. –  nikhil Jun 16 '11 at 14:38
@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. –  Wayne Conrad Jun 16 '11 at 15:21

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
# => true
# => 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.

share|improve this answer
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? –  nikhil Jun 16 '11 at 16:06
You might find something at mathworld.wolfram.com/Divisor.html but it seems that there's no "magic" formula. –  Jonas Elfström Jun 16 '11 at 16:21
Come to think of it, it feels pretty clear that there is no known easy way since that would identify prime numbers. –  Jonas Elfström Jun 17 '11 at 7:52
This problem continues to elude me. I have all but given up on coming up with a solution to this. –  nikhil Mar 29 '12 at 10:41
"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 –  Jonas Elfström Mar 29 '12 at 12:33

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}
share|improve this answer
I think that this is what I wanted here, This is really cool any ideas on how something is actually implemented? –  nikhil Jun 16 '11 at 14:52
Matz Ruby is written in C, which supports Infinity (and Nan). I guess Ruby just uses the C routines. –  steenslag Jun 16 '11 at 15:01
in Ruby < 1.9 create your own infinity: 1.0/0 –  tokland Nov 30 '11 at 9:32

This would be best as a simple loop.

triangle_number = 1
i  = 1
while num_divisors < 500
  i += 1
  triangle_number += i
  # ...
puts i
share|improve this answer
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. –  nikhil Jun 16 '11 at 14:23
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/… –  Amadan Jun 16 '11 at 14:27
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. ;) –  Taryn East Jun 16 '11 at 16:42

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

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

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


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

puts (0..19).map{ tri.next }.inspect
share|improve this answer
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. –  nikhil Jun 16 '11 at 14:44
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. –  Victor Moroz Jun 16 '11 at 15:02
+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." –  Wayne Conrad Jun 25 '13 at 14:59

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

share|improve this answer
I've always hated longjmps. You can use generators in R 1.8.7 with similar effect. –  Victor Moroz Jun 16 '11 at 15:04

Your Answer


