Project Euler Problem 883
In this problem we consider triangles drawn on a hexagonal lattice, where each lattice point in the plane has six neighb
Solution
Answer: 14854003484704
Let the hexagonal lattice be identified with the Eisenstein integers
$$\Lambda={a+b\omega : a,b\in \mathbb Z,\ \omega=e^{i\pi/3}},$$
with quadratic norm
$$N(a+b\omega)=a^2+ab+b^2.$$
Distances squared between lattice points are therefore exactly values of
$$Q(x,y)=x^2+xy+y^2.$$
We must count triangles:
- with vertices in $\Lambda$,
- with incentre also in $\Lambda$,
- having at least one $60^\circ$ angle,
- counted up to translation only,
- but with rotations/reflections counted separately.
1. Geometry of a $60^\circ$ triangle on the hexagonal lattice
Put the $60^\circ$ vertex at the origin.
Let the two sides adjacent to that angle be vectors $u,v\in\Lambda$, with angle $60^\circ$ between them.
Using the lattice basis, every such pair can be parameterised by two coprime integers $k>l>0$:
$$u=(k,l),\qquad v=(l,k).$$
The side lengths become
$$|u|=\sqrt{k^2+kl+l^2},\qquad |v|=\sqrt{k^2+kl+l^2},$$
and the third side has length
$$|u-v|=\sqrt{k^2-kl+l^2}.$$
Define
$$s=\sqrt{k^2-kl+l^2}.$$
The condition that the triangle has lattice incentre forces $s\in\mathbb Z$.
The inradius of a $60^\circ$ triangle satisfies
$$r=\frac{\sqrt3}{2}\cdot \frac{ab}{a+b+c},$$
and after substituting the above parameterisation one obtains
$$r^2=\frac{Q(p)}{12d^2},$$
where
$$d=k+l-s,$$
and $p$ is a primitive lattice vector.
Thus counting remarkable triangles reduces to counting lattice vectors satisfying
$$Q(p)\le \frac{12R^2}{d^2}.$$
2. Arithmetic structure
The integer solutions of
$$k^2-kl+l^2=s^2$$
split into two families.
Family 1
$$d=3uv,$$
where
$$u>v,\qquad \gcd(u,v)=1,\qquad u\not\equiv v\pmod3.$$
For fixed $t=uv$, the number of such pairs equals
$$2^{\omega(t)-1},$$
where $\omega(t)$ is the number of distinct prime factors.
This family exists only when
$$t\not\equiv 1\pmod3.$$
Family 2
Let
$$a=u-v.$$
Then
$$d=a(a+3v),$$
with
$$\gcd(u,v)=1,\qquad u\not\equiv v\pmod3.$$
So every admissible $d$ has a multiplicity $M[d]$.
3. Counting lattice points
We need the number of integer pairs satisfying
$$x^2+xy+y^2\le B.$$
Call this quantity $N(B)$.
A classical identity gives
$$N(B) = 1+6\sum_{n\le B}\chi(n)\Big\lfloor\frac{B}{n}\Big\rfloor,$$
where $\chi$ is the nontrivial Dirichlet character modulo $3$:
$$\chi(n)= \begin{cases} 1,&n\equiv1\pmod3,\ -1,&n\equiv2\pmod3,\ 0,&n\equiv0\pmod3. \end{cases}$$
This can be evaluated in $O(\sqrt B)$ using divisor-block grouping.
4. Equilateral triangles
Equilateral triangles are also remarkable.
If the inradius is $r$, then a vertex vector $A$ satisfies
$$Q(A)\le 4R^2.$$
Each equilateral triangle is represented three times (rotations by $120^\circ$), so:
$$T_{\text{eq}}(R)=\frac{N(4R^2)-1}{3}.$$
5. Final counting formula
For every admissible $d$,
$$B=\left\lfloor \frac{12R^2}{d^2}\right\rfloor.$$
If $3\mid d$, all lattice points are allowed; otherwise only an index-3 sublattice contributes.
Hence
$$T(R) = 2\sum_d M[d]\cdot P_d(R) + \frac{N(4R^2)-1}{3},$$
where
$$P_d(R)= \begin{cases} N(B)-1,&3\mid d,\[4pt] N(\lfloor B/3\rfloor)-1,&3\nmid d. \end{cases}$$
The factor $2$ accounts for the reflected configuration.
6. Python implementation
from array import array
from math import gcd, isqrt
def count_hex_points_leq(B, cache):
"""
Count integer pairs (x,y) with x^2 + x*y + y^2 <= B.
"""
if B <= 0:
return 1
if B in cache:
return cache[B]
def chi_prefix(m):
# count of 1 mod 3 minus count of 2 mod 3
return (m + 2) // 3 - (m + 1) // 3
total = 0
i = 1
while i <= B:
q = B // i
j = B // q
total += q * (chi_prefix(j) - chi_prefix(i - 1))
i = j + 1
ans = 1 + 6 * total
cache[B] = ans
return ans
def remarkable_triangles(R_num, R_den=1):
Dmax = isqrt((12 * R_num * R_num) // (R_den * R_den))
# multiplicity for each d
M = array("I", [0]) * (Dmax + 1)
#
# ---- Family 1 ----
#
Nmax = Dmax // 3
omega = array("B", [0]) * (Nmax + 1)
for p in range(2, Nmax + 1):
if omega[p] == 0:
for k in range(p, Nmax + 1, p):
omega[k] += 1
for t in range(2, Nmax + 1):
if t % 3 == 1:
continue
M[3 * t] += 1 << (omega[t] - 1)
#
# ---- Family 2 ----
#
vmax = Dmax // 3
for v in range(1, vmax + 1):
disc = 9 * v * v + 4 * Dmax
amax = (isqrt(disc) - 3 * v) // 2
for a in range(1, amax + 1):
u = v + a
if u % 3 == v % 3:
continue
if gcd(u, v) != 1:
continue
d = a * (a + 3 * v)
M[d] += 1
#
# ---- Main summation ----
#
cache = {}
total_scalene = 0
C_num = 12 * R_num * R_num
C_den = R_den * R_den
for d in range(1, Dmax + 1):
mult = M[d]
if mult == 0:
continue
B = C_num // (C_den * d * d)
if B == 0:
continue
if d % 3 == 0:
pts = count_hex_points_leq(B, cache) - 1
else:
pts = count_hex_points_leq(B // 3, cache) - 1
total_scalene += 2 * mult * pts
#
# ---- Equilateral triangles ----
#
Beq = (4 * R_num * R_num) // (R_den * R_den)
equi_points = count_hex_points_leq(Beq, cache) - 1
total_equilateral = equi_points // 3
return total_scalene + total_equilateral
# verification
print(remarkable_triangles(1, 2)) # 2
print(remarkable_triangles(2)) # 44
print(remarkable_triangles(10)) # 1302
# final answer
print(remarkable_triangles(10**6))
7. Code walkthrough
count_hex_points_leq
Computes
$$N(B)=#{(x,y):x^2+xy+y^2\le B}$$
using the Dirichlet-character formula.
The divisor-block trick groups equal values of
$$\left\lfloor \frac{B}{i}\right\rfloor,$$
giving $O(\sqrt B)$ complexity.
Building M[d]
M[d] stores how many primitive triangle shapes correspond to a given parameter $d$.
Two independent parametrisations are enumerated:
- Family 1 via factorisations $uv=t$,
- Family 2 via $d=a(a+3v)$.
Main summation
For each admissible $d$:
$$B=\left\lfloor\frac{12R^2}{d^2}\right\rfloor$$
determines how many lattice vectors are possible.
A factor of $2$ counts reflected versions separately.
Equilateral contribution
Computed separately using
$$\frac{N(4R^2)-1}{3}.$$
8. Verification
The program reproduces all provided values:
$$T(0.5)=2, \qquad T(2)=44, \qquad T(10)=1302.$$
Running the same algorithm for $R=10^6$ gives
$$14854003484704.$$
This magnitude is reasonable: lattice-point growth is quadratic in $R$, and the arithmetic multiplicities contribute only logarithmic-average growth.
Answer: 14854003484704