Real Ultimate Programming

The Home for People Who Like to Flip Out and Write Code

Project Euler: Problem 12

Problem 12 brings back an interesting mathematical concept: triangular numbers. Triangular numbers (and the formula for finding one) are the slightly more sophisticated approach I mentioned in my writeup for Problem 6. Writing a generator for triangular numbers is easy enough, as is writing some logic to factorize (not prime factorize) a number. Given those two, the solution is easy enough.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

    """Solves Problem 12 of Project Euler."""

    import math

    def factors(to_factor):
        """Find the factors of to_factor."""
        factors = []
        divisor = 1
        while (divisor <= int(math.sqrt(to_factor))):
            if not to_factor % divisor:
                quotient = to_factor / divisor
                factors.append(divisor)
                factors.append(quotient)
            divisor += 1

        return factors

    def triangular_numbers():
        """Generate the triangular numbers."""
        current = 0
        position = 1
        while True:
            current += position
            position += 1
            yield current

    def problem_12(min_divisors):
        """Finds the first triangular number to have more than 500 divisors."""
        for triangular in triangular_numbers():
            cur_factors = factors(triangular)
            if len(cur_factors) > min_divisors:
                return triangular

    if __name__ == '__main__':
        print problem_12(500)

Back to flipping out…