Triangle-numbers with lots of divisors (Project-Euler Problem 12)

Question

The following is my python solution of project euler 12.

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:

 1: 1 
 3: 1,3 
 6: 1,2,3,6 
10: 1,2,5,10 
15: 1,3,5,15 
21: 1,3,7,21 
28: 1,2,4,7,14,28 

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?

It works fine and runs in half second. I fixed a random upper limit for the search of primes (using the sieve of eratosthenes).

def SE(n): #Sieve of Eratosthenes
 sieve = range(3, n, 2)
 top = len(sieve)
 for si in sieve:
 if si:
 bottom = (si*si - 3)/2
 if bottom >= top:
 break
 sieve[bottom::si] = [0] * -((bottom-top)//si) 
 return [2] + filter(None, sieve)
primes = SE(13000) #Here's the problem
def nod(n): #function that returns the number of divisors
 nd = 1
 for i in primes:
 if i <= n:
 t = 1
 while n % i == 0:
 n /= i
 t += 1
 nd *= t
 else:
 return nd
c = 0
i = 1
d = 1
d1 = 0
while c < 500: #loop for checking each triangle number
 if i % 2 == 0:
 d = nod(i+1)
 else:
 d1 = nod((i+1)/2)
 c = d * d1
 i += 1
print i*(i-1)/2

Answer 1

I'm going to focus on the coding style of your question, as there something to be said on that regard. On the subject of improving or alternate solution on how to do the Project Euler #12, see result of search here on Code Review for euler 12 [python].

• Use better names for functions! – If you change your function names to sieve_of_eratoshenes and number_of_divisors you can remove the comments , and instead add proper docstrings explaining more on what the functions does or returns.
• Use better names for variables – What are the c, d, d1 ́, andi` variables? They don't convey their meaning, which they really should.

• Avoid top level code inbetween functions – Between your functions you suddenly do primes = SE(13000), and then proceed to use this a global within nod(). Both are code smells. You should gather all of your top level code into a main(), pass the primes as a parameter and call main() like in the following:

  import itertools
  MAX_FACTOR = 13000
  MAX_NUMBER = MAX_FACTOR ** 2
  def main():
   primes = sieve_of_erasthones(MAX_FACTOR)
   divisor_count = 0
   for i in itertools.count(1):
   if i > MAX_NUMBER:
   raise ValueError("Will fail as we don't have enough primes!")
   if i % 2 == 0:
   even_divisor_count = number_of_divisors(i+1)
   else:
   odd_divisor_count = number_of_divisors((i+1)//2)
   divisor_count = even_divisor_count * odd_divisor_count
   if divisor_count >= 500:
   break
   print(i*(i-1)/2)
  if __name__ == '__main__':
   main()
  

  Do note that this code is untested, and I'm mostly unsure on what the i is and whether i > MAX_NUMBER is the correct test

• Possibly add an extension of primes table – Like suggested with i > MAX_NUMBER you should add some sort of test to handle the situation when you run out of primes, and possibly build a method to extend the primes further. This could be done tracking current high, and reiterate over primes already found extending beyond the current high to the double of previous high or similar

• Loop on the loop counter – As seen in the code above, I've changed your loop into looping on the i instead of resorting to manually updating the i within the while loop. To still maintain the same functionality, I've added the break statemen as a termination clause on the loop instead.

• BUG: Your nod() function will return None if n > max(primes) – Given that the highest number of primes is less than n your code will terminate the loop and return None.

• Is it correct to do nd *= t? – I haven't tested, and neither fully grasped your nod() function, but shouldn't it add t to the total number of divisors, and not multiply it?

So to summarize, I think you need to work a little on naming your variables and functions, and add a check for when you code will fail to prevent it producing false and erroneous results. And possibly add a method to extend the primes list if going beyond already calculated primes.

• Pigna: Wow, thanks for the detailed answewr @holroy! I'll do as you say. Is the loop on the loop counter more efficient? As for the bug: that's why I was searching a way of automatically determining the sieve limit :) Yeah, 'nd *= t' is correct: the total number of proper divisors of a number is equal to the product of the exponents (each one increased by one) of the prime factors of that number
• holroy: @Pigna The loop efficiency is the same, it just make more sense, to me at least, to have it like I suggest