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

 

Logo

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 56th year, we are closing in on 350,000 sequences, and we’ve crossed 9,700 citations (which often say “discovered thanks to the OEIS”).

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.

Index entries for sequences related to coordinates of 2D curves

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 A345927

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 November 30 20:17 EST 2021. Contains 349425 sequences. (Running on oeis4.)