Project Euler Problem 351
A hexagonal orchard of order n is a triangular lattice made up of points within a regular hexagon with side n.
Solution
Answer: 11762187201804552
Let the center of the orchard be the origin. A lattice point is hidden if another lattice point lies on the same ray from the center and is closer.
The key observation is:
A point is visible from the center iff its direction vector is primitive (its coordinates are coprime).
We will turn the geometry into a number-theoretic counting problem involving Euler’s totient function.
1. Mathematical analysis
Step 1: Model the hexagonal lattice
A hexagonal orchard of order $n$ consists of all lattice points inside a regular hexagon of side $n$.
Because of the hexagonal symmetry, it suffices to count points in one of the six $60^\circ$ sectors and multiply by 6.
Inside one sector, lattice points can be represented by integer coordinates
$$(a,b), \qquad a,b\ge 0,\qquad a+b\le n.$$
The center $(0,0)$ is excluded.
A point $(a,b)$ is visible from the center iff
$$\gcd(a,b)=1.$$
Why? Because if $d=\gcd(a,b)>1$, then
$$(a,b)=d\left(\frac a d,\frac b d\right),$$
so the closer lattice point $(a/d,b/d)$ blocks it.
Thus hidden points correspond exactly to non-primitive vectors.
Step 2: Count visible points in one sector
Fix $k=a+b$, where
$$1 \le k \le n.$$
We want the number of primitive pairs $(a,b)$ with
$$a+b=k.$$
Since $b=k-a$,
$$\gcd(a,b)=\gcd(a,k).$$
Thus visibility means $a$ is coprime to $k$.
The number of such $a\in{1,\dots,k-1}$ is exactly
$$\varphi(k),$$
where $\varphi$ is Euler’s totient function.
Hence:
- visible points in one sector:
$$\sum_{k=1}^{n} \varphi(k).$$
Multiplying by 6 gives total visible non-center points:
$$6\sum_{k=1}^{n}\varphi(k).$$
Step 3: Count all points
In one sector, the total number of non-center lattice points is
$$1+2+\cdots+n = \frac{n(n+1)}{2}.$$
Across all 6 sectors:
$$6\cdot \frac{n(n+1)}{2}.$$
Therefore hidden points are
$$H(n) = 6\left( \frac{n(n+1)}{2} - \sum_{k=1}^{n}\varphi(k) \right).$$
So the problem reduces to computing the summatory totient
$$\Phi(n)=\sum_{k=1}^{n}\varphi(k)$$
for $n=10^8$.
Step 4: Efficient computation of the totient summatory function
A direct sieve to $10^8$ is too expensive.
Use the classic divide-and-conquer identity:
$$\Phi(n) = \frac{n(n+1)}{2} - \sum_{i=2}^{n}\Phi!\left(\left\lfloor\frac{n}{i}\right\rfloor\right).$$
The floor values repeat in ranges, so group equal quotients:
If
$$q=\left\lfloor \frac{n}{l}\right\rfloor,$$
then all indices
$$l \le i \le r=\left\lfloor \frac{n}{q}\right\rfloor$$
share the same quotient.
This reduces complexity to roughly
$$O(n^{2/3})$$
with memoization.
2. Python implementation
from functools import lru_cache
def hidden_points(n):
@lru_cache(None)
def totient_sum(x):
# S(x) = sum_{k<=x} phi(k)
if x == 1:
return 1
# Start with 1 + 2 + ... + x
result = x * (x + 1) // 2
l = 2
while l <= x:
q = x // l
r = x // q
# Subtract grouped contributions
result -= (r - l + 1) * totient_sum(q)
l = r + 1
return result
visible_sector = totient_sum(n)
total_sector = n * (n + 1) // 2
return 6 * (total_sector - visible_sector)
# Verification against examples
print(hidden_points(5)) # 30
print(hidden_points(10)) # 138
print(hidden_points(1000)) # 1177848
# Final answer
print(hidden_points(100000000))
3. Code walkthrough
totient_sum(x)
Computes
$$\Phi(x)=\sum_{k\le x}\varphi(k).$$
Using the identity:
$$\Phi(x) = \frac{x(x+1)}{2} - \sum_{i=2}^{x} \Phi!\left(\left\lfloor \frac{x}{i}\right\rfloor\right).$$
The loop groups equal quotient values:
q = x // l
r = x // q
Every index in [l, r] has the same quotient q, so we subtract:
(r - l + 1) * totient_sum(q)
Memoization prevents recomputation.
Final computation
We use:
$$H(n) = 6\left( \frac{n(n+1)}{2} - \Phi(n) \right).$$
4. Verification
The formula reproduces the problem’s examples exactly:
- $H(5)=30$
- $H(10)=138$
- $H(1000)=1177848$
The final result is positive and has the expected order of magnitude (roughly proportional to $n^2$).
Answer: 11762187201804552