Project Euler Problem 630

Solution

Answer: 9669182880384

Let the set of unique lines be $L$.

For a line $\ell\in L$, define $c(\ell)$ as the number of other lines that cross it.

Then

$$S(L)=\sum_{\ell\in L} c(\ell).$$

Two distinct lines fail to cross iff they are parallel.

Therefore, for every line,

$$c(\ell)=M(L)-(\text{number of lines parallel to }\ell).$$

So the problem reduces to:

1. Count all distinct lines.
2. Group them by slope.

---

Step 1 — Generating the points

The sequence is:

$$S_0=290797,\qquad S_{n+1}=S_n^2 \bmod 50515093$$

and

$$T_n=(S_n \bmod 2000)-1000.$$

The points are

$$(T_1,T_2),(T_3,T_4),\dots$$

For $n=2500$, we generate 2500 points.

The first three are indeed:

$$(527,144),\ (-488,732),\ (-454,-947).$$

---

Step 2 — Representing a line uniquely

A line through points $(x_1,y_1)$ and $(x_2,y_2)$ has direction vector

$$(dx,dy)=(x_2-x_1,\ y_2-y_1).$$

Normalize by dividing by

$$g=\gcd(dx,dy),$$

so the slope representation becomes primitive.

We also force a unique sign convention:

• $dx>0$, or
• $dx=0$ and $dy>0$.

Thus every slope has exactly one canonical representation.

---

Canonical line form

Using normalized $(dx,dy)$, the quantity

$$c = dy\cdot x - dx\cdot y$$

is constant along the line, since

$$dy,x - dx,y = \text{constant}$$

is equivalent to the line equation.

Therefore a unique line is represented by

$$(dy,dx,c).$$

This removes duplicates automatically.

---

Step 3 — Counting crossings

Suppose slope class $i$ contains $m_i$ lines.

Then:

• total lines:

$$M=\sum_i m_i$$

• each line in class $i$ is crossed by exactly $M-m_i$ lines.

Hence

$$S=\sum_i m_i(M-m_i).$$

Expanding:

$$S=M^2-\sum_i m_i^2.$$

So we only need:

1. the number of unique lines,
2. the number of lines in each slope class.

---

Python implementation

from math import gcd
from collections import defaultdict

MOD = 50515093

# ------------------------------------------------------------
# Generate the 2500 points
# ------------------------------------------------------------

s = 290797
points = []

for _ in range(2500):
    s = (s * s) % MOD
    x = (s % 2000) - 1000

    s = (s * s) % MOD
    y = (s % 2000) - 1000

    points.append((x, y))

# ------------------------------------------------------------
# Build all unique lines
# ------------------------------------------------------------

lines = set()
slope_count = defaultdict(int)

n = len(points)

for i in range(n):
    x1, y1 = points[i]

    for j in range(i + 1, n):
        x2, y2 = points[j]

        dx = x2 - x1
        dy = y2 - y1

        # normalize slope
        g = gcd(dx, dy)
        dx //= g
        dy //= g

        # canonical sign
        if dx < 0 or (dx == 0 and dy < 0):
            dx = -dx
            dy = -dy

        # canonical line constant
        c = dy * x1 - dx * y1

        line = (dy, dx, c)

        # count only unique lines
        if line not in lines:
            lines.add(line)
            slope_count[(dy, dx)] += 1

# ------------------------------------------------------------
# Compute M and S
# ------------------------------------------------------------

M = len(lines)

S = M * M - sum(v * v for v in slope_count.values())

print(M)
print(S)

---

Code walkthrough

Point generation

s = (s * s) % MOD

implements the recurrence exactly.

Each pair of generated $T_n$ values becomes one point.

---

Slope normalization

g = gcd(dx, dy)
dx //= g
dy //= g

reduces the direction vector to primitive form.

---

Sign normalization

if dx < 0 or (dx == 0 and dy < 0):

ensures that $(1,2)$ and $(-1,-2)$ are treated as the same slope.

---

Unique line representation

c = dy * x1 - dx * y1
line = (dy, dx, c)

gives a canonical identifier for the infinite line.

---

Counting crossings

If a slope class contains $v$ lines, those lines do not intersect each other, but intersect every other line.

Thus:

S = M*M - sum(v*v for v in slope_count.values())

implements

$$S=M^2-\sum_i m_i^2.$$

---

Verification on the small example

For $n=3$:

• there are 3 unique lines,
• no two are parallel,

so

$$M=3,\qquad S=3^2-3=6,$$

matching the statement.

For $n=100$, the program gives:

$$M(L_{100})=4948,$$

$$S(L_{100})=24477690,$$

again matching the problem statement.

---

Final computation

The program produces:

$$M(L_{2500}) = 3,!109,!535$$

and

$$S(L_{2500}) = 9,!669,!182,!880,!384.$$

The value is positive and of the expected magnitude since $M^2\approx 9.67\times10^{12}$.

---

Answer: 9669182880384