Problem 202: Laserbeam

Project Euler Problem 202 Solution

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

Problem Summary In the equilateral-triangle mirror system of Problem 202, the task is to count how many admissible laser directions leave through vertex $C$ after exactly $R=12017639147$ reflections. The important point is that the implementations do not simulate reflections one by one; they replace the geometric path count by a much smaller arithmetic counting problem. The key reduction is to introduce $$n=\frac{R+3}{2}.$$ Once that number is known, every valid trajectory is encoded by an integer $k$ with $1 \le k \lt n$, and the answer becomes a count of those integers satisfying two precise conditions: one congruence condition picks out the correct exit corner, and one coprimality condition rules out trajectories that would hit a corner too early. Mathematical Approach The arithmetic used by the C++, Python, and Java implementations comes from the standard unfolding of mirror reflections in an equilateral triangle. After unfolding, a zig-zag laser path becomes a straight segment in a triangular lattice, so the geometric question turns into a lattice-point visibility question. Unfolding Reflections Into a Triangular Lattice Reflect the triangle across the side hit by the beam after each bounce. In the unfolded picture, the beam no longer reflects; instead it travels in a straight line across copies of the original triangle....

Detailed mathematical approach

Problem Summary

Three mirrors form an equilateral triangle with vertices $A$, $B$ and $C$, their reflective surfaces facing inwards, and each vertex has an infinitesimal gap through which a laser beam can pass. A beam enters through the gap at $C$, bounces from mirror to mirror and leaves as soon as it reaches a vertex. We must count the ways, that is, the entry directions, in which a beam can enter at $C$, bounce off exactly $R=12017639147$ surfaces and leave through $C$ again. For $R=11$ there are $2$ ways, one drawn in the statement and the other its reverse, and for $R=1000001$ there are $80840$ ways. ^[1]

The whole solution in one sentence: reflecting the triangle instead of the beam straightens every beam, so that the ways correspond to the points $(a,b)$ with positive whole-number coordinates and $a+b=(R+3)/2$ that have no common factor and a difference divisible by $3$, which we count by inclusion–exclusion over the prime factors of $(R+3)/2$.

Mathematical Approach

The simplest way back is the beam from $C$ to the midpoint of $AB$, which meets that mirror at a right angle and returns to $C$ after $1$ bounce. Longer paths zig-zag, so we first straighten them.

1. Reflect the triangle, not the beam

At a mirror the angle of incidence equals the angle of reflection, ^[2] so the reflected beam is the mirror image, in the mirror's line, of the path the beam would have taken without the mirror. Instead of bending the beam we may therefore reflect the triangle in that mirror and let the beam run straight on into the copy. Doing this at every bounce turns the zig-zag path into a straight line through a chain of copies, each the reflection of the previous one in the side the line crosses. Each crossing of a side is one bounce, and when the line reaches a corner of a copy, the real beam reaches the vertex of which that corner is a copy and leaves. ^[2] Reflecting an equilateral triangle in a side gives the equal triangle on the other side of it, so all copies are tiles of the triangular tiling, in which six triangles meet at every corner. ^[3]

2. Coordinates on the tiling

Put $C$ at the origin, let $\mathbf u$ and $\mathbf v$ be the unit vectors from $C$ to $A$ and to $B$, at an angle of $60^\circ$, and write $(x,y)$ for the point $x\mathbf u+y\mathbf v$. The corners of the tiles are the points $(x,y)$ with integer coordinates, the triangular lattice, ^[3] and the sides of the tiles lie on the lines $x=i$, $y=j$ and $x+y=k$ for integers $i$, $j$, $k$. The original triangle is $x\ge0$, $y\ge0$, $x+y\le1$, with $C=(0,0)$, $A=(1,0)$ and $B=(0,1)$.

A beam entering at $C$ points strictly between the sides $CA$ and $CB$, so its line consists of the points $(s\alpha,s\beta)$ with $s\gt0$, for fixed $\alpha,\beta\gt0$. If $\alpha/\beta$ is irrational, the line meets no lattice point and the beam never leaves. Otherwise the beam leaves at the first lattice point $(a,b)$ on its line, where $a,b\ge1$. Different beams have different first points, so we count such first points.

3. Counting the bounces

Claim. If the segment from $C$ to $(a,b)$, where $a,b\ge1$, contains no lattice point other than its ends, the beam aimed at $(a,b)$ bounces exactly $2(a+b)-3$ times before it leaves there.

Proof. Along the segment the coordinate $x$ grows steadily from $0$ to $a$, so the segment crosses each of the $a-1$ lines $x=i$ with $0\lt i\lt a$ exactly once. In the same way it crosses the $b-1$ lines $y=j$ with $0\lt j\lt b$ and the $a+b-1$ lines $x+y=k$ with $0\lt k\lt a+b$, and it touches the lines through its ends only at the ends. Two lines of different families meet at a lattice point, for instance $x=i$ and $x+y=k$ at $(i,k-i)$, and the segment avoids the lattice points between its ends, so no two crossings coincide. Each crossing therefore passes through the inside of exactly one side of a tile, which is one bounce, and the total is $(a-1)+(b-1)+(a+b-1)$${}=2(a+b)-3$. $\square$

So every way back to a corner has an odd number of bounces, and a beam aimed at $(a,b)$ bounces $R$ times exactly when $a+b=n$, where $n=(R+3)/2$. For the example of the statement, $R=11$ gives $n=7$, and the segment to $(2,5)$ crosses the line $x=1$, the four lines $y=1,\dots,4$ and the six lines $x+y=1,\dots,6$, which makes $1+4+6=11$ bounces.

4. Through which vertex the beam leaves

We write $x\equiv y\pmod 3$ when $3$ divides $x-y$, and $x\bmod 3$ for the remainder $0$, $1$ or $2$ of $x$ on division by $3$; for instance $-1\equiv2\pmod 3$. ^[4]

Claim. The lattice point $(a,b)$ is a copy of $C$ if $a-b\equiv0$, of $A$ if $a-b\equiv1$ and of $B$ if $a-b\equiv2\pmod 3$.

Proof. Colour each lattice point $(x,y)$ with $(x-y)\bmod 3$. With $c=i-j$, an upward tile with the corners $(i,j)$, $(i+1,j)$, $(i,j+1)$ has the colours $c$, $c+1$, $c-1$, and a downward tile with the corners $(i+1,j)$, $(i,j+1)$, $(i+1,j+1)$ has the colours $c+1$, $c-1$, $c$, so the corners of every tile have three different colours. In the original triangle the names $C$, $A$, $B$ match the colours $0$, $1$, $2$. Reflecting a copy in a side keeps the two corners on that side, and the new third corner carries the one name not used on the side and, since its tile has three colours, also the one colour not used there. By induction along the chain of Section 1, names and colours match on every copy the beam passes through. $\square$

So the beam leaves through $C$ exactly when $a\equiv b\pmod 3$. With $b=n-a$ this reads $2a\equiv n$, that is, $a\equiv 2n\pmod 3$, after multiplying by $2$ and using $4\equiv1$. If $3$ divides $n$, the condition forces $a\equiv0$ and $b=n-a\equiv0\pmod 3$, and by Section 5 the beam would leave earlier, so no way exists when $R\equiv3\pmod 6$. For both checkpoints and for the target, $n\equiv1\pmod 3$, and the condition is $a\equiv2\pmod 3$.

5. Leaving too early

Claim. The segment from $C$ to $(a,b)$ contains a lattice point between its ends exactly when $\gcd(a,b)\gt1$.

Proof. If $g=\gcd(a,b)\gt1$, the lattice point $(a/g,b/g)$ lies between the ends. Conversely, a point between the ends is $(ta,tb)$ with $0\lt t\lt1$. If it is a lattice point, $t$ is the fraction $ta/a$; write $t=p/q$ in lowest terms, with $q\ge2$. Since $q$ divides $pa$ and $pb$ and is coprime to $p$, it divides $a$ and $b$, so $\gcd(a,b)\ge q\gt1$. $\square$

In the square grid this is the familiar fact that $(a,b)$ is visible from the origin exactly when $a$ and $b$ are coprime; ^[5] our lattice is the square grid after a linear change of coordinates, which keeps segments and lattice points. Since $\gcd(a,n-a)=\gcd(a,n)$, the condition becomes $\gcd(a,n)=1$. For example, $R=13$ gives $n=8$ and the candidates $a=1,4,7$ with $a\equiv2n\equiv1\pmod 3$. The beam aimed at $(4,4)$ meets $(1,1)$, a copy of $C$, after $2\cdot2-3=1$ bounce: it is the altitude beam from the beginning of this approach. So $R=13$ has the $2$ ways aimed at $(1,7)$ and $(7,1)$.

6. The counting problem

Sections 2 to 5 match the ways one to one with the integers $a$ that satisfy three conditions:

$1\le a\le n-1$, so that $b=n-a\ge1$ and the beam bounces $R$ times (Section 3);
$a\equiv 2n\pmod 3$, so that it leaves through $C$ (Section 4);
$\gcd(a,n)=1$, so that it does not leave earlier (Section 5).

Write $W(R)$ for their number; for even $R$ there is no way at all. For $R=1,3,\dots,19$ the values of $W(R)$ are $1,0,0,2,0,2,2,0,0,4$, respectively; the first counts the altitude beam. The mirror image in the altitude through $C$ swaps $a$ and $b$, and $a=b$ forces $a=b=1$, so $W(R)$ is even for every $R\gt1$. For $R=11$ both candidates, $a=2$ and $a=5$, are coprime to $7$; the two ways, aimed at $(2,5)$ and $(5,2)$, are mirror images, and the second is also the first one run backwards, as in the statement.

7. Inclusion–exclusion over the prime factors

Let $p_1,\dots,p_k$ be the distinct primes that divide $n$. An integer is coprime to $n$ exactly when none of them divides it, and it is divisible by all primes of a set $S$ exactly when it is divisible by their product $d_S$. Call the integers $a$ with $1\le a\le n-1$ and $a\equiv2n\pmod 3$ the candidates, and let $N(d)$ be the number of candidates divisible by $d$. The inclusion–exclusion principle ^[6] gives

$$W(R)=\sum_{S}(-1)^{|S|}\,N(d_S),$$

where $S$ runs over all $2^k$ sets of these primes, the empty set with $d_\varnothing=1$ included. Indeed, a candidate divisible by exactly the primes of a nonempty set $T$ is counted once for every $S\subseteq T$, with total weight $(1-1)^{|T|}=0$, while a candidate coprime to $n$ is counted only for $S=\varnothing$.

8. Multiples of $d$ in one residue class

We may assume that $3$ does not divide $n$, since otherwise $W(R)=0$. The multiples of $d=d_S$ are $a=dt$, and $1\le a\le n-1$ means $1\le t\le m$ with $m=\lfloor(n-1)/d\rfloor$. As $d$ divides $n$, it is $\equiv1$ or $\equiv2\pmod 3$, so $d\cdot d\equiv1$, and $dt\equiv2n$ becomes $t\equiv2nd\pmod 3$. For $n\equiv1$ this is $t\equiv2$ when $d\equiv1$ and $t\equiv1$ when $d\equiv2$. The integers $t\le m$ in a class $r\in\{1,2\}$ are $r,r+3,r+6,\dots$, so

$$N(d)=\begin{cases}0,&r\gt m,\\[2pt]1+\left\lfloor\dfrac{m-r}{3}\right\rfloor,&r\le m.\end{cases}$$

9. Worked example: the checkpoint $R=1000001$

Here $n=500002=2\cdot53^2\cdot89$ and $n\equiv1\pmod 3$, so $k=3$ and there are $8$ sets $S$. The eight terms are:

$d=1$: $m=500001$, $t\equiv2$, $N=166667$;
$d=2$: $m=250000$, $t\equiv1$, $N=83334$;
$d=53$: $m=9433$, $t\equiv1$, $N=3145$;
$d=89$: $m=5617$, $t\equiv1$, $N=1873$;
$d=106$: $m=4716$, $t\equiv2$, $N=1572$;
$d=178$: $m=2808$, $t\equiv2$, $N=936$;
$d=4717$: $m=105$, $t\equiv2$, $N=35$;
$d=9434$: $m=52$, $t\equiv1$, $N=18$.

Products of an even number of primes are added, the others subtracted:

$$\begin{aligned}W&=(166667+1572+936+35)\\&\quad-(83334+3145+1873+18)\\&=169210-88370=80840,\end{aligned}$$

the value of the statement. For $R=11$ the number $n=7$ is prime, $N(1)=2$ counts $a=2$ and $a=5$, and $N(7)=0$, so $W(11)=2$.

10. A closed form as a check

Still assuming that $3$ does not divide $n$, for a divisor $d$ of $n$ the bound is exact, $m=e-1$ with $e=n/d$, and the class of $t$ is $2nd=2d^2e\equiv2e\pmod 3$. The $t$ from $1$ to $e-1$ in this class number $(e-1)/3$ when $e\equiv1$ and $(e+1)/3$ when $e\equiv2\pmod 3$, so $N(d)=(e-\chi(e))/3$, where $\chi(e)$ is $1$, $-1$ or $0$ for $e\equiv1$, $2$ or $0\pmod 3$. This $\chi$ is the non-principal Dirichlet character modulo $3$, which is completely multiplicative, $\chi(xy)=\chi(x)\chi(y)$. ^[7] In the sum over $S$, the terms $n/d_S$ add up to Euler's totient $\varphi(n)$, the number of integers from $1$ to $n$ coprime to $n$, by Euler's product formula: ^[8]

$$\begin{aligned}\sum_S(-1)^{|S|}\frac{n}{d_S}&=n\prod_{p\mid n}\Bigl(1-\frac1p\Bigr)\\&=\varphi(n),\end{aligned}$$

and since $\chi(d_S)^2=1$, we have $\chi(n/d_S)=\chi(n)\chi(d_S)$, so the signed terms $(-1)^{|S|}\chi(n/d_S)$ add up to $\chi(n)P(n)$, where $P(n)=\prod_{p\mid n}(1-\chi(p))$. Hence

$$3\,W(R)=\varphi(n)-\chi(n)\,P(n).$$

A prime $p\equiv1\pmod 3$ contributes the factor $0$ to $P(n)$ and a prime $p\equiv2$ the factor $2$. So $W(R)=\varphi(n)/3$ as soon as some prime $p\equiv1\pmod 3$ divides $n$, as for $n=7$, where $\varphi(7)/3=2$; only when all $k$ primes of $n$ are $\equiv2\pmod 3$ is $W(R)=(\varphi(n)-2^k\chi(n))/3$ different from a third of $\varphi(n)$. The second checkpoint is such a case: $2$, $53$ and $89$ are $\equiv2\pmod 3$, $\varphi(500002)=53\cdot52\cdot88=242528$ is not even a multiple of $3$, and $(242528-8)/3=80840$. The programs do not use this formula, but it checks their count independently.

How the Code Works

The C++ program ^[9] reads --reflections=R, with the default $12017639147$, and --skip-checkpoints; any other argument, or $R\lt1$, gives exit code 1. Unless skipped, run_checkpoints requires solve(11) to return $2$ and solve(1000001) to return $80840$, else the exit code is 2; then main prints solve(R).

solve sets $n=(R+3)/2$ by integer division (Section 3). distinct_prime_factors uses trial division: for $p=2,3,4,\dots$, while $p^2$ does not exceed the part of $n$ not yet divided out, it records each $p$ that divides and divides it out completely, so composite values of $p$ never divide; a remainder above $1$ is the last prime. Exponents are not kept, as Section 7 needs none.

The recursive lambda dfs(self, index, product, parity) decides prime by prime whether it belongs to $S$. At each of its leaves, where product is $d_S$ and parity is $|S|$, it adds or subtracts count_multiples_with_mod2(n, product), the number $N(d_S)$ of Section 8. Before including a prime $p$ it tests product > (n - 1) / p, an overflow-free form of $d\cdot p\gt n-1$; then every leaf below has $m=0$, and the branch is skipped. count_multiples_with_mod2 returns $0$ if $3\mid d$; otherwise it sets $m=(n-1)/d$, gets the class $r$ by doubling the inverse of $d$ modulo $3$, which is $1$ for $d\equiv1$ and $2$ for $d\equiv2$, and calls count_residue_upto(m, r), which returns $0$ if $r\gt m$ and $1+\lfloor(m-r)/3\rfloor$ otherwise.

The Python program hard-wires $R$ and, in count_coprime_mod3, runs through all $2^k$ bit masks without the pruning; the Java program follows the C++ recursion in dfs and countMod2. For the target and both checkpoints $n\lt2^{33}$, every $d_S$ divides $n$, and the partial sums stay below $2^kn\lt2^{42}$ in absolute value, so the 64-bit long long and long cannot overflow; Python's integers are unbounded anyway. Only the C++ program runs the checkpoints.

All three programs hard-wire the class $a\equiv2\pmod 3$, through $dt\equiv2$, which is right exactly when $n\equiv1\pmod 3$, that is, $R\equiv5\pmod 6$, as for both checkpoints and the target. With other values of --reflections= the C++ program counts the wrong beams: for odd $R\equiv1$ or $3\pmod 6$ those leaving through $B$ or through $A$, respectively, so that $R=1$ gives $0$ instead of the altitude beam, and for even $R$, which admits no way, the value for $R-1$. Neither the parser nor $R+3$ is checked for overflow, so values near $2^{63}$ fail.

Complexity and Verification

Trial division needs at most about $\sqrt n\approx7.8\cdot10^4$ candidate divisors, and fewer when small prime factors lower the bound. As the product of the first ten primes, $6469693230$, exceeds $n$, we have $k\le9$. The C++ and Java recursions visit fewer than $2^{k+1}$ nodes, with a few divisions each, while Python tests all $k$ bits of each of its $2^k$ masks, so the time is $O(\sqrt n+2^k)$, or $O(\sqrt n+k\,2^k)$ in Python, and the memory $O(k)$. All three programs finish in a small fraction of a second, while tracing about $n/3$ beams bounce by bounce would take some $10^{19}$ steps.

Besides the checkpoints of the C++ program, we made these checks, which are not part of the published solutions:

An exact simulation in rational coordinates, reflecting at each mirror without unfolding, traced every beam towards a point $(a,b)$ with $\gcd(a,b)=1$ and $a+b\le120$, which covers all ways with at most $237$ bounces: each bounced $2(a+b)-3$ times and left through the vertex given by $a-b\bmod 3$, so the returns to $C$ agree with $W(R)$ for every odd $R\le237$.
The closed form of Section 10 agrees with a direct count of the conditions of Section 6 for every $R\le40000$.
The inclusion–exclusion as programmed agrees with that count for every $R\equiv5\pmod 6$ up to $40000$, and so does the C++ program, run with --reflections=, for every such $R\lt1500$.
The three programs print the same number for the target.

Footnotes and References

The references below supply the background facts used above. The bounce count $2(a+b)-3$, the colouring rule for the exit vertex, the inclusion–exclusion count and the closed form are derived explicitly in this article.

Project Euler 202 — Laserbeam. The official statement: three inward-facing mirrors form an equilateral triangle with an infinitesimal gap at each vertex; a beam can enter at C, bounce off 11 surfaces and exit through C in 2 ways, and in 80840 ways for 1000001 surfaces. The task asks for the number of ways for 12017639147 surfaces.
Wikipedia — Triangular billiards. Light inside a triangle with mirrored sides reflects with equal angles of incidence and reflection and is extinguished at a vertex; the section on unfolded paths follows a straight line through copies of the triangle, each reflected across the side the line crosses.
Wikipedia — Triangular tiling. Six equilateral triangles meet at every vertex of the tiling, and its vertex arrangement is the A2 lattice, the triangular lattice of Section 2.
Wikipedia — Modular arithmetic. Integers are congruent modulo m when their difference is a multiple of m, equivalently when they leave the same remainder on division by m; this applies to negative integers too, and b mod m denotes that remainder of b.
Wikipedia — Coprime integers. Integers a and b are coprime exactly when the point (a, b) is visible from the origin, with no point of integer coordinates on the segment between them.
Wikipedia — Inclusion–exclusion principle. An alternating sum over sets of properties counts the elements that have none of them, for instance the positive integers up to n coprime to n.
Wikipedia — Dirichlet character. A Dirichlet character modulo m is completely multiplicative, periodic with period m and zero at the integers sharing a factor with m; the non-principal character modulo 3 is 1 at 1 and −1 at 2.
Wikipedia — Euler's totient function. φ(n) counts the integers from 1 to n coprime to n, and Euler's product formula gives φ(n) = n ∏ (1 − 1/p) over the distinct primes p dividing n.
C++ — Euler202.cpp. The linked immutable C++ revision contains distinct_prime_factors, the recursive inclusion–exclusion in solve, count_multiples_with_mod2 and run_checkpoints. It is the implementation record for this article.

Problem 202 source code

C++

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

namespace {

using i64 = long long;
using i128 = __int128_t;

struct Options {
    i64 reflections = 12017639147LL;
    bool run_checkpoints = true;
};

bool parse_i64_after_prefix(const std::string& arg, const std::string& prefix, i64& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    i64 parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<i64>(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_i64_after_prefix(arg, "--reflections=", options.reflections)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }

    return options.reflections >= 1;
}

std::vector<i64> distinct_prime_factors(i64 n) {
    std::vector<i64> factors;
    for (i64 p = 2; p * p <= n; ++p) {
        if (n % p != 0) {
            continue;
        }
        factors.push_back(p);
        while (n % p == 0) {
            n /= p;
        }
    }
    if (n > 1) {
        factors.push_back(n);
    }
    return factors;
}

i64 count_residue_upto(const i64 m, const int residue) {
    if (m <= 0) {
        return 0;
    }

    i64 first = residue;
    if (first == 0) {
        first = 3;
    }
    if (first > m) {
        return 0;
    }

    return 1 + (m - first) / 3;
}

i64 count_multiples_with_mod2(const i64 n, const i64 d) {
    if (d % 3 == 0) {
        return 0;
    }
    const i64 m = (n - 1) / d;
    const int inv_mod3 = (d % 3 == 1) ? 1 : 2;
    const int residue_t = (2 * inv_mod3) % 3;
    return count_residue_upto(m, residue_t);
}

i64 solve(const i64 reflections) {
    const i64 n = (reflections + 3) / 2;
    const std::vector<i64> factors = distinct_prime_factors(n);

    i64 answer = 0;
    const auto dfs = [&](const auto& self, const std::size_t index, const i64 product, const int parity) -> void {
        if (index == factors.size()) {
            const i64 cnt = count_multiples_with_mod2(n, product);
            if ((parity & 1) == 0) {
                answer += cnt;
            } else {
                answer -= cnt;
            }
            return;
        }

        self(self, index + 1, product, parity);

        const i64 p = factors[index];
        if (product > (n - 1) / p) {
            return;
        }
        self(self, index + 1, product * p, parity + 1);
    };

    dfs(dfs, 0U, 1, 0);
    return answer;
}

bool run_checkpoints() {
    if (solve(11) != 2) {
        std::cerr << "Checkpoint failed for 11 reflections" << '\n';
        return false;
    }
    if (solve(1000001) != 80840) {
        std::cerr << "Checkpoint failed for 1000001 reflections" << '\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.reflections) << '\n';
    return 0;
}

Python

# Problem 202: Laserbeam
# Count how many times a laser exits through vertex C after exactly 12017639147 reflections
# in an equilateral triangle.

from math import gcd

def solve():
    reflections = 12017639147
    n = (reflections + 3) // 2
    # Factor n
    factors = []
    tmp = n
    p = 2
    while p * p <= tmp:
        if tmp % p == 0:
            factors.append(p)
            while tmp % p == 0:
                tmp //= p
        p += 1
    if tmp > 1:
        factors.append(tmp)

    # Count t in [1, n) with t%3==2 and gcd(t, n)==1 using inclusion-exclusion
    def count_coprime_mod3(n_val, factors_list):
        ans = 0
        for mask in range(1 << len(factors_list)):
            d = 1
            bits = 0
            for i in range(len(factors_list)):
                if mask & (1 << i):
                    d *= factors_list[i]
                    bits += 1
            if d % 3 == 0:
                continue
            m = (n_val - 1) // d
            # Count t in [1, m] with (t*d) % 3 == 2
            # t*d % 3 == 2 => t % 3 == (2 * modinv(d,3)) % 3
            inv3 = 1 if d % 3 == 1 else 2
            residue = (2 * inv3) % 3
            if residue == 0:
                first = 3
            else:
                first = residue
            if first > m:
                cnt = 0
            else:
                cnt = 1 + (m - first) // 3
            if bits % 2 == 0:
                ans += cnt
            else:
                ans -= cnt
        return ans

    print(count_coprime_mod3(n, factors))

solve()

Java

public class Euler202 {
    public static void main(String[] args) {
        long reflections = 12017639147L;
        long n = (reflections + 3) / 2;
        // Factor n
        java.util.List<Long> factors = new java.util.ArrayList<>();
        long tmp = n;
        for (long p = 2; p * p <= tmp; p++) {
            if (tmp % p == 0) {
                factors.add(p);
                while (tmp % p == 0)
                    tmp /= p;
            }
        }
        if (tmp > 1)
            factors.add(tmp);
        long[] f = factors.stream().mapToLong(Long::longValue).toArray();
        long[] ans = { 0 };
        dfs(f, 0, 1, 0, n, ans);
        System.out.println(ans[0]);
    }

    static void dfs(long[] factors, int idx, long prod, int parity, long n, long[] ans) {
        if (idx == factors.length) {
            long cnt = countMod2(n, prod);
            if (parity % 2 == 0)
                ans[0] += cnt;
            else
                ans[0] -= cnt;
            return;
        }
        dfs(factors, idx + 1, prod, parity, n, ans);
        long p = factors[idx];
        if (prod > (n - 1) / p)
            return;
        dfs(factors, idx + 1, prod * p, parity + 1, n, ans);
    }

    static long countMod2(long n, long d) {
        if (d % 3 == 0)
            return 0;
        long m = (n - 1) / d;
        int inv3 = (d % 3 == 1) ? 1 : 2;
        int res = (2 * inv3) % 3;
        long first = (res == 0) ? 3 : res;
        if (first > m)
            return 0;
        return 1 + (m - first) / 3;
    }
}