|
|
A194045
|
|
Numbers whose binary expansion is a preorder traversal of a binary tree
|
|
0
|
|
|
0, 4, 20, 24, 84, 88, 100, 104, 112, 340, 344, 356, 360, 368, 404, 408, 420, 424, 432, 452, 456, 464, 480, 1364, 1368, 1380, 1384, 1392, 1428, 1432, 1444, 1448, 1456, 1476, 1480, 1488, 1504, 1620, 1624, 1636, 1640, 1648, 1684, 1688, 1700, 1704, 1712, 1732, 1736, 1744, 1760, 1812, 1816, 1828, 1832, 1840, 1860, 1864, 1872, 1888, 1924, 1928, 1936, 1952, 1984
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
When traversing the tree in preorder, emit 1 at each node and 0 if it has no child on the current branch. The smallest binary tree is empty, so we emit 0 at the root; thus a(0) = 0. The next binary tree is a single node (emit 1) with no left (emit 0) or right child (emit 0); thus a(1) = 100 in binary or 4.
|
|
LINKS
|
|
|
FORMULA
|
|
|
PROG
|
(JavaScript)
// n is the number of internal nodes (or 1s in the binary expansion)
// f is a function to display each result
function trees(n, f) {
// h is the "height", thinking of 1 as a step up and 0 as a step down
// s is the current state
function enumerate(n, h, s, f) {
if (n===0 && h===0) { f(2 * s); }
else {
if (h > 0) { enumerate(n, h - 1, 2 * s, f) }
if (n > 0) { enumerate(n - 1, h + 1, 2 * s + 1, f) }
}
}
enumerate(n, 0, 0, f);
}
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|