Problem #12 easy

Highly divisible triangular number

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

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?

Additional Notes

This problem involves finding the smallest triangular number with more than 500 divisors. Triangular numbers are generated by the formula n(n+1)/2. The solution uses number theory to efficiently count divisors by analyzing the prime factorization of each triangular number.

ruby

Implementations

View Raw

require 'prime'

# Divisor extension for Integer
module Divisors
  def divisor_count
    sum = 1
    # see https://en.wikipedia.org/wiki/Divisor_function
    prime_division.each do |x|
      sum *= (x[1] + 1)
    end
    sum
  end
end

# Integer mixin
class Integer
  include Divisors
end

#!/usr/bin/env ruby
require 'core_extensions/integer/divisors'

# @see http://en.wikipedia.org/wiki/Triangular_number
def triangle(num)
  return 3 if num == 1
  ((num + 1) * num) / 2
end

def highest_divisible_triangular_number(stop)
  i = 1
  i += 1 while triangle(i).divisor_count < stop
  triangle(i)
end

puts highest_divisible_triangular_number(500) if __FILE__ == $PROGRAM_NAME

All Solutions