Snippet

project_euler/12.rb

Code:

# Project Euler Problem 12: Highly Divisible Triangular Number

# https://projecteuler.net/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?

def prime_factors(n)
    (2...n).each { |f| return [*prime_factors(f), *prime_factors(n / f)] if (n % f == 0) }
    return [n]
end

def divisors(n)
    prime_factors(n).tap { |pf| return pf.uniq.map { |f| pf.count(f) + 1 }.inject(:*) }
end

def solve(n)
    i = 1
    while true
        t = i * (i + 1) / 2
        return t if divisors(t) > n
        i += 1
    end
end

puts solve(5)
# puts solve(500)

Code:

Output: