A319572 -id:A319572 - 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

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)

A343854 Irregular triangle read by rows: the n-th row gives the column indices of the matrix of 1..n^2 filled successively back and forth along antidiagonals.

Original entry on oeis.org

1, 1, 2, 1, 2, 1, 2, 1, 1, 2, 3, 3, 2, 3, 1, 2, 1, 1, 2, 3, 4, 3, 2, 1, 2, 3, 4, 4, 3, 4, 1, 2, 1, 1, 2, 3, 4, 3, 2, 1, 1, 2, 3, 4, 5, 5, 4, 3, 2, 3, 4, 5, 5, 4, 5, 1, 2, 1, 1, 2, 3, 4, 3, 2, 1, 1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1, 2, 3, 4, 5, 6, 6, 5, 4, 3, 4, 5, 6, 6, 5, 6

Offset: 1

Stefano Spezia, May 01 2021

			The triangle begins:
1
1   2   1   2
1   2   1   1   2   3   3   2   3
1   2   1   1   2   3   4   3   2   1   2   3   4   4   3   4
...

Stefano Spezia, First 30 rows of the triangle, flattened

Cf. A000290 (row length), A002411 (row sums), A060747 (number of antidiagonals), A078475, A319572, A343853 (row indices).

a={};For[n=1,n<=6,n++,For[d=1,d<=n,d++, If[EvenQ[d],i=d;For [k=1,k<=d,k++, AppendTo[a,i-k+1]],i=1;For[k=1,k<=d,k++, AppendTo[a,i+k-1]]]];For[d=n+1,d<=2n-1,d++, If[EvenQ[d],i= n; For[k=1,k<=2n-d,k++,AppendTo[a,i-k+1]],If[OddQ[d],i=d-n+1;For[k=1,k<=2n-d,k++, AppendTo[a,i+k-1]]]]]]; a

A135317 Let h(2n, 1) = 2n and h(2n, m) = h(2n, m-1) + 2 * d(2n, m) for m > 1, where d(2n, m) = (least multiple of m not less than h(2n, m-1)) - h(2n, m-1). Then d(2n, m) is eventually 2-periodic as a function of m, and a(n) is defined as d(2n, 2*m+1) for large m.

Original entry on oeis.org

0, 1, 2, 0, 1, 2, 3, 4, 0, 3, 4, 5, 1, 2, 3, 6, 0, 1, 4, 5, 6, 2, 5, 6, 7, 8, 0, 7, 8, 9, 3, 4, 5, 1, 2, 3, 6, 7, 10, 4, 7, 8, 0, 1, 2, 9, 10, 11, 5, 8, 9, 12, 6, 7, 10, 11, 12, 8, 9, 10, 0, 3, 4, 13, 1, 2, 5, 6, 11, 3, 4, 9, 14, 0, 1, 10, 11, 12, 2, 7, 8, 13, 5, 6, 9, 12, 13, 7, 10, 11, 14, 15, 16, 14

Offset: 0

Alex Abercrombie, Feb 15 2008

nonn

Sequence yielding an ordering of N*N derived from a family of recurrences.
For any integer k define h(k,1)=k and for m>1 define h(k,m)=h(k,m-1)+2*((-h(k,m-1)) mod m) where "r mod s" denotes least nonnegative residue of r modulo s [informally, h(k,m) is got by "reflecting" h(k,m-1) in the least multiple of m that is >=h(k,m-1)]. Then for fixed k>=0 there are integers c(k), b(k), m(k) such that for all m>m(k) we have h(k,2*m+1)-h(k,2*m)=2*c(k) and h(k,2*m+2)-h(k,2*m+1)=2*b(k). [In the terms of the function d defined in the Name, c(k) = d(k, 2*m+1) and b(k) = d(k, 2*m+2) for all m>m(k).]
For all n we have c(2*n+1)=c(2*n) and b(2*n+1)=1+b(2*n). Moreover b(2*n) is even for all n. The function n->(c(2*n),b(2*n)/2) is a bijection from the nonnegative integers N to N*N [as well as n->(b(n),c(n))]. It is "monotone" in the sense that n<=n' whenever c(2*n)<=c(2*n') and b(2*n)<=b(2*n').
This sequence is a(n) = c(2*n).
The results on which the definition is based are not yet proved, but they are plausible and overwhelmingly supported by numerical evidence.
For each fixed m, k->h(k,m) is a bijection Z->Z (this is easy!). However for k<0 the sequence h(k,m) does not have the pseudo-periodic property we have used in defining c(k) and b(k).
m(k) appears to be O(sqrt k).
From Andrey Zabolotskiy, Dec 28 2024: (Start)
See my Github link for the proof that the sequence is indeed well-defined.
That fact is equivalent to the quantity d(k,m) + d(k,m+1) eventually becoming constant. That constant value can be first reached when m is odd (case B) or even (case C).
On the plane (b(k), c(k)), the points from case B (resp. case C) fall in the region which is approximately the octant b(k) > c(k) (resp. c(k) > b(k)).
On the plane (x=n, y=a(n)), the graph of this sequence fills in a certain region in the plane. It's bounded from below by the line y=0 and from above, it seems, by the curve y = sqrt(Pi*x). That region, it seems, is further divided into two parts: the one below the curve y = sqrt((4/Pi)*x) contains points from case B, the one above it contains points from case C. The latter part looks more dense on the graph. (End)

			h(18,m) for m>=1 goes 18,18,18,22,28,32,38,42,48...so we can take m(18) = 2, then 2*c(18)=28-22=38-32=48-42=...=6, so a(9) = c(18) = 3 and similarly b(18) = 2.

Andrey Zabolotskiy, Table of n, a(n) for n = 0..20000
Jon Maiga, Computer-generated formulas for A135317, Sequence Machine.
Andrey Zabolotskiy, Abercrombie's sequence, Github (formalized Lean proof that this sequence is well-defined).

Cf. A319571, A319572, A319573, A252448.

a[n_] := Module[{h = 2 n, b, c = 0, m = 1},
   While[Ceiling[h/(m+1)] != Floor[h/m],
    m++; b = Mod[-h, m]; h += 2 b;
    m++; c = Mod[-h, m]; h += 2 c];
   c];
Table[a[n], {n, 0, 93}] (* Andrey Zabolotskiy, Apr 29 2023, Dec 25 2024 *)

def a(n):
    h, m, c = 2*n, 1, 0
    while (h+m)//(m+1) != h//m:
        m += 1; b = (-h) % m; h += 2*b
        m += 1; c = (-h) % m; h += 2*c
    return c
print([a(n) for n in range(30)]) # Andrey Zabolotskiy, Dec 25 2024

It appears that a(n) = A319573(A252448(2*n+1)) [discovered by Sequence Machine], moreover, c(n) = A319573(n') and b(n) = A319572(n') with n' = A252448(n), where b and c are described above. - Andrey Zabolotskiy, Apr 28 2023

Edited by Andrey Zabolotskiy, Apr 29 2023

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

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

A343854 Irregular triangle read by rows: the n-th row gives the column indices of the matrix of 1..n^2 filled successively back and forth along antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A135317 Let h(2*n, 1) = 2*n and h(2*n, m) = h(2*n, m-1) + 2 * d(2*n, m) for m > 1, where d(2*n, m) = (least multiple of m not less than h(2*n, m-1)) - h(2*n, m-1). Then d(2*n, m) is eventually 2-periodic as a function of m, and a(n) is defined as d(2*n, 2*m+1) for large m.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A135317 Let h(2n, 1) = 2n and h(2n, m) = h(2n, m-1) + 2 * d(2n, m) for m > 1, where d(2n, m) = (least multiple of m not less than h(2n, m-1)) - h(2n, m-1). Then d(2n, m) is eventually 2-periodic as a function of m, and a(n) is defined as d(2n, 2*m+1) for large m.