Problem 410: Circle and Tangent Line

Detailed mathematical approach

Problem Summary

Let \(C\) be the circle \(x^2+y^2=r^2\) of radius \(r\). We choose two points \(P(a,b)\) and \(Q(-a,c)\) so that the line through \(P\) and \(Q\) is tangent to \(C\). The statement's example is \((r,a,b,c)=(2,6,2,-7)\): the line through \((6,2)\) and \((-6,-7)\) touches the circle of radius \(2\). Let \(F(R,X)\) be the number of integer quadruplets \((r,a,b,c)\) with this property and with \(0\lt r\le R\) and \(0\lt a\le X\); the heights \(b\) and \(c\) are unrestricted integers, positive, negative or zero. We must find \(F(10^8,10^9)+F(10^9,10^8)\). The statement gives the checkpoints \(F(1,5)=10\), \(F(2,10)=52\) and \(F(10,100)=3384\). ^[1]

The whole solution in one sentence: tangency forces \(a^2\) to split into two factors, every splitting reduces to a pair of coprime squares, and the only conditions that survive are one divisibility and one parity test, which turn \(F(R,X)\) into a single weighted sum of products of two floor divisions.

Mathematical Approach

1. Tangency as one equation

Because \(a\gt0\), the points \(P\) and \(Q\) have different abscissae and always determine one non-vertical line, which is tangent to \(C\) exactly when its distance from the centre \((0,0)\) is \(r\). For the line through \((x_1,y_1)\) and \((x_2,y_2)\) that distance is ^[2]

$$\frac{|x_2y_1-y_2x_1|}{\sqrt{(y_2-y_1)^2+(x_2-x_1)^2}}.$$

With \((x_1,y_1)=(a,b)\) and \((x_2,y_2)=(-a,c)\) the numerator is \(|{-ab}-ca|=a|b+c|\) and the radicand is \((c-b)^2+4a^2\). Tangency therefore says \(a|b+c|=r\sqrt{(c-b)^2+4a^2}\), and squaring both sides, which are non-negative, gives the equation we use throughout:

$$a^2(b+c)^2=r^2\bigl((c-b)^2+4a^2\bigr).$$

The statement's example fits: \(36\cdot(-5)^2=900\) on the left and \(4\cdot(81+144)=900\) on the right.

2. Sum and difference coordinates

Put \(s=b+c\) and \(d=c-b\). The pair \((b,c)\) can be recovered as \(b=(s-d)/2\) and \(c=(s+d)/2\), so \((b,c)\mapsto(s,d)\) is a bijection from integer pairs onto the integer pairs with \(s\equiv d\pmod 2\). In these coordinates the equation is

$$a^2s^2=r^2\bigl(d^2+4a^2\bigr).$$

3. A hidden factorisation of \(a^2\)

Define \(w=a|s|/r\). Dividing the equation of Section 2 by \(r^2\) gives \(w^2=d^2+4a^2\), a positive integer. A non-negative rational whose square is an integer is itself an integer: writing \(w=p/q\) in lowest terms, \(p^2=w^2q^2\) shows that \(q^2\) divides \(p^2\), while \(\gcd(p,q)=1\) forces \(\gcd(p^2,q^2)=1\), so \(q=1\). (This is the rational root theorem for a monic quadratic.) ^[3] Moreover \(w^2=d^2+4a^2\gt d^2\), hence \(w\gt|d|\ge0\), so \(w\ge1\) and \(s\ne0\). Finally \(w^2-d^2=4a^2\) is divisible by \(4\), which is impossible if \(w\) and \(d\) have different parities; so \(w\equiv d\pmod 2\) and

$$u=\frac{w-d}{2},\qquad v=\frac{w+d}{2}$$

are positive integers with

$$\begin{aligned}uv&=\frac{w^2-d^2}{4}=a^2,\\v-u&=d,\\u+v&=w.\end{aligned}$$

Conversely, start from an ordered pair \((u,v)\) of positive integers with \(uv=a^2\) and a sign \(\varepsilon=\pm1\), and put \(d=v-u\), \(w=u+v\) and \(s=\varepsilon\,rw/a\). Then

$$\begin{aligned}a^2s^2&=r^2w^2\\&=r^2\bigl((v-u)^2+4uv\bigr)\\&=r^2\bigl(d^2+4a^2\bigr),\end{aligned}$$

so the equation of Section 2 holds automatically; only the integrality of \(s\), \(b\) and \(c\) has to be checked.

Claim. For fixed \(r\) and \(a\), the quadruplets counted by \(F\) correspond one to one with the pairs \(\bigl((u,v),\varepsilon\bigr)\) in which \(u,v\) are positive integers with \(uv=a^2\), the sign \(\varepsilon\) is \(\pm1\), and the two conditions

$$\begin{aligned}&a\mid r(u+v),\\&\frac{r(u+v)}{a}\equiv v-u \pmod 2\end{aligned}$$

hold. The first condition makes \(s\) an integer and the second makes \(b\) and \(c\) integers. Neither mentions \(\varepsilon\), so an admissible splitting yields exactly \(2\) quadruplets.

4. Worked example: the nine splittings of \(36\)

Take \(a=6\), so \(a^2=36\). The nine ordered pairs \((u,v)\) with \(uv=36\), each with \(w=u+v\) and \(d=v-u\), are

• \((1,36)\) and \((36,1)\): \(w=37\), \(d=\pm35\);
• \((2,18)\) and \((18,2)\): \(w=20\), \(d=\pm16\);
• \((3,12)\) and \((12,3)\): \(w=15\), \(d=\pm9\);
• \((4,9)\) and \((9,4)\): \(w=13\), \(d=\pm5\);
• \((6,6)\): \(w=12\), \(d=0\).

Let \(r=2\). The first condition \(6\mid 2w\) means \(3\mid w\), which holds only for \(w=15\) and \(w=12\). For \((3,12)\) we get \(rw/a=5\) and \(d=9\), whose difference \(-4\) is even; for \((6,6)\) we get \(rw/a=4\) and \(d=0\). So three splittings survive, each with two signs, giving six quadruplets with \(r=2\) and \(a=6\): from \((3,12)\) the pairs \((b,c)=(-2,7)\) and \((-7,2)\), from \((6,6)\) the pairs \((2,2)\) and \((-2,-2)\), and from \((12,3)\) the pairs \((7,-2)\) and \((2,-7)\). The last one is the statement's example.

5. Every splitting has a coprime core

Let \(g=\gcd(u,v)\) and write \(u=gu_0\), \(v=gv_0\) with \(\gcd(u_0,v_0)=1\). From \(g^2u_0v_0=a^2\) we get \(u_0v_0=(a/g)^2\), where \(a/g\), a rational with integral square, is again an integer. ^[3] Now \(u_0v_0\) is a perfect square whose two factors are coprime, so by unique factorisation every prime occurs in exactly one of \(u_0,v_0\), and there to an even exponent. ^[4] Hence \(u_0=x^2\) and \(v_0=y^2\) for coprime positive integers \(x,y\), and

$$u=gx^2,\quad v=gy^2,\quad a=gxy.$$

Conversely every triple \((g,x,y)\) with \(\gcd(x,y)=1\) and \(gxy=a\) produces a splitting, and the two constructions invert each other, since \(g=\gcd(u,v)\), \(x=\sqrt{u/g}\) and \(y=\sqrt{v/g}\). In the new parameters

$$w=g(x^2+y^2),\qquad d=g(y^2-x^2).$$

For \(a=6\) the splitting \((3,12)\) has \(g=3\), \(x=1\), \(y=2\), while \((4,9)\) has \(g=1\), \(x=2\), \(y=3\), and \((6,6)\) has \(g=6\), \(x=y=1\).

6. The divisibility condition becomes \(m\mid r\)

Write \(m=xy\), so that \(a=gm\). The first condition of Section 3, \(a\mid rw\), reads \(gm\mid rg(x^2+y^2)\), that is \(m\mid r(x^2+y^2)\). The two factors are coprime: if a prime \(\ell\) divides \(m=xy\) then it divides \(x\) or \(y\), say \(x\); if \(\ell\) also divided \(x^2+y^2\) it would divide \(y^2\) and hence \(y\), contradicting \(\gcd(x,y)=1\). So \(\gcd(m,x^2+y^2)=1\) and the condition reads

$$m\mid r.$$

Since \(a=gm\) we also have \(m\mid a\), so a splitting can contribute only when \(m\) divides \(\gcd(r,a)\). Writing \(r=m\rho\), the value \(s\) of Section 3 has absolute value \(rw/a=\rho(x^2+y^2)\).

7. The parity condition

With \(\rho=r/m\) and \(g=a/m\) the second condition of Section 3 compares the two quantities \(\rho(x^2+y^2)\) and \(g(y^2-x^2)\) modulo \(2\). Since \(z^2\equiv z\pmod 2\) for every integer, both \(x^2+y^2\) and \(y^2-x^2\) are congruent to \(x+y\). If \(m=xy\) is odd then \(x\) and \(y\) are both odd, \(x+y\) is even, both quantities are even and the condition holds for every \(\rho\) and \(g\). If \(m\) is even then exactly one of the coprime numbers \(x,y\) is even, \(x+y\) is odd, and the condition becomes

$$\frac{r}{m}\equiv\frac{a}{m}\pmod 2,$$

which is the same as \(2m\mid r-a\). In both cases only the parity of \(m\) matters, not \(x\) and \(y\) themselves.

8. How many quadruplets belong to one pair \((r,a)\)

Fix \(m\). The number of ordered pairs \((x,y)\) with \(xy=m\) and \(\gcd(x,y)=1\) is \(2^{\omega(m)}\), where \(\omega(m)\) counts the distinct prime divisors of \(m\): ^[5] by unique factorisation each of the \(\omega(m)\) prime powers in \(m\) must go entirely to \(x\) or entirely to \(y\). Equivalently, \(x\) runs through the unitary divisors of \(m\). ^[6] Each pair fixes \(g=a/m\) and hence one splitting, worth \(2\) quadruplets. Combining Sections 3 to 7:

Claim. For fixed \(r,a\ge1\), the number \(G(r,a)\) of integer pairs \((b,c)\) making the line through \((a,b)\) and \((-a,c)\) tangent to \(x^2+y^2=r^2\) is

$$G(r,a)=2\sum_{m\in D(r,a)}2^{\omega(m)},$$

where \(D(r,a)\) consists of those divisors \(m\) of \(\gcd(r,a)\) that are odd, together with those even ones for which \(2m\) divides \(r-a\).

Two instances. For \(r=2\), \(a=6\): \(\gcd=2\), the divisor \(m=1\) is odd and contributes \(1\), and \(m=2\) is even with \(2m=4\) dividing \(r-a=-4\), contributing \(2\); so \(G(2,6)=2(1+2)=6\), exactly the six quadruplets listed in Section 4. For \(r=1\) only \(m=1\) is available, so \(G(1,a)=2\) for every \(a\) — the two horizontal tangents \(y=1\) and \(y=-1\), realised by \(b=c=1\) and \(b=c=-1\). This already gives the first checkpoint, \(F(1,5)=2\cdot5=10\).

A check on the weights: dropping both conditions, \(\sum_{m\mid a}2^{\omega(m)}\) must count all ordered splittings of \(a^2\), that is the number of divisors \(d(a^2)\). For \(a=6\) this reads \(1+2+2+4=9=d(36)\).

9. Summing over the rectangle

Now sum \(G\) over the rectangle and exchange the order of summation: instead of asking which \(m\) suit a given \((r,a)\), ask which \((r,a)\) suit a given \(m\). Write

$$t=\Bigl\lfloor\frac{R}{m}\Bigr\rfloor,\qquad h=\Bigl\lfloor\frac{X}{m}\Bigr\rfloor,$$

so that the multiples of \(m\) in range are \(r=m\rho\) with \(1\le\rho\le t\) and \(a=mg\) with \(1\le g\le h\). For odd \(m\) all \(th\) pairs are admissible. For even \(m\) only those with \(\rho\equiv g\pmod 2\) are, and their number is

$$\Bigl\lceil\frac t2\Bigr\rceil\Bigl\lceil\frac h2\Bigr\rceil+\Bigl\lfloor\frac t2\Bigr\rfloor\Bigl\lfloor\frac h2\Bigr\rfloor=\frac{th+\tau\eta}{2},$$

where \(\tau\) and \(\eta\) are the parities of \(t\) and \(h\); the identity follows from \(\lceil t/2\rceil=(t+\tau)/2\) and \(\lfloor t/2\rfloor=(t-\tau)/2\) by expanding both products. Since \(m\mid\gcd(r,a)\) forces \(m\le\min(R,X)\), we obtain the formula the programs evaluate:

$$F(R,X)=\sum_{m=1}^{\min(R,X)}2^{\omega(m)}\,U_m,$$

with \(U_m=2th\) when \(m\) is odd and \(U_m=th+\tau\eta\) when \(m\) is even. The factor \(2\) of the two signs has been absorbed into \(U_m\), which is why the even case loses the division by \(2\).

10. Worked example: \(F(10,100)=3384\)

Here \(\min(R,X)=10\), so there are ten terms. Each line below gives \(m\), the weight \(2^{\omega(m)}\), then \(t\), \(h\), \(U_m\) and the term. No even \(m\) here has both \(t\) and \(h\) odd, so the correction \(\tau\eta\) vanishes throughout.

• \(m=1\): \(1\), \(t=10\), \(h=100\), \(U=2000\), term \(2000\);
• \(m=2\): \(2\), \(t=5\), \(h=50\), \(U=250\), term \(500\);
• \(m=3\): \(2\), \(t=3\), \(h=33\), \(U=198\), term \(396\);
• \(m=4\): \(2\), \(t=2\), \(h=25\), \(U=50\), term \(100\);
• \(m=5\): \(2\), \(t=2\), \(h=20\), \(U=80\), term \(160\);
• \(m=6\): \(4\), \(t=1\), \(h=16\), \(U=16\), term \(64\);
• \(m=7\): \(2\), \(t=1\), \(h=14\), \(U=28\), term \(56\);
• \(m=8\): \(2\), \(t=1\), \(h=12\), \(U=12\), term \(24\);
• \(m=9\): \(2\), \(t=1\), \(h=11\), \(U=22\), term \(44\);
• \(m=10\): \(4\), \(t=1\), \(h=10\), \(U=10\), term \(40\).

The ten terms add up to \(3384\), the third checkpoint. The second shows the parity correction at work: for \(F(2,10)\), \(m=1\) gives \(1\cdot2\cdot2\cdot10=40\), and \(m=2\) has \(t=1\) and \(h=5\), both odd, so \(U_2=1\cdot5+1=6\) and the term is \(2\cdot6=12\); the total is \(40+12=52\). Without the correction \(\tau\eta\) the second term would be \(10\) and the total \(50\).

11. A symmetry and the size of the result

The quantity \(U_m\) is symmetric in \(t\) and \(h\), so \(F(R,X)=F(X,R)\) for all bounds: the requested total is twice one evaluation, although the geometry gives \(r\) and \(a\) quite different roles. For the size, \(U_m\le 2th\le 2RX/m^2\), so we need the sum of \(2^{\omega(m)}/m^2\). For real \(s\gt1\) let \(\zeta(s)=\sum_{n\ge1}n^{-s}\) be the Riemann zeta function, which unique factorisation turns into the Euler product \(\prod_p(1-p^{-s})^{-1}\). ^[6] In our sum every positive power of a prime \(p\) carries the weight \(2\), so the factor of \(p\) is

$$\begin{aligned}1+2\sum_{k\ge1}p^{-ks}&=\frac{1+p^{-s}}{1-p^{-s}}\\&=\frac{1-p^{-2s}}{(1-p^{-s})^2},\end{aligned}$$

and multiplying these factors over all primes gives the Dirichlet series of the weights,

$$\sum_{m\ge1}\frac{2^{\omega(m)}}{m^s}=\frac{\zeta(s)^2}{\zeta(2s)}.$$

At \(s=2\), where \(\zeta(2)=\pi^2/6\) and \(\zeta(4)=\pi^4/90\), this is exactly \(\tfrac52\), ^[6] so

$$F(R,X)\le 2RX\cdot\tfrac52=5RX,$$

and both values, and their sum, therefore stay comfortably inside the signed 64-bit range.

How the Code Works

All three programs evaluate the formula of Section 9 directly; the only preparation is a table of \(\omega\). The names below are the C++ ones; Java spells them buildDistinctPrimeCounts and solveF, called from solve, while the Python solve builds the sieve inline and defines solve_F as a nested function over the enclosing omega. ^[9]

build_distinct_prime_counts(limit) builds that table in three passes. First it marks the odd composites: a bit vector indexed by p >> 1, that is by \(\lfloor p/2\rfloor\), holds one flag per odd number, and for every still unmarked odd \(p\) up to the square root of the limit it marks \(p^2,\,p^2+2p,\,p^2+4p,\dots\), which is the sieve of Eratosthenes on the odd numbers. ^[7] Second it adds \(1\) to \(\omega(m)\) for every even \(m\), the contribution of the prime \(2\). Third, for every unmarked odd \(p\) it adds \(1\) to \(\omega(m)\) for all multiples \(m\) of \(p\). The entry \(\omega(1)\) stays \(0\), the correct weight \(1\), and the table holds bytes because \(\omega(m)\le8\) for \(m\le10^8\): the product of the first eight primes is \(9\,699\,690\), while including \(23\) gives \(223\,092\,870\).

solve_F_with_omega(R, X, omega, …) is the loop of Section 9. It sets limit = min(R, X) and for each \(m\) reads t = R / m, g = X / m and weight = 1ULL << omega[m], then forms unit as 2 * t * g for odd \(m\) and as t * g + ((t & 1) & (g & 1)) for even \(m\) — the \(th+\tau\eta\) of Section 9, the bitwise and of the low bits being \(\tau\eta\) — and accumulates weight * unit. solve_F is the same routine with the sieve built on the spot, which is how the checkpoints call it.

main builds one table for the larger of the two values of \(\min(R,X)\) (both are \(10^8\) here), evaluates the first \(F\), and reuses that value for the second pair when the second pair is the first one swapped, which is the symmetry of Section 11.

brute_force_reference(R, X) is the slow reference. For every \(r\le R\) and \(a\le X\) it tries every \(u\) from \(1\) to \(a^2\), keeps the divisors of \(a^2\), sets \(v=a^2/u\), \(d=v-u\), \(k=u+v\), and applies the two tests of Section 3, namely \(a\mid rk\) and the parity of \(rk/a-d\), adding \(2\) for the two signs. It thus enumerates the bijection of Section 3 one splitting at a time, testing the regrouping of Sections 5 to 9 but not the geometry.

run_checkpoints compares the fast routine with the statement's three values, then checks that brute_force_reference(12, 20) gives \(824\) and that the fast routine agrees, and under the default options evaluates \(F(200\,000,300\,000)\) twice, accumulating the terms in two different orders and requiring the two results to agree. The C++ command line can override the four bounds and skip the checkpoints, which produced the smaller values quoted here; the Python and Java programs use fixed bounds and carry no checks of their own.

The implementations also differ in arithmetic and bookkeeping. The C++ accumulates in unsigned __int128 and prints through a hand-written decimal conversion; Java emulates that width with a sumHi/sumLo pair, detecting carries with Long.compareUnsigned, and converts to BigInteger at the end; Python uses its unbounded integers. By Section 11 even 64 bits would suffice, and no single product weight * unit exceeds \(2RX\), since \(2^{\omega(m)}/m^2\le1\) for every \(m\). Java keeps its odd-composite flags in a byte[] rather than a bit vector, eight times the memory, and Python mirrors the sieve with two bytearrays and has no symmetry shortcut, so it evaluates the \(10^8\)-term sum twice.

Complexity and Verification

Let \(L=\min(R,X)\), which is \(10^8\) for both requested pairs. Marking the odd composites costs \(O(L\log\log L)\) operations ^[7] and performs \(96\,285\,414\) writes at \(L=10^8\). The two counting passes increment once for each pair of a prime \(p\le L\) and a multiple of \(p\), that is \(\sum_{p\le L}\lfloor L/p\rfloor\) times, exactly \(315\,037\,281\) here with \(5\cdot10^7\) of them from the prime \(2\); before the quotients are rounded down, Mertens' estimate \(\sum_{p\le L}1/p\approx\log\log L+M\) with \(M\approx0.2615\) predicts about \(3.17\cdot10^8\). ^[5] The summation itself is \(O(L)\): two floor divisions, a shift and a few multiplications per term. The method is therefore \(O(L\log\log L)\) in time and \(O(L)\) in memory, the sieve tables dominating storage: at \(L=10^8\) about \(106\) MB in C++, namely \(100\) MB for the byte table and \(6.25\) MB for the packed odd flags, and about \(150\) MB in Java and Python, which store the flags one byte each.

One run of each program on the same machine needed about \(0.6\) seconds and \(108\) MB of resident memory for the C++ version, \(0.7\) seconds of wall time and \(200\) MB for Java, and \(40\) seconds and \(164\) MB for Python, the last consistent with the two sums it evaluates instead of one. Resident memory exceeds the table sizes by runtime overhead, largest for Java.

Beyond the packaged checkpoints, separate programs were run for this article. The first goes back to the original equation, over a search interval taken from Section 3: since \(u,v\ge1\) and \(uv=a^2\), the inequality \((u-1)(v-1)\ge0\) gives \(u+v\le a^2+1\), and \(|v-u|\le a^2-1\), so \(|s|\le r(a^2+1)/a\) and \(|d|\le a^2-1\), which bounds \(b=(s-d)/2\). For every \(b\) in that interval the program solves

$$\begin{aligned}(a^2-r^2)c^2&+2b(a^2+r^2)c\\&+(a^2-r^2)b^2-4a^2r^2=0\end{aligned}$$

for \(c\) in exact integer arithmetic, treating the degenerate case \(a=r\) separately, where the condition collapses to \(bc=a^2\). For \(a\ne r\) the discriminant is \(16a^2r^2(a^2+b^2-r^2)\), that is \(16a^2r^2\) times the power \(a^2+b^2-r^2\) of the point \(P\) with respect to \(C\), so an integer root needs an integral tangent length from \(P\) ^[8] and, beyond that, a numerator divisible by \(2(a^2-r^2)\). Apart from that search interval the check uses nothing from Sections 5 to 9 and no sieve: it solves the tangency equation itself. It agrees with the formula for every \(R,X\le12\), among them \(F(1,5)=10\), \(F(2,10)=52\), \(F(3,7)=58\) and \(F(5,5)=70\), and separately at \(F(12,20)=824\). The remaining checks were these.

• The claim of Section 8: \(G(r,a)\) agrees with the geometric count for every \(r,a\le16\), and summing \(G\) over the rectangle agrees with the closed formula for all \(R,X\le15\).
• The weight: the number of ordered coprime pairs \((x,y)\) with \(xy=m\) equals \(2^{\omega(m)}\) for all \(m\le2000\), and \(\sum_{m\mid a}2^{\omega(m)}=d(a^2)\) for all \(a\le2000\).
• The parity identity of Section 9 for all \(0\le t,h\lt60\), and the partial sum of \(2^{\omega(m)}/m^2\) over \(m\le4000\), which is approximately \(2.498239\) and approaches the limit \(\tfrac52\) of Section 11.
• The symmetry \(F(R,X)=F(X,R)\) for all \(R,X\le30\) and at \((10^3,10^4)\); and the published sieve reproduces \(\omega(m)\) from a factorisation of every \(m\le200\,000\).
• Agreement between the implementations: the C++ program and an independent Python evaluation of the formula both give \(F(10^4,10^5)=3\,996\,520\,500\), and at the requested bounds the three programs' outputs have matching checksums.

Two notes on robustness, not on the result: the sieve takes \(\sqrt{L}\) from a floating-point square root, exact at \(L=10^8\) but able to undershoot by one for far larger limits, which would leave the square of a prime unmarked; and 2 * t * g would overflow 64 bits for bounds beyond a few times \(10^9\). Both are safe here.

Footnotes and References

The references below supply the background facts used above. The bijection between quadruplets and splittings of \(a^2\), the coprime parameters of Section 5, the two arithmetic conditions, the count \(G(r,a)\) and the closed formula are derived explicitly in this article.

1. Project Euler 410 — Circle and Tangent Line. The official statement defines F(R, X) as the number of integer quadruplets (r, a, b, c) for which the line through P(a, b) and Q(−a, c) is tangent to the circle x² + y² = r², with 0 < r ≤ R and 0 < a ≤ X, gives the example (2, 6, 2, −7) and the three values quoted in the summary, and asks for F(10⁸, 10⁹) + F(10⁹, 10⁸).
2. Wikipedia — Distance from a point to a line. Under "Line defined by two points" the article gives the distance from (x₀, y₀) to the line through (x₁, y₁) and (x₂, y₂) as |(y₂ − y₁)x₀ − (x₂ − x₁)y₀ + x₂y₁ − y₂x₁| over the square root of (y₂ − y₁)² + (x₂ − x₁)². At the origin only x₂y₁ − y₂x₁ survives, which is Section 1.
3. Wikipedia — Rational root theorem. A rational root p/q in lowest terms of a polynomial with integer coefficients has q dividing the leading coefficient, and the article states the monic case separately as the integral root theorem. Sections 3 and 5 use the consequence that a rational number whose square is an integer is an integer.
4. Wikipedia — Fundamental theorem of arithmetic. Every integer greater than 1 is a product of primes, uniquely up to order, and the article writes each integer in canonical form as a product of prime powers with uniquely determined exponents. Sections 5 and 8 split the exponents of a square between two coprime factors this way.
5. Wikipedia — Prime omega function. The article defines ω(n) as the number of distinct prime factors of n, notes that ω is additive and gives log log n as an average order — the quantity that appears, through Mertens' estimate for the sum of reciprocals of primes, in the sieve's operation count.
6. OEIS A034444 — number of unitary divisors. The entry counts the divisors d of n with gcd(d, n/d) = 1 and gives both a(n) = 2 raised to ω(n) and the Dirichlet generating function zeta(s)²/zeta(2s), used in Sections 8 and 11. NIST DLMF §25.2 defines the zeta series in equation 25.2.1 and its Euler product over the primes in 25.2.11, both for Re s > 1, and equation 25.6.1 lists ζ(2) = π²/6 and ζ(4) = π⁴/90.
7. Wikipedia — Sieve of Eratosthenes. The article marks the multiples of each prime, states that the outer loop need not exceed the square root of the limit, and gives the running time as O(n log log n) when each array update is O(1).
8. Wikipedia — Power of a point. The power of P with respect to a circle of centre O and radius r is |PO|² − r²; it is positive exactly when P lies outside the circle and then equals the squared length of the tangent segment from P. It is the factor a² + b² − r² of the discriminant in the geometric check.
9. C++ — Euler410.cpp. The linked immutable revision contains build_distinct_prime_counts, solve_F_with_omega, brute_force_reference and the checkpoints at F(1, 5), F(2, 10), F(10, 100) and F(12, 20). It is the implementation record for this article; the additional checks listed above are not packaged in it.