Skip to content

# publiccoleifer/project-euler

### Subversion checkout URL

You can clone with HTTPS or Subversion.

Newer
Older
100644 89 lines (71 sloc) 2.773 kb
 ``` fed19bb3 » coleifer ``` 2010-01-17 Solved problem 61 1 import math 2 3 def triangle(n): 4 return ((n * n) + n) / 2 5 6 def is_triangle(n): 7 return (-1 + math.sqrt(1 + (8 * n))) % 2 == 0 8 9 def square(n): 10 return n*n 11 12 def is_square(n): 13 return int(math.sqrt(n)) == math.sqrt(n) 14 15 def pentagonal(n): 16 return (n * ((3 * n) - 1)) / 2 17 18 def is_pentagonal(n): 19 return (1 + math.sqrt(1 + (24 * n))) % 6 == 0 20 21 def hexagonal(n): 22 return (2*n*n - n) 23 24 def is_hexagonal(n): 25 return (1 + math.sqrt(1 + (8 * n))) % 4 == 0 26 27 def heptagonal(n): 28 return (n * (5 * n - 3)) / 2 29 30 def is_heptagonal(n): 31 return (3 + math.sqrt(9 + (40 * n))) % 10 == 0 32 33 def octagonal(n): 34 return (n * (3 * n - 2)) 35 36 def is_octagonal(n): 37 return (2 + math.sqrt(4 + (12 * n))) % 6 == 0 38 39 nums = [] 40 41 # build a list of all numbers that pass one of the tests 42 for i in xrange(1000, 10000): 43 if is_triangle(i) or \ 44 is_square(i) or \ 45 is_pentagonal(i) or \ 46 is_hexagonal(i) or \ 47 is_heptagonal(i) or \ 48 is_octagonal(i): 49 nums.append(i) 50 51 # a list of tests our numbers need to pass 52 tests_available = [is_triangle, is_square, is_pentagonal, is_hexagonal, 53 is_heptagonal, is_octagonal] 54 55 def test_nums(all_nums, matches, tests_remaining): 56 if len(matches) > 0: 57 # if we've got a matching number already, filter down the numbers we 58 # iterate over to ones whose first two digits will be the last two of 59 # the previous number 60 min_match = int(str(matches[-1])[2:]) * 100 61 max_match = min_match + 100 62 else: 63 min_match = max_match = None 64 # if a matches last two started with a zero, bail out 65 if len(matches) and not min_match > 1000: return 66 67 # iterate over all numbers 68 for num in all_nums: 69 # if we have a match condition and number is in range, or if this is the 70 # first go-round 71 if (min_match and num > min_match and num < max_match) or not min_match: 72 for i, test in enumerate(tests_remaining): 73 if test(num): 74 # if we're down to our last test and the number we're 75 # looking at completes the sequence, print them out! 76 if len(tests_remaining) == 1 and \ 77 int(str(num)[2:]) == int(str(matches[0])[:2]): 78 print matches + [num] 79 print sum(matches + [num]) 80 return 81 else: 82 # call it recursively 83 test_nums(all_nums, matches + [num], 84 tests_remaining[:i] + tests_remaining[i+1:]) 85 elif (min_match and num > max_match): 86 # we can safely get out of here now 87 return 88 test_nums(nums, [], tests_available)
Something went wrong with that request. Please try again.