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

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, 25, 27, 32, 30, 34, 29, 31, 33, 35, 28, 41, 39, 43, 37, 40, 42, 44, 36, 38, 51, 48, 53, 46, 50, 52, 54, 45, 47, 49, 62, 58, 64, 56, 60, 63, 65, 55, 57, 59, 61

Offset: 0

Author

Peter Luschny, Sep 01 2024

Keywords

• nonn
• tabl

Comments

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.

Examples

			Triangle starts:
  I(n)   ->                   E(n)
  --------------------------------------------------
  0      -> [ 0]
  1..2   -> [ 2,  1]
  3..5   -> [ 4,  3,  5]
  6..9   -> [ 8,  7,  9, 6]
  10..14 -> [13, 11, 14, 10, 12]
  15..20 -> [18, 16, 20, 15, 17, 19]
  21..27 -> [24, 22, 26, 21, 23, 25, 27]
  28..35 -> [32, 30, 34, 29, 31, 33, 35, 28]
  36..44 -> [41, 39, 43, 37, 40, 42, 44, 36, 38]
  45..53 -> [51, 48, 53, 46, 50, 52, 54, 45, 47, 49]
		

Links

• Maxim Zaks, Binary Search vs. Eytzinger Order, blog post, 2020.

Crossrefs

Cf. A375825.

Programs

Maple

Erow := proc(n) local E, row, i, j;
    row := [seq(0, 0..n)]:
    E := proc(n, k, i) option remember; j := i:
    if k <= n + 1 then
        j := E(n, 2 * k, j): row[k] := j:
        j := E(n, 2 * k + 1, j + 1):
    fi: j end:
    E(n, 1, 0):
row end:
Trow := n -> local k; seq((n*(n + 1)/2) + Erow(n)[k + 1], k = 0..n):
seq(Trow(n), n = 0..10);

Python

def A375469row(n: int) -> list[int]:
    t = n * (n + 1) // 2
    return [A375825row(n + 1)[k + 1] + t - 1 for k in range(n + 1)]
print([A375469row(n)[k] for n in range(11) for k in range(n + 1)])