[seqfan] Re: Anyone have a 3-D "Ulam" spiral?

[M. F. Hasler]

On Mon, Apr 26, 2021 at 1:03 AM Neil Sloane <njasloane at gmail.com> wrote:

> Dear Sequence Fans,
> In two dimensions there is an obvious way to number the cells of the square
> grid starting at the origin and going around in what is often called the
> square spiral (aka Ulam spiral).  It visits every square once and gradually
> works its way outwards.  Is there a nice analog in 3D?
>

One possible systematic approach to construct a hamiltonian path visiting
all grid points could be the following:

- classify the grid points into "shells" by (square of) Euclidean distance
(2-norm) from the origin
  (alternatives : use sup  (= oo-)norm or taxicab (= 1-)norm).
  shell 0 : the origin O = (0,0,0)
  shell 1 : (1,0,0), (0,1,0), (0,0,1), (-1,0,0), (0,-1,0), (0,0,-1)
  shell 2 (distance sqrt(2)): (1,1,0), ...
  shell 3 (distance sqrt(3)): (1,1,1), ...
  shell 4 (distance  2): (2,0,0), ...

(Spoiler: shell 0 concatenated with shell 1 as written above is certainly
the start of a "greedy-optimal" path as defined in the sequel.)

- use one among the shortest (again, say: w.r.t. 2-norm) hamiltonian paths
  which travels exactly once through all of the points of one shell after
the other.
  (By "length of a path" I mean here the sum of the Euclidean lengths of
all the edges.)

Obviously, there is a "trivial" symmetry which will always yield at least 6
equivalent solutions if we don't fix one preferred direction,
so let's say we start WLOG in direction (1,0,0).
With this convention, we still will have "equivalent" candidates because of
other symmetries.
To fix a choice, we could decide to order the chains (of equal total
length) by lexicographical order in the spirit above:
 point after point, 1 before 0 before -1, and x before y before z.

But the total length must remain the priority over this lexicographical
ordering which should only serve to choose among several solutions
equivalent up to symmetry.

So we must not do this lexicographical ordering after completion of a given
shell
at the risk of getting a suboptimal solution when considering completion of
the subsequent shells.

In order to ensure a well defined optimal solution, we must probably fix
some lookahead,
and choose, shell by shell, the optimal path without searching further than
that lookahead.

For example, lookahead = 2 would mean to consider the total length of all
paths that complete shell 1 and then shell 2,
and take the shortest among these to complete shell 1.
Then, to complete shell 2, we'd consider the shortest extension of that
path which completes shell 2 + shell 3 in the shortest possible way,
and so on.

I think it is well probable that for each lookahead threshold, we might get
a different (probably overall better and better) solution.
I have no idea if there will be some "convergence" (stabilization) for
larger and larger lookahead, and if so, whether and how this could be
proved.

- Maximilian