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!)
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. 8
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,9

COMMENTS

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).

REFERENCES

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

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 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.

EXAMPLE

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);

PROG

(Julia)

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)

CROSSREFS

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.

Sequence in context: A029223 A305576 A129679 * A141454 A301564 A334361

Adjacent sequences:  A319511 A319512 A319513 * A319515 A319516 A319517

KEYWORD

nonn

AUTHOR

Peter Luschny, Sep 22 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 25 14:07 EST 2021. Contains 341609 sequences. (Running on oeis4.)