cp's OEIS Frontend

A375469 Triangle read by rows: a permutation of the nonnegative integers based on the Eytzinger order.

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