cp's OEIS Frontend

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.

%I A319571 #32 May 22 2022 01:52:12
%S A319571 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,
%T A319571 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,
%U A319571 6,1,7,0,8,0,7,1,6,2,5,3,4,4,3,5,2,6,1
%N 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.
%C A319571 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.
%C A319571 We implemented the recursive enumeration as a state machine with two states to avoid the evaluation of the square root function.
%C A319571 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.
%H A319571 Peter Luschny, <a href="/A319571/b319571.txt">Table of n, a(n) for n = 0..10000</a>
%H A319571 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 A319571 Steven Pigeon, <a href="https://hbfs.wordpress.com/2018/07/31/moeud/">Mœud</a>, 2018.
%H A319571 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 A319571 <a href="/index/Con#coordinates_2D_curves">Index entries for sequences related to coordinates of 2D curves</a>
%e A319571 The map starts, for n = 0, 1, 2, ...
%e A319571 (0, 0), (0, 1), (1, 0), (2, 0), (1, 1), (0, 2), (0, 3), (1, 2), (2, 1), (3, 0),
%e A319571 (4, 0), (3, 1), (2, 2), (1, 3), (0, 4), (0, 5), (1, 4), (2, 3), (3, 2), (4, 1),
%e A319571 (5, 0), (6, 0), (5, 1), (4, 2), (3, 3), (2, 4), (1, 5), (0, 6), (0, 7), (1, 6),
%e A319571 (2, 5), (3, 4), (4, 3), (5, 2), (6, 1), (7, 0), ...
%e A319571 The enumeration can be seen as diagonal stripes layering on the origin:
%e A319571 (0, 0),
%e A319571 (0, 1), (1, 0),
%e A319571 (2, 0), (1, 1), (0, 2),
%e A319571 (0, 3), (1, 2), (2, 1), (3, 0),
%e A319571 (4, 0), (3, 1), (2, 2), (1, 3), (0, 4),
%e A319571 (0, 5), (1, 4), (2, 3), (3, 2), (4, 1), (5, 0),
%e A319571 (6, 0), (5, 1), (4, 2), (3, 3), (2, 4), (1, 5), (0, 6),
%e A319571 (0, 7), (1, 6), (2, 5), (3, 4), (4, 3), (5, 2), (6, 1), (7, 0)
%o A319571 (Julia)
%o A319571 function A319571(n)
%o A319571     k, r = divrem(n, 2)
%o A319571     d = div(isqrt(8k+1) - 1, 2)
%o A319571     s = k - div(d*(d + 1), 2)
%o A319571     isodd(d) ? (s, d-s)[r+1] : (d-s, s)[r+1]
%o A319571 end
%o A319571 function stripe(x, y, state)
%o A319571     x == 0 && !state && return x, y+1, !state
%o A319571     y == 0 &&  state && return x+1, y, !state
%o A319571     state && return x+1, y-1, state
%o A319571     return x-1, y+1, state
%o A319571 end
%o A319571 function StripeEnumeration(len)
%o A319571     x, y, state = 0, 0, false
%o A319571     for n in 0:len
%o A319571         println("$n -> ($x, $y)")
%o A319571         x, y, state = stripe(x, y, state)
%o A319571     end
%o A319571 end
%o A319571 function Pairing(x, y)
%o A319571     p = isodd(x - y) ? x : y
%o A319571     div((x + y)*(x + y + 1), 2) + p
%o A319571 end
%o A319571 StripeEnumeration(40)
%o A319571 (Python)
%o A319571 from itertools import count, islice
%o A319571 def A319571_gen(): # generator of terms
%o A319571     for n in count(0):
%o A319571         for m in range(n+1):
%o A319571              yield from (m,n-m) if n % 2 else (n-m,m)
%o A319571 A319571_list = list(islice(A319571_gen(),100)) # _Chai Wah Wu_, May 21 2022
%Y A319571 Cf. A319572 (stripe x), A319573 (stripe y).
%Y A319571 Cf. A319514 (shell enumeration), A319289 (shell x), A319290 (shell y).
%K A319571 nonn
%O A319571 0,7
%A A319571 _Peter Luschny_, Sep 23 2018