Problem 351: Hexagonal Orchards

Mathematical Foundation

We work in the standard hexagonal coordinate system with basis vectors $\mathbf{e}_1 = (1,0)$ and $\mathbf{e}_2 = (1/2, \sqrt{3}/2)$. Every lattice point in the hexagonal grid of order $n$ can be written as $a\mathbf{e}_1 + b\mathbf{e}_2$ for integers $a, b$ satisfying certain constraints. The hexagonal grid of order $n$ has exactly $3n(n+1)$ lattice points excluding the center.

Theorem 1 (Visibility criterion). A lattice point $P = a\mathbf{e}_1 + b\mathbf{e}_2$ is visible from the origin if and only if $\gcd(a, b) = 1$.

Proof. Suppose $\gcd(a,b) = d > 1$. Then the point $Q = (a/d)\mathbf{e}_1 + (b/d)\mathbf{e}_2$ is a lattice point lying on the segment from the origin to $P$, so $P$ is not visible. Conversely, if $\gcd(a,b) = 1$, then no lattice point lies strictly between the origin and $P$ on the line through them, since any such point would have the form $(ta, tb)$ for $0 < t < 1$ rational, forcing $t = k/d$ with $d | a$ and $d | b$, contradicting $\gcd(a,b)=1$. $\square$

Theorem 2 (Visible point count). The number of visible lattice points in the hexagonal grid of order $n$ is

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

Proof. By the six-fold rotational symmetry of the hexagonal lattice, it suffices to count visible points in one fundamental sector and multiply by 6. In one sector, the lattice points at distance layer $k$ (for $1 \le k \le n$) correspond to pairs $(a,b)$ with $a + b = k$, $a \ge 1$, $b \ge 0$ (or an equivalent parameterization). A point at layer $k$ is visible if and only if $\gcd(a,b) = 1$. The number of integers $b$ with $0 \le b < k$ and $\gcd(b,k) = 1$ is exactly $\varphi(k)$. Summing over layers and multiplying by the symmetry factor gives $V(n) = 6\sum_{k=1}^{n}\varphi(k)$. $\square$

Corollary (Hidden point formula). The number of hidden points is

Proof. Immediate from $H(n) = T(n) - V(n)$ where $T(n) = 3n(n+1)$. $\square$

Editorial

H(n) = 3n(n+1) - 6 * sum(phi(k) for k in 1..n) We sieve Euler’s totient function up to n = 10^8. We compute Euler’s totient via linear sieve. We then accumulate prefix sum. Finally, compute hidden count.

Pseudocode

Compute Euler's totient via linear sieve
Accumulate prefix sum
Compute hidden count

Complexity Analysis

• Time: $O(n \log \log n)$ for the sieve of Euler’s totient function (each integer is visited once per prime factor), plus $O(n)$ for the prefix sum. Total: $O(n \log \log n)$.
• Space: $O(n)$ for the array storing $\varphi(k)$ for $k = 1, \ldots, n$.

Answer

#include <bits/stdc++.h>
using namespace std;

/*
 * Problem 351: Hexagonal Orchards
 *
 * H(n) = 3n(n+1) - 6 * sum_{k=1}^{n} phi(k)
 *
 * We sieve Euler's totient function up to n = 10^8
 * and compute the prefix sum.
 */

int main() {
    const int N = 100000000; // 10^8

    // Sieve for Euler's totient function
    vector<int> phi(N + 1);
    iota(phi.begin(), phi.end(), 0); // phi[i] = i initially

    for (int i = 2; i <= N; i++) {
        if (phi[i] == i) { // i is prime
            for (int j = i; j <= N; j += i) {
                phi[j] -= phi[j] / i;
            }
        }
    }

    // Compute sum of phi[k] for k = 1..N
    long long phi_sum = 0;
    for (int k = 1; k <= N; k++) {
        phi_sum += phi[k];
    }

    // H(n) = 3n(n+1) - 6 * phi_sum
    long long n = N;
    long long total = 3LL * n * (n + 1);
    long long hidden = total - 6LL * phi_sum;

    cout << hidden << endl;

    return 0;
}

"""
Problem 351: Hexagonal Orchards

H(n) = 3*n*(n+1) - 6 * sum(phi(k) for k in 1..n)

We sieve Euler's totient function up to n = 10^8.
"""

def solve():
    N = 100000000  # 10^8

    # Sieve for Euler's totient function
    phi = list(range(N + 1))

    for i in range(2, N + 1):
        if phi[i] == i:  # i is prime
            for j in range(i, N + 1, i):
                phi[j] -= phi[j] // i

    # Compute sum of phi[k] for k = 1..N
    phi_sum = sum(phi[1:])

    # H(n) = 3*n*(n+1) - 6 * phi_sum
    total = 3 * N * (N + 1)
    hidden = total - 6 * phi_sum

    print(hidden)

if __name__ == "__main__":
    solve()