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,2

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.

Links

Table of n, a(n) for n=0..65.

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

Example

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]

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);

Prog

(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)])

Crossrefs

Cf. A375825.

Sequence in context: A259019 A375779 A262663 * A075348 A326062 A055631

Adjacent sequences: A375466 A375467 A375468 * A375470 A375471 A375472

Keyword

nonn,tabl

Author

Peter Luschny, Sep 01 2024

Status

approved