notebook.community

Edit and run

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?



In [3]:

    
def find_factor(target)
  result = []
  (2..target).lazy.each do |i|
    reminder = target % i
    
    if reminder != 0
      next
    else
      target = target / i
      result << i
      if target == 1
        break
      end
      redo
    end
  end

  return result
end

find_factor(28)









    Out[3]:





[2, 2, 7]



In [4]:

    
def find_divisor(num)
  result = [1, num]
  factors = find_factor(num)
  (1..(factors.length - 1)).each do |i|
    result << factors.combination(i).to_a.map{|set|set.inject(&:*)}
  end

  return result.flatten.uniq.sort
end

find_divisor(28)









    Out[4]:





[1, 2, 4, 7, 14, 28]



In [5]:

    
def triangle_number
  return Fiber.new do 
    (1..Float::INFINITY).each do |last|
      Fiber.yield (1..last).to_a.inject(&:+)
    end
  end
end



In [6]:

    
tn = triangle_number
target = 0

loop do
  target = tn.resume
  divisors = find_divisor(target)
  break if divisors.length >= 500
end

target









    Out[6]:





76576500



In [ ]: