A319514 - OEIS

%I #29 Sep 24 2018 09:25:03

%S 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,

%T 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,

%U 5,1,5,0,6,0,6,1,6,2,6,3,6,4,6,5,6,6,5

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

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

%C We implemented the enumeration also as a state machine to avoid the evaluation of the square root function.

%C The inverse function, computing n for given (x, y), is m*(m + 1) + (-1)^(m mod 2)*(y - x) where m = max(x, y).

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

%H Peter Luschny, <a href="/A319514/b319514.txt">Table of n, a(n) for n = 0..10000</a>

%H Georg Cantor, <a href="http://gdz.sub.uni-goettingen.de/dms/resolveppn/?PPN=GDZPPN002156806">Ein Beitrag zur Mannigfaltigkeitslehre</a>, Journal für die reine und angewandte Mathematik 84 (1878), 242-258.

%H Steven Pigeon, <a href="https://hbfs.wordpress.com/2018/08/07/moeud-deux/">Mœud deux</a>, 2018.

%H A. L. Rosenberg, <a href="https://doi.org/10.1145/321850.321861">Allocating storage for extendible Arrays</a>, J. ACM, vol 21(4), 1974, p. 652-670.

%H M. P. Szudzik, <a href="http://arxiv.org/abs/1706.04129">The Rosenberg-Strong Pairing Function</a>, arXiv:1706.04129 [cs.DM], 2017.

%e The map starts, for n = 0, 1, 2, ...

%e (0, 0), (0, 1), (1, 1), (1, 0), (2, 0), (2, 1), (2, 2), (1, 2), (0, 2), (0, 3),

%e (1, 3), (2, 3), (3, 3), (3, 2), (3, 1), (3, 0), (4, 0), (4, 1), (4, 2), (4, 3),

%e (4, 4), (3, 4), (2, 4), (1, 4), (0, 4), (0, 5), (1, 5), (2, 5), (3, 5), (4, 5),

%e (5, 5), (5, 4), (5, 3), (5, 2), (5, 1), (5, 0), (6, 0), (6, 1), (6, 2), (6, 3),

%e (6, 4), (6, 5), (6, 6), (5, 6), (4, 6), (3, 6), (2, 6), (1, 6), (0, 6), ...

%e The enumeration can be seen as shells growing around the origin:

%e (0, 0);

%e (0, 1), (1, 1), (1, 0);

%e (2, 0), (2, 1), (2, 2), (1, 2), (0, 2);

%e (0, 3), (1, 3), (2, 3), (3, 3), (3, 2), (3, 1), (3, 0);

%e (4, 0), (4, 1), (4, 2), (4, 3), (4, 4), (3, 4), (2, 4), (1, 4), (0, 4);

%e (0, 5), (1, 5), (2, 5), (3, 5), (4, 5), (5, 5), (5, 4), (5, 3), (5, 2),(5,1),(5,0);

%o (Julia)

%o function A319514(n)

%o     k, r = divrem(n, 2)

%o     m = x = isqrt(k)

%o     y = k - x^2

%o     x <= y && ((x, y) = (2x - y, x))

%o     isodd(m) ? (y, x)[r+1] : (x, y)[r+1]

%o end

%o [A319514(n) for n in 0:52] |> println

%o # The enumeration of N X N with a state machine:

%o # PigeonRosenbergStrong(n)

%o function PRS(x, y, state)

%o     x == 0 && state == 0 && return x, y+1, 1

%o     y == 0 && state == 2 && return x+1, y, 3

%o     x == y && state == 1 && return x, y-1, 2

%o     x == y && return x-1, y, 0

%o     state == 0 && return x-1, y, 0

%o     state == 1 && return x+1, y, 1

%o     state == 2 && return x, y-1, 2

%o     return x, y+1, 3

%o end

%o function ShellEnumeration(len)

%o     x, y, state = 0, 0, 0

%o     for n in 0:len

%o         println("$n -> ($x, $y)")

%o         x, y, state = PRS(x, y, state)

%o     end

%o end

%o # Computes n for given (x, y).

%o function Pairing(x::Int, y::Int)

%o     m = max(x, y)

%o     d = isodd(m) ? x - y : y - x

%o     m*(m + 1) + d

%o end

%o ShellEnumeration(20)

%Y Cf. A319289 (x coordinates), A319290 (y coordinates).

%Y Cf. A319571 (stripe enumeration), A319572 (stripe x), A319573 (stripe y).

%Y A319513 uses the encoding 2^x*3*y.

%Y Cf. A038566/A038567, A157807/A157813.

%K nonn

%O 0,9

%A _Peter Luschny_, Sep 22 2018