prob12.rb

require 'euler'

#triangle numbers are generated by n(n+1)/2
#   do a prime factorization, count instances of unique primes
#   put number into the form p0^e0 * p1^e1 * ... * pn^en
#
# number of factors = PI(ei + 1) i in [1, n]
# ei must be at least 1
# minimum of PI(ei+1) i in [1,n] = 2^(n+1)
# we want 2^(n+1) > 501
# n = log_2(501) - 1
# n = 7
# so we must have 7 unique prime numbers
# the lower bound for this is 2 * 3 * 5 * 7 * 11 * 13 * 17 = 510510

# triangle numbers are calculated by tn = n(n + 1)/2
# n(n+1)/2 >= 510510
# n^2 + n >= 1021020
# solution: n >= 1009 by wolfram alpha



primes_hint = SieveOfAtkin.primes_upto((1<<12) -1) #this is a guess
n = 1009
factor_count = -1
while factor_count < 501
  nth_triangle = n * (n + 1) / 2
  factorization = Factorize.trial_divide nth_triangle, primes_hint
  factor_count = factorization.values.inject(1) { |prod, e| prod * (e + 1) }
  puts "#{nth_triangle}, #{factor_count}"
  n += 1
end