Back to index.

The problem: https://projecteuler.net/problem=39.

We'll have a solution if, and only if, $(p - a - b)^2 = a^2 + b^2$. If we consider $a$ to be the length of the smallest side and $b$ to be the length of the other leg (notice that because $p$ is integer, then $b \neq a$ since $p = a + b + c$ and if $a = b$, we'd have $c = \sqrt{2}a$ and thus $p = (2+\sqrt{2})a$, a contradiction). From this, it seems we're good to start testing.

We know that $a < p$, of course, but it is also true that $b < p - a$. Not just that, since $a$ is the least side length, we also know that $p > 3a$ and, for similar reasons, $p > 2b + a$. This may help with prunning.

Another remark is that $(p - a - b)^2 = a^2 + b^2$ implies in both: $(p - a - b)^2 - a^2 = b^2$ and $(p - a - b)^2 - b^2 = a^2$. This gives $(p - a - 2b)(p-a) = a^2$ and $(p - b - 2a)(p-b) = b^2$. This will give more tests for prunning. We're specially interested in the fact that $p-a$ divides $a^2$. In the case that it does, then we'll have a solution if, and only if, $p - a - \frac {a^2} {p-a}$ is even and $2b$ will be that number.

p_with_max_sols = 1
max_num_sols = 0

def count_solutions_for(p):
    num_sols = 0
    a = 1
    while 3*a < p:
        if (a**2) % (p-a) == 0:
            rat_a2_diffpa = (a**2)/(p-a)
            if (p - a - rat_a2_diffpa) % 2 == 0:
                num_sols += 1
        a += 1
    return num_sols

for p in range(3, 1001):
    n = count_solutions_for(p)
    if n > max_num_sols:
        print("for", p, "=>", n)
        max_num_sols = n
        p_with_max_sols = p

print(p_with_max_sols)

for 12 => 1
for 60 => 2
for 120 => 3
for 240 => 4
for 420 => 6
for 840 => 9
840

With the remarks above, we could can solve this fast for values larger than 1000.