Python Implementation of Problem 12

View source code here on GitHub!

Includes

Problem Solution

Project Euler Problem 12

Still having trouble with prime_factors, but I don't know how to make it faster yet

Problem:

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:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

 1: 1
 3: 1,3
 6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

python.src.p0012.main() → int
 1"""
 2Project Euler Problem 12
 3
 4Still having trouble with prime_factors, but I don't know how to make it faster
 5yet
 6
 7Problem:
 8
 9The sequence of triangle numbers is generated by adding the natural numbers. So
10the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten
11terms would be:
12
131, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
14
15Let us list the factors of the first seven triangle numbers:
16
17.. code-block::
18
19     1: 1
20     3: 1,3
21     6: 1,2,3,6
22    10: 1,2,5,10
23    15: 1,3,5,15
24    21: 1,3,7,21
25    28: 1,2,4,7,14,28
26
27We can see that 28 is the first triangle number to have over five divisors.
28
29What is the value of the first triangle number to have over five hundred
30divisors?
31"""
32from itertools import count
33
34from .lib.factors import proper_divisors
35
36
37def main() -> int:
38    num = 0
39    for x in count(1):
40        num += x
41        if sum(1 for _ in proper_divisors(num)) > 500:
42            return num
43    return -1  # pragma: no cover

Tags: divisor-count, factorization, python-iterator