A257676 Permutation of nonnegative integers obtained by traversing the tendrils (finite side-trees) of the binary beanstalk in depth-first order, with also each number in the infinite trunk visited, but only after its sister branch has been traversed first.
0, 1, 2, 3, 5, 4, 6, 7, 9, 8, 10, 12, 13, 11, 14, 15, 17, 16, 18, 20, 21, 19, 22, 24, 25, 28, 29, 23, 27, 26, 30, 31, 33, 32, 34, 36, 37, 35, 38, 40, 41, 44, 45, 39, 43, 42, 47, 50, 54, 58, 59, 55, 51, 46, 48, 49, 52, 53, 56, 60, 61, 57, 62, 63, 65, 64, 66, 68, 69, 67, 70, 72, 73, 76, 77, 71, 75, 74, 79, 82, 86, 90, 91, 87, 83, 78, 80, 81
Offset: 0
Keywords
Examples
Please look at Paul Tek's illustration: We start at root, 0, go up to 1, visit its left child 2 (which is a leaf), before proceeding the infinite trunk (A179016) to 3, then visit first the leaf 5 at the right hand side, before proceeding the infinite trunk to 4, then visit the leaf 6 at the left hand side, before proceeding the infinite trunk right to 7, from which we first visit the leaf 9 at the right hand side, before proceeding the infinite trunk to 8 at the left hand side. Thus we have ten initial terms of the sequence: 0, 1, 2, 3, 5, 4, 6, 7, 9, 8, ...
From 8 we proceed first to the left 10, because it is not a part of the infinite trunk, and we traverse a finite side-tree ("tendril") of three nodes in order 10, 12, 13, only after which we proceed the infinite trunk to the right, to 11, thus we have the next four terms of the sequence 10, 12, 13, 11.
Links
- Antti Karttunen, Table of n, a(n) for n = 0..16384
- Antti Karttunen, Same Scheme-function as in Program section, but indented and commented properly
- Paul Tek, Illustration of how natural numbers in range 0 .. 133 are organized as a binary tree in the binary beanstalk
- Index entries for sequences that are permutations of the natural numbers
Crossrefs
Formula
a(0) = 0; a(1) = 1;
otherwise set prev = a(n-1);
else a(n) = A213724(prev);
otherwise,
a(n) = {the first unvisited node of binary beanstalk tree found when we backtrack out of a finite branch just traversed in depth-first order}.
Other identities and observations:
If a(n-1) is an even term of A055938 then a(n) = a(n-1)+1.