Detailed mathematical approach

Problem Summary

The point set is generated by

$x_n=(1248^n \bmod 32323)-16161,\qquad y_n=(8421^n \bmod 30103)-15051,$

and \(P_n=\{(x_1,y_1),\dots,(x_n,y_n)\}\). We must compute \(C(n)\), the number of triangles with vertices in \(P_n\) that contain the origin strictly in their interior. The published checkpoints are \(C(8)=20\), \(C(600)=8950634\), and \(C(40000)=2666610948988\).

Mathematical Approach

Step 1: Replace each point by its primitive direction

Write a nonzero point as \(p=(x,y)\), let

$g=\gcd(|x|,|y|),\qquad d(p)=\left(\frac{x}{g},\frac{y}{g}\right).$

Then \(d(p)\) is the primitive lattice direction of \(p\). If \(p=r\,d\) with \(r\gt 0\), the condition that the origin lies strictly inside the triangle \(\operatorname{conv}(p_1,p_2,p_3)\) is equivalent to the existence of positive barycentric coefficients:

$0\in \operatorname{int}\operatorname{conv}(p_1,p_2,p_3)\iff \exists \lambda_1,\lambda_2,\lambda_3\gt 0,\ \lambda_1+\lambda_2+\lambda_3=1,\ \lambda_1p_1+\lambda_2p_2+\lambda_3p_3=0.$

After substituting \(p_t=r_t d_t\), this becomes a positive linear relation among the directions \(d_t\), so only the ray of each point matters. Therefore the implementations group equal primitive directions and store only their multiplicities. Let the distinct direction classes be \(d_1,\dots,d_m\) with weights \(w_1,\dots,w_m\).

If two chosen vertices come from the same direction class, they lie on the same ray from the origin. Such a triangle cannot strictly contain the origin, so every valid triangle must use three distinct direction classes.

Step 2: Count all weighted triples of distinct directions

The weighted number of ways to choose one point from each of three distinct direction classes is

$T_{\mathrm{distinct}}=\sum_{1\le i\lt j\lt k\le m} w_i w_j w_k.$

Introduce the power sums

$W=\sum_{i=1}^{m} w_i,\qquad S_2=\sum_{i=1}^{m} w_i^2,\qquad S_3=\sum_{i=1}^{m} w_i^3.$

Expanding \((\sum_i w_i)^3\) and collecting equal-index patterns gives the elementary symmetric sum identity

$\boxed{T_{\mathrm{distinct}}=\frac{W^3-3WS_2+2S_3}{6}.}$

This counts every choice from three different direction classes, regardless of whether the origin ends up inside, outside, or on the boundary.

Step 3: Characterize the invalid triples geometrically

For three distinct directions there are exactly two ways to fail the strict interior condition.

First, one pair may be opposite directions. Then the segment joining those two vertices passes through the origin, so the origin lies on the boundary of the triangle rather than in its interior.

Second, all three directions may lie inside a single open semicircle. In that case there exists a line through the origin with all three vertices on the same open side, so the origin is strictly outside the triangle.

Conversely, if there is no opposite pair and the three directions are not contained in any open semicircle, then the three rays wrap completely around the origin, which forces the origin to be strictly inside the triangle. So the answer is obtained by subtracting exactly these two invalid families from \(T_{\mathrm{distinct}}\).

Step 4: Boundary triples coming from opposite directions

Consider one unordered opposite pair \(\{d,-d\}\) with weights \(a\) and \(b\). A boundary triangle is formed by choosing one point from each of these two classes and a third point from any other class, so the contribution is

$a\,b\,(W-a-b).$

Summing over all unordered opposite pairs gives

$\boxed{B=\sum_{\{d,-d\}} w_d\,w_{-d}\,(W-w_d-w_{-d}).}$

This term removes every triple for which the origin lies on an edge.

Step 5: Count triples contained in one open semicircle

Sort the direction classes by polar angle around the origin. The implementations do this exactly, without floating-point angles: directions are split into two half-planes, and within the same half-plane the sign of the determinant

$\det(a,b)=a_x b_y-a_y b_x$

determines angular order.

Fix an anchor direction \(d_i\). Move a second pointer forward while the next direction still satisfies

$\det(d_i,d_j)\gt 0,$

which is equivalent to saying that the angular difference from \(d_i\) is strictly between \(0\) and \(\pi\). Thus the window \(i+1,\dots,j-1\) contains exactly the directions that lie with \(d_i\) in one open semicircle.

Let

$A_i=\sum_{k=i+1}^{j-1} w_k,\qquad Q_i=\sum_{k=i+1}^{j-1} w_k^2.$

The weighted number of unordered pairs of distinct direction classes inside this window is

$\sum_{i\lt u\lt v\lt j} w_u w_v=\frac{A_i^2-Q_i}{2}.$

Multiplying by the anchor weight \(w_i\) yields the contribution of all invalid triangles whose smallest angle in circular order is \(d_i\):

$w_i\frac{A_i^2-Q_i}{2}.$

Every triple contained in an open semicircle is counted exactly once in this scheme, namely at its first direction in the circular order. Therefore

$\boxed{O=\sum_{i=1}^{m} w_i\frac{A_i^2-Q_i}{2}.}$

Step 6: Final formula

Subtracting both invalid contributions gives the desired count:

$\boxed{C(n)=T_{\mathrm{distinct}}-O-B.}$

This is the complete formula implemented in all three languages.

How the Code Works

The C++, Python, and Java implementations generate the modular sequences iteratively, normalize each point with a greatest-common-divisor reduction, and store the resulting primitive directions. They first sort these normalized directions lexicographically so equal directions can be merged into weighted classes. From those weights they compute \(W\), \(S_2\), \(S_3\), and therefore \(T_{\mathrm{distinct}}\).

Next, the implementation searches the merged direction list for opposite classes and accumulates the boundary term \(B\). After that, the same weighted direction classes are sorted again by exact angular order. A duplicated circular array and prefix sums of \(w_i\) and \(w_i^2\) allow the two-pointer sweep to evaluate every window sum \(A_i\) and \(Q_i\) in constant time, so the open-semicircle term \(O\) is obtained in one linear scan after sorting.

Complexity Analysis

Let \(n\) be the number of generated points and \(m\) the number of distinct primitive directions. Sequence generation and normalization cost \(O(n)\) time. The implementations then sort all \(n\) normalized directions before compression, so that stage costs \(O(n\log n)\) time and uses \(O(n)\) memory. Merging equal directions is \(O(n)\), finding opposite classes with ordered search is \(O(m\log m)\), sorting the \(m\) direction classes by angle is \(O(m\log m)\), and the two-pointer sweep with prefix sums is \(O(m)\). The overall running time is therefore dominated by \(O(n\log n)\), and the implemented memory usage is \(O(n)\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=456
2. Barycentric coordinates and point-in-triangle tests: Wikipedia — Barycentric coordinate system
3. Cross product and planar orientation: Wikipedia — Cross product
4. Rotating calipers and angular sweeps: Wikipedia — Rotating calipers