Python generator for "barely obtuse" triangles (Project Euler 224) I am trying to solve Project Euler Problem 224:


  Let us call an integer sided triangle with sides a ≤ b ≤ c barely obtuse if the sides satisfy a2 + b2 = c2 - 1.
  
  How many barely obtuse triangles are there with perimeter ≤ 75,000,000?


For large v_max and v_max_n, the generator below yields very slow when I have 750000000 and 500000000, respectively. Having tried for days, I am still looking for an algorithm that can do this in under a minute.

from itertools import product
import math

n = 15 * 10 ** 8
v_max = math.floor(n / 2 - 1 / (2 * n))
v_max_n = n // 3

(i for i in product(range(2, v_max_n + 1, 2), 
                    range(2, v_max + 1, 2), 
                    range(3, v_max + 1)) 
 if i[0] &lt;= i[1] and i[1] &lt;= i[2] and sum(i) &lt;= n and
 i[0] ** 2 + i[1] ** 2 == i[2] ** 2 - 1)


I have tried using it as map(lambda x: x, gen), nested for loops, and have generally been racking my brain to no avail.

I tried re-writing b, c as expressions. This tends to be quick but misses some of the triples.

n = 12
v_max = math.floor(n / 2 - 1 / (2 * n))
v_max_n = n // 3
j = 0  # tested this with low n and compared: 12, 150 to see 
for a in range(1, v_max_n + 1, 1):
    b = (n ** 2 - 2 * n * a - 1) / (2 * (n - a))
    c = (a ** 2 + b ** 2 + 1) ** 0.5
    if c % 1 == 0 and b % 1 == 0 and a + int(b) + int(c) &lt;= n:
        # print(a, int(b), int(c))
        j += 1
print(j)
It seems like you want to find a solution for a²+b²=c²-1 with some added constraints, like a&lt;=b&lt;=c, a+b+c&lt;=n, etc. by trying all possible combinations of a, b, and c and testing whether they satisfy all your conditions at once. This is pretty wasteful.

Instead of itertools.product, you can use a generator expression with three regular for loops. This has several advantages:


you could move some of the if clauses up after the first or second loop, i.e. you don't have to run the other loops if those conditions already fail at this point, e.g.

 for x in ... if test(x) for y in ... if test(y) ...

you can use the values of your previous variables in the lower and upper bounds for the later variables (in your case this replaces most of your if conditions)
you can basically calculate the value for c from a and b without testing all possible values


This is how I'd do it:

gen = ((a, b, int(c))
       for a in range(2, v_max_n + 1, 2)
       for b in range(a, min(v_max + 1, n - a - a), 2) # use a for lower and upper bounds
       for c in [(a ** 2 + b ** 2 + 1)**0.5]           # just a single candidate for c
       if  c % 1 == 0)                                 # whole-numbered c found?


Note that the calculation of c using very_large_number**0.5 might be imprecise with float; using decimal might work, though. However, even with those optimizations, testing much fewer values than your original loop (on the order of O(n²) instead of O(n³)), it might not be feasible to find solution for large values of a, b and c.

Also note that I did not thoroughly test this for off-by-one errors, since performance was the main concern.

Another thing that you might try: Invert the loops for a and for b, i.e. instead of testing all b for each a, no matter how large the difference, test all a up to b first. This does not decrease the number of combinations to test, but it seems to yield much more valid combinations in the "smaller" number much faster. Like this (upper bound for b can probably be reduced):

       for b in range(2, v_max + 1, 2)
       for a in range(2, b+1, 2)