Detailed mathematical approach

Problem Summary

A lenticular hole is the convex region enclosed by two circles such that both centres are lattice points, the two circles intersect at two distinct lattice points, and the interior of the lens contains no lattice points. A lenticular pair is an ordered radius pair \((r_1,r_2)\) for which such two circles exist. We must count distinct pairs with

$0 < r_1 \le r_2 \le N.$

Mathematical Approach

1. Normalizing the common chord

Take two lattice intersection points \(P,Q\). After a translation we may assume

$P=(0,0),\qquad Q=(a,b).$

Only the difference vector matters. The code keeps only primitive vectors with

$\gcd(a,b)=1.$

If \(a\) and \(b\) had opposite parity, then the midpoint of \(PQ\) would have one integer and one half-integer coordinate, and the perpendicular bisector could not pass through two lattice centres. Since the vector is primitive, the only possible equal-parity case is that both \(a\) and \(b\) are odd. That is exactly why the search runs over primitive odd vectors.

Let

$s^2 = a^2+b^2.$

2. All lattice-centred circles through the same two lattice points

The midpoint of the chord is \((a/2,b/2)\), and the perpendicular direction is \((-b,a)\). Therefore every circle through \(P\) and \(Q\) has centre

$O_k=\left(\frac{a-kb}{2},\frac{b+ka}{2}\right)$

for some real parameter \(k\). Because \(a\) and \(b\) are both odd, \(O_k\) is a lattice point exactly when \(k\) is odd. So lattice-centred circles through the chord are indexed by odd integers \(k\).

The radius is the distance from \(O_k\) to \(P\):

$R_k^2=\left(\frac{a-kb}{2}\right)^2+\left(\frac{b+ka}{2}\right)^2 =\frac{(a^2+b^2)(1+k^2)}{4} =\frac{s^2(1+k^2)}{4}.$

This is the central formula used throughout the solver.

3. Why one primitive vector produces an arithmetic sequence of radii

For a fixed primitive odd \((a,b)\), every odd \(k\) gives a candidate radius. Choosing one circle on each side of the common chord corresponds to parameters \(-m\) and \(n\) with positive odd \(m,n\). Since

$R_k^2=\frac{s^2(1+k^2)}{4}$

depends only on \(|k|\), each primitive vector defines a whole increasing sequence of realized radius squares.

Two examples from the problem statement appear immediately:

Family \((a,b)=(1,1)\). Here \(s^2=2\) and the threshold turns out to be \(t=1\). The odd values \(k=1,3,5,7,\ldots\) give

$R^2=1,5,13,25,\ldots$

so the pair \((1,5)\) is obtained from \(k=1\) and \(k=7\).

Family \((a,b)=(1,3)\). Here \(s^2=10\) and \(t=3\). Then \(k=3,5,7,\ldots\) gives

$R^2=25,65,125,\ldots$

so \((5,\sqrt{65})\) comes from \(k=3\) and \(k=5\).

4. The no-interior-lattice-point condition and the threshold \(t(a,b)\)

The subtle part is deciding which odd parameters are actually valid. The lens must not contain any lattice point in its interior. For a fixed chord direction \((a,b)\), lattice points near the chord lie on the parallel lattice lines

$-bx+ay=c,\qquad c\in\mathbb Z.$

Because \(\gcd(a,b)=1\), the closest nonzero parallel lines are

$-bx+ay=\pm 1.$

It is enough to analyse one of them, say \(-bx+ay=1\), because the other side is symmetric.

Now define

$A=ax+by.$

For lattice points on \(-bx+ay=1\), the code shows that the obstruction to keeping such a point outside the lens is controlled by the quadratic expression

$M(A)=A-\frac{A^2+1}{s^2}.$

The worst possible obstruction is the maximum of this quantity over all lattice points on that nearest line. If one particular solution of

$-bx+ay=1$

is \((x_0,y_0)\), then all other solutions differ by multiples of \((a,b)\), so \(A\) is determined modulo \(s^2\). That is why the code computes one residue

$A_0=ax_0+by_0,$

reduces it to the nearest representative

$r \in [0,s^2/2],$

and then evaluates

$M=r-\left\lfloor\frac{r^2+1}{s^2}\right\rfloor.$

The minimal valid odd parameter is the smallest odd integer not below \(M\), but at least \(1\):

$t(a,b)=\max\!\Bigl(1,\ \text{odd-ceiling}(M)\Bigr).$

The key geometric fact is that a lens formed by parameters \(-m\) and \(n\) is valid exactly when

$m\ge t(a,b),\qquad n\ge t(a,b).$

So every primitive vector produces not all odd \(k\), but only the odd tail

$k=t,\ t+2,\ t+4,\ldots$

until the global radius bound cuts it off.

5. Finite sequence generation under the radius bound

For a fixed family \((s^2,t)\), the largest admissible odd parameter is determined by

$R_k \le N \quad\Longleftrightarrow\quad \frac{s^2(1+k^2)}{4}\le N^2.$

Hence

$k_{\max}=\text{largest odd }k\text{ with }k^2\le \frac{4N^2}{s^2}-1.$

The code stores every realized occurrence as

$\bigl(R^2,\text{sequence id}\bigr).$

It uses \(R^2\) instead of \(R\) so that equality can be checked exactly with integers and no floating-point comparison is ever needed.

Different primitive vectors can lead to the same radius sequence, so generation is deduplicated by the pair \((s^2,t)\).

6. Membership sets for each distinct radius

After all occurrences are collected and sorted by \(R^2\), each distinct radius receives a small membership set

$I(R)=\{\text{sequence ids that realize }R\}.$

A pair \((r_1,r_2)\) is lenticular exactly when the two radii come from at least one common sequence family, namely when

$I(r_1)\cap I(r_2)\neq\varnothing.$

So the problem is no longer geometric; it has become a pure set-intersection counting problem.

7. Inclusion-exclusion for intersecting radius pairs

Let \(c_J\) be the number of distinct radii whose membership set contains a fixed nonempty id-subset \(J\):

$c_J=\#\{R:J\subseteq I(R)\}.$

Then \(\binom{c_J}{2}\) counts unordered pairs of distinct radii that share every id in \(J\). Summing over all nonempty \(J\) with alternating signs gives exactly the number of unordered distinct-radius pairs with nonempty intersection:

$\sum_{J\ne\varnothing}(-1)^{|J|+1}\binom{c_J}{2}.$

Finally, every realized radius also forms the diagonal pair \((R,R)\), so the solver adds the number of distinct radii at the end.

8. Checkpoints

The implementation validates itself with the values

$L(10)=30,\qquad L(100)=3442.$

These are the official sample results from the problem statement and confirm that both the geometric threshold logic and the set-counting phase are correct.

How the Code Works

compute_threshold_for_vector carries out the lattice-line analysis above and returns \(t(a,b)\). generate_sequences enumerates all primitive odd vectors, turns each into a deduplicated sequence \((s^2,t,k_{\max})\), and keeps only families that can produce some radius at most \(N\). build_occurrences expands each family into its realized \((R^2,\text{id})\) occurrences. After sorting, the code compresses equal radii into membership sets, accumulates all subset frequencies, applies inclusion-exclusion, and finally adds the diagonal \((R,R)\) pairs.

Complexity Analysis

If \(T\) is the total number of occurrences \((R^2,\text{id})\), sorting costs

$O(T\log T).$

Grouping equal radii is linear in \(T\). The inclusion-exclusion stage iterates over all nonempty subsets of each membership set. Since the membership size is empirically tiny (the code caps it at \(8\) for \(N=100000\)), this part stays practical. Memory usage is \(O(T)\).

Further Reading

1. Problem page: https://projecteuler.net/problem=295
2. Inclusion-exclusion principle: https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle
3. Geometry of numbers: https://en.wikipedia.org/wiki/Geometry_of_numbers