|
| |
|
|
A114567
|
|
Numbers k such that the binary expansion of n mod 2^k is the postorder traversal of a binary tree, where 1 indicates a node and 0 indicates there are no children on that side.
|
|
1
|
|
|
|
1, 3, 1, 5, 1, 5, 1, 7, 1, 3, 1, 7, 1, 7, 1, 9, 1, 3, 1, 7, 1, 7, 1, 9, 1, 3, 1, 9, 1, 9, 1, 11, 1, 3, 1, 5, 1, 5, 1, 9, 1, 3, 1, 9, 1, 9, 1, 11, 1, 3, 1, 9, 1, 9, 1, 11, 1, 3, 1, 11, 1, 11, 1, 13, 1, 3, 1, 5, 1, 5, 1, 9, 1, 3, 1, 9, 1, 9, 1, 11, 1, 3, 1, 9, 1, 9, 1, 11, 1, 3, 1, 11, 1, 11, 1, 13, 1, 3, 1, 5, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,2
|
|
|
COMMENTS
|
Postorder traversals of a binary tree form an instantaneous code; any integer has a unique decomposition into codewords. To get the first codeword, find a(n). Then set n' = floor(n/2^(a(n))), find a(n'), and so on.
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) = 1, if n is even, and a(n) = 1 + a(floor(n/2)) + a(floor(n/2^{a(floor(n/2)) + 1})), if n is odd.
|
|
|
EXAMPLE
|
a(37) = 1 + a(floor(37/2)) + a(floor(37/2^{a(floor(37/2)) + 1}))
= 1 + a(18) + a(floor(37/2^{a(18) + 1}))
= 1 + 1 + a(floor(37/2^{1 + 1}))
= 2 + a(9)
= 2 + 1 + a(floor(9/2)) + a(floor(9/2^{a(floor(9/2)) + 1}))
= 3 + a(4) + a(floor[9/2^{a(4) + 1}))
= 3 + 1 + a(floor(9/4))
= 4 + a(2)
= 5.
37 mod 2^5 = 5 = 00101, which is the postorder traversal of the binary tree with a root node and a single left child.
|
|
|
MAPLE
|
a := proc(n) option remember; if 0 = n mod 2 then 1; else 1 + a(floor(n/2)) + a(floor(n/2^(a(floor(n/2)) + 1))); end if; end proc; # Petros Hadjicostas, Nov 20 2019
|
|
|
MATHEMATICA
|
a[n_] := a[n] = If[EvenQ[n], 1, 1 + a[Floor[n/2]] + a[ Floor[ n/2^( a[Floor[n/2]] + 1)]]]; a /@ Range[0, 100] (* Giovanni Resta, Nov 21 2019 *)
|
|
|
PROG
|
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
