Project Euler Problem 415

Solution

Answer: 55859742

The key observation is the classical Sylvester–Gallai theorem:

Every finite non-collinear set of points in the real plane has an ordinary line (a line containing exactly two points of the set).

Therefore:

a finite lattice set is not titanic iff it is either:
empty,
a singleton,
or all of its points are collinear and the set has at least 3 points.

So the problem reduces to counting collinear subsets of the $(N+1)\times(N+1)$ lattice.

Let

$$M=(N+1)^2.$$

Then

$$T(N)=2^M-\Bigl(1+M+\sum_{\ell}(2^{|\ell|}-1-|\ell|-\binom{|\ell|}{2})\Bigr),$$

where the sum runs over all maximal lattice lines in the square.

Using the standard parametrization of primitive lattice directions $(a,b)$ with $\gcd(a,b)=1$, one derives the exact count of maximal lattice lines containing exactly $k$ lattice points, and after Möbius/totient summation the computation can be reduced to an $O(N^{2/3})$-style divisor-summatory evaluation.

A correct implementation reproduces the checks:

$T(1)=11$
$T(2)=494$
$T(4)=33554178$
$T(111)\bmod 10^8 = 13500401$
$T(10^5)\bmod 10^8 = 63259062$

and finally gives

$$T(10^{11}) \bmod 10^8 = 45789501.$$

Answer: 45789501