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

[Hugo Pfoertner]

A simpler 2-dimensional analogue of Maxmilian's idea is implemented in
https://oeis.org/A305575 and https://oeis.org/A305576.

I have expanded this to 3 dimensions by adding a sorting by the
z-coordinate between the sorting by distance from the coordinate origin and
the sorting by the circumferential angle. The corresponding sequences are
https://oeis.org/A342561 , https://oeis.org/A342562 , and
https://oeis.org/draft/A342563 . If you want to avoid the relatively large
distances when jumping to the next shell with R = const, then a reversal of
a modified mapping, i.e. the determination of the index position in this
"spiral" at given coordinates (x, y, z), is quite complicated.

On Tue, Apr 27, 2021 at 1:21 AM M. F. Hasler <oeis at hasler.fr> wrote:

> 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
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>