3
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Also, all those casts to int are unnecessary. Just use the floor division operator // \$\endgroup\$ – Tamoghna Chowdhury Aug 19 '17 at 5:13
  • \$\begingroup\$ Take a look here for some ideas \$\endgroup\$ – Tamoghna Chowdhury Aug 19 '17 at 5:29
2
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ The problem is not about just factorization. It is about factorization of triangular numbers. Your factorization advice, while valid, misses the point of the exercise entirely. See this shameless plug about multiplicativity of \$\sigma\$. PS: ProjectEuler is not about programming. \$\endgroup\$ – vnp Aug 19 '17 at 7:23
  • \$\begingroup\$ @vnp Didn't notice that - perhaps you'd like to put in your own answer. Upvoted it there too. I'll link that thread into my answer - you and Martin have already discussed it really well and I don't feel I could do it more justice. I'm sorry that I've never done or even seen anything related to Project Euler outside of CRSE, and did not notice the mathematical bias in its problems. As it stands, my code is still valid advice, so I'll keep it. \$\endgroup\$ – Tamoghna Chowdhury Aug 19 '17 at 10:19
  • \$\begingroup\$ Thanks a lot for the detailed answer! Now with the improvements, I got the execution time down to 9 seconds. The system that took 10 hours was a 6 core AMD processor (don't remember which), Windows 10 Home x64, and 8 GB of ram. The system that I got i down to 9 seconds is a mid 2012 MacBook Pro with a quad core i7 and 16 GB of ram \$\endgroup\$ – Ryan Aug 19 '17 at 15:37
  • \$\begingroup\$ @Ryan, What version on Python was installed on these systems? I've heard that CPython 3.6 has a lot of optimizations for such things (my code still runs 3 orders of magnitude faster on my system than yours, and I'm not prepared to admit my system is better than yours although my processor is a bit newer). Could you try to run the code on the AMD system with a more recent Python version and let me know? If I had to hazard a guess, it would be that your processor was an FX series, maybe an 8350. \$\endgroup\$ – Tamoghna Chowdhury Aug 19 '17 at 20:17
  • \$\begingroup\$ I don't remember the exact Python version, I will next be at my desktop tomorrow. I will try upgrading to 3.6 if I am not on it. Also, the processor is the AMD Phenom II X6 1045T. \$\endgroup\$ – Ryan Aug 21 '17 at 1:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.