triangle numbers in python

Question

I'm trying to solve the problem:

What is the value of the first triangle number to have over five hundred divisors?

A triangle number is a number in the sequence of the sum of numbers i.e. 1+2+3+4+5...

I'm pretty sure that this is working code but I don't know because my computer is taking too long to calculate it. Does anybody have any idea of how to make the program a little faster.
Thanks.

import math

def main():
    l = []
    one = 0
    a = 1
    b = 2
    while one == 0:
        a = a + b 
        b += 1
        for x in range(1, int(a/2 + 1)):
            if a % x == 0:
                l.append(x)
                if len(l) > 499:
                    print a 

if __name__ == '__main__':
    main()

Answer 1

Hints:

• what is the formula for n-th triangular number?
• n and n+1 have no common factors (except 1). Question: given number of factors in n and n+1 how to calculate number of factors in n*(n+1)? What about n/2 and (n+1) (or n and (n+1)/2)?
• if you know all prime factors of n how to calculate number of divisors of n?

If you don't want to change your algorithm then you can make it faster by:

• replace l.append by factor_count += 1
• enumerate to int(a**.5) instead of a/2 (use factor_count += 2 in this case).

Answer 2

You'll have to think more and use less brute force to solve Project Euler questions.

In this case you should investigate which and how many divisors triangle numbers have. Start at the beginning, look for patterns, try to understand the problem.

Answer 3

You're not updating the value of one, so your program will never end.

Answer 4

Just for sanity's sake, you should use

while True:

and get rid of one.

Answer 5

First of all, the people telling you that you can't solve this problem with brute force in under a minute are wrong. A brute force algorithm for a problem this size will run in a few seconds.

Second, the code that you posted has several problems, some of them already mentioned.

• You should terminate the loop by setting one to some value other than 0 once you reach your goal condition (where you currently print a).
• You never reinitialize the list (l = []). This should be done each time you recalculate a and b, right before you enter the for loop.
• The question asks for the first triangle number to have over five hundred divisors. Your condition for termination should be if len(l) > 500:.
• Your probably don't want to print a inside the for loop, but wait until the while loop is done.

The thing that's really slowing you down is that for each triangle number a you're checking every value up to a / 2 to see if it's a divisor. Your only need to check values up to the square root of a. This way for each value of x, if x is a divisor you can just add x and a / x to the list.

Here's your code with the modifications I outlined above:

import math

def main():
    l = []
    one = 0
    a = 1
    b = 2
    while one == 0:
        a = a + b 
        b += 1
        l = []

        sqrt_a = int(math.sqrt(a))

        for x in range(1, sqrt_a + 1):
            if a % x == 0:
                l.append(x)
                if x < math.sqrt(a):
                    l.append(a // x)
                if len(l) > 500:
                    # print(a)
                    one = 1

    print(a, b, len(l))

if __name__ == '__main__':
    main()

You'll see that it runs in about 5 or 6 seconds, so well under a minute with these modifications.

Answer 6

Your current brute force algorithm is too inefficient to solve this problem in the Project Euler time limit of 1 minute. Instead, I suggest looking at the Divisor Function:

http://www.artofproblemsolving.com/Wiki/index.php/Divisor_function