Project Euler Problem 504

Solution

Answer: 694687

Using Pick’s Theorem is the key observation.

For the quadrilateral with vertices

$$A(a,0),\quad B(0,b),\quad C(-c,0),\quad D(0,-d),$$

the area is

$$\text{Area}=\frac{ab+bc+cd+da}{2}.$$

The number of lattice points on the boundary is

$$B=\gcd(a,b)+\gcd(b,c)+\gcd(c,d)+\gcd(d,a).$$

By Pick’s Theorem,

$$\text{Area} = I + \frac{B}{2} - 1,$$

so the number of strictly interior lattice points is

$$I = \frac{ ab+bc+cd+da - \gcd(a,b)-\gcd(b,c)-\gcd(c,d)-\gcd(d,a) }{2} +1.$$

We then count all quadruples $(a,b,c,d)$ with $1\le a,b,c,d\le 100$ for which $I$ is a perfect square.

A direct brute force over $100^4$ cases is feasible with optimization/precomputation.

Python verification:

from collections import Counter
from math import gcd

def solve(m):
    t = [[0]*(m+1) for _ in range(m+1)]

    for a in range(1, m+1):
        for b in range(1, m+1):
            t[a][b] = a*b - gcd(a, b)

    # Possible targets:
    # I = total/2 + 1 must be a square
    squares = set(i*i for i in range(150))
    targets = set(2*(s-1) for s in squares)

    # Precompute distributions
    X = [[None]*(m+1) for _ in range(m+1)]
    Y = [[None]*(m+1) for _ in range(m+1)]

    for b in range(1, m+1):
        for d in range(1, m+1):

            cx = Counter()
            cy = Counter()

            for a in range(1, m+1):
                cx[t[a][b] + t[d][a]] += 1

            for c in range(1, m+1):
                cy[t[b][c] + t[c][d]] += 1

            X[b][d] = cx
            Y[b][d] = cy

    ans = 0

    for b in range(1, m+1):
        for d in range(1, m+1):
            cx = X[b][d]
            cy = Y[b][d]

            for s, v in cx.items():
                for target in targets:
                    ans += v * cy.get(target - s, 0)

    return ans

print(solve(4))    # 42
print(solve(100))

This reproduces the given check:

$$m=4 \Rightarrow 42$$

and for $m=100$ gives:

$$694687$$

Answer: 694687