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

28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

"""
triangle_numbers = {}
max_divisor = {}


def triangle_number(n):
  tNum = int(n*(n+1)/2)
  divisors = calculate_divisors(tNum,False)
  print("Calculating divisors for (num): "+str(n)+" (tNum):"+str(tNum))
  #print("divisors of "+str(tNum)+" = "+str(divisors))
  return {"divisors":divisors,"num_divisors":len(divisors),"triangle_number":tNum}
  
def array_unique(arr1,arr2):
  new_list = []
  a = 0
  b = 0
  
  # merge two lists
  while a < len(arr1) and b < len(arr2):
    if arr1[a] < arr2[b]:
      new_list.append(arr1[a])
      a += 1
    elif arr1[a] == arr2[b]:
      new_list.append(arr1[a])
      a += 1
      b += 1
    else:
      new_list.append(arr2[b])
      b += 1
  
  while a < len(arr1):
    new_list.append(arr1[a])
    a += 1
  
  while b < len(arr2):
    new_list.append(arr2[b])
    b += 1
  
  return new_list

# grab the number of divisors
def calculate_divisors(num,use_cache):
  global max_divisor
  global triangle_numbers
  divisors = []
  start = 1
  
  # how to speed this up?
  # maybe see if num is divisible by another triangular number
  # grab the divisors for that triangle number, and start the range from
  # that triangle number onwards
  # no reason to recalculate the divisors again, if we have a suitable starting
  # point in memory
  
  # see what triangle numbers are already in the puzzle and have divisors
  
  # Idea doesn't work
  #if use_cache:
  #  for item in triangle_numbers:
  #    if num % item == 0:
  #      print(str(num) + " is divisible by "+str(item))
        #print(item)
        #print(triangle_numbers[item])
  #      if len(divisors) > 0:
  #        divisors = array_unique(divisors,triangle_numbers[item])
  #      else:
  #        divisors = triangle_numbers[item]
  
  #print(divisors)
  
  # where to start?
  if len(divisors) > 0:
    start = divisors[-1:][0]
  
  for i in range(start,num+1):
    if int(num) % int(i) == 0:
      #print(i)
      divisors.append(i)
  
  triangle_numbers[num] = divisors
  
  if len(max_divisor) == 0:
    max_divisor['num'] = len(divisors)
    max_divisor['triangle_number'] = num
    max_divisor['divisors'] = divisors
  elif max_divisor['num'] < len(divisors):
    max_divisor['num'] = len(divisors)
    max_divisor['triangle_number'] = num
    max_divisor['divisors'] = divisors
  #print(max_divisor)
  
  #print(divisors)
  
  return divisors

#for i in range(1,5000):
#  triangle_number(i)

#print(max_divisor)