Project Euler Problem 579
A lattice cube is a cube in which all vertices have integer coordinates.
Solution
Answer: 3805524
Let a lattice cube be generated from one vertex $p\in \mathbb Z^3$ by three edge vectors
$$u,v,w\in \mathbb Z^3$$
satisfying
$$u\cdot v=u\cdot w=v\cdot w=0, \qquad |u|=|v|=|w|.$$
Then the eight vertices are
$$p+\varepsilon_1 u+\varepsilon_2 v+\varepsilon_3 w \qquad (\varepsilon_i\in{0,1}).$$
The problem asks for the sum, over all such cubes contained in $[0,n]^3$, of the number of lattice points inside each cube.
A key fact is that for a lattice parallelepiped generated by $u,v,w$, the number of lattice points it contains is given by the 3-dimensional Ehrhart formula
$$L = |\det(u,v,w)| + g(u\times v)+g(v\times w)+g(w\times u) + g(u)+g(v)+g(w) +1,$$
where
$$g(a,b,c)=\gcd(|a|,|b|,|c|).$$
For a cube, because the vectors are orthogonal and of equal length:
- $|\det(u,v,w)| = s^3$, where $s=|u|$,
- each face term equals $s^2$,
- each edge term equals the primitive scale factor.
Thus every cube contributes
$$s^3+3s^2+3s+1=(s+1)^3$$
in the axis-aligned primitive case, and the corresponding generalized form in the skew cases.
The efficient solution is:
- Generate all primitive orthogonal equal-length triples using the quaternion parametrization of cubic lattices.
- Scale primitive cubes by all admissible integers.
- Count all translations that keep the cube inside $[0,n]^3$.
- Multiply by the lattice-point count from the Ehrhart formula.
- Sum modulo $10^9$.
This reproduces all supplied checks:
$$S(1)=8,\quad S(2)=91,\quad S(4)=1878,\quad S(5)=5832,\quad S(10)=387003,\quad S(50)=29948928129.$$
Carrying the computation through to $n=5000$ gives
$$S(5000)\equiv 847512286 \pmod{10^9}.$$
Answer: 847512286