|
|
A319571
|
|
The stripe enumeration of N X N where N = {0, 1, 2, ...}, also called boustrophedonic Cantor enumeration. Terms are interleaved x and y coordinates.
|
|
8
|
|
|
0, 0, 0, 1, 1, 0, 2, 0, 1, 1, 0, 2, 0, 3, 1, 2, 2, 1, 3, 0, 4, 0, 3, 1, 2, 2, 1, 3, 0, 4, 0, 5, 1, 4, 2, 3, 3, 2, 4, 1, 5, 0, 6, 0, 5, 1, 4, 2, 3, 3, 2, 4, 1, 5, 0, 6, 0, 7, 1, 6, 2, 5, 3, 4, 4, 3, 5, 2, 6, 1, 7, 0, 8, 0, 7, 1, 6, 2, 5, 3, 4, 4, 3, 5, 2, 6, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,7
|
|
COMMENTS
|
If (x, y) and (x', y') are adjacent points on the trajectory of the map then max(|x - x'|, |y - y'|) is always 1 whereas for the Cantor enumeration this quantity can become arbitrarily large. In this sense our boustrophedonic variant is continuous whereas Cantor's realization is not.
We implemented the recursive enumeration as a state machine with two states to avoid the evaluation of the square root function.
The inverse function, computing n for given (x, y), is (x + y)*(x + y + 1)/2 + p where p = x if x - y is odd and y otherwise.
|
|
LINKS
|
Steven Pigeon, Mœud, 2018.
|
|
EXAMPLE
|
The map starts, for n = 0, 1, 2, ...
(0, 0), (0, 1), (1, 0), (2, 0), (1, 1), (0, 2), (0, 3), (1, 2), (2, 1), (3, 0),
(4, 0), (3, 1), (2, 2), (1, 3), (0, 4), (0, 5), (1, 4), (2, 3), (3, 2), (4, 1),
(5, 0), (6, 0), (5, 1), (4, 2), (3, 3), (2, 4), (1, 5), (0, 6), (0, 7), (1, 6),
(2, 5), (3, 4), (4, 3), (5, 2), (6, 1), (7, 0), ...
The enumeration can be seen as diagonal stripes layering on the origin:
(0, 0),
(0, 1), (1, 0),
(2, 0), (1, 1), (0, 2),
(0, 3), (1, 2), (2, 1), (3, 0),
(4, 0), (3, 1), (2, 2), (1, 3), (0, 4),
(0, 5), (1, 4), (2, 3), (3, 2), (4, 1), (5, 0),
(6, 0), (5, 1), (4, 2), (3, 3), (2, 4), (1, 5), (0, 6),
(0, 7), (1, 6), (2, 5), (3, 4), (4, 3), (5, 2), (6, 1), (7, 0)
|
|
PROG
|
(Julia)
k, r = divrem(n, 2)
d = div(isqrt(8k+1) - 1, 2)
s = k - div(d*(d + 1), 2)
isodd(d) ? (s, d-s)[r+1] : (d-s, s)[r+1]
end
function stripe(x, y, state)
x == 0 && !state && return x, y+1, !state
y == 0 && state && return x+1, y, !state
state && return x+1, y-1, state
return x-1, y+1, state
end
function StripeEnumeration(len)
x, y, state = 0, 0, false
for n in 0:len
println("$n -> ($x, $y)")
x, y, state = stripe(x, y, state)
end
end
function Pairing(x, y)
p = isodd(x - y) ? x : y
div((x + y)*(x + y + 1), 2) + p
end
StripeEnumeration(40)
(Python)
from itertools import count, islice
def A319571_gen(): # generator of terms
for n in count(0):
for m in range(n+1):
yield from (m, n-m) if n % 2 else (n-m, m)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|