%I #10 Sep 02 2024 03:49:02
%S 0,2,1,4,3,5,8,7,9,6,13,11,14,10,12,18,16,20,15,17,19,24,22,26,21,23,
%T 25,27,32,30,34,29,31,33,35,28,41,39,43,37,40,42,44,36,38,51,48,53,46,
%U 50,52,54,45,47,49,62,58,64,56,60,63,65,55,57,59,61
%N Triangle read by rows: a permutation of the nonnegative integers based on the Eytzinger order.
%C Let T(n) denote the triangular numbers. Set, for n >= 0, I(n) = [T(n), T(n+1)), lower bound included, upper bound excluded. Applying the Eytzinger ordering to I(n) gives E(n) = [A375825(n + 1, k + 1) + T(n) - 1 for k in 0..n]. Joining E(0), E(1), E(2), ... gives a permutation of the nonnegative integers. The Eytzinger order of 1..n is described in A375825.
%H Maxim Zaks, <a href="https://medium.com/swlh/binary-search-vs-eytzinger-order-301f0a9a797d">Binary Search vs. Eytzinger Order</a>, blog post, 2020.
%e Triangle starts:
%e I(n) -> E(n)
%e --------------------------------------------------
%e 0 -> [ 0]
%e 1..2 -> [ 2, 1]
%e 3..5 -> [ 4, 3, 5]
%e 6..9 -> [ 8, 7, 9, 6]
%e 10..14 -> [13, 11, 14, 10, 12]
%e 15..20 -> [18, 16, 20, 15, 17, 19]
%e 21..27 -> [24, 22, 26, 21, 23, 25, 27]
%e 28..35 -> [32, 30, 34, 29, 31, 33, 35, 28]
%e 36..44 -> [41, 39, 43, 37, 40, 42, 44, 36, 38]
%e 45..53 -> [51, 48, 53, 46, 50, 52, 54, 45, 47, 49]
%p Erow := proc(n) local E, row, i, j;
%p row := [seq(0, 0..n)]:
%p E := proc(n, k, i) option remember; j := i:
%p if k <= n + 1 then
%p j := E(n, 2 * k, j): row[k] := j:
%p j := E(n, 2 * k + 1, j + 1):
%p fi: j end:
%p E(n, 1, 0):
%p row end:
%p Trow := n -> local k; seq((n*(n + 1)/2) + Erow(n)[k + 1], k = 0..n):
%p seq(Trow(n), n = 0..10);
%o (Python)
%o def A375469row(n: int) -> list[int]:
%o t = n * (n + 1) // 2
%o return [A375825row(n + 1)[k + 1] + t - 1 for k in range(n + 1)]
%o print([A375469row(n)[k] for n in range(11) for k in range(n + 1)])
%Y Cf. A375825.
%K nonn,tabl
%O 0,2
%A _Peter Luschny_, Sep 01 2024