princeofsudan

Project Euler#12 Highly divisible triangular number

Mar 3rd, 2013
183
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.27 KB | None | 0 0
  1. #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:
  2.  
  3. #1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
  4.  
  5. #Let us list the factors of the first seven triangle numbers:
  6.  
  7. #     1: 1
  8. #     3: 1,3
  9. #     6: 1,2,3,6
  10. #    10: 1,2,5,10
  11. #    15: 1,3,5,15
  12. #    21: 1,3,7,21
  13. #    28: 1,2,4,7,14,28
  14.  
  15. #We can see that 28 is the first triangle number to have over five divisors.
  16.  
  17. #What is the value of the first triangle number to have over five hundred divisors?
  18.  
  19. #An integer x is triangular if and only if 8x + 1 is a square.
  20. #Source: http://en.wikipedia.org/wiki/Triangular_number
  21. #Section: Triangular roots and tests for triangular numbers
  22.  
  23. def isPerfectSquare(n):
  24.     if n < 0:
  25.         return False
  26.     result = int(n**0.5)
  27.     return result*result == n
  28.      
  29. def isTriangle(n):
  30.     return isPerfectSquare((8*n)+1)
  31.      
  32. def divisors(n):
  33.     acc = 0
  34.     for i in range(1,int(n**0.5)+1):
  35.         if n % i == 0:
  36.             acc += 1
  37.     return acc * 2
  38.      
  39.      
  40. i = 1
  41.      
  42. while True:
  43.        
  44.     if isTriangle(i):
  45.         divisorsCount = divisors(i)
  46.         if divisorsCount > 500:
  47.             print i, divisorsCount
  48.             break
  49.     i += 1
Advertisement
Add Comment
Please, Sign In to add comment