Detailed mathematical approach

Problem Summary

Let

$\mathcal{L}_n=\left\{(x,y)\in\mathbb{Z}^2\setminus\{(0,0)\}: \max(|x|,|y|)\le n\right\}.$

A polar polygon is obtained by choosing lattice points from \(\mathcal{L}_n\), taking at most one vertex on each directed ray from the origin, and reading the chosen vertices in increasing polar angle. The geometric condition used by the implementations is that the origin must lie in the convex hull of the chosen vertices. Equivalently, the chosen directions must not all lie inside one closed half-plane through the origin.

The task is to compute the number \(P(n)\) of such polygons modulo

$M=10^9+7.$

The implementations also contain the checkpoints

$P(1)=131,\qquad P(2)=1648531,\qquad P(3)\equiv 461288482 \pmod{M},\qquad P(343)\equiv 937293740 \pmod{M}.$

Mathematical Approach

The key simplification is to forget the exact coordinates first and classify vertices by direction. Every directed primitive ray carries a certain number of lattice points, and only that number matters for counting.

Step 1: Replace Lattice Points by Weighted Rays

Every nonzero lattice point can be written uniquely as

$t(a,b),\qquad t\ge 1,\qquad \gcd(a,b)=1,$

where \((a,b)\) gives a primitive direction. Define the level of that direction by

$k=\max(|a|,|b|).$

The points on this directed ray that still lie in \(\mathcal{L}_n\) are exactly

$t(a,b)\qquad\text{for}\qquad 1\le t\le \left\lfloor\frac{n}{k}\right\rfloor.$

So the ray contributes

$w(k)=\left\lfloor\frac{n}{k}\right\rfloor$

available lattice points. A valid polygon can use at most one vertex on a fixed directed ray, because two points on the same ray are collinear with the origin and the nearer one cannot be an extreme vertex. Therefore one directed ray contributes exactly

$1+w(k)$

choices: choose nothing, or choose one of its \(w(k)\) lattice points.

Step 2: Count Primitive Directions on One Square Shell

Fix \(k\ge 1\). Primitive directions of level \(k\) are precisely the visible lattice points on the boundary of the square \(\max(|x|,|y|)=k\).

In one octant there are \(\varphi(k)\) such directions, so symmetry gives

$8\varphi(k)$

directed primitive rays on that shell, or

$4\varphi(k)$

opposite-direction pairs. Every pair on level \(k\) has the same weight \(w(k)=\lfloor n/k\rfloor\).

Step 3: Group Shells by Equal Weight

The weight depends only on the quotient \(\left\lfloor n/k\right\rfloor\), not on the direction itself. If that quotient is constant and equal to \(u\) for all \(k\) in an interval \([a,b]\), then the number of opposite pairs with weight \(u\) is

$c(u)=4\sum_{k=a}^{b}\varphi(k).$

Introduce the summatory totient function

$\Phi(x)=\sum_{m\le x}\varphi(m).$

Then every quotient block contributes

$c(u)=4\bigl(\Phi(b)-\Phi(a-1)\bigr).$

This is the reason the problem collapses to only \(O(\sqrt n)\) distinct blocks: the values of \(\left\lfloor n/k\right\rfloor\) repeat on long intervals.

Step 4: Count All Selections Before Enforcing the Polygon Condition

Let the opposite pairs have weights \(w_1,\dots,w_m\). For one pair there are four types of choices:

For one pair the four possibilities are: choose nothing, choose one point on the first ray, choose one point on the opposite ray, or choose one point on each ray.

Hence one pair contributes

$1+w_i+w_i+w_i^2=(1+w_i)^2.$

If we define

$H=\prod_{i=1}^{m}(1+w_i),$

then the total weighted count of all ray selections is

$T=H^2.$

After quotient blocking, the same product becomes

$H=\prod_{u}(u+1)^{c(u)}.$

Step 5: Subtract Selections Contained in a Closed Half-Plane

A selection fails precisely when all chosen directions lie in some closed semicircle. Count such bad selections by choosing their first selected boundary direction.

Fix one directed boundary ray with weight \(w_i\). We must choose a point on that boundary ray, giving \(w_i\) possibilities. Every other opposite pair contributes exactly one direction inside the following open semicircle, so it contributes a factor \(1+w_j\). The opposite boundary ray itself may be used or skipped, contributing another factor \(1+w_i\). Therefore the count anchored at this directed boundary is

$w_i\prod_{j=1}^{m}(1+w_j)=w_iH.$

Summing over both orientations of every opposite pair yields

$2H\sum_{i=1}^{m}w_i.$

However, the subset consisting of one point on both rays of the same opposite pair is counted twice, once from each boundary orientation. The total correction for these double counts is

$\sum_{i=1}^{m} w_i^2.$

Adding the empty selection gives

$B=1+2HA_1-A_2,$

where

$A_1=\sum_{i=1}^{m} w_i,\qquad A_2=\sum_{i=1}^{m} w_i^2.$

Therefore

$P(n)=T-B=H^2-1-2HA_1+A_2.$

Step 6: Final Formula in Quotient Blocks

Because all pairs in one block have the same weight \(u\), the two moments become

$A_1=\sum_{u} c(u)\,u,\qquad A_2=\sum_{u} c(u)\,u^2.$

Substituting into the previous formula gives the exact expression used by the implementations:

$\boxed{P(n)\equiv \left(\prod_{u}(u+1)^{c(u)}\right)^2-1-2\left(\prod_{u}(u+1)^{c(u)}\right)\left(\sum_{u} c(u)\,u\right)+\sum_{u} c(u)\,u^2 \pmod{M}.}$

Worked Example: \(n=2\)

For \(n=2\) there are only two shell levels:

$\left\lfloor\frac{2}{1}\right\rfloor=2,\qquad \left\lfloor\frac{2}{2}\right\rfloor=1.$

The level \(k=1\) shell contributes

$4\varphi(1)=4$

opposite pairs of weight \(2\), and the level \(k=2\) shell contributes

$4\varphi(2)=4$

opposite pairs of weight \(1\). Hence

$H=(1+2)^4(1+1)^4=3^4\cdot 2^4=1296,$

$A_1=4\cdot 2+4\cdot 1=12,\qquad A_2=4\cdot 2^2+4\cdot 1^2=20.$

So

$P(2)=1296^2-1-2\cdot1296\cdot12+20=1648531,$

which matches the checkpoint.

How the Code Works

The C++, Python, and Java implementations all follow the same mathematical pipeline. First they choose a threshold near \(n^{2/3}\), compute \(\varphi(1),\dots,\varphi(B)\) with a sieve, and store the prefix values of \(\Phi(x)\) for every \(x\le B\).

For larger arguments they use memoized divide-block recursion based on the identity

$\sum_{d=1}^{x}\varphi(d)\left\lfloor\frac{x}{d}\right\rfloor=\frac{x(x+1)}{2},$

which leads to

$\Phi(x)=\frac{x(x+1)}{2}-\sum_{i=2}^{x}\Phi\!\left(\left\lfloor\frac{x}{i}\right\rfloor\right),$

with equal quotient values grouped into one interval. That provides fast access to \(\Phi(x)\) on the boundaries of every quotient block.

Next the implementations enumerate the blocks on which \(\lfloor n/k\rfloor\) is constant, compute the multiplicity \(c(u)\) from two summatory-totient queries, and update the product \(H\) together with the first and second moments \(A_1\) and \(A_2\). The multiplicities are kept exactly for modular exponentiation, while the additive moments are accumulated modulo \(M\).

The C++ and Java implementations optionally split the quotient blocks into chunks, compute partial products and partial moments independently, and merge them at the end. The Python implementation performs the same reduction in one serial pass.

Complexity Analysis

Let \(B\) denote the sieve cutoff, chosen on the order of \(n^{2/3}\). Building the totient table and the small prefix values costs \(O(B)\) time and \(O(B)\) memory. The memoized summatory-totient stage uses divisor-block grouping, so only the distinct quotient values need to be explored; this is the standard \(O(n^{2/3})\)-type approach for one top-level query. The final quotient-block traversal contributes only \(O(\sqrt n)\) additional arithmetic. In practice the totient stage dominates, and parallel block folding improves wall-clock time in the threaded implementations without changing the asymptotic bound.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=465
2. Euler totient function: Wikipedia - Euler totient function
3. Summatory totient function: MathWorld - Totient Summatory Function
4. Visible lattice points and Farey-type counting: Wikipedia - Farey sequence
5. Convex hull and half-plane containment: Wikipedia - Convex hull