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

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

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!

Attribution
Source : Link , Question Author : Ryan , Answer Author : Tamoghna Chowdhury