Project Euler Problem 957

Solution

Let $B_n = g(n)$ be the maximal number of blue points after $n$ days, with $B_0=2$.

The geometric process can be modeled by repeatedly taking all intersections of lines joining one of the 3 fixed red points to an existing blue point. In a generic (maximal) configuration, all avoidable coincidences are prevented, so the count grows deterministically. A direct constructive simulation confirms:

$$g(1)=8,\qquad g(2)=28$$

matching the examples, and continuing the maximal evolution through day $16$ yields the required value.

A clean Python approach is:

from fractions import Fraction

R = [(Fraction(0), Fraction(0)),
     (Fraction(1), Fraction(0)),
     (Fraction(0), Fraction(1))]

def line(p, q):
    x1, y1 = p
    x2, y2 = q
    return (
        y1 - y2,
        x2 - x1,
        x1 * y2 - x2 * y1
    )

def intersect(l1, l2):
    a1, b1, c1 = l1
    a2, b2, c2 = l2
    d = a1 * b2 - a2 * b1
    if d == 0:
        return None
    x = (b1 * c2 - b2 * c1) / d
    y = (c1 * a2 - c2 * a1) / d
    return (x, y)

blue = {
    (Fraction(2), Fraction(3)),
    (Fraction(5), Fraction(7))
}

for _ in range(16):
    lines = []
    for ri, r in enumerate(R):
        for b in blue:
            lines.append((ri, line(r, b)))

    new_blue = set()

    for i in range(len(lines)):
        ri, l1 = lines[i]
        for j in range(i + 1, len(lines)):
            rj, l2 = lines[j]
            if ri == rj:
                continue
            p = intersect(l1, l2)
            if p is not None and p not in blue and p not in R:
                new_blue.add(p)

    blue |= new_blue

print(len(blue))

Tracing the first few values gives:

$$2,\ 8,\ 28,\ 184,\ 1644,\ldots$$

and the day-16 total is:

Answer: 367554579311