Problem 228: Minkowski Sums

Project Euler Problem 228 Solution

EulerSolve provides an optimized solution for Project Euler Problem 228, Minkowski Sums, with C++, Python, Java, and a step-by-step mathematical explanation.

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....

Detailed mathematical approach

Problem Summary

For $n\ge3$, $S_n$ is the regular polygon with $n$ sides whose vertices $v_1,\dots,v_n$ lie on the unit circle at the angles $\theta_k=(2k-1)\cdot180^\circ/n$, that is, $v_k=(\cos\theta_k,\sin\theta_k)$. It is filled: it contains its boundary and its interior. The Minkowski sum $S+T$ of two shapes is the set of all points $s+t$ with $s$ in $S$ and $t$ in $T$, added coordinate by coordinate. The statement shows that $S_3+S_4$ has six sides and asks how many sides the sum of the $46$ polygons $S_{1864}+S_{1865}+\dots+S_{1909}$ has. ^[1]

The whole solution in one sentence: the sum has one side for each direction in which at least one of the polygons has a side, so we write these directions as fractions of a full turn, reduce them to lowest terms and count them denominator by denominator with Euler's totient function.

Mathematical Approach

We find the side directions of one polygon, prove that a Minkowski sum keeps exactly these directions, and count them. Directions are measured anticlockwise from the positive $x$-axis, in degrees or in full turns.

1. Where the sides of $S_n$ face

The outward normal of a side is the direction perpendicular to it that points away from the polygon; we say that the side faces this direction. The triangle $S_3$ has its vertices at $60^\circ$, $180^\circ$ and $300^\circ$, and its sides face $0^\circ$, $120^\circ$ and $240^\circ$. The square $S_4$ has its vertices at $45^\circ$, $135^\circ$, $225^\circ$ and $315^\circ$, and its sides face $0^\circ$, $90^\circ$, $180^\circ$ and $270^\circ$.

In general the side from $v_k$ to $v_{k+1}$, with $v_{n+1}=v_1$, faces the angle $k\cdot360^\circ/n$. Its endpoints lie at $(2k-1)\cdot180^\circ/n$ and $(2k+1)\cdot180^\circ/n$, both at distance $1$ from the centre $O$, so the triangle $Ov_kv_{k+1}$ is isosceles, and the ray that halves its angle at $O$, at $2k\cdot180^\circ/n$, meets the side at its midpoint at a right angle. The centre lies inside the polygon, so this ray is the outward normal. For $k=1,\dots,n$ these angles are the multiples $j\cdot360^\circ/n$ with $0\le j\lt n$, since $k=n$ gives $360^\circ$, the direction $0^\circ$. In full turns, the sides of $S_n$ face the $n$ directions

$$0,\ \frac1n,\ \frac2n,\ \dots,\ \frac{n-1}n.$$

As complex numbers, the outward unit normals are the $n$-th roots of unity $e^{2\pi ij/n}$. ^[2] Every $S_n$ has a vertical side on the right, between $v_n$ and $v_1$, that faces $0^\circ$.

2. The face of a convex polygon in a direction

For a filled convex polygon $P$ and a unit vector $u$, with the dot product $u\cdot x=u_1x_1+u_2x_2$, let

$$\begin{aligned}h_P(u)&=\max_{x\in P}u\cdot x,\\F_P(u)&=\{x\in P:u\cdot x=h_P(u)\}.\end{aligned}$$

The function $h_P$ is the support function of $P$, ^[3] and the face $F_P(u)$ consists of the points of $P$ that lie farthest in the direction $u$: a ruler perpendicular to $u$, pushed against $P$ from far away in the direction $u$, touches $P$ exactly there. For $S_4$ and $u$ at $30^\circ$, the dot products with the vertices at $45^\circ$, $135^\circ$, $225^\circ$ and $315^\circ$ are the cosines of the angle differences, about $0.966$, $-0.259$, $-0.966$ and $0.259$, so the face is the vertex at $45^\circ$; for $u$ at $0^\circ$ the vertices at $45^\circ$ and $315^\circ$ tie, and the face is the whole right side. In general the face lies on the line $u\cdot x=h_P(u)$, which touches $P$ without cutting into it, and such a line meets a convex polygon in a single vertex or along the whole side that faces $u$. So a convex polygon has as many sides as there are directions in which its face is a segment of positive length.

3. Faces of a Minkowski sum

Claim. For filled convex polygons $A$ and $B$ and every unit vector $u$,

$$\begin{aligned}h_{A+B}(u)&=h_A(u)+h_B(u),\\F_{A+B}(u)&=F_A(u)+F_B(u).\end{aligned}$$

Proof. A point of $A+B$ is a sum $a+b$ with $a\in A$ and $b\in B$, and $u\cdot(a+b)=u\cdot a+u\cdot b$${}\le h_A(u)+h_B(u)$, with equality exactly when $a\in F_A(u)$ and $b\in F_B(u)$. Such pairs exist, so the maximum over $A+B$ is $h_A(u)+h_B(u)$, and it is reached exactly at the sums of a point of $F_A(u)$ and a point of $F_B(u)$.

Both faces are points or segments perpendicular to $u$, and a segment of length $\ell_1$ plus a parallel segment of length $\ell_2$ is a parallel segment of length $\ell_1+\ell_2$, where a point counts as a segment of length $0$. So $A+B$ has a side facing $u$ exactly when $A$ or $B$ has one, and its length is the sum of theirs. The sum of two convex polygons is again a convex polygon, the convex hull of the sums of a vertex of $A$ and a vertex of $B$, since the convex hull of a sum of sets is the sum of their convex hulls; in practice it is built by merging the two edge lists in the order of direction. ^[4] Adding the $46$ polygons one at a time gives:

Consequence. The sides of $S_{1864}+\dots+S_{1909}$ face exactly the directions faced by a side of at least one summand, one side for each such direction. Sides of different summands that face the same direction merge into one longer side.

4. The example of the statement

The sides of $S_3$ face $0$, $\tfrac13$ and $\tfrac23$ of a turn, and those of $S_4$ face $0$, $\tfrac14$, $\tfrac12$ and $\tfrac34$. Of these seven sides, only the right-hand vertical sides of the triangle and of the square face the same direction, so they merge into one, and $S_3+S_4$ has $6$ sides: the hexagon of the statement. A side of $S_n$ has length $2\sin(180^\circ/n)$, which is $\sqrt3$ for the triangle and $\sqrt2$ for the square. So the side of the hexagon facing $0^\circ$ has length $\sqrt3+\sqrt2\approx3.146$, and its other five sides are single sides of the triangle or the square.

5. Fractions in lowest terms and Euler's totient

A fraction $j/n$ with $0\le j\lt n$ has exactly one form $a/d$ in lowest terms with $0\le a\lt d$ and $\gcd(a,d)=1$: dividing by $g=\gcd(j,n)$ gives $d=n/g$, a divisor of $n$. Conversely, a fraction $a/d$ in lowest terms with $d\mid n$ equals $(an/d)/n$. So the directions of $S_n$ are exactly the fractions in lowest terms in $[0,1)$ whose denominator divides $n$.

The fractions in lowest terms with denominator $d$ have the numerators $a$ with $0\le a\lt d$ and $\gcd(a,d)=1$. Their number is Euler's totient $\varphi(d)$, the number of integers among $1,\dots,d$ that are coprime to $d$; ^[5] the two ranges differ only in $a=0$ and $a=d$, and $\gcd(0,d)=\gcd(d,d)$, so they give the same count. For $d=1,\dots,6$ the totients are $1,1,2,2,4,2$, and for $d=7,\dots,12$ they are $6,4,6,4,10,4$. The twelve directions of $S_{12}$ reduce to $0$, $\tfrac1{12}$, $\tfrac16$, $\tfrac14$, $\tfrac13$, $\tfrac5{12}$, $\tfrac12$, $\tfrac7{12}$, $\tfrac23$, $\tfrac34$, $\tfrac56$ and $\tfrac{11}{12}$: one each with the denominators $1$ and $2$, two each with $3$, $4$ and $6$, and four with $12$, and indeed $1+1+2+2+2+4=12$. The same grouping for any $n$ proves Gauss's identity $\sum_{d\mid n}\varphi(d)=n$. ^[5] For roots of unity it says that every $n$-th root $z$ is a primitive $d$-th root, one for which $d$ is the smallest positive exponent with $z^d=1$, for exactly one $d\mid n$, and that there are $\varphi(d)$ of those. ^[2]

6. The counting formula

Let $U$ be the set of positive integers that divide at least one of the numbers $1864,1865,\dots,1909$. By Sections 3 and 5, the fraction $a/d$ in lowest terms is faced by a side of the sum exactly when $d$ divides some $n$ of the range, that is, when $d\in U$. Different denominators give different fractions, so the number of sides is

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

A direction shared by several polygons is counted once, as Section 3 requires. Two polygons $S_n$ and $S_m$ share exactly the directions whose denominator divides $\gcd(n,m)$, and by Gauss's identity there are $\gcd(n,m)$ of them.

7. A worked example: $S_{10}+S_{11}+S_{12}$

The divisors are $1,2,5,10$ for $10$, $1,11$ for $11$ and $1,2,3,4,6,12$ for $12$, so

$$U=\{1,2,3,4,5,6,10,11,12\}.$$

The totients of these nine denominators are $1,1,2,2,4,2,4,10,4$, so the sum has $N=30$ sides. Counted with repetition, the three polygons have $10+11+12=33$ sides. The direction $0$ belongs to all three and the direction $\tfrac12$ to $S_{10}$ and $S_{12}$, in agreement with $\gcd(10,12)=2$ and $\gcd(10,11)=\gcd(11,12)=1$, so three sides merge into others, and $33-3=30$.

8. Which denominators occur

The range consists of $46$ consecutive integers, and among any $d$ consecutive integers one is a multiple of $d$, so every $d\le46$ lies in $U$. In general the number of multiples of $d$ from $1$ to $x$ is $\lfloor x/d\rfloor$, where the floor $\lfloor y\rfloor$ is the largest integer not exceeding $y$, so

$$d\in U\iff\Bigl\lfloor\frac{1909}{d}\Bigr\rfloor\gt\Bigl\lfloor\frac{1863}{d}\Bigr\rfloor.$$

For example $47\in U$ and $48\in U$, because $47\cdot40=1880$ and $48\cdot39=1872$, but $49\notin U$, because $49\cdot38=1862$ and $49\cdot39=1911$ lie on the two sides of the range; the $\varphi(49)=42$ directions with denominator $49$ are missing, and $49$ is the smallest missing denominator. Every $d$ with $955\le d\le1863$ is missing too, since $2d\ge1910$ leaves $d$ itself, which lies below the range, as its only multiple up to $1909$. So $U$ consists of all $d\le46$, some of the numbers from $47$ to $954=1908/2$, and the $46$ numbers of the range.

9. Two pitfalls: orientation and precision

The vertices at the odd multiples of $180^\circ/n$ give every $S_n$ a side facing $0^\circ$, and this makes the side directions the fractions $j/n$. With the vertices at $k\cdot360^\circ/n$ instead, the sides would face $(2j+1)/(2n)$ of a turn: $\tfrac16$, $\tfrac12$, $\tfrac56$ for the triangle and $\tfrac18$, $\tfrac38$, $\tfrac58$, $\tfrac78$ for the square. These seven directions are all different, and $S_3+S_4$ would have seven sides instead of six.

Two different directions $a/b$ and $c/e$ differ by $|ae-bc|/(be)\ge1/(be)$, since $ae-bc$ is a nonzero integer. The directions $\tfrac1{1909}$ and $\tfrac1{1908}$ of the sum differ by only $1/3642372$ of a turn, less than a ten-thousandth of a degree, and no two of its directions are closer: different denominators have $be\le1909\cdot1908$, equal ones give at least $1/b$, and the gap across $0$, $1-|a/b-c/e|$, is also a positive integer over $be$. A floating-point construction would have to separate such directions while merging the $46$ slightly different computed copies of the direction $0$; counting by denominators needs integers only.

10. Totients by a sieve

Euler's product formula, ^[5] with the product over the distinct primes $p$ that divide $k$,

$$\varphi(k)=k\prod_{p\mid k}\Bigl(1-\frac1p\Bigr),$$

gives for example $\varphi(12)=12\cdot\tfrac12\cdot\tfrac23=4$. It follows from the inclusion–exclusion principle: ^[5] among $1,\dots,12$ there are $6$ multiples of $2$ and $4$ of $3$, and the $2$ multiples of $6$ lie in both groups, so $12-6-4+2=4$ numbers are coprime to $12$, which is $12(1-\tfrac12)(1-\tfrac13)$ multiplied out. In general, $k/\prod p$ of the numbers up to $k$ are divisible by all primes of a set of prime divisors of $k$, and these counts with alternating signs form the product multiplied out. A sieve applies the formula to all $k$ up to a bound $M$ at once. It keeps an entry $t_k$ for every $k\le M$, starting with $t_k=k$, and runs through $p=2,3,\dots,M$; whenever $t_p=p$, the number $p$ is prime, and every multiple $k$ of $p$ gets $t_k\leftarrow t_k-t_k/p$, which multiplies the entry by $1-1/p$. ^[6] For $k=12$ the prime $2$ gives $12-6=6$, and the prime $3$ gives $6-2=4$.

Two facts make this correct. A prime $p$ is not a multiple of a smaller prime, so its entry is still $p$ at its turn, while a composite $p$ was already lowered by its smallest prime factor. When the prime $p$ reaches a multiple $k$, the entry is $k\prod(1-1/q)$ over the primes $q\lt p$ dividing $k$, which is $k/\prod q$ times $\prod(q-1)$, and $k/\prod q$ is still divisible by $p$, so $t_k/p$ is exact. After the last prime, $t_k=\varphi(k)$.

How the Code Works

The C++ program ^[7] keeps the default range in Options; parse_arguments accepts --from= and --to=, read by parse_int_after_prefix, and --skip-checkpoints, and main returns $1$ for an unknown argument or a range that does not satisfy $3\le{}$from${}\le{}$to. The digits are collected in an int without an overflow check, so a number above $2^{31}-1$ causes undefined behaviour instead of an error.

compute_totients(limit) is the sieve of Section 10 in a std::vector<int>. solve(from_n, to_n) builds the totients up to to_n and the byte array denominator_used, which holds the set $U$ of Section 6. For each $n$ of the range it tries $d=1,2,\dots$ while $d^2\le n$, with the square taken in long long, and for every divisor $d$ it marks both $d$ and $e=n/d$; this finds all divisors, because one of $d$ and $n/d$ is at most $\sqrt n$. Then it adds $\varphi(d)$ once for every marked $d$ to the 64-bit unsigned counter sides, which gives $N$.

run_checkpoints requires that solve(3, 4) returns $6$, the hexagon of Section 4, and that solve(4, 4) returns $4$, the square alone, where the sum is Gauss's identity $\varphi(1)+\varphi(2)+\varphi(4)=4$. If a check fails, it writes a message to the error stream and main returns $2$; otherwise main prints solve(from_n, to_n). With --from=10 --to=12 the program prints $30$, the count of Section 7.

Python's compute_totients and solve(from_n=1864, to_n=1909) do the same with a list and a bytearray; the script calls solve() with the default range. Java's computeTotients and parameterless solve(), with the range fixed inside, use int[], byte[], the test (long) d * d <= n and a long sum. Neither has options or checkpoints; both return the count as a string, which is printed. No integer type comes near its limit: every $\varphi(d)\le1909$, and the count is at most the total number of sides of the summands.

Complexity and Verification

Let $M=1909$ and let $L=46$ be the number of polygons. The sieve makes $\sum_{p\le M}\lfloor M/p\rfloor$ updates, which is $O(M\log\log M)$ as for the sieve of Eratosthenes; ^[6] here these are $4239$ updates for $292$ primes. The divisor search makes $\lfloor\sqrt n\rfloor=43$ trials for every $n$ of the range, since $43^2=1849$ and $44^2=1936$, so $46\cdot43=1978$ trials in all, and $O(L\sqrt M)$ in general. With the final scan of $M$ steps the time is $O(M\log\log M+L\sqrt M)$, and the memory is $O(M)$: an integer array and a byte array of $M+1$ entries, in Python a list of integer objects and a bytearray. In our tests each program finished in a few hundredths of a second.

All three programs print the same number, and the C++ checkpoints pass. Further checks for this article, which are not part of the published programs:

a floating-point convex hull of the sums of vertices, which does not rely on Section 3, gives for all $406$ ranges $3\le a\le b\le30$ the number of sides of $S_a+\dots+S_b$ predicted by Section 6 and by a direct count of the fractions $j/n$, and for the orientation of Section 9 the count of the fractions $(2j+1)/(2n)$ for all $b\le20$;
for the range of the problem, the exact set of all fractions $j/n$ has as many elements as the totient sum, and the test of Section 8 marks the same $239$ denominators as the divisor search;
floating-point normals of all $46$ polygons, computed from the vertex coordinates and merged when closer than $10^{-10}$ of a turn, give the same count;
the sieve agrees with a direct count of the coprime numbers for every $d\le1909$.

Footnotes and References

The references below supply the background facts; the side directions of $S_n$, the rule for the faces of a Minkowski sum and the counting formula are derived in this article.

Project Euler 228 — Minkowski Sums. The official statement defines Sₙ as the filled regular n-gon with the vertices (cos((2k − 1)/n × 180°), sin((2k − 1)/n × 180°)) and the Minkowski sum, shows that S₃ + S₄ has six sides, and asks how many sides S₁₈₆₄ + S₁₈₆₅ + ⋯ + S₁₉₀₉ has.
Wikipedia — Root of unity. The n-th roots of unity exp(2kπi/n), k = 0, …, n − 1, are the vertices of a regular n-gon in the unit circle; the φ(n) primitive ones are those with k/n in lowest terms, and every n-th root is a primitive d-th root for exactly one divisor d of n.
Wikipedia — Support function. The support function of a nonempty closed convex set A is h_A(x) = sup{x · a : a ∈ A}, and for a Minkowski sum h_{A+B} = h_A + h_B.
Wikipedia — Minkowski addition. Conv(S₁ + S₂) = Conv(S₁) + Conv(S₂), and the sum of two convex polygons with m and n vertices is a convex polygon with at most m + n vertices, computed in O(m + n) time by merging their edges ordered by polar angle.
Wikipedia — Euler's totient function. φ(n) counts the k with 1 ≤ k ≤ n and gcd(n, k) = 1; φ(n) = n ∏(1 − 1/p) over the primes p dividing n, also proved by inclusion–exclusion; and Gauss's identity, the sum of φ(d) over the divisors d of n equals n, follows by putting the fractions 1/20, …, 20/20 into lowest terms.
cp-algorithms — Euler's totient function. The sieve sets phi[i] = i and applies phi[j] -= phi[j] / i to the multiples j of every i with phi[i] = i, a prime; like the sieve of Eratosthenes, it takes O(n log log n) time.
C++ — Euler228.cpp. The linked immutable C++ revision contains compute_totients, solve and run_checkpoints. It is the implementation record for this article.

Problem 228 source code

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

namespace {

using u64 = std::uint64_t;

struct Options {
    int from_n = 1864;
    int to_n = 1909;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }
    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--from=", options.from_n) ||
            parse_int_after_prefix(arg, "--to=", options.to_n)) {
            continue;
        }
        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.from_n >= 3 && options.to_n >= options.from_n;
}

std::vector<int> compute_totients(const int limit) {
    std::vector<int> phi(static_cast<std::size_t>(limit + 1));
    for (int i = 0; i <= limit; ++i) {
        phi[static_cast<std::size_t>(i)] = i;
    }
    for (int p = 2; p <= limit; ++p) {
        if (phi[static_cast<std::size_t>(p)] != p) {
            continue;
        }
        for (int k = p; k <= limit; k += p) {
            phi[static_cast<std::size_t>(k)] -= phi[static_cast<std::size_t>(k)] / p;
        }
    }
    return phi;
}

u64 solve(const int from_n, const int to_n) {
    const std::vector<int> phi = compute_totients(to_n);
    std::vector<std::uint8_t> denominator_used(static_cast<std::size_t>(to_n + 1), 0U);

    for (int n = from_n; n <= to_n; ++n) {
        for (int d = 1; static_cast<long long>(d) * d <= n; ++d) {
            if (n % d != 0) {
                continue;
            }
            denominator_used[static_cast<std::size_t>(d)] = 1U;
            const int e = n / d;
            denominator_used[static_cast<std::size_t>(e)] = 1U;
        }
    }

    u64 sides = 0;
    for (int d = 1; d <= to_n; ++d) {
        if (denominator_used[static_cast<std::size_t>(d)] != 0U) {
            sides += static_cast<u64>(phi[static_cast<std::size_t>(d)]);
        }
    }
    return sides;
}

bool run_checkpoints() {
    if (solve(3, 4) != 6ULL) {
        std::cerr << "Checkpoint failed for S3 + S4 sample" << '\n';
        return false;
    }
    if (solve(4, 4) != 4ULL) {
        std::cerr << "Checkpoint failed for single polygon S4" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }
    std::cout << solve(options.from_n, options.to_n) << '\n';
    return 0;
}

Python

def compute_totients(limit):
    phi = list(range(limit + 1))
    for p in range(2, limit + 1):
        if phi[p] == p:
            for k in range(p, limit + 1, p):
                phi[k] -= phi[k] // p
    return phi

def solve(from_n=1864, to_n=1909):
    phi = compute_totients(to_n)
    denominator_used = bytearray(to_n + 1)
    
    for n in range(from_n, to_n + 1):
        d = 1
        while d * d <= n:
            if n % d == 0:
                denominator_used[d] = 1
                denominator_used[n // d] = 1
            d += 1
            
    sides = 0
    for d in range(1, to_n + 1):
        if denominator_used[d]:
            sides += phi[d]
            
    return str(sides)

if __name__ == '__main__':
    print(solve())

Java

public class Euler228 {
    static int[] computeTotients(int limit) {
        int[] phi = new int[limit + 1];
        for (int i = 0; i <= limit; ++i) {
            phi[i] = i;
        }
        for (int p = 2; p <= limit; ++p) {
            if (phi[p] != p)
                continue;
            for (int k = p; k <= limit; k += p) {
                phi[k] -= phi[k] / p;
            }
        }
        return phi;
    }

    public static String solve() {
        int fromN = 1864;
        int toN = 1909;

        int[] phi = computeTotients(toN);
        byte[] denominatorUsed = new byte[toN + 1];

        for (int n = fromN; n <= toN; ++n) {
            for (int d = 1; (long) d * d <= n; ++d) {
                if (n % d != 0)
                    continue;
                denominatorUsed[d] = 1;
                denominatorUsed[n / d] = 1;
            }
        }

        long sides = 0;
        for (int d = 1; d <= toN; ++d) {
            if (denominatorUsed[d] != 0) {
                sides += phi[d];
            }
        }

        return String.valueOf(sides);
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}