Shell enumeration of ℕ × ℕ

This article page is a stub, please help by expanding it.

This article needs more work.

Please help by expanding it!

The shell enumeration of

ℕ × ℕ

is a bijection (one-to-one and onto mapping) from

ℕ

to

ℕ × ℕ

, where

ℕ = {0, 1, 2, ...}

.^[1] If the shell enumeration goes from (0, 0) to (1, 0) instead of (0, 1), we just get the mirror image through the rising diagonal, thus swapping the

x

and

y

coordinates.

{{(0, 0)}, {(0, 1), (1, 1), (1, 0)}, {(2, 0), (2, 1), (2, 2), (1, 2), (0, 2)}, {(0, 3), (1, 3), (2, 3), (3, 3), (3, 2), (3, 1), (3, 0)}, {(4, 0), (4, 1), (4, 2), (4, 3), (4, 4), (3, 4), (2, 4), (1, 4), (0, 4)}, {(0, 5), (1, 5), (2, 5), (3, 5), (4, 5), (5, 5), (5, 4), (5, 3), (5, 2), (5, 1), (5, 0)}, {(6, 0), (6, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 6), (5, 6), (4, 6), (3, 6), (2, 6), (1, 6), (0, 6)}, ...}

Zero indexed sequence of

( x, y)

pairs of the shell enumeration of

ℕ × ℕ

.

{(0, 0), (0, 1), (1, 1), (1, 0), (2, 0), (2, 1), (2, 2), (1, 2), (0, 2), (0, 3), (1, 3), (2, 3), (3, 3), (3, 2), (3, 1), (3, 0), (4, 0), (4, 1), (4, 2), (4, 3), (4, 4), (3, 4), (2, 4), (1, 4), (0, 4), (0, 5), (1, 5), (2, 5), (3, 5), (4, 5), (5, 5), (5, 4), (5, 3), (5, 2), (5, 1), (5, 0), (6, 0), (6, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 6), (5, 6), (4, 6), (3, 6), (2, 6), (1, 6), (0, 6), ...}

A319514 The shell enumeration of

ℕ × ℕ

where

ℕ = {0, 1, 2, ...}

, also called boustrophedonic Rosenberg-Strong function. Terms are interleaved

x

and

y

coordinates.

{0, 0, 0, 1, 1, 1, 1, 0, 2, 0, 2, 1, 2, 2, 1, 2, 0, 2, 0, 3, 1, 3, 2, 3, 3, 3, 3, 2, 3, 1, 3, 0, 4, 0, 4, 1, 4, 2, 4, 3, 4, 4, 3, 4, 2, 4, 1, 4, 0, 4, 0, 5, 1, 5, 2, 5, 3, 5, 4, 5, 5, 5, 5, 4, 5, 3, 5, 2, 5, 1, 5, 0, 6, 0, 6, 1, 6, 2, 6, 3, 6, 4, 6, 5, 6, 6, 5, ...}

Sequences pertaining to

( x, y)

pairs of the shell enumeration of

ℕ × ℕ

Sequence

A-number

x

{0, 0, 1, 1, 2, 2, 2, 1, 0, 0, 1, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 3, 2, 1, 0, 0, 1, 2, 3, 4, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 5, 4, 3, 2, 1, 0, 0, 1, 2, 3, 4, 5, 6, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 7, 6, 5, 4, 3, 2, 1, 0, 0, 1, 2, 3, 4, 5, ...}

A319289

y

{0, 1, 1, 0, 0, 1, 2, 2, 2, 3, 3, 3, 3, 2, 1, 0, 0, 1, 2, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 4, 3, 2, 1, 0, 0, 1, 2, 3, 4, 5, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 6, 5, 4, 3, 2, 1, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, ...}

A319290

Δ x

{0, 1, 0, 1, 0, 0, −1, −1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, −1, −1, −1, −1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, ...}

A??????

Δ y

{1, 0, −1, 0, 1, 1, 0, 0, 1, 0, 0, 0, −1, −1, −1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, −1, −1, −1, −1, −1, 0, ...}

A??????

Pairing function

ℕ → ℕ × ℕ

For

n = 0

: (0, 0);
For

n ≥ 1

:

k (n) ≡ 1 (mod 2)
: (odd indexed shell)

t (n) = 0
(first
k (n)
points):
(n mod s (k (n)), k (n));
t (n) = 1
(last
k (n) + 1
points):
(k (n), k (n) − {n − o (k (n))});

k (n) ≡ 0 (mod 2)
: (even indexed shell)

t (n) = 0
(first
k (n)
points):
(k (n), n mod s (k (n)));
t (n) = 1
(last
k (n) + 1
points):
(k (n) − {n − o (k (n))}, k (n));

where

k (n) =

⌊

2√ n

⌋

is the shell index,

t (n) =

⌊ n / o (k (n)) ⌋

yields either 0 (first

k (n)

points of shell) or 1 (last

k (n) + 1

points of shell).

This can be rewritten in a one liner as (where the row vector is right-multiplied by [either identity or swap] matrix)

( x, y) = (0, 0) + [n ≥ 1] { [t (n) = 0] (n mod s (k (n)), k (n)) + [t (n) = 1] (k (n), k (n) − {n − o (k (n))}) }

k (n) mod 2		1 − {k (n) mod 2}
1 − {k (n) mod 2}		k (n) mod 2

,

where

[·]

is the Iverson bracket.

ℕ × ℕ → ℕ

With nonnegative shell index given by

k = max (x, y)

:

If
k mod 2 ≡ 1
: (odd indexed shell)

If
x = k : n = (k + 1) 2 − 1 − y
;
If
y = k : n = k 2 + x
;

If
k mod 2 ≡ 0
: (even indexed shell)

If
x = k : n = k 2 + y
;
If
y = k : n = (k + 1) 2 − 1 − x
.

This can be rewritten in a one liner as

n = [k mod 2 ≡ 1] { [x = k ] ((k + 1) 2 − 1 − y) + [ y = k ] (k 2 + x) } + [k mod 2 ≡ 0] { [x = k ] (k 2 + y) + [ y = k ] ((k + 1) 2 − 1 − x) },

where

k = max (x, y)

and

[·]

is the Iverson bracket.

Shell enumeration path

Shell enumeration path expressed with absolute headings

As the shell enumeration of all complex numbers with nonnegative integer real part and imaginary part.

We can have the sequence of absolute headings before each move along the shell enumeration path expressed by the exponents {0, 1, 2, 3} = {right, up, left, down}, i.e. exponents {0, 1, 2, 3} of

i

:

{i 0, i 1, i 2, i 3}

.
For each shell

n ≥ 1

, sequence of absolute headings before each move along path of shell enumeration of all complex numbers with nonnegative integer real part and imaginary part.

{{1, 0, 3}, {0, 1, 1, 2, 2}, {1, 0, 0, 0, 3, 3, 3}, {0, 1, 1, 1, 1, 2, 2, 2, 2}, {1, 0, 0, 0, 0, 0, 3, 3, 3, 3, 3}, {0, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2}, {1, 0, 0, 0, 0, 0, 0, 0, 3, 3, 3, 3, 3, 3, 3}, ...}

A?????? Zero indexed sequence of absolute headings before each move along path of shell enumeration of all complex numbers with nonnegative integer real part and imaginary part.

{1, 0, 3, 0, 1, 1, 2, 2, 1, 0, 0, 0, 3, 3, 3, 0, 1, 1, 1, 1, 2, 2, 2, 2, 1, 0, 0, 0, 0, 0, 3, 3, 3, 3, 3, 0, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 1, 0, 0, 0, 0, 0, 0, 0, 3, 3, 3, 3, 3, 3, 3, ...}

Shell enumeration path expressed with relative headings

As the shell enumeration of all complex numbers with nonnegative integer real part and imaginary part.

We can have the sequence of relative headings before each move along the shell enumeration path expressed by the exponents { − 1, 0, +1} = {clockwise, forward, counterclockwise}, i.e. exponents { − 1, 0, + 1} of

i

:

{i − 1, i 0, i + 1}

used as multiplicand.
If we consider the absolute heading to be initially to the left (

i 2

) when at initial point (0, 0), and see (0, 0) as the completed 0-th shell, then

for
n ≥ 0
, when the
n
-th shell is completed, the 2 successive relative headings after completing
(n + 1) 2
points are
{( − 1) n +1, ( − 1) n +1}, n ≥ 0
;

for
n ≥ 1
, after completing
(n + 1) 2 − n = n 2 + n + 1
points, the relative heading for next move is
( − 1) n
;

for all other points, the relative headings are 0.

For each shell

n ≥ 1

, sequence of relative headings before each move along path of shell enumeration of all complex numbers with nonnegative integer real part and imaginary part. (We consider the absolute heading to be initially to the left (

i 2

) when at (0, 0).)

{{ − 1, − 1, − 1}, {1, 1, 0, 1, 0}, { − 1, − 1, 0, 0, − 1, 0, 0}, {1, 1, 0, 0, 0, 1, 0, 0, 0}, { − 1, − 1, 0, 0, 0, 0, − 1, 0, 0, 0, 0}, {1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0}, { − 1, − 1, 0, 0, 0, 0, 0, 0, − 1, 0, 0, 0, 0, 0, 0}, ...}

A?????? Zero indexed sequence of relative headings before each move along path of shell enumeration of all complex numbers with nonnegative integer real part and imaginary part. (We consider the absolute heading to be initially to the left (

i 2

) when at (0, 0).)

{−1, −1, −1, 1, 1, 0, 1, 0, −1, −1, 0, 0, −1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, −1, −1, 0, 0, 0, 0, −1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, −1, −1, 0, 0, 0, 0, 0, 0, −1, 0, 0, 0, 0, 0, 0, ...}