A375469 - OEIS

%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