Lattice Points in Lattice Cubes

A lattice cube is a cube in which all vertices have integer coordinates. Let $C(n)$ be the number of different lattice cubes in which the coordinates of all vertices range between (and including) $0$ and $n$. Two cubes are hereby considered different if any of their vertices have different coordinates.
For example, $C(1)=1$, $C(2)=9$, $C(4)=100$, $C(5)=229$, $C(10)=4469$ and $C(50)=8154671$.

Different cubes may contain different numbers of lattice points.

For example, the cube with the vertices
$(0, 0, 0)$, $(3, 0, 0)$, $(0, 3, 0)$, $(0, 0, 3)$, $(0, 3, 3)$, $(3, 0, 3)$, $(3, 3, 0)$, $(3, 3, 3)$ contains $64$ lattice points ($56$ lattice points on the surface including the $8$ vertices and $8$ points within the cube).
In contrast, the cube with the vertices
$(0, 2, 2)$, $(1, 4, 4)$, $(2, 0, 3)$, $(2, 3, 0)$, $(3, 2, 5)$, $(3, 5, 2)$, $(4, 1, 1)$, $(5, 3, 3)$ contains only $40$ lattice points ($20$ points on the surface and $20$ points within the cube), although both cubes have the same side length $3$.

Let $S(n)$ be the sum of the lattice points contained in the different lattice cubes in which the coordinates of all vertices range between (and including) $0$ and $n$.
For example, $S(1)=8$, $S(2)=91$, $S(4)=1878$, $S(5)=5832$, $S(10)=387003$ and $S(50)=29948928129$.
Find $S(5000) \bmod 10^9$.

This problem can be solved using a dynamic programming approach in combination with the technique of integer partitioning, which breaks up an integer into a sum of other integers and uses those solutions recursively.

Firstly, let’s define C(n, m) as the number of different lattice cubes of side length m in which the coordinates of all vertices range between 0 and n, where 0 ≤ n, m ≤ 5000.

The cube has all its vertices in the range [0, n] if and only if it is contained in an (n+1) x (n+1) x (n+1) box. For each m from 1 to n+1, we can put the cube in $((n+1)-m)^3$ ways. So, C(n, m) = $((n+1)-m)^3$.

Now, let’s define S(n, m) as the sum of the lattice points contained in the different lattice cubes of side length m in which the coordinates of all vertices range between 0 and n.

The total number of lattice points in a cube of side length m is m^3 + 3m^2 + 12m + 8. So, S(n, m) = C(n, m) * (m^3 + 3m^2 + 12m + 8).

Finally, S(n) is the sum of S(n, m) for all m from 1 to n+1.

S(n) can be computed with the following pseudocode:

“`
S = [0]*(n+2)
for m in range(1, n+2):
for i in range(n, m-2, -1):
S[i] = (S[i] + ((i+1) – m)^3 * (m^3 + 3m^2 + 12m + 8)) mod 10^9
return S[n]
“`

This solution takes O(n^2) operations. Since n ≤ 5000, it can be computed in a reasonable time.

After calculating S(5000), you need to return the result mod $10^9$, as required by the problem statement.

Please note that this problem is suited for computer programming and it is difficult (if not impossible) to compute S(5000) mod $10^9$ manually.

More Answers: