Project Euler Problem 577

Solution

Answer: 265695031399260211

Let the triangular lattice be generated by the basis vectors

$$e_1=(1,0), \qquad e_2=\left(\tfrac12,\tfrac{\sqrt3}{2}\right).$$

The large equilateral triangle of side length $n$ consists of all lattice points

$$(i,j)\qquad (i\ge0,\ j\ge0,\ i+j\le n).$$

We must count all regular hexagons whose vertices are lattice points.

---

1. Mathematical analysis

Step 1: Describe every lattice regular hexagon

Take one side vector of the hexagon to be

$$u=a e_1+b e_2, \qquad a,b\ge0, \qquad (a,b)\ne(0,0).$$

Rotating by $60^\circ$ gives the next side vector

$$v=-b e_1+(a+b)e_2.$$

A regular hexagon is obtained by walking around with side vectors

$$u,\ v,\ v-u,\ -u,\ -v,\ u-v.$$

Thus every lattice regular hexagon is determined by integers $a,b\ge0$, not both zero.

Let

$$t=a+b.$$

We now determine how many placements are possible.

---

Step 2: Size of the containing triangle

Translate the hexagon so that one vertex is at the origin.

Its vertices become

$$(0,0),\quad (a,b),\quad (a-b,a+2b),\quad (-b,a+b),\quad (-a-b,b),\quad (-a,-b).$$

After shifting to make all coordinates nonnegative, the hexagon fits exactly inside a smallest equilateral lattice triangle of side length

$$3(a+b)=3t.$$

Therefore:

• a hexagon of type $t$ can be placed anywhere inside the big triangle of side $n$,
• provided a triangle of side $3t$ fits inside it.

The number of placements equals the number of lattice translations of a side-$3t$ triangle inside a side-$n$ triangle:

$$\frac{(n-3t+1)(n-3t+2)}2.$$

---

Step 3: Count the different shapes for fixed $t$

For fixed

$$t=a+b,$$

the possibilities are

$$(a,b)=(0,t),(1,t-1),\dots,(t-1,1),$$

exactly $t$ distinct orientations/shapes.

Hence

$$H(n)=\sum_{t=1}^{\lfloor n/3\rfloor} t\cdot \frac{(n-3t+1)(n-3t+2)}2.$$

So the final task is

$$\sum_{n=3}^{12345} H(n).$$

---

Step 4: Verify against the examples

$n=3$

Only $t=1$:

$$H(3)=1\cdot \frac{1\cdot2}{2}=1.$$

Correct.

---

$n=6$

$$H(6) = 1\cdot \frac{4\cdot5}{2} + 2\cdot \frac{1\cdot2}{2} = 10+2=12.$$

Correct.

---

$n=20$

$$H(20) = \sum_{t=1}^{6} t\cdot \frac{(20-3t+1)(20-3t+2)}2 =966.$$

Correct.

---

2. Python implementation

def H(n):
    total = 0

    # t = a + b
    for t in range(1, n // 3 + 1):

        # Number of placements of a side-(3t) triangle
        placements = (n - 3 * t + 1) * (n - 3 * t + 2) // 2

        # There are exactly t distinct hexagon shapes
        total += t * placements

    return total

# Compute the required sum
answer = sum(H(n) for n in range(3, 12346))

print(answer)

---

3. Code walkthrough

Function H(n)

for t in range(1, n // 3 + 1):

The parameter $t=a+b$.

Since the smallest containing triangle has side $3t$, we need $3t\le n$.

---

placements = (n - 3 * t + 1) * (n - 3 * t + 2) // 2

Counts how many translations of the minimal containing triangle fit inside the big triangle.

This is a triangular-number count.

---

total += t * placements

For fixed $t$, there are exactly $t$ distinct lattice hexagon shapes.

---

answer = sum(H(n) for n in range(3, 12346))

Computes the required sum.

---

4. Final verification

The formula reproduces all examples:

• $H(3)=1$
• $H(6)=12$
• $H(20)=966$

The growth rate is roughly quartic in $n$, so a final answer around $10^{17}$–$10^{18}$ is reasonable for $n=12345$.

The exact computation gives:

$$265695031399260211.$$

---

Answer: 265695031399260211