Problem 415: Titanic Sets

Detailed mathematical approach

Problem Summary

A lattice point has integer coordinates. A finite set \(S\) of lattice points is a titanic set if some straight line passes through exactly two points of \(S\). The statement illustrates both sides of the definition. ^[1] The set

$$\begin{aligned}S=\{&(0,0),(0,1),(0,2),\\ &(1,0),(1,1),(2,0)\}\end{aligned}$$

is titanic: the line through \((0,1)\) and \((2,0)\) misses the other four points. The set \(\{(0,0),(1,1),(2,2),(4,4)\}\) is not, since all four sit on \(y=x\), so every line through two of them runs through all four and every other line meets the set at most once.

For a positive integer \(N\) let

$$G_N=\{(x,y)\in\mathbb{Z}^2:0\le x,y\le N\}$$

be the square grid of \((N+1)^2\) lattice points, and let \(T(N)\) count the titanic subsets \(S\subseteq G_N\). The statement gives five checkpoints: \(T(1)=11\), \(T(2)=494\), \(T(4)=33554178\), and modulo \(10^8\) the values \(T(111)\equiv 13500401\) and \(T(10^5)\equiv 63259062\). We must compute \(T(10^{11})\bmod 10^8\), where the grid holds \(10000000000200000000001\) points.

The whole solution in one sentence: rather than counting the titanic subsets we subtract the few that are not titanic — the empty set, the single points, and the sets of three or more points that all lie on one line — and we count that last group by sorting the lines of the grid according to how many lattice points they carry.

Mathematical Approach

1. The definition on the smallest grids

Start with \(N=1\), the four corners of a unit square and its \(2^4=16\) subsets. The empty set and the four singletons contain no two points, so no line meets them in exactly two. Each of the other \(11\) has one: for a pair, the line through it; for a triple, any two of its points, since no three corners of a square are collinear; for the full square, either diagonal. Hence \(T(1)=11\).

Now \(N=2\), the \(3\times3\) grid with \(9\) points and \(2^9=512\) subsets. The failures are the empty set, the \(9\) singletons and the \(8\) three-point lines — three rows, three columns, two diagonals — so \(T(2)=512-1-9-8=494\). Both match the checkpoints, and both show the pattern we now prove.

2. Which sets fail to be titanic

Call a line ordinary for \(S\) if it holds exactly two points of \(S\); a set is titanic precisely when it has one. The classification is clean.

• If \(|S|\le 1\), every line meets \(S\) at most once, so there is no ordinary line.
• If \(|S|=2\), the line through the two points is ordinary, so \(S\) is titanic.
• If \(|S|\ge3\) and all points lie on one line \(L\), then \(L\) contains \(|S|\ge3\) of them, while any other line meets \(L\) — and hence \(S\) — at most once. No line is ordinary, so \(S\) is not titanic.
• If \(|S|\ge3\) and \(S\) is not collinear, the Sylvester–Gallai theorem gives an ordinary line, so \(S\) is titanic. The theorem says precisely this: every finite non-collinear set of points in the Euclidean plane has a line through exactly two of them. Finiteness and real coordinates are both essential, and lattice points give both. ^[2]

Claim. \(S\subseteq G_N\) is not titanic if and only if \(|S|\le1\), or \(|S|\ge3\) and \(S\) is collinear. The four cases are exhaustive and mutually exclusive, which proves it. Writing \(U(N)\) for the number of non-titanic subsets,

$$T(N)=2^{(N+1)^2}-U(N).$$

3. Counting the complement line by line

A collinear set of three or more points lies on exactly one line, since two distinct points determine it, so these sets group by that line with none counted twice. For a line \(L\) put \(k_L=|L\cap G_N|\). The subsets of \(L\cap G_N\) of size at least three number

$$2^{k}-1-k-\binom{k}{2},\qquad k=k_L,$$

because we discard the empty set, the \(k\) singletons and the \(\binom k2\) pairs. Adding the empty set and the \((N+1)^2\) singletons of the whole grid,

$$U(N)=1+(N+1)^2+\sum_{L}\left(2^{k_L}-1-k_L-\binom{k_L}{2}\right),$$

the sum running over all lines that meet \(G_N\) in at least two points. At \(N=4\) enumeration finds \(108\) lines with two grid points, \(16\) with three, \(4\) with four and \(12\) with five. The bracket vanishes for \(k=2\) and equals \(1\), \(5\), \(16\) for \(k=3,4,5\), so

$$U(4)=1+25+16\cdot1+4\cdot5+12\cdot16=254,$$

and \(T(4)=2^{25}-254=33554178\), the third checkpoint.

4. From subset counts to a line-length statistic

Enumerating lines is hopeless at \(N=10^{11}\), so we regroup the sum by length. Define

$$F_\ell(N)=\#\{L:k_L\ge \ell+1\}.$$

The useful identity is a telescoping one: for every integer \(k\ge2\),

$$\sum_{\ell=2}^{k-1}\bigl(2^{\ell}-\ell-1\bigr)=2^{k}-1-k-\binom{k}{2}.$$

To see it, note \(\sum_{\ell=2}^{k-1}2^{\ell}=2^{k}-4\) and \(\sum_{\ell=2}^{k-1}(\ell+1)=\tfrac{k(k+1)}2-3\), so the left side is \(2^{k}-1-\tfrac{k(k+1)}2\), and so is the right, because \(1+k+\binom k2=1+\tfrac{k(k+1)}2\). Substituting and exchanging the summations — a line with \(k_L\) points carries the weight \(2^{\ell}-\ell-1\) for each \(\ell\) with \(k_L\ge\ell+1\) — gives

$$U(N)=1+(N+1)^2+\sum_{\ell\ge2}F_\ell(N)\bigl(2^{\ell}-\ell-1\bigr).$$

A line holds at most \(N+1\) grid points, so the sum stops at \(\ell=N\). At \(N=4\) the values \(F_2=32\), \(F_3=16\), \(F_4=12\) with weights \(1\), \(4\), \(11\) give \(1+25+32+64+132=254\), the same \(U(4)\).

5. Lines through the grid and their primitive directions

Let \(a=N+1\). If a line \(L\) meets \(\mathbb{Z}^2\) in distinct points \(P,Q\), dividing \(Q-P\) by the gcd of the absolute values of its coordinates yields a primitive vector \(d=(u,v)\) with \(\gcd(u,v)=1\); a displacement \((6,4)\), for instance, gives the step \((3,2)\). Every point of \(L\) is \(P+td\) for some real \(t\), and the lattice points are exactly those with \(t\) an integer: if \(tu\) and \(tv\) are integers, writing \(t=b/c\) in lowest terms forces \(c\) to divide both \(u\) and \(v\), so \(c=1\). Primitive vectors are exactly the lattice points visible from the origin. ^[4] Intersecting with the box keeps a contiguous run of \(t\), so

the grid points of a line are \(k_L\) equally spaced points, consecutive multiples of its primitive step.

Normalising \(d\) so that \(u\gt0\), or \(u=0\) and \(v\gt0\), splits the lines into four disjoint families: horizontal \(d=(1,0)\), vertical \(d=(0,1)\), positive slope with \(u,v\ge1\) coprime, and negative slope \(d=(u,-v)\) with \(u,v\ge1\) coprime. The reflection \((x,y)\mapsto(x,N-y)\) maps \(G_N\) onto itself and sends each positive-slope line to a negative-slope one of the same length, so the slanted families contribute equally.

6. Counting segments instead of lines

Counting lines of a given minimum length is awkward; counting segments is easy. Call an \(\ell\)-segment a pair of grid points \(\ell\) primitive steps apart on one line; a line with \(k_L\) grid points carries \(\max(k_L-\ell,0)\) of them, one per starting position. Over all lines of a slanted direction \((u,v)\) the \(\ell\)-segments are just the pairs \(\bigl((x,y),(x+\ell u,y+\ell v)\bigr)\) inside the box, so their number is

$$P_\ell(u,v)=\max(a-\ell u,0)\cdot\max(a-\ell v,0).$$

Now the trick. Since \(\max(k-\ell,0)-\max(k-\ell-1,0)\) equals \(1\) when \(k\ge\ell+1\) and \(0\) otherwise, subtracting the \((\ell+1)\)-segment count from the \(\ell\)-segment count leaves exactly the long-enough lines: there are \(P_\ell(u,v)-P_{\ell+1}(u,v)\) with \(k_L\ge\ell+1\). The axis directions work the same way: \(P_\ell(1,0)=a(a-\ell)\) and the difference is \(a\), matching the fact that all \(a\) horizontal lines have \(k_L=a\ge\ell+1\) for every \(\ell\le N\). Collecting the four families,

$$F_\ell(N)=2a+2\!\!\sum_{\substack{u,v\ge1\\ \gcd(u,v)=1}}\!\!\bigl(P_\ell(u,v)-P_{\ell+1}(u,v)\bigr).$$

Since \(P_\ell(u,v)\) is nonzero only when \(\ell u\le N\) and \(\ell v\le N\), the inner sum is finite, ranging over coprime pairs with \(u,v\le M=\lfloor N/\ell\rfloor\).

7. Coprime pairs as totient sums

Let \(\mathcal{C}_M\) be the ordered pairs with \(1\le u,v\le M\) and \(\gcd(u,v)=1\). Expanding \((a-\ell u)(a-\ell v)\) shows only three statistics of \(\mathcal{C}_M\) matter:

$$\begin{aligned}c(M)&=\sum_{(u,v)\in\mathcal{C}_M}1,\\ s(M)&=\sum_{(u,v)\in\mathcal{C}_M}(u+v),\\ p(M)&=\sum_{(u,v)\in\mathcal{C}_M}uv,\end{aligned}$$

and then

$$\sum_{\substack{u,v\le M\\ \gcd=1}}\!\!(a-\ell u)(a-\ell v)=a^2c(M)-a\ell\,s(M)+\ell^2p(M).$$

All three collapse to weighted sums of Euler's totient \(\varphi\), the count of integers in \([1,n]\) coprime to it. ^[3] Group the pairs by their larger entry. The only one with \(u=v\) is \((1,1)\). For \(u\lt v\), \(v\ge2\), there are \(\varphi(v)\) admissible \(u\), and since \(\gcd(u,v)=1\) exactly when \(\gcd(v-u,v)=1\) they pair off as \(u\leftrightarrow v-u\) and sum to \(v\varphi(v)/2\). Doubling for \(u\gt v\) and writing

$$\begin{aligned}\Phi(M)&=\sum_{d=1}^{M}\varphi(d),\\ \Psi_1(M)&=\sum_{d=1}^{M}d\,\varphi(d),\\ \Psi_2(M)&=\sum_{d=1}^{M}d^2\varphi(d),\end{aligned}$$

we obtain, for \(M\ge1\),

$$\begin{aligned}c(M)&=2\Phi(M)-1,\\ s(M)&=3\Psi_1(M)-1,\\ p(M)&=\Psi_2(M).\end{aligned}$$

For \(c\) the count is \(1+2\sum_{v=2}^{M}\varphi(v)\); for \(s\) each \(v\) gives \(v\varphi(v)/2\) from the smaller entries and \(v\varphi(v)\) from the larger, so \(2+3\sum_{v=2}^{M}v\varphi(v)\); for \(p\) each gives \(v\cdot v\varphi(v)/2\), so \(1+\sum_{v=2}^{M}v^2\varphi(v)\). All three are tabulated: \(c(M)=1,3,7,11,19,\dots\) with exactly the formula \(2\Phi(M)-1\), ^[5] \(\Psi_1=1,3,9,17,37,\dots\) ^[6] and \(\Psi_2=1,5,23,55,155,\dots\) ^[7] A brute-force check for every \(M\le44\) confirms the identities. The empty range needs its own value: \(c(0)=s(0)=p(0)=0\), since no pair qualifies, whereas the closed forms would wrongly give \(-1\) for the first two. This happens at \(\ell=N\), where \(M'=0\); both the worked example below and the program rely on it.

8. A quadratic in \(\ell\) on each block

Put \(M=\lfloor N/\ell\rfloor\) and \(M'=\lfloor N/(\ell+1)\rfloor\). Subtracting the two expansions of Section 7 and using \((\ell+1)^2=\ell^2+2\ell+1\) gives

$$F_\ell(N)=2a+2\bigl(q_2\ell^2+q_1\ell+q_0\bigr)$$

with

$$\begin{aligned}q_2&=p(M)-p(M'),\\ q_1&=a\bigl(s(M')-s(M)\bigr)-2p(M'),\\ q_0&=a^2\bigl(c(M)-c(M')\bigr)\\ &\quad+a\,s(M')-p(M').\end{aligned}$$

This is the decisive fact. The coefficients depend on \(\ell\) only through \(M\) and \(M'\), and \(\lfloor N/\ell\rfloor\) takes only \(O(\sqrt N)\) distinct values: for \(\ell\le\sqrt N\) there are at most \(\sqrt N\) indices, and beyond that the quotient itself is below \(\sqrt N\). So \(2\le\ell\le N\) splits into \(O(\sqrt N)\) maximal blocks on which \(q_0,q_1,q_2\) are constant, each summable in closed form. At \(N=10^{11}\) the common refinement of the two quotient sequences has \(894424\) blocks and \(632453\) distinct values of \(M\).

9. Worked example: \(N=4\)

Here \(a=5\). From \(\Phi(1)=\Psi_1(1)=\Psi_2(1)=1\) and \(\Phi(2)=2\), \(\Psi_1(2)=3\), \(\Psi_2(2)=5\) we get \(c(1)=1\), \(s(1)=2\), \(p(1)=1\) and \(c(2)=3\), \(s(2)=8\), \(p(2)=5\). Take \(\ell=2\), so \(M=2\) and \(M'=1\). The coprime pairs with \(u,v\le2\) are \((1,1),(1,2),(2,1)\), and

$$\sum(5-2u)(5-2v)=9+3+3=15,$$

while for \(\ell=3\) only \((1,1)\) survives, giving \((5-3)^2=4\). Hence \(F_2(4)=2\cdot5+2(15-4)=32\). The coefficients agree: \(q_2=4\), \(q_1=5(2-8)-2=-32\), \(q_0=25(3-1)+5\cdot2-1=59\), and \(10+2(16-64+59)=32\). For \(\ell=3\), \(M=M'=1\) gives \(q_2=0\), \(q_1=-2\), \(q_0=9\) and \(F_3(4)=16\); for \(\ell=4\), \(M=1\) and \(M'=0\) give \(q_2=1\), \(q_1=-10\), \(q_0=25\) and \(F_4(4)=10+2(16-40+25)=12\). These are the values used in Section 4, reproducing \(U(4)=254\). As a further check, \(F_N(N)=2N+4\) for every \(N\) from \(2\) to \(11\): the \(2(N+1)\) axis-parallel lines plus the two main diagonals are exactly the lines with the maximal \(N+1\) points.

10. Summatory totients without a full sieve

The blocks need \(\Phi\), \(\Psi_1\) and \(\Psi_2\) at arguments as large as \(\lfloor N/2\rfloor=5\cdot10^{10}\), far beyond what this program sieves. Gauss's identity \(\sum_{d\mid n}\varphi(d)=n\) ^[3] rescues us: summed over \(n\le x\), with \(n=qd\),

$$\sum_{q\le x}\Phi\!\left(\left\lfloor\frac xq\right\rfloor\right)=\sum_{m\le x}m=\frac{x(x+1)}2 .$$

Multiplying the identity by \(n\) before summing, and then by \(n^2\), gives two companions:

$$\sum_{q\le x}q\,\Psi_1\!\left(\left\lfloor\frac xq\right\rfloor\right)=\sum_{m\le x}m^2,$$

$$\sum_{q\le x}q^2\,\Psi_2\!\left(\left\lfloor\frac xq\right\rfloor\right)=\sum_{m\le x}m^3 .$$

Isolating the \(q=1\) term turns all three into one recurrence. Write \(A_0=\Phi\), \(A_1=\Psi_1\), \(A_2=\Psi_2\) and let \(H_j(x)=\sum_{m\le x}m^{\,j}\). Then for \(r=0,1,2\),

$$A_r(x)=H_{r+1}(x)-\sum_{q=2}^{x}q^{\,r}A_r\!\left(\left\lfloor\frac xq\right\rfloor\right),$$

and every argument on the right is smaller than \(x\). Equal quotients group into \(O(\sqrt x)\) blocks: a block starting at \(L\) has \(t=\lfloor x/L\rfloor\), ends at \(R=\lfloor x/t\rfloor\), and contributes \(A_r(t)\) with multiplier \(H_r(R)-H_r(L-1)\). At \(x=6\), \(q=2\), \(q=3\) and \(q=4,5,6\) give quotients \(3\), \(2\) and \(1\), so

$$\Phi(6)=21-\Phi(3)-\Phi(2)-3\Phi(1)=12.$$

Sieving \(\varphi\) to a cutoff \(B\), answering queries below \(B\) from a prefix table and memoising the rest costs \(O(B+x/\sqrt B)\), minimised near \(B\sim x^{2/3}\). The idea is standard for the Mertens function, whose analogue \(\sum_{q\le x}M(\lfloor x/q\rfloor)=1\) comes with sublinear evaluation of isolated values. ^[8] All three recurrences were verified numerically for every \(x\le119\).

11. Summing a block in closed form

On a block \(L_1\le\ell\le L_2\) write \(p_2=2q_2\), \(p_1=2q_1\) and \(p_0=2q_0+2a\), so that \(F_\ell(N)=p_2\ell^2+p_1\ell+p_0\). The block's contribution to \(U(N)\) is

$$\sum_{\ell=L_1}^{L_2}\bigl(p_2\ell^2+p_1\ell+p_0\bigr)\bigl(2^{\ell}-\ell-1\bigr),$$

which needs three exponential sums, three power sums and the block length. The exponential prefix sums are

$$\begin{aligned}\sum_{j=0}^{n}2^{j}&=2^{n+1}-1,\\ \sum_{j=0}^{n}j\,2^{j}&=(n-1)2^{n+1}+2,\\ \sum_{j=0}^{n}j^2 2^{j}&=(n^2-2n+3)2^{n+1}-6,\end{aligned}$$

each provable by induction. Differences at \(L_2\) and \(L_1-1\) turn them into the block sums \(E_i=\sum_\ell \ell^i2^{\ell}\); writing \(W_j\) for \(\sum_\ell \ell^j\) over the same block, with \(W_0=L_2-L_1+1\), and expanding the factor \(\ell+1\) gives the block's contribution as

$$\begin{aligned}&p_2E_2+p_1E_1+p_0E_0\\ &\quad-p_2(W_3+W_2)-p_1(W_2+W_1)\\ &\quad-p_0(W_1+W_0),\end{aligned}$$

the program's sum_pow \(-\) sum_poly, with \(W_0\) kept as cnt. One subtlety matters: \(10^8=2^8\cdot5^8\), so \(2\) and \(6\) are not invertible, and the divisions in \(\tfrac{n(n+1)}2\), \(\tfrac{n(n+1)(2n+1)}6\) and \(\bigl(\tfrac{n(n+1)}2\bigr)^2\) must be cancelled on exact integers before any reduction. The exponential identities, being division-free, reduce term by term.

How the Code Works

The C++ program ^[9] fixes MOD \(=10^8\), DEFAULT_N \(=10^{11}\) and a sieve cutoff PRECOMP_LIMIT \(=25000000\). The struct TotientSummatory owns Section 10. Its constructor runs a linear sieve filling phi up to limit, the smaller of PRECOMP_LIMIT and the max_n it is handed, reaching each composite once through its smallest prime factor, then builds the uint32_t prefix tables pref_phi, pref_weighted and pref_weighted2 for \(\Phi\), \(\Psi_1\) and \(\Psi_2\). The methods phi_sum, phi_weighted_sum and phi_weighted2_sum read a table entry for small arguments and otherwise run the matching recurrence over the quotient blocks of \(\lfloor n/l\rfloor\), recursing and memoising into three unordered_maps keyed through FastHash, which mixes each key's bits before the bucket is chosen.

The power-sum helpers show the two ways of obeying Section 11. sum1_upto and sum2_upto build \(\sum m\) and \(\sum m^2\) whole in __int128, dividing by \(2\) and \(6\) there. sum3_upto cannot, since \(\bigl(\tfrac{n(n+1)}2\bigr)^2\) outgrows even __int128 here; it halves the even one of \(n\) and \(n+1\) exactly, then reduces both factors and multiplies and squares with mod_mul. sum_lpow_upto and sum_l2pow_upto take \(2^{n+1}\bmod 10^8\) as a parameter, so pow2_mod computes it once per block endpoint; its exponent is an unsigned __int128, since the first quantity needed is \(2^{(N+1)^2}\).

The function compute_T assembles the answer. After \(2^{(N+1)^2}\bmod 10^8\) and a short cut for \(N\lt2\) (no line carries three grid points, so \(U(N)=1+(N+1)^2\)), it walks \(\ell\) upward: for each start \(L\) it reads \(M_1=\lfloor N/L\rfloor\) and \(M_2=\lfloor N/(L+1)\rfloor\), takes the smaller of the last indices at which they stay constant as the block end, and collects the positive quotients into ms, using \((0,0,0)\) directly when \(M_2=0\). Sorting and uniquing ms makes each distinct quotient a single query; the triples of Section 7 go into precomp, then onto every block in ranges. Each block evaluates \(q_2,q_1,q_0\), converts them to \(p_2,p_1,p_0\), builds the six sums of Section 11 with the block length cnt, and contributes sum_pow \(-\) sum_poly; a block's term depends only on its own data, so the terms may be added in any order. Finally \(U(N)\) is subtracted from \(2^{(N+1)^2}\). Differences that may turn negative use mod_norm, though the three recurrences instead add MOD before subtracting, and products of residues use mod_mul, which widens to __int128; the sieve and prefix tables multiply directly within their ranges. Beforehand validate recomputes the five checkpoints and aborts on a mismatch, main having handed the constructor the larger of its optional target and \(100000\) so that \(T(10^5)\) is always covered.

The Python and Java files are thin drivers, not independent ports. Python looks for solutionsCpp/Euler415.cpp below its script's parent directory, Java below the working directory, and neither passes a target on, so both compute the default \(N\). Each compiles that source with clang++ or g++ at -O2 when the cached binary is missing or stale, runs it, and reads the value back with parse_output / parseOutput, which prefers a line matching answer:, then one containing =, else the last non-empty line. Each also scans the source for a --skip-checkpoints marker and forwards it when present; the current source has none, so validation always runs. Keeping the mathematics in one file avoids reproducing __int128 arithmetic in Java, which has no unsigned 128-bit type, and spares Python a \(2.5\cdot10^7\)-entry sieve.

Complexity and Verification

Let \(B\) be the sieve limit. Sieve and prefix tables cost \(O(B)\). The block walk gives \(O(\sqrt N)\) blocks — \(894424\) at \(N=10^{11}\) — each a constant number of modular multiplications plus a few exponentiations, so \(O(\sqrt N\log N)\) with the quotient sort. Of the \(632453\) positive quotients only \(3998\) exceed \(B\), and memoisation holds their combined cost to \(O(N/\sqrt B)\), giving \(O(B+N/\sqrt B+\sqrt N\log N)\). That is minimised by \(B\sim(N/2)^{2/3}\approx1.4\cdot10^7\), which would give \(O\bigl(N^{2/3}\bigr)\); the program does not tune \(B\) but caps it at \(25000000\), just above that optimum. The totient array and its prefix tables dominate memory at about \(400\) MB, with \(57\) MB and \(29\) MB in the two block tables and more in the quotient list and maps; the \(25\) MB flag array lives only inside the constructor. Measured on one machine at -O2, peak resident size was about \(0.6\) GB and a sequential run took \(3.2\) seconds, both environment-dependent.

The program verifies itself against all five checkpoints on every run. These further checks were carried out for this article.

• Exhaustive enumeration of all subsets for \(N=0,1,2\) — \(2\), \(16\) and \(512\) of them — testing every pair for an ordinary line: \(T(0)=0\), \(T(1)=11\), \(T(2)=494\), and Section 2 holds with zero exceptions. Both statement examples behave as described, the six-point set's ordinary line holding only \((0,1)\) and \((2,0)\).
• A direct line enumeration for \(N\le8\) reproduces \(T(N)\) for \(N=1,\dots,8\) and the length profile of Section 3.
• The coefficients of Section 8 match a direct coprime-pair segment count for every \(\ell\) at \(N=2,\dots,59\), \(111\) and \(257\).
• The identities \(c=2\Phi-1\), \(s=3\Psi_1-1\), \(p=\Psi_2\) were checked against brute force for \(M\le44\); Section 4's telescoping identity for \(k\le39\); Section 11's exponential identities for \(n\le39\); Section 10's recurrences for \(x\le119\).
• An independent re-implementation in arbitrary-precision integers reproduces all five checkpoints and the exhaustive values for \(N\le8\).

These computations check the counting identities and their implementation; the classification of Section 2 rests on the cited Sylvester–Gallai theorem.

Footnotes and References

The sources below supply the background facts used above; the reduction to the complement, the telescoping identity, the segment argument and the block quadratic are derived here.

1. Project Euler 415 — Titanic Sets. The official statement calls a set of lattice points titanic when some line passes through exactly two of its points, defines T(N) on the grid 0 ≤ x, y ≤ N, and lists the checkpoints T(1) = 11, T(2) = 494, T(4) = 33554178, T(111) mod 10⁸ = 13500401 and T(10⁵) mod 10⁸ = 63259062 before asking for T(10¹¹) mod 10⁸.
2. Wikipedia — Sylvester–Gallai theorem. Every finite set of points in the Euclidean plane has either a line through exactly two of them — an ordinary line — or a line through all of them; equivalently, every finite non-collinear set has an ordinary line, the form used in Section 2. The article notes that finiteness is essential and that the result fails over the complex numbers.
3. Wikipedia — Euler's totient function. φ(n) counts the integers in [1, n] coprime to n. The article states Gauss's property that the sum of φ(d) over the positive divisors d of n equals n, the identity behind all three recurrences of Section 10.
4. Wikipedia — Coprime integers. The article characterises a coprime pair (a, b) by the absence of any lattice point strictly between the origin and (a, b), the visibility criterion used for primitive vectors in Section 5.
5. OEIS A018805. The number of pairs (x, y) with 1 ≤ x, y ≤ n and gcd(x, y) = 1, beginning 1, 3, 7, 11, 19, 23, 35, 43, with the stated formula 2·(φ(1) + ⋯ + φ(n)) − 1: the c(M) of Section 7 with its closed form.
6. OEIS A011755. The partial sums of k·φ(k), beginning 1, 3, 9, 17, 37, 49, 91, 123 — the Ψ₁ of Section 7. Section 9 uses its first two terms, 1 and 3.
7. OEIS A319087. The partial sums of k²·φ(k), beginning 1, 5, 23, 55, 155, 227, 521, 777 — the Ψ₂ of Section 7, which supplies the coefficient of ℓ² in the block quadratic.
8. Wikipedia — Mertens function. The article records that the sum of M(⌊n/q⌋) over q = 1, …, n equals 1, the Möbius analogue of Section 10's relations, and gives O(x^(2/3) (log log x)^(1/3)) for isolated values of M(x) by combinatorial algorithms — the sublinear order Section 10 achieves.
9. C++ — Euler415.cpp. The linked immutable revision holds TotientSummatory, compute_T with the block walk of Section 8, the helpers of Section 11 and validate. It is the implementation record for this article; the re-implementation and sweeps above are extra validation, not tests in that file.