Solution

Answer: 86226

Let the edge outward normal directions of a polygon determine its sides.

A standard fact about Minkowski sums of convex polygons is:

The set of edge directions (equivalently outward normal directions) of

$P+Q$ is the union of the edge directions of $P$ and $Q$.

So the problem reduces to counting the distinct edge directions appearing among

$$S_{1864},S_{1865},\dots,S_{1909}.$$

1. Geometry of $S_n$

The vertices of $S_n$ are

$$v_k=\left(\cos\frac{(2k-1)\pi}{n},, \sin\frac{(2k-1)\pi}{n}\right).$$

These are equally spaced around the unit circle, rotated by $\pi/n$.

Adjacent vertices are at angles

$$\frac{(2k-1)\pi}{n},\qquad \frac{(2k+1)\pi}{n}.$$

The edge between them has midpoint direction

$$\frac{2k\pi}{n}.$$

Hence the outward normal directions of the $n$ sides are exactly

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

So $S_n$ contributes the directions

$$\left{\frac{k}{n}\pmod 1\right}.$$

2. Distinct directions in the Minkowski sum

Two directions coincide iff

$$\frac{k_1}{n_1}\equiv \frac{k_2}{n_2}\pmod 1.$$

After reduction to lowest terms, every direction corresponds uniquely to a reduced fraction

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

Such a direction appears iff $d\mid n$ for at least one

$n\in[1864,1909]$.

For each denominator $d$, there are exactly $\varphi(d)$ reduced fractions with that denominator.

Therefore:

\boxed{ \text{# sides} = \sum_{\substack{d\ge1\ d\mid n\text{ for some }1864\le n\le1909}} \varphi(d) }

where $\varphi$ is Euler’s totient function.

3. Python implementation

from math import gcd

# Euler totient
def phi(n):
    result = n
    p = 2
    m = n

    while p * p <= m:
        if m % p == 0:
            while m % p == 0:
                m //= p
            result -= result // p
        p += 1

    if m > 1:
        result -= result // m

    return result

# Collect every divisor of numbers 1864..1909
divisors = set()

for n in range(1864, 1910):
    for d in range(1, int(n**0.5) + 1):
        if n % d == 0:
            divisors.add(d)
            divisors.add(n // d)

# Sum Euler totients
answer = sum(phi(d) for d in divisors)

print(answer)

This prints:

4. Code walkthrough

Totient function

def phi(n):

Computes Euler’s totient $\varphi(n)$.

The formula used is

$$\varphi(n)=n\prod_{p\mid n}\left(1-\frac1p\right).$$

We factor $n$ by trial division and apply the product formula.

Gathering divisors

for n in range(1864, 1910):

Loops through all polygons $S_n$.

For each $n$, we enumerate all divisors:

if n % d == 0:
    divisors.add(d)
    divisors.add(n // d)

A denominator $d$ contributes directions iff $d\mid n$ for some $n$.

Final summation

answer = sum(phi(d) for d in divisors)

Each denominator $d$ contributes exactly $\varphi(d)$ distinct directions.

5. Verification on the example $S_3+S_4$

Divisors involved:

$${1,2,3,4}$$

Thus the number of sides is

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

matching the statement in the problem.

The result $86226$ is reasonable:

there are $46$ polygons,
each contributes roughly $1900$ directions,
many overlap through common divisors,
leaving a total on the order of $10^5$.

Everything is consistent.

Answer: 86226

Project Euler Problem 228