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.

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

Offset: 0

Author

Peter Luschny, Sep 23 2018

Keywords

• nonn

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.

Examples

			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)
		

Links

• Peter Luschny, Table of n, a(n) for n = 0..10000
• Georg Cantor, Ein Beitrag zur Mannigfaltigkeitslehre, Journal für die reine und angewandte Mathematik 84 (1878), 242-258.
• Steven Pigeon, Mœud, 2018.
• A. L. Rosenberg, Allocating storage for extendible Arrays, J. ACM, vol 21(4), 1974, p. 652-670.
• Index entries for sequences related to coordinates of 2D curves

Crossrefs

Cf. A319572 (stripe x), A319573 (stripe y).

Cf. A319514 (shell enumeration), A319289 (shell x), A319290 (shell y).

Programs

Julia

function A319571(n)
    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)
A319571_list = list(islice(A319571_gen(),100)) # Chai Wah Wu, May 21 2022