Return to Answer

 >>> timeit(lambda:problem75(10**5),number=1)
 12 (3, 4, 5)
 24 (6, 8, 10)
 30 (5, 12, 13)
 [... much output deleted ...]
 33.87288845295552

from collections import Counter
from itertools import count
def gcd(m, n):
 """Return the greatest common divisor of m and n."""
 while n != 0:
 m, n = n, m % n
  return m
def coprime(m, n):
 """Return True iff m and n are coprime."""
 return gcd(m, n) == 1
def all_primitive_triples():
 """Generate all primitive Pythagorean triples, together with a lower
 bound on the perimeter for which all triples have been generated
 so far.
 """
 for m in count(1):
 for n in range(1, m):
 if (m + n) % 2 and coprime(m, n):
 a = m * m - n * n
 b = 2 * m * n
 yield a, b, m * m + n * n, 2 * m * (m + 1)
def problem75(limit):
 """Return the number of values of L <= limit such that there is
 exactly one integer-sided right-angled triangle with perimeter
 L.
 """
 triangles = Counter()
 for a, b, c, q in all_primitive_triples():
 if q > limit:
 break
 p = a + b + c
 for i in range(p, limit + 1, p):
 triangles[i] += 1
 return sum(n == 1 for n in triangles.values())

>>> timeit(lambda:problem75(1500000), number=1)
2.164217948913574

 >>> from timeit import timeit
 >>> timeit(lambda:problem75(10**5),number=1)
 12 (3, 4, 5)
 24 (6, 8, 10)
 30 (5, 12, 13)
 [... much output deleted ...]
 33.87288845295552

from collections import Counter
from fractions import gcd
from itertools import count
def coprime(m, n):
 """Return True iff m and n are coprime."""
 return gcd(m, n) == 1
def all_primitive_triples():
 """Generate all primitive Pythagorean triples, together with a lower
 bound on the perimeter for which all triples have been generated
 so far.
 """
 for m in count(1):
 for n in range(1, m):
 if (m + n) % 2 and coprime(m, n):
 a = m * m - n * n
 b = 2 * m * n
 yield a, b, m * m + n * n, 2 * m * (m + 1)
def problem75(limit=1500000):
 """Return the number of values of L <= limit such that there is
 exactly one integer-sided right-angled triangle with perimeter
 L.
 """
 triangles = Counter()
 for a, b, c, q in all_primitive_triples():
 if q > limit:
 break
 p = a + b + c
 for i in range(p, limit + 1, p):
 triangles[i] += 1
 return sum(n == 1 for n in triangles.values())

>>> timeit(problem75, number=1)
2.164217948913574

In particular, when you want to speed up a program, it's counterproductive to say, "I don't want to implement a different algorithm, I just want to speed up the code I wrote". The biggest speedups come from finding better algorithms. (And that's especially so in this case.)

1. The print statement near the end of the main loop is unnecessary. (Saves about 3 seconds, bringing the time down to 31.0 seconds.)

2. Your function aFactors makes an initial call to isPrime, taking O(√n), in order to avoid a loop that also takes O(√n). The test costs as much as it saves, so it's not worth it. Remove the call to isPrime and rewrite the function like like this:

    def factors(n):
    """Return the set of factors of n."""
    result = set([1, n])
    add = result.add
    for i in range(2, int(math.sqrt(n)) + 1):
    if n % i == 0:
    add(i)
    add(n // i)
    return result
   

Note the improved name for the function, and the docstring explaining what it does. (Saves about 4 seconds; time now 27.7 seconds.)

This avoids having to construct an intermediate list in memory. (Saves about 3 seconds; time now 24.3 s.)

This avoids the lookups. (Saves about 3 seconds; time now 21.2 seconds.)

1. You construct a list of triangles, some of which have sides with negative or zero length. You then go through the list and del the triangles which are invalid. But del on a list is a potentially expensive operation: it has to copy the remainder of the list to keep it contiguous. (See the TimeComplexity page on the Python wiki for the cost of basic operations on Python's built-in data structures, where you can see that "delete item" operation on a list takes O(n).)

(Saves about 6 seconds; time now 15.1 seconds.)

(Saves about 1 second; time now 13.9 seconds.)

We can further speed things up by only generating the primitive Pythagorean triples, and then multiplying the primitive triples by successive numbers 1, 2, 3, ... to generate the remaining Pythagorean triples in the required range. (In fact, we only need to multiply their perimeters.)

Euclid’s formula can be used to generate all primitive Pythagorean triples. Given coprime positive integers m and n, with m > n, and exactly one of m and n even,

a = m² − n², b = 2mn, c = m² + n²

is a primitive Pythagorean triple.

The remaining subtlety is that Euclid’s formula doesn’t generate triples in order by length of the perimeter, so there needs to be some way to determine when to stop. My strategy in the code below is to iterate over ascending values of m. The perimeter of the triple is 2m² + 2mn, which is at least 2m(m + 1), since n ≥ 1. So 2m(m + 1) is a lower bound on the perimeter for which all triples have been generated so far. When this exceeds the limit, we can stop the search: there are no more triples to be found in the required range.

In particular, when you want to speed up a program, it's counterproductive to say, "I don't want to implement a different algorithm, I just want to speed up the code I wrote". The biggest speedups come from finding better algorithms.

1. The print statement near the end of the main loop is unnecessary. This saves about 3 seconds, bringing the time down to 31.0 seconds.

2. Your function aFactors makes an initial call to isPrime, taking \$ O(\sqrt n) \$, in order to avoid a loop that also takes \$ O(\sqrt n) \$. The test costs as much as it saves, so it's not worth it. Remove the call to isPrime and rewrite the function like like this:

    def factors(n):
    """Return the set of factors of n."""
    result = set([1, n])
    add = result.add
    for i in range(2, int(math.sqrt(n)) + 1):
    if n % i == 0:
    add(i)
    add(n // i)
    return result
   

Here I've picked a better name for the function, written a docstring explaining what it does, and cached the value of result.add so that it does not need to be looked up each time arounnd the loop. This saves about 4 seconds; time now 27.7 seconds.

This avoids having to construct an intermediate list in memory. This saves about 3 seconds; time now 24.3 seconds.

This avoids the sequence lookups. This saves about 3 seconds; time now 21.2 seconds.

1. You construct a list of triangles, some of which have sides with negative or zero length. You then go through the list and del the triangles which are invalid. But del on a list is a potentially expensive operation: it has to copy the remainder of the list to keep it contiguous. See the TimeComplexity page on the Python wiki for the cost of basic operations on Python's built-in data structures, where you can see that "delete item" operation on a list takes \$O(n)\$.

This saves about 6 seconds; time now 15.1 seconds.

This saves about 1 second; time now 13.9 seconds.

We can further speed things up by only generating the primitive Pythagorean triples, and then multiplying the primitive triples by successive numbers 1, 2, 3, ... to generate the remaining Pythagorean triples in the required range. In fact, we only need to multiply their perimeters.

Euclid’s formula can be used to generate all primitive Pythagorean triples. Given coprime positive integers \$m\$ and \$n\$, with \$m > n\$, and exactly one of \$m\$ and \$n\$ even,$$ \eqalign{ a &= m^2 − n^2 \\ b &= 2mn \\ c &= m^2 + n^2} $$ is a primitive Pythagorean triple.

The remaining subtlety is that Euclid’s formula doesn’t generate triples in order by length of the perimeter, so there needs to be some way to determine when to stop. My strategy in the code below is to iterate over ascending values of \$m\$. The perimeter of the triple is \$a + b + c = 2m^2 + 2mn\$, which is at least \2ドルm(m + 1)\$, since \$n ≥ 1\$. So \2ドルm(m + 1)\$ is a lower bound on the perimeter for which all triples have been generated so far. When this exceeds the limit, we can stop the search: there are no more triples to be found in the required range.

from collections import Counter
from itertools import count
def gcd(m, n):
 """Return the greatest common divisor of m and n."""
 while n != 0:
 m, n = n, m % n
 return m
def coprime(m, n):
 """Return True iff m and n are coprime."""
 return gcd(m, n) == 1
def all_primitive_triples():
 """Generate all primitive Pythagorean triples, together with a lower
 bound on the perimeter for which all triples have been generated
 so far.
 """
 for m in count(1):
 for n in range(1, m):
 if (m + n) % 2 and coprime(m, n):
 a = m * m - n * n
 b = 2 * m * n
 yield a, b, m * m + n * n, 2 * m * (m - 1)
def problem75(limit):
 """Return the number of values of L <= limit such that there is
 exactly one integer-sided right-angled triangle with perimeter
 L.
 """
 triangles = Counter()
 for a, b, c, q in all_primitive_triples():
 if q > limit:
 break
 p = a + b + c
 for i in range(p, limit + 1, p):
 triangles[i] += 1
 return sum(n == 1 for n in triangles.values())

from collections import Counter
from itertools import count
def gcd(m, n):
 """Return the greatest common divisor of m and n."""
 while n != 0:
 m, n = n, m % n
 return m
def coprime(m, n):
 """Return True iff m and n are coprime."""
 return gcd(m, n) == 1
def all_primitive_triples():
 """Generate all primitive Pythagorean triples, together with a lower
 bound on the perimeter for which all triples have been generated
 so far.
 """
 for m in count(1):
 for n in range(1, m):
 if (m + n) % 2 and coprime(m, n):
 a = m * m - n * n
 b = 2 * m * n
 yield a, b, m * m + n * n, 2 * m * (m + 1)
def problem75(limit):
 """Return the number of values of L <= limit such that there is
 exactly one integer-sided right-angled triangle with perimeter
 L.
 """
 triangles = Counter()
 for a, b, c, q in all_primitive_triples():
 if q > limit:
 break
 p = a + b + c
 for i in range(p, limit + 1, p):
 triangles[i] += 1
 return sum(n == 1 for n in triangles.values())