3 added 760 characters in body

Imagine I place a turtle on some desired vertex, $v_i$, of a bounded $d$-dimensional integer lattice, $Z^d$, with dimensions $(l_1, ..., l_d)$. The turtle is able to travel from vertex to vertex along the edges of the lattice, but is forbidden from ever returning to a previously visited vertex (i.e. it "burns" the vertices it visits with probability $p = 1$).

We want to teach the turtle to cover the $d$-dimensional integer lattice by repeating a series of $P$ deterministic moves along the set of $2*d$ possible direction vectors. For example, in two-dimensions ($d = 2$), we might label the four possible directions in which the turtle can move as $(N, W, E, S)$ and train the turtle with an instruction set like the following: {{Step 1, GO NORTH}, {Step 2, GO SOUTH}, ..., {Step P, GO SOUTH}, {GOTO Step 1}}. With the right instruction set, after some number of GOTO loops, the turtle will visit all possible vertices and quit.

Provided that the turtle can be initialized anywhere one desires on the lattice, and provided dimensions of the $d$-dimensional integer lattice, $(l_1, ..., l_d)$, what is the smallest value of $P$ that permits the turtle to cover the lattice?

Note - The turtle is forbidden from leaving the grid, and any instruction that leads to this will be counted as illegal (not simply ignored).

Let me provide a few trivial examples:

For $d = 1$, the optimal solution is to place the turtle at the far left or right-side of the lattice, and then (assuming the turtle is placed on the far left), program the turtle with the two-line $(P = 1)$ instruction set: {{Step 1, GO RIGHT}, {GOTO Step 1}}.

For $d = 2$, with a bounded lattice that has dimensions $N$ by $M$, if $M < N$, we can program the turtle to: (1) first move from $(i, 1)$ to $(i, M)$, (2) move from $(i, M)$ to $(i+1, M)$, (3) move from $(i+1, M)$ to $(i+1, 1)$, and finally (4) move from $(i+1, 1)$ to $(i+2, 1)$, then GOTO (1) until we sweep through the 2D lattice. This constitutes a value of $P = (M - 1) + 1 + (M - 1) + 1 = 2M$. I wonder if it's possible to do better?

2 added 145 characters in body

Imagine I place a turtle on some desired vertex, $v_i$, of a bounded $d$-dimensional integer lattice, $Z^d$, with dimensions $(l_1, ..., l_d)$. The turtle is able to travel from vertex to vertex along the edges of the lattice, but is forbidden from ever returning to a previously visited vertex (i.e. it "burns" the vertices it visits with probability $p = 1$).

We want to teach the turtle to cover the $d$-dimensional integer lattice by repeating a series of $P$ deterministic moves along the set of $2*d$ possible direction vectors. For example, in two-dimensions ($d = 2$), we might label the four possible directions in which the turtle can move as $(N, W, E, S)$ and train the turtle with an instruction set like the following: {{Step 1, GO NORTH}, {Step 2, GO SOUTH}, ..., {Step P, GO SOUTH}, {GOTO Step 1}}. With the right instruction set, after some number of GOTO loops, the turtle will visit all possible vertices and quit.

Provided that the turtle can be initialized anywhere one desires on the lattice, and provided dimensions of the $d$-dimensional integer lattice, $(l_1, ..., l_d)$, what is the smallest value of $P$ that permits the turtle to cover the lattice?

Note - The turtle is forbidden from leaving the grid, and any instruction that leads to this will be counted as illegal (not simply ignored).

1

# Covering a $d$-dimensional integer lattice by repeating a minimal set of deterministic moves

Imagine I place a turtle on some desired vertex, $v_i$, of a bounded $d$-dimensional integer lattice, $Z^d$, with dimensions $(l_1, ..., l_d)$. The turtle is able to travel from vertex to vertex along the edges of the lattice, but is forbidden from ever returning to a previously visited vertex (i.e. it "burns" the vertices it visits with probability $p = 1$).

We want to teach the turtle to cover the $d$-dimensional integer lattice by repeating a series of $P$ deterministic moves along the set of $2*d$ possible direction vectors. For example, in two-dimensions ($d = 2$), we might label the four possible directions in which the turtle can move as $(N, W, E, S)$ and train the turtle with an instruction set like the following: {{Step 1, GO NORTH}, {Step 2, GO SOUTH}, ..., {Step P, GO SOUTH}, {GOTO Step 1}}. With the right instruction set, after some number of GOTO loops, the turtle will visit all possible vertices and quit.

Provided that the turtle can be initialized anywhere one desires on the lattice, and provided dimensions of the $d$-dimensional integer lattice, $(l_1, ..., l_d)$, what is the smallest value of $P$ that permits the turtle to cover the lattice?