Project Euler #12 in python

Question

Hi, I'm trying to solve Euler problem #12 which is '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

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

Answer 2

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 3

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 4

Just for sanity's sake, you should use

while True:

and get rid of one.

Answer 5

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