# 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?
#
# This can obviously be brute-forced, but that is suboptimal.
# Instead, recognize triangular numbers, due to being a sum of natural numbers up to n,
# are always of the form n(n+1)/2.
#
# This is much easier to factorize. Furthermore, if you write a number as a product
# of its x prime factors, in the form p_1^n_1 * p_2^n_2 * ... * (p_x)^(n_x), then
# the number of divisors equals exactly prod(n_i + 1), i from 1 to x, since every
# divisor must be some combination of the prime factors.
#
# 2^9 > 512, so not that many unique prime factors are necessary to exceed 500 total divisors.
# Nevertheless, sieve primes up to 100k, just to be safe.
#
# Optimization can be made by recognizing n and n+1 don't share any divisors except 1, and
# thus factoring them separately.
from Problem10 import optimized_sieve
MAX_N = 100000


def triangular_number_n(n):
    return n * (n + 1) // 2


def run():
    # log_file = open("logs/Problem12.txt", "w")
    sieve = list(optimized_sieve(MAX_N))
    # print("Sieve size is {0}".format(len(sieve)))
    for n in range(1, MAX_N):
        if n % 2 == 0:
            factor_1 = n // 2
            factor_2 = n + 1
        else:
            factor_1 = n
            factor_2 = (n + 1) // 2

        factor_count = 1
        # print("Factorizing Triangular number {0} = {1} = {2} * {3}"
        #     .format(n, factor_1 * factor_2, factor_1, factor_2))

        # for prime in sieve:
        #     exponent_count = 0
        #     while factor_1 % prime == 0:
        #         # print("Factorizing {0} by {1} = {2} * {1}".format(factor_1, prime, factor_1 // prime))
        #         exponent_count += 1
        #         factor_1 //= prime
        #     while factor_2 % prime == 0:
        #         # print("Factorizing {0} by {1} = {2} * {1}".format(factor_2, prime, factor_2 // prime))
        #         exponent_count += 1
        #         factor_2 //= prime
        #     if exponent_count > 0:
        #         factor_count *= (exponent_count + 1)
        #         # print("Factorized factors to {0} * {1} * {2}^{3}"
        #         #       .format(factor_1, factor_2, prime, exponent_count))
        #     if factor_1 == factor_2 == 1:
        #         # print("Factorization complete.")
        #         # print("Total divisor count for T_{0} = {1} is {2}"
        #         #       .format(n, triangular_number_n(n), factor_count), file=log_file)
        #         # input("Press Enter to continue...")
        #         break
        for prime in sieve:
            exponent_count = 1
            while factor_1 % prime == 0:
                exponent_count += 1
                factor_1 //= prime
            factor_count *= exponent_count
            if factor_1 == 1:
                break
            if prime * prime > factor_1:
                # Factor is now prime
                factor_count *= 2
                break
        for prime in sieve:
            exponent_count = 1
            while factor_2 % prime == 0:
                exponent_count += 1
                factor_2 //= prime
            factor_count *= exponent_count
            if factor_2 == 1:
                break
            if prime * prime > factor_2:
                # Factor is now prime
                factor_count *= 2
                break
        if factor_count > 500:
            print("Triangular number {0} = {1} has {2} factors".format(n, triangular_number_n(n), factor_count))
            break

# Sample Output:
# Triangular number 12375 = 76576500 has 576 factors
#
# Total running time for Problem12.py is 0.13857281408917604 seconds

# 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?
#
# This can obviously be brute-forced, but that is suboptimal.
# Instead, recognize triangular numbers, due to being a sum of natural numbers up to n,
# are always of the form n(n+1)/2.
#
# This is much easier to factorize. Furthermore, if you write a number as a product
# of its x prime factors, in the form p_1^n_1 * p_2^n_2 * ... * (p_x)^(n_x), then
# the number of divisors equals exactly prod(n_i + 1), i from 1 to x, since every
# divisor must be some combination of the prime factors.
#
# 2^9 > 512, so not that many unique prime factors are necessary to exceed 500 total divisors.
# Nevertheless, sieve primes up to 100k, just to be safe.
#
# Optimization can be made by recognizing n and n+1 don't share any divisors except 1, and
# thus factoring them separately.
from Problem10 import optimized_sieve
MAX_N = 100000


def triangular_number_n(n):
    return n * (n + 1) // 2


def run():
    # log_file = open("logs/Problem12.txt", "w")
    sieve = list(optimized_sieve(MAX_N))
    # print("Sieve size is {0}".format(len(sieve)))
    for n in range(1, MAX_N):
        if n % 2 == 0:
            factor_1 = n // 2
            factor_2 = n + 1
        else:
            factor_1 = n
            factor_2 = (n + 1) // 2

        factor_count = 1
        # print("Factorizing Triangular number {0} = {1} = {2} * {3}"
        #     .format(n, factor_1 * factor_2, factor_1, factor_2))

        # for prime in sieve:
        #     exponent_count = 0
        #     while factor_1 % prime == 0:
        #         # print("Factorizing {0} by {1} = {2} * {1}".format(factor_1, prime, factor_1 // prime))
        #         exponent_count += 1
        #         factor_1 //= prime
        #     while factor_2 % prime == 0:
        #         # print("Factorizing {0} by {1} = {2} * {1}".format(factor_2, prime, factor_2 // prime))
        #         exponent_count += 1
        #         factor_2 //= prime
        #     if exponent_count > 0:
        #         factor_count *= (exponent_count + 1)
        #         # print("Factorized factors to {0} * {1} * {2}^{3}"
        #         #       .format(factor_1, factor_2, prime, exponent_count))
        #     if factor_1 == factor_2 == 1:
        #         # print("Factorization complete.")
        #         # print("Total divisor count for T_{0} = {1} is {2}"
        #         #       .format(n, triangular_number_n(n), factor_count), file=log_file)
        #         # input("Press Enter to continue...")
        #         break
        for prime in sieve:
            exponent_count = 1
            while factor_1 % prime == 0:
                exponent_count += 1
                factor_1 //= prime
            factor_count *= exponent_count
            if factor_1 == 1:
                break
            if prime * prime > factor_1:
                # Factor is now prime
                factor_count *= 2
                break
        for prime in sieve:
            exponent_count = 1
            while factor_2 % prime == 0:
                exponent_count += 1
                factor_2 //= prime
            factor_count *= exponent_count
            if factor_2 == 1:
                break
            if prime * prime > factor_2:
                # Factor is now prime
                factor_count *= 2
                break
        if factor_count > 500:
            print("Triangular number {0} = {1} has {2} factors".format(n, triangular_number_n(n), factor_count))
            break

# Sample Output:
# Triangular number 12375 = 76576500 has 576 factors
#
# Total running time for Problem12.py is 0.13857281408917604 seconds

# 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? # # This can obviously be brute-forced, but that is suboptimal. # Instead, recognize triangular numbers, due to being a sum of natural numbers up to n, # are always of the form n(n+1)/2. # # This is much easier to factorize. Furthermore, if you write a number as a product # of its x prime factors, in the form p_1^n_1 * p_2^n_2 * ... * (p_x)^(n_x), then # the number of divisors equals exactly prod(n_i + 1), i from 1 to x, since every # divisor must be some combination of the prime factors. # # 2^9 > 512, so not that many unique prime factors are necessary to exceed 500 total divisors. # Nevertheless, sieve primes up to 100k, just to be safe. # # Optimization can be made by recognizing n and n+1 don't share any divisors except 1, and # thus factoring them separately. # log_file = open("logs/Problem12.txt", "w") # print("Sieve size is {0}".format(len(sieve))) # print("Factorizing Triangular number {0} = {1} = {2} * {3}" #     .format(n, factor_1 * factor_2, factor_1, factor_2)) # for prime in sieve: #     exponent_count = 0 #     while factor_1 % prime == 0: #         # print("Factorizing {0} by {1} = {2} * {1}".format(factor_1, prime, factor_1 // prime)) #         exponent_count += 1 #         factor_1 //= prime #     while factor_2 % prime == 0: #         # print("Factorizing {0} by {1} = {2} * {1}".format(factor_2, prime, factor_2 // prime)) #         exponent_count += 1 #         factor_2 //= prime #     if exponent_count > 0: #         factor_count *= (exponent_count + 1) #         # print("Factorized factors to {0} * {1} * {2}^{3}" #         #       .format(factor_1, factor_2, prime, exponent_count)) #     if factor_1 == factor_2 == 1: #         # print("Factorization complete.") #         # print("Total divisor count for T_{0} = {1} is {2}" #         #       .format(n, triangular_number_n(n), factor_count), file=log_file) #         # input("Press Enter to continue...") #         break # Factor is now prime # Factor is now prime # Sample Output: # Triangular number 12375 = 76576500 has 576 factors # # Total running time for Problem12.py is 0.13857281408917604 seconds