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

[Neil Fernandez]

Hi Neil and everyone,

In message <CAAOnSgSZqG_2Aesj6VcjHQ0MyNTX3=vpnwO+s7TV3aFG_vEMKQ at mail.gma
il.com>, Neil Sloane <njasloane at gmail.com> writes

>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?

Possibly this...


Consider 2D rule first.

**************
2D Ulam spiral
**************

RULE
====
(Notation: lose the brackets and commas from coordinate notation and
write "a" for -1):

- Start at origin

- Fill one shell at a time, where n-shell contains all points that
satisfy two conditions:

1) each coordinate has absolute value <= n;
2) not in a shell with smaller n

- Cycled list of rules: x+, y+, x-, y-, where x+ means increment
x_coordinate by 1, etc.

- At each step, apply the first rule you can.


GENERATE SPIRAL
===============

00 (now we apply x+)

10 (now we apply y+)
11 (now we apply x-)
01
a1 (now we apply y-)
a0
aa (now we apply x+ again)
0a
1a (shell is now full, so apply x+)

2a
etc,


One algorithm for a 3D spiral is as follows.

**************
3D Ulam spiral
**************

RULE
====
- same as for 2D, but with rules x+, y+, z+, x-, y-, z-, and then list
rule pairs with consecutive (0-jump) pairs first, then 1-jump pairs,
i.e.
x+y+, y+z+, z+x-, x-y-, y-z-, z-x+;
x+z+, y+x-, z+y-, x-z-, y-x+, z-y+


GENERATE SPIRAL
===============
We are expecting 26 points in shell 1.

We get:

000 (now we apply x+)

100 (now we apply y+)
110 (now we apply z+)
111 (now we apply x-)
011 
a11 (now we apply y+)
a01
aa1 (now we apply z-)
aa0
aaa (now we apply x+)
0aa
1aa (now we apply y+)
10a
11a (now we apply x-)
01a
a1a (now we apply y-)
a0a (now we apply x+)
00a (now no single rule will work, so try pairs, beginning x+y+; first
that works is y+z+)
010 (check singles beginning with y+; first that works is x-)
a10 (now we apply y-)
a00 (now we apply z-)
a0a (now no single rule will work, so try pairs, beginning z-x+; first
that works is y+z+)
a10 (check singles beginning with y+; first that works is y-)
a00 (no singles work, no consecutive pairs work, check 1-jump pairs
beginning with y-x+; this works)
0a0 (now we apply x+)
1a0 (now we apply z+)
1a1 (now we apply x-)
0a1 (now we apply y+)
001 (now we apply x+)
101 (1-shell is now full; start 2-shell either at 201 or 200; I am not
sure which rule is best for shell-jumping)

If the most recent rule applied was a pair, we start looking at singles
beginning with the first element of the pair. E.g. if we have just
applied x+y+, then when deciding what point to move to next we start
checking with x+.

I did this by hand and hope it generalises to n-shells where n>1.

Neil


-- 
Neil Fernandez