SHARE
TWEET

Xavier Ho

a guest Jul 5th, 2009 103 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. # This one only took 8 seconds on my machine. Wow?
  2.  
  3. """The sequence of triangle numbers is generated by adding the natural numbers. So the 7^(th) triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:
  4.  
  5. 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
  6.  
  7. Let us list the factors of the first seven triangle numbers:
  8.  
  9.     1: 1
  10.     3: 1,3
  11.     6: 1,2,3,6
  12.    10: 1,2,5,10
  13.    15: 1,3,5,15
  14.    21: 1,3,7,21
  15.    28: 1,2,4,7,14,28
  16.  
  17. We can see that 28 is the first triangle number to have over five divisors.
  18.  
  19. What is the value of the first triangle number to have over five hundred divisors?"""
  20.  
  21. from operator import mul
  22.  
  23. def factorise(num):
  24.     """Returns a list of prime factors. For example:
  25.        factorise(6) will return
  26.        [0, 0, 1, 1, 0, 0]
  27.        as in, 2^1 * 3^1 = 6."""
  28.     powers = [0, 0]
  29.     factor = 2
  30.     while num > 1:
  31.         if num % factor == 0:
  32.             powers[factor-1] += 1
  33.             num /= factor
  34.         else:
  35.             powers.append(0)
  36.             factor += 1
  37.     return powers
  38.    
  39. def countDivisors(powers):
  40.     """Takes a factorised form and returns the number of possible divisors.
  41.        For example: 24 = 2^3 * 3^1
  42.        There are (3 + 1)*(1 + 1) possible divisors, or 8.
  43.        24 has divisors of 1, 2, 3, 4, 6, 8, 12, 24 - 8 of them."""
  44.     return reduce(mul, [(x+1) for x in powers if x != 0])
  45.  
  46. # MAIN
  47. n = 2
  48. tri = 1
  49. while True:
  50.     tri += n
  51.     count = countDivisors(factorise(tri))
  52.     if count > 500:
  53.         print tri, count
  54.         break
  55.     n += 1
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top