login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 5
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

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.

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)

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)

CROSSREFS

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

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

Sequence in context: A147310 A025886 A117355 * A086966 A140080 A065359

Adjacent sequences:  A319568 A319569 A319570 * A319572 A319573 A319574

KEYWORD

nonn

AUTHOR

Peter Luschny, Sep 23 2018

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 28 08:21 EST 2020. Contains 332321 sequences. (Running on oeis4.)