Project Euler Problem 12 in Python 3 (Find triangle number with 500 divisors)

Question

I am doing Project Euler, and 12 is the one that takes significantly longer then everything else.

Here is my code:

# 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:
#
# Omitted
#
# 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?

import time

start = time.time()

def count_factors(num):
    # One and itself are included now
    count = 2
    for i in range(2, num):
        if num % i == 0:
            count += 1
    return count


def tri_nums(num):
    return int(num * (num + 1) / 2)

x = 500

while True:
    if count_factors(tri_nums(int(x))) > 500:
        break
    x += 1

print('The answer is', tri_nums(x))

print('Answer found in', time.time() - start, 'seconds')

# The answer is 76576500
# Answer found in 36164.39957642555 seconds

The first time that I ran this code it took over 10 hours. I can't really think of any ways to make this faster, but I am sure that there are.

Also, is count_factors() faster than:

def factors(num):
for i in range(1, num):
    if num % i == 0:
        yield i

Answer 1

As @vnp notes in the comments, the fact that triangular numbers are products of coprime numbers allow for very efficient factorization - see this thread for an illustration of the idea in Java, easily carryable over to Python - which I'll illustrate in my code too.

The idea here is that since the \$n\$^th triangular number is the product of 2 numbers \$n\$ and \$\displaystyle\lfloor\frac{n+1}{2}\rfloor\$, which implies that if \$n\$ is even then \$\displaystyle\frac{n}{2}\$ and \$n+1\$ are 2 relatively prime integers, whereas if \$n\$ is odd then \$\displaystyle\frac{n+1}{2}\$ and \$n\$ are 2 relatively prime integers. This makes factorizing the resultant \$n\$^th triangular number take less time as now a divide-and-conquer approach can be employed, making this part of the algorithm \$\mathrm{O}(\log_2n)\$ in time.

As I previously posted in my comment to the question, this StackOverflow thread is a good reference for efficient factorization, especially the first answer there.

The idea is that there can be no prime factors of a number greater than its square root, and factors are paired in the sense that each factor \$i\$ of a number \$\text{num}\$ has a complementary factor \$\displaystyle\frac{\text{num}}{i}\$. Thus we can use a sublinear time algorithm to factorize integers, which involves enumerating to only \$\lceil\sqrt{\text{num}}\ \ \rceil\ (\mathrm{O}(\text{num}^{\frac{1}{2}}))\$ instead of \$\text{num} - c\ (\mathrm{O}(\text{num}))\$, where \$c\$ is some constant factor.

That gives us the major time savings.

You adhere to the Python style guide, PEP8, quite well, so I have no stylistic comments for you, except for the fact that tri_nums could be a bit more descriptive, e.g., triangular_numbers (you're using an editor with autocomplete support, aren't you?)

Side notes:

1. The while loop searching for the required number can and should be extracted into a function, which receives the initial value of x as a parameter, instead of hard-coding it to 500.

2. The timing and actual execution should be moved into a main() function, which is called using the standard script idiom of if __name__ == "__main__".

3. The floor (or integer) division operator // makes all those casts to int redundant.

4. Use a proper benchmarking toolkit for timing execution, with recommended best practices, e.g. timeit.

5. Last but the most important - the while True: ... if <condition>: break ... idiom is frowned upon in the community, when an equivalent while not <condition>: ... can be used without control flow redirection. It makes reasoning about the code more linear.

Finally, here is the code (only minimally changed from your original to incorporate my suggestions):

# 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:
#
# Omitted
#
# 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?

import time
import math


def count_factors(num):
    # One and itself are included now
    count = 2
    for i in range(2, int(math.sqrt(num)) + 1):
        if num % i == 0:
            count += 2
    return count


def triangle_number(num):
    return (num * (num + 1) // 2)


def divisors_of_triangle_number(num):
    if num % 2 == 0:
        return count_factors(num // 2) * count_factors(num + 1)
    else:
        return count_factors((num + 1) // 2) * count_factors(num)


def factors_greater_than_triangular_number(n):
    x = n
    while divisors_of_triangle_number(x) <= n:
        x += 1
    return triangle_number(x)


def main():
    start = time.time()
    print('The answer is', factors_greater_than_triangular_number(500))
    print('Answer found in', time.time() - start, 'seconds')

if __name__ == '__main__':
    main()

This runs in about 0.01 seconds on my system (CPython 3.6.0 Windows x64, Windows 10 Pro 1703, Intel™ Core i7 6500U (Dual Core), 8GB RAM).

I cannot believe that on your system it really took over 10 hours to run - do comment with details of your system like I did above and let me know how much better this version does!