A little over a year ago I started working on Project Euler problems. Used them as a handy way of learning Python. About that time I ran into a problem that stumped me completely. Problem 12 wanted to know the first triangle number with more than 500 divisors.
A triangle number of order (n) is defined as the sum of the arithmetic sequence from 1 to n, so triangle(3)=1+2+3=6 and triangle(7)=1+2+3+4+5+6+7=28. Calculating a triangle number is trivial. Figuring out how many divisors it has is a bit more challenging. I was trying various things that first time with caching the number of divisors for various numbers as you go up so that you don't have to calculate it again. Honestly, I don't really remember exactly what I did, but I remember that it was big and it took far more than the 1 minute maximum that any Project Euler problem should take. It took so long that I didn't even have the patience to let it run until it found a solution.
I skipped the problem then and let it sit undone for a long time. Until today. I fired up my trusty editor and busted out a solution. And it worked. And I'm thrilled. Not least because the code I came up with for finding the divisor takes all of 4 lines and only breaks the 1 second execution time mark at around n=1e+13 . Here's the code:
def divisors(n): total = 2 for i in xrange(2, int(math.sqrt(n)) + 1): total += 2 if n % i == 0 else 0 if math.sqrt(n) == math.floor(math.sqrt(n)): total -= 1 return total
This works for n greater than 1.