Solution

Answer: 1725323624056

Let $S_r$ be the set of nonzero lattice points strictly inside the circle

$$x^2+y^2<r^2 .$$

We must count triangles with vertices in $S_{105}$ that contain the origin strictly in their interior.

1. Mathematical analysis

Step 1 — Geometry of the origin condition

Take three nonzero points and look at their polar angles

$$0 \le \theta_1 < \theta_2 < \theta_3 < 2\pi.$$

The triangle contains the origin iff the three points are not contained in any closed semicircle.

Equivalently:

$$\theta_3-\theta_1 > \pi.$$

If instead

$$\theta_3-\theta_1 \le \pi,$$

then all three points lie in a semicircle, so the origin is outside (or on the boundary).

Thus the problem becomes:

Count all triples of lattice points whose angular span is strictly greater than $\pi$.

Step 2 — Group points by direction

Many lattice points lie on the same ray from the origin.

For example:

$$(1,1), (2,2), (3,3), \dots$$

all have the same angle.

A triangle containing the origin can never use two points on the same ray, because then the origin cannot lie strictly inside the triangle.

So we compress points by primitive direction.

For each point $(x,y)$, define

$$g=\gcd(|x|,|y|), \qquad \left(\frac{x}{g},\frac{y}{g}\right)$$

which is its primitive direction.

For each direction $d_i$, let:

$$c_i = \text{number of lattice points on that ray}.$$

We sort all primitive directions by angle.

Step 3 — Count bad triples

A triple is “bad” if all three directions fit inside a closed semicircle.

Fix a starting direction $i$.

Let the directions strictly after $i$ but within angle $\pi$ be the window.

Suppose the total number of points in that window is

$$W_i.$$

But we must choose points from distinct directions, otherwise the triangle is degenerate.

If the multiplicities in the window are $c_j$, then the number of unordered pairs of points from distinct directions is

$$\frac{W_i^2-\sum c_j^2}{2}.$$

Multiplying by $c_i$ (choices for the first direction) gives the number of bad triples whose minimal angle direction is $i$.

Summing over all $i$ counts every bad triple exactly once.

Step 4 — Total distinct-direction triples

Let

$$N=\sum_i c_i$$

be the total number of nonzero lattice points.

All triples:

$$\binom{N}{3}.$$

But we must remove triples using the same direction twice (or three times).

For a direction with multiplicity $c_i$:

triples with exactly two points on that ray:

$$\binom{c_i}{2}(N-c_i)$$

triples with all three on that ray:

$$\binom{c_i}{3}$$

Subtracting these from $\binom{N}{3}$ gives the number of triples using distinct directions.

Finally:

$$\text{good}= \text{distinct-direction triples} - \text{bad triples}.$$

2. Python implementation

from math import gcd, atan2, pi, comb
from collections import Counter

R = 105

# Count how many lattice points lie on each primitive direction
direction_count = Counter()

for x in range(-(R - 1), R):
    for y in range(-(R - 1), R):

        if x == 0 and y == 0:
            continue

        if x * x + y * y < R * R:

            g = gcd(abs(x), abs(y))
            dx = x // g
            dy = y // g

            direction_count[(dx, dy)] += 1

# Sort primitive directions by polar angle
dirs = sorted(
    (atan2(y, x) % (2 * pi), cnt)
    for (x, y), cnt in direction_count.items()
)

angles = [a for a, c in dirs]
counts = [c for a, c in dirs]

m = len(dirs)

# Duplicate arrays for circular two-pointer sweep
angles2 = angles + [a + 2 * pi for a in angles]
counts2 = counts + counts

# Prefix sums of counts and counts^2
pref = [0]
pref_sq = [0]

for v in counts2:
    pref.append(pref[-1] + v)
    pref_sq.append(pref_sq[-1] + v * v)

# Total number of lattice points (excluding origin)
N = sum(counts)

# Total triples
total = comb(N, 3)

# Remove triples using repeated directions
duplicate_direction_triples = 0

for c in counts:
    duplicate_direction_triples += comb(c, 2) * (N - c)
    duplicate_direction_triples += comb(c, 3)

distinct_direction_triples = total - duplicate_direction_triples

# Count bad triples (contained in a semicircle)
bad = 0

j = 0

for i in range(m):

    if j < i + 1:
        j = i + 1

    while j < i + m and angles2[j] <= angles[i] + pi + 1e-15:
        j += 1

    # Window excludes i itself
    W = pref[j] - pref[i + 1]
    SQ = pref_sq[j] - pref_sq[i + 1]

    # Number of unordered pairs from distinct directions
    pairs = (W * W - SQ) // 2

    bad += counts[i] * pairs

answer = distinct_direction_triples - bad

print(answer)

3. Code walkthrough

Primitive directions

g = gcd(abs(x), abs(y))
dx = x // g
dy = y // g

This converts every lattice point to its primitive ray.

Example:

$$(6,9)\to(2,3).$$

Sorting by angle

atan2(y, x)

lets us process directions in circular order.

Two-pointer sweep

For each starting direction $i$, pointer j advances until the angular difference exceeds $\pi$.

Thus all directions in

$$[i+1,; j-1]$$

fit inside a semicircle with $i$.

Counting pairs from distinct directions

If the counts are $a_1,a_2,\dots$, then

$$\sum_{u<v} a_u a_v = \frac{ \left(\sum a_u\right)^2 - \sum a_u^2 }{2}.$$

That is exactly:

pairs = (W * W - SQ) // 2

4. Verification on small cases

The program gives:

$r=2 \Rightarrow 8$
$r=3 \Rightarrow 360$
$r=5 \Rightarrow 10600$

matching the problem statement exactly.

For $r=105$, the computed value is:

$$1725323624056$$

which is of the expected magnitude (roughly cubic in the number of lattice points).

Answer: 1725323624056

Project Euler Problem 184