# Highly divisible triangular number
# 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?

# Answer:
# 76576500


TRIANGLES = [0, 1]


# ------------------------------------------------------------------------------
def getPrimeFactors(n):
  # loop from 2 to n/2 (i)
  # if n % i == 0, then set n to n/i
  i = 2
  factors = []

  while i <= n:
    # if i is a factor, it must be prime, since we've checked (and divided out) all factors less than i
    if (n % i == 0):
      n = n / i
      factors.append(i)
    else:
      # Can we optimize this by incrementing by 2?
      i += 1

  return factors


# ------------------------------------------------------------------------------
def countDivisors(n):
  # Consider prime factorization:
  # n = a^p + b^q + ... + c^r
  #   only check up to c where c = sqrt(n)
  # Then n has z factors, where z = (p+1) * (q+1) * (r+1)

  z = 1

  primeFactors = getPrimeFactors(n)
  uniqueFactors = set(primeFactors)

  for i in uniqueFactors:
    # count how many times it appears
    occurences = primeFactors.count(i)

    z = z * (occurences+1)

  # print primeFactors
  # print uniqueFactors

  return z


# ------------------------------------------------------------------------------
def triangle(n):
  # If we already have a value calculated
  if n < len(TRIANGLES):
    return TRIANGLES[n]

  # If not already calculated, then calc and return
  # First, check if the immediately previous triangle has been calc.
  if (n-1) < len(TRIANGLES):
    lastTriangle = TRIANGLES[n-1]
  else:
    lastTriangle = triangle(n-1)

  thisTriangle = n + lastTriangle
  TRIANGLES.append(thisTriangle)

  return thisTriangle;


# ------------------------------------------------------------------------------
def problem_012():

  answerFound = False
  i = 1

  while answerFound != True:
    thisTriangle = triangle(i)
    divisors = countDivisors(thisTriangle)

    if (divisors > 500):
      print `i` + ": " + `thisTriangle` + " has " + `divisors` + " divisors."
      answerFound = True

    else:
      i += 1

# ------------------------------------------------------------------------------
# Execute standalone
problem_012()

