A319290 -id:A319290 - cp's OEIS frontend

A319514 The shell enumeration of N X N where N = {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

Offset: 0

Peter Luschny, Sep 22 2018

nonn

If (x, y) and (x', y') are adjacent points on the trajectory of the map then for the boustrophedonic Rosenberg-Strong function max(|x - x'|, |y - y'|) is always 1 whereas for the Rosenberg-Strong function this quantity can become arbitrarily large. In this sense the boustrophedonic variant is continuous in contrast to the original Rosenberg-Strong function.
We implemented the enumeration also as a state machine to avoid the evaluation of the square root function.
The inverse function, computing n for given (x, y), is m*(m + 1) + (-1)^(m mod 2)*(y - x) where m = max(x, y).

			The map starts, for n = 0, 1, 2, ...
(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), ...
The enumeration can be seen as shells growing around the origin:
(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);

A. L. Rosenberg, H. R. Strong, Addressing arrays by shells, IBM Technical Disclosure Bulletin, vol 14(10), 1972, p. 3026-3028.

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 deux, 2018.
A. L. Rosenberg, Allocating storage for extendible Arrays, J. ACM, vol 21(4), 1974, p. 652-670.
M. P. Szudzik, The Rosenberg-Strong Pairing Function, arXiv:1706.04129 [cs.DM], 2017.

Cf. A319289 (x coordinates), A319290 (y coordinates).
Cf. A319571 (stripe enumeration), A319572 (stripe x), A319573 (stripe y).
A319513 uses the encoding 2^x*3*y.
Cf. A038566/A038567, A157807/A157813.

function A319514(n)
    k, r = divrem(n, 2)
    m = x = isqrt(k)
    y = k - x^2
    x <= y && ((x, y) = (2x - y, x))
    isodd(m) ? (y, x)[r+1] : (x, y)[r+1]
end
[A319514(n) for n in 0:52] |> println
# The enumeration of N X N with a state machine:
# PigeonRosenbergStrong(n)
function PRS(x, y, state)
    x == 0 && state == 0 && return x, y+1, 1
    y == 0 && state == 2 && return x+1, y, 3
    x == y && state == 1 && return x, y-1, 2
    x == y && return x-1, y, 0
    state == 0 && return x-1, y, 0
    state == 1 && return x+1, y, 1
    state == 2 && return x, y-1, 2
    return x, y+1, 3
end
function ShellEnumeration(len)
    x, y, state = 0, 0, 0
    for n in 0:len
        println("$n -> ($x, $y)")
        x, y, state = PRS(x, y, state)
    end
end
# Computes n for given (x, y).
function Pairing(x::Int, y::Int)
    m = max(x, y)
    d = isodd(m) ? x - y : y - x
    m*(m + 1) + d
end
ShellEnumeration(20)

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.

Original entry on oeis.org

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

Peter Luschny, Sep 23 2018

nonn

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.

			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)

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

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

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

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)

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

A319572 The x coordinates of the stripe enumeration of N X N where N = {0, 1, 2, ...}.

Original entry on oeis.org

0, 0, 1, 2, 1, 0, 0, 1, 2, 3, 4, 3, 2, 1, 0, 0, 1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 7, 6, 5, 4, 3, 2, 1, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 11, 10, 9, 8, 7, 6

Offset: 0

Peter Luschny, Sep 23 2018

nonn

See A319571 for comments and references.

Index entries for sequences related to coordinates of 2D curves

Cf. A319571 (stripe enumeration), this sequence (stripe x), A319573 (stripe y).

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

# Function stripe is defined in A319571.
function StripeEnumerationX(len)
    x, y, state = 0, 0, false
    for n in 0:len
        print("$x, ")
        x, y, state = stripe(x, y, state)
    end
end
StripeEnumerationX(84)

A319573 The y coordinates of the stripe enumeration of N X N where N = {0, 1, 2, ...}.

Original entry on oeis.org

0, 1, 0, 0, 1, 2, 3, 2, 1, 0, 0, 1, 2, 3, 4, 5, 4, 3, 2, 1, 0, 0, 1, 2, 3, 4, 5, 6, 7, 6, 5, 4, 3, 2, 1, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 0, 1, 2, 3, 4, 5, 6

Offset: 0

Peter Luschny, Sep 23 2018

nonn

See A319571 for comments and references.

Index entries for sequences related to coordinates of 2D curves

Cf. A319571 (stripe enumeration), A319572 (stripe x), this sequence (stripe y).

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

# Function stripe is defined in A319571.
function StripeEnumerationY(len)
    x, y, state = 0, 0, false
    for n in 0:len
        print("$y, ")
        x, y, state = stripe(x, y, state)
    end
end
StripeEnumerationY(84)

cp's OEIS Frontend

A319514 The shell enumeration of N X N where N = {0, 1, 2, ...}, also called boustrophedonic Rosenberg-Strong function. Terms are interleaved x and y coordinates.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Julia

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Julia

Python

A319572 The x coordinates of the stripe enumeration of N X N where N = {0, 1, 2, ...}.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Julia

A319573 The y coordinates of the stripe enumeration of N X N where N = {0, 1, 2, ...}.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Julia