We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #12: Highly divisible triangular number
  4. Discussions

Project Euler #12: Highly divisible triangular number

  • valogonor
     + 0 comments

    Here's an efficient solution in Python that takes advantage of the fact that the formula for the nth triangular number is n * (n+1) // 2 and the fact that n and n + 1 are coprime:

    def count_factors(num):
    ans = 0
    for i in range(1, int(num**.5) + 1):
        if num % i == 0:
            ans += 1 if i * i == num else 2
    return ans
    
def solve(mindivs):
    n = 1
    while True:
        trinum = n * (n + 1) // 2
        if n % 2 == 0:
            divcount = count_factors(n // 2) * count_factors(n + 1)
        else:
            divcount = count_factors((n+1)//2) * count_factors(n)
        if divcount > mindivs:
            return trinum
        n += 1

t = int(input())
for _ in range(t):
    n = int(input())
    print(solve(n))