Detailed mathematical approach

Problem Summary

For each integer \(n\), let \(S_n\) be the regular \(n\)-gon with the fixed orientation from the problem. The task is to count the sides of the Minkowski sum

$S_{1864}+S_{1865}+\cdots+S_{1909}.$

The implementations show that this is not really a coordinate-geometry problem. To determine how many sides the final polygon has, we only need to know which outer-normal directions occur on the boundary. Once those directions are classified correctly, the rest is a number-theoretic counting argument.

Mathematical Approach

The key idea is to translate the geometry of Minkowski sums into a union of direction classes, and then count those classes by Euler's totient function.

Why only outer-normal directions matter

For a convex set \(P\), its support function is \(h_P(u)=\max_{x\in P} u\cdot x\). Minkowski addition satisfies

$h_{A+B}(u)=h_A(u)+h_B(u).$

When the direction \(u\) rotates around the circle, the boundary of a convex polygon changes edge whenever one of its supporting directions changes. Therefore the edge normals of a Minkowski sum are exactly the distinct edge normals contributed by the summands. If several summands have the same normal direction, they only lengthen the corresponding edge of the sum; they do not create extra sides.

So if \(D(P)\) denotes the set of outer-normal directions of a polygon \(P\), then

$D\!\left(\sum_{n=1864}^{1909} S_n\right)=\bigcup_{n=1864}^{1909} D(S_n),$

and the number of sides is simply the size of that union.

The direction set of one regular \(n\)-gon

With the orientation used in the problem, the outer normals of \(S_n\) occur at the equally spaced angles

$D(S_n)=\left\{\frac{2\pi k}{n}: 0\le k \lt n\right\},$

with angles understood modulo \(2\pi\). Now reduce the fraction \(k/n\) to lowest terms, say

$\frac{k}{n}=\frac{a}{d},\qquad \gcd(a,d)=1.$

The integer \(d\) is the exact denominator of that direction, and it is always a divisor of \(n\). For every divisor \(d\mid n\), define the primitive direction class

$\Theta_d=\left\{\frac{2\pi a}{d}: 0\le a \lt d,\ \gcd(a,d)=1\right\}.$

Its size is \(|\Theta_d|=\varphi(d)\). Distinct values of \(d\) give disjoint classes because a rational angle has a unique reduced denominator. Therefore the directions of one regular \(n\)-gon split as

$D(S_n)=\bigcup_{d\mid n}\Theta_d,$

and counting those directions gives the familiar identity

$n=\sum_{d\mid n}\varphi(d).$

Geometrically, this says that \(S_n\) contains every primitive direction whose denominator divides \(n\).

Reducing the whole interval to a divisor set

Now collect every denominator that appears for at least one polygon in the interval:

$U=\left\{d\ge 1:\exists n\in[1864,1909],\ d\mid n\right\}.$

Because the Minkowski sum just unions the direction sets, we get

$D\!\left(\sum_{n=1864}^{1909} S_n\right)=\bigcup_{d\in U}\Theta_d.$

The classes \(\Theta_d\) are disjoint, so the final side count is

$\boxed{N=\sum_{d\in U}\varphi(d)}$

This formula is exactly what the C++, Python, and Java implementations evaluate: mark every divisor that occurs somewhere between 1864 and 1909, then add the totient of each marked divisor once.

Worked example: \(S_3+S_4\)

This small case is useful because it mirrors the checkpoint used in the implementations. The triangle contributes the denominator classes \(1\) and \(3\), while the square contributes \(1\), \(2\), and \(4\). Hence

$U=\{1,2,3,4\}.$

The resulting polygon has

$\varphi(1)+\varphi(2)+\varphi(3)+\varphi(4)=1+1+2+2=6$

sides. The denominator \(1\) is shared by both summands, but it is counted only once because repeated directions do not create new edges in the Minkowski sum.

How the Code Works

The C++, Python, and Java implementations follow the formula above directly. They never build explicit polygon coordinates, never add vectors on the boundary, and never run a geometric hull algorithm.

Totient preprocessing

First, the implementation computes \(\varphi(d)\) for every \(1\le d\le 1909\) with a standard sieve. It starts from \(\varphi(d)=d\) and, for each prime \(p\), applies the update

$\varphi(k)\leftarrow \varphi(k)-\frac{\varphi(k)}{p}$

to every multiple \(k\) of \(p\). After this pass, the totient table is ready for the final sum.

Marking the denominators that actually occur

Next, the code scans every \(n\) from 1864 through 1909. For each \(n\), it tries every divisor candidate \(d\) with \(d^2\le n\). Whenever \(d\mid n\), it marks both \(d\) and \(n/d\). After all values of \(n\) have been processed, a denominator is marked exactly when it divides at least one integer in the interval.

This is the computational version of building the set \(U\).

Summing the contribution of each direction class

Finally, the implementation loops over all denominators \(d\le 1909\) and adds \(\varphi(d)\) whenever \(d\) was marked. Because each denominator class is added only once, the program matches the geometric rule that coincident directions merge into a single side of the final polygon.

Complexity Analysis

Let \(M=1909\). The totient sieve runs in \(O(M\log\log M)\) time. The divisor-marking phase checks all integers \(d\) up to \(\sqrt n\) for each \(n\in[1864,1909]\), so its cost is

$O\!\left(\sum_{n=1864}^{1909}\sqrt n\right),$

or, in the usual worst-case form, \(O((N_2-N_1+1)\sqrt{N_2})\).

The final summation over marked denominators is \(O(M)\), and the memory usage is \(O(M)\) for the totient table and the boolean marker array. Since the interval is short and \(M\) is small, this direct divisor scan is already more than sufficient.

Footnotes and References

1. Project Euler 228: Minkowski Sums
2. Minkowski addition
3. Support function
4. Euler's totient function
5. Regular polygon