Introduction

Project Euler 233 looks geometric on the surface, but it is really a number-theory problem. The challenge asks for values of N where the circle passing through (0, 0), (N, 0), (0, N), and (N, N) contains exactly 420 lattice points, then asks for the sum of all such N below a large limit.

Turn the Geometry into an Arithmetic Equation

The circle through those four corner points has center (N / 2, N / 2) and radius N / sqrt(2). Its equation is:

(x - N/2)^2 + (y - N/2)^2 = N^2 / 2

Multiply by four to avoid fractions:

(2x - N)^2 + (2y - N)^2 = 2N^2

Now define:

• 'a = 2x - N'
• 'b = 2y - N'

Then the lattice-point count becomes the number of integer solutions to:

a^2 + b^2 = 2N^2

So the geometry has been converted into a sum-of-two-squares counting problem.

Use the Sum-of-Two-Squares Formula

For an integer m, the number of integer pairs solving a^2 + b^2 = m is commonly written as r2(m). A classic theorem gives:

r2(m) = 4 * (d1(m) - d3(m))

Here:

• 'd1(m) counts divisors congruent to 1 mod 4'
• 'd3(m) counts divisors congruent to 3 mod 4'

For this problem, m = 2N^2, and that simplifies beautifully. If:

N = 2^k * product(p_i^e_i) * product(q_j^f_j)

where each p_i is a prime congruent to 1 mod 4 and each q_j is a prime congruent to 3 mod 4, then:

f(N) = r2(2N^2) = 4 * product(2e_i + 1)

The exponents of primes congruent to 3 mod 4 do not change the count as long as they appear in a square, which they do inside N^2.

Because the target is 420 lattice points:

4 * product(2e_i + 1) = 420

So:

product(2e_i + 1) = 105

That factorization is the heart of the problem.

What Exponent Patterns Are Possible

Since 105 = 3 * 5 * 7, the allowed odd factors of the form 2e + 1 lead to exponent patterns such as:

• '1, 2, 3 because 3 * 5 * 7 = 105'
• '1, 17 because 3 * 35 = 105'
• '2, 10 because 5 * 21 = 105'
• '3, 7 because 7 * 15 = 105'
• '52 because 105 = 105'

These exponents apply only to primes congruent to 1 mod 4. The rest of N can be multiplied by powers of 2 and primes congruent to 3 mod 4 without changing the 420-point condition, as long as the product stays within the limit.

That observation is why brute force over every N up to the full bound is the wrong strategy. The efficient approach is to generate candidate cores from 1 mod 4 primes, then multiply by allowed square-safe factors.

A Small Prototype in Python

The following code shows the arithmetic core for smaller limits:

1from math import prod
2
3def lattice_count_from_exponents(exponents):
4    return 4 * prod(2 * e + 1 for e in exponents)
5
6print(lattice_count_from_exponents([1, 2, 3]))   # 420
7print(lattice_count_from_exponents([3, 7]))      # 420

A search helper for candidate prime cores:

1def build_core(primes, exponents):
2    value = 1
3    for p, e in zip(primes, exponents):
4        value *= p ** e
5    return value
6
7core = build_core([5, 13, 17], [1, 2, 3])
8print(core)

A full accepted solver adds:

• A prime generator split by 1 mod 4 and 3 mod 4
• Depth-first search over exponent patterns
• Pruning once the partial product exceeds the problem limit
• A second stage that multiplies each valid core by allowed factors from 2 and 3 mod 4 primes

Why This Works Better Than Brute Force

The limit in Euler 233 is far too large for checking every N individually and counting lattice points with direct geometry. The theorem compresses the search into prime exponents, which is dramatically smaller.

This is a common Euler pattern: the problem statement looks like geometry, but the winning move is to replace point counting with a multiplicative number-theory formula.

Common Pitfalls

• Brute-forcing every N and testing points on a circle directly.
• Forgetting that the count is for 2N^2, not for N itself.
• Applying the divisor formula without separating 1 mod 4 and 3 mod 4 primes.
• Missing the fact that several exponent patterns can produce the same target count of 420.

Summary

• Euler 233 reduces to counting representations of 2N^2 as a sum of two squares.
• The lattice-point count becomes 4 * product(2e_i + 1) over primes congruent to 1 mod 4.
• Setting that expression equal to 420 gives the valid exponent patterns.
• Efficient solutions enumerate prime-factor structures rather than scanning all N.
• The key idea is turning geometry into multiplicative number theory.