• API
• FAQ
• Tools
• Archive
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.

Top