A157807 -id:A157807 - cp's OEIS frontend

A161638 The largest number of steps in Euclid's algorithm applied to A157807(n) and A157813(n).

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

Offset: 1

Yalcin Aktar, Jun 15 2009

The sequence of fractions is ordered as follows: 1/1, 2/1, 1/2, 1/3, 3/1, 4/1, 3/2, 2/3, 1/4, 1/5, 5/1,...

			a(8) = 3 because the algorithm applied to the pair (2,3) needs the steps 2 = 3 x 0 + 2 then 3 = 2 x 1 + 1 and 2 = 1 x 2 + 0.

Anonymous, Euclidean algorithm, Springer's Encyclopedia of Maths.
Eric W. Weisstein, Euclidean algorithm, MathWorld.
Wikipedia, Euclid's algorithm

from math import gcd
def euclid_steps(a, b):
  if b == 0:
    return 0
  else:
    return 1 + euclid_steps(b, a % b)
for s in range(2, 100, 2):
  for i in range(1, s):
    if gcd(i, s - i) != 1: continue
    print(euclid_steps(i, s - i))
  for i in range(s, 0, -1):
    if gcd(i, s + 1 - i) != 1: continue
    print(euclid_steps(i, s + 1 - i))
# Hiroaki Yamanouchi, Oct 06 2014

Partially edited by R. J. Mathar, Sep 23 2009

a(1) prepended and a(12)-a(87) added by Hiroaki Yamanouchi, Oct 06 2014

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)

A157813 Denominators of fractions arranged in "antidiagonal boustrophedon" ordering with equivalent fractions removed: (1/1, 2/1, 1/2, 1/3, 3/1, 4/1, 3/2, 2/3, 1/4, 1/5, 5/1, 6/1, 5/2, ...).

Original entry on oeis.org

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

Offset: 1

Ron R. King, Mar 07 2009

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A157807 (numerators), A038567.

With Cantor's ordering: A020652, A020653, A352911.

R:= NULL: count:= 0:
for m from 2 while count < 100 do
  S:= select(t -> igcd(t,m-t)=1, [$1..m-1]);
  count:= count+nops(S);
  if m::odd then R:= R, op(S) else R:= R, seq(m-t,t=S) fi;
od:
R; # Robert Israel, Oct 09 2023

from math import gcd
for s in range(2, 100, 2):
  for i in range(1, s):
    if gcd(i, s - i) != 1: continue
    print(s - i)
  for i in range(s, 0, -1):
    if gcd(i, s + 1 - i) != 1: continue
    print(s + 1 - i)
# Hiroaki Yamanouchi, Oct 06 2014

a(58)-a(83) from Hiroaki Yamanouchi, Oct 06 2014

Name corrected by Andrey Zabolotskiy, Oct 10 2023

A319513 The boustrophedonic Rosenberg-Strong function maps N onto N X N where N = {0, 1, 2, ...} and n -> factor(a(n)) = 2^x*3^y -> (x, y).

Original entry on oeis.org

1, 3, 6, 2, 4, 12, 36, 18, 9, 27, 54, 108, 216, 72, 24, 8, 16, 48, 144, 432, 1296, 648, 324, 162, 81, 243, 486, 972, 1944, 3888, 7776, 2592, 864, 288, 96, 32, 64, 192, 576, 1728, 5184, 15552, 46656, 23328, 11664, 5832, 2916, 1458, 729, 2187, 4374, 8748, 17496

Offset: 0

Peter Luschny, Sep 21 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.

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

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.

See A319514 for a non-decoded variant with interleaved x and y coordinates.

Cf. A038566/A038567, A157807/A157813.

function bRS(n)
    m = x = isqrt(n)
    y = n - x^2
    x <= y && ((x, y) = (2x - y, x))
    isodd(m) ? (y, x) : (x, y)
end
A319513(n) = ((x, y) = bRS(n); 2^x * 3^y)
[A319513(n) for n in 0:52] |> println

A319513 := proc(n) local b, r, p, m;
    b := floor(sqrt(n)); r := n - b^2;
    p := `if`(r < b, [b, r], [2*b-r, b]);
    m := `if`(p[1] > p[2], p[1], p[2]);
    `if`(irem(m,2) = 0, 2^p[1]*3^p[2], 2^p[2]*3^p[1]) end:
seq(A319513(n), n=0..52);

a[n_] := Module[{b, r, p1, p2, m}, b = Floor[Sqrt[n]]; r = n-b^2; {p1, p2} = If[rp2, p1, p2]; If[EvenQ[m], 2^p1 3^p2, 2^p2 3^p1]]; Table[a[n], {n, 0, 52}] (* Jean-François Alcover, Feb 14 2019, from Maple *)

cp's OEIS Frontend

A161638 The largest number of steps in Euclid's algorithm applied to A157807(n) and A157813(n).

Views

Author

Keywords

Comments

Examples

Links

Programs

Python

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

A157813 Denominators of fractions arranged in "antidiagonal boustrophedon" ordering with equivalent fractions removed: (1/1, 2/1, 1/2, 1/3, 3/1, 4/1, 3/2, 2/3, 1/4, 1/5, 5/1, 6/1, 5/2, ...).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Python

Extensions

A319513 The boustrophedonic Rosenberg-Strong function maps N onto N X N where N = {0, 1, 2, ...} and n -> factor(a(n)) = 2^x*3^y -> (x, y).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Julia

Maple

Mathematica