A319571 -id:A319571 - cp's OEIS frontend

A354266 Pairs of integers (s, t) such that 0 < s < t and gcd(s, t) > 1, where the pairs are generated by the boustrophedonic Cantor enumeration A319571.

2, 4, 2, 6, 3, 6, 2, 8, 4, 6, 2, 10, 3, 9, 4, 8, 2, 12, 4, 10, 6, 8, 3, 12, 5, 10, 6, 9, 2, 14, 4, 12, 6, 10, 2, 16, 3, 15, 4, 14, 6, 12, 8, 10, 2, 18, 4, 16, 5, 15, 6, 14, 8, 12, 3, 18, 6, 15, 7, 14, 9, 12, 2, 20, 4, 18, 6, 16, 8, 14, 10, 12, 2, 22, 3, 21

Offset: 1

Peter Luschny, May 21 2022

nonn

			The sequence of pairs starts:
(2, 4), (2, 6), (3, 6), (2, 8), (4, 6), (2, 10), (3, 9), (4, 8), (2, 12), (4, 10),(6, 8), (3, 12), (5, 10), (6, 9), (2, 14), (4, 12), (6, 10), (2, 16), (3, 15),(4, 14), (6, 12), (8, 10), ...

Cf. A319571.

function A354266List(upto)
    L = Int[]
    for n in 1:upto
        d = div(isqrt(8n + 1) - 1, 2)
        s = n - div(d*(d + 1), 2)
        t = d - s
        if s > 0 && s < t && gcd(s, t) > 1
            push!(L, s)
            push!(L, t)
        end
    end
L end
println(A354266List(303))

A092542 Table whose n-th row is constant and equal to n, read by antidiagonals alternately upwards and downwards.

Original entry on oeis.org

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

Offset: 1

Sam Alexander, Feb 27 2004

Let A be sequence A092542 (this sequence) and B be sequence A092543 (1, 2, 1, 1, 2, 3, 4, ...). Under upper trimming or lower trimming, A transforms into B and B transforms into A. Also, B gives the number of times each element of A appears. For example, A(7) = 1 and B(7) = 4 because the 1 in A(7) is the fourth 1 to appear in A. - Kerry Mitchell, Dec 28 2005
First inverse function (numbers of rows) for pairing function A056023 and second inverse function (numbers of columns) for pairing function A056011. - Boris Putievskiy, Dec 24 2012
The rational numbers a(n)/A092543(n) can be systematically ordered and numbered in this way, as Georg Cantor first proved in 1873. - Martin Renner, Jun 05 2016

			The table
  1 1 1 1 1 ...
  2 2 2 2 2 ...
  3 3 3 3 3 ...
  4 4 4 4 4 ...
gives
  1;
  1 2;
  3 2 1;
  1 2 3 4;
  5 4 3 2 1;
  1 2 3 4 5 6;

Amir D. Aczel, "The Mystery of the Aleph, Mathematics, the Kabbalah and the Search for Infinity", Barnes & Noble, NY 2000, page 112.

Boris Putievskiy, Transformations Integer Sequences And Pairing Functions, arXiv:1212.2732 [math.CO], 2012.
Eric Weisstein's MathWorld, Pairing functions

Cf. A092543, A056011, A056023.

Variants of Cantor's enumeration are: A352911, A366191, A319571, A354266.

Table[ Join[Range[2n - 1], Reverse@ Range[2n - 2]], {n, 8}] // Flatten (* Robert G. Wilson v, Sep 28 2006 *)

a(n) = ((-1)^t+1)*j/2-((-1)^t-1)*i/2, where i=n-t*(t+1)/2, j=(t*t+3*t+4)/2-n, t=floor((-1+sqrt(8*n-7))/2). - Boris Putievskiy, Dec 24 2012

Name edited by Michel Marcus, Dec 14 2023

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.

Original entry on oeis.org

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)

A332662 Put-and-count: An enumeration of N X N where N = {0, 1, 2, ...}. The terms are interleaved x and y coordinates. Or: A row-wise storage scheme for sequences of regular triangles.

Original entry on oeis.org

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

Offset: 0

Peter Luschny, Feb 18 2020

nonn

Other enumerations of N X N designed with storage allocation for extensible arrays in mind include A319514 and A319571.

			Illustrating the linear storage layout of a sequence of regular triangles.
(A) [ 0], [ 2,  3], [ 7,  8,  9], [16, 17, 18, 19], [30, 31, 32, 33, 34], ...
(B) [ 1], [ 5,  6], [13, 14, 15], [26, 27, 28, 29], ...
(C) [ 4], [11, 12], [23, 24, 25], ...
(D) [10], [21, 22], ...
(E) [20], ...
...
The first column is A000292.
The start values of all partial rows (in ascending order) are 0 plus A014370.
The start values of the partial rows in the first row are A005581 (without first 0).
The start values of the partial rows on the main diagonal are A331987.
The end values of all partial rows (in ascending order) are A332023.
The end values of the partial rows in the first row are A062748.
The end values of the partial rows on the main diagonal are A332698.

Peter Luschny, Table of n, a(n) for n = 0..10000

A332663 (x-coordinates), A056559 (y-coordinates).
Cf. A000292, A014370, A002260, A005581, A319514, A319571, A331987.
Cf. A332023, A062748, A332698.

function a_list(N)
    a = Int[]
    for n in 1:N
        i = 0
        for j in ((k:-1:1) for k in 1:n)
            t = n - j[1]
            for m in j
                push!(a, i, t)
                i += 1
end end end; a end
a_list(5) |> println

count := (k, A) -> ListTools:-Occurrences(k, A): t := n -> n*(n+1)/2:
PutAndCount := proc(N) local L, n, v, c, seq; L := NULL; seq := NULL;
for n from 1 to N do
   for v from 0 to t(n)-1 do
     # How often did you see v in this sequence before?
     c := count(v, [seq]);
     L := L, v, c; seq := seq, v;
od od; L end:  PutAndCount(6);
# Returning 'seq' instead of 'L' gives the x-coordinates (A332663).

t[n_] := n*(n+1)/2;
PutAndCount[N_] := Module[{L, n, v, c, seq},
L = {}; seq = {};
For[n = 1, n <= N, n++,
   For[v = 0, v <= t[n]-1, v++,
      c = Count[seq, v];
      L = Join[L, {v, c}]; seq = Append[seq, v]
]]; L];
PutAndCount[6] (* Jean-François Alcover, Oct 13 2024, after Maple program *)

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)

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

A354266 Pairs of integers (s, t) such that 0 < s < t and gcd(s, t) > 1, where the pairs are generated by the boustrophedonic Cantor enumeration A319571.

Views

Author

Keywords

Examples

Crossrefs

Programs

Julia

A092542 Table whose n-th row is constant and equal to n, read by antidiagonals alternately upwards and downwards.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

A332662 Put-and-count: An enumeration of N X N where N = {0, 1, 2, ...}. The terms are interleaved x and y coordinates. Or: A row-wise storage scheme for sequences of regular triangles.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Julia

Maple

Mathematica

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

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.