Project Euler

Minkowski Sums

Let S_n be the regular n -gon whose vertices are (cos((2k-1)pi/n),\ sin((2k-1)pi/n)), k=1,...,n. How many sides does the Minkowski sum S_1864+S_1865+...+S_1909 have?

Source sync May 21, 2026

Problem #0228

Level Level 12

Solved By 1,567

Languages C++, Python

Answer 86226

Length 243 words

geometrynumber_theorygraph

Let $S_n$ be the regular $n$-sided polygon â€“ or shape â€“ whose vertices $v_k$ ($k = 1, 2, \dots, n$) have coordinates: \begin{align*} x_k &= \cos((2k - 1)/n \times 180^\circ)\\ y_k &= \sin((2k - 1)/n \times 180^\circ) \end{align*} Each $S_n$ is to be interpreted as a filled shape consisting of all points on the perimeter and in the interior.

The Minkowski sum, $S + T$, of two shapes $S$ and $T$ is the result of adding every point in $S$ to every point in $T$, where point addition is performed coordinate-wise: $(u, v) + (x, y) = (u + x, v + y)$.

For example, the sum of $S_3$ and $S_4$ is the six-sided shape shown in pink below:

Problem illustration

How many sides does $S_{1864} + S_{1865} + \cdots + S_{1909}$ have?

Problem 228: Minkowski Sums

Mathematical Development

For a convex polygon, each side corresponds to an outward normal direction. The Minkowski sum adds support functions, so its sides are obtained by taking the union of all outward normal directions that appear in the summands.

With the given orientation, the outward normals of $S_n$ are the directions

\frac{2\pi k}{n}, \qquad k=0,1,\dots,n-1.

Two such directions coincide exactly when the fractions $k/n$ reduce to the same rational number. So a reduced fraction

\frac{p}{q}, \qquad 0 \le p < q, \qquad \gcd(p,q)=1,

appears in the union if and only if some polygon $S_n$ in the range has a side normal in that direction, which is equivalent to

q \mid n

for at least one $n \in [1864,1909]$ .

Therefore each denominator $q$ contributes all reduced numerators modulo $q$ , namely $\varphi(q)$ directions, provided the interval contains a multiple of $q$ . The denominator $q=1$ contributes the single direction $0$ .

So the answer is

1+\sum_{\substack{2 \le q \le 1909\\ \exists n \in [1864,1909],\ q\mid n}}\varphi(q).

The divisibility condition is easy to test:

\left\lfloor \frac{1909}{q} \right\rfloor > \left\lfloor \frac{1863}{q} \right\rfloor.

Editorial

This problem looks geometric, but the geometry disappears almost immediately. The Minkowski sum only cares about which edge normals occur, and a regular $n$ -gon contributes the $n$ equally spaced directions $2\pi k/n$ .

So the question becomes arithmetic: how many reduced fractions $p/q$ occur with a denominator $q$ that divides at least one integer between $1864$ and $1909$ ? Once $q$ is fixed, there are exactly $\varphi(q)$ such fractions. That reduces the whole problem to a totient sieve followed by a short scan over the possible denominators.

Pseudocode

Compute Euler's totient function phi(q) for every q up to 1909.

Start the answer at 1 for the denominator q = 1.

For q from 2 to 1909:
    If the interval [1864, 1909] contains a multiple of q:
        add phi(q) to the answer

Print the result.

Complexity Analysis

Time: $O(1909 \log \log 1909)$ for the totient sieve, plus a linear scan.
Space: $O(1909)$ .

Answer

\boxed{86226}

C++ project_euler/problem_228/solution.cpp

#include <iostream>
#include <vector>

using namespace std;

int main() {
    const int first = 1864;
    const int last = 1909;

    vector<int> phi(last + 1);
    for (int i = 0; i <= last; i++) {
        phi[i] = i;
    }

    for (int value = 2; value <= last; value++) {
        if (phi[value] == value) {
            for (int multiple = value; multiple <= last; multiple += value) {
                phi[multiple] = phi[multiple] / value * (value - 1);
            }
        }
    }

    long long total = 1;
    for (int denominator = 2; denominator <= last; denominator++) {
        if (last / denominator > (first - 1) / denominator) {
            total += phi[denominator];
        }
    }

    cout << total << '\n';
    return 0;
}

Python project_euler/problem_228/solution.py

"""
Problem 228: Minkowski Sums

The outward normals of S_n are the directions 2*pi*k/n, so the Minkowski sum
has one side for each reduced fraction p/q in [0, 1) whose denominator q
divides at least one n in [1864, 1909].
"""


def solve():
    first = 1864
    last = 1909

    phi = list(range(last + 1))
    for value in range(2, last + 1):
        if phi[value] == value:
            for multiple in range(value, last + 1, value):
                phi[multiple] = phi[multiple] // value * (value - 1)

    total = 1
    for denominator in range(2, last + 1):
        if last // denominator > (first - 1) // denominator:
            total += phi[denominator]

    print(total)


if __name__ == "__main__":
    solve()