|
Search: id:A114567
|
|
|
| A114567 |
|
a_n = 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. |
|
+0
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; listen)
|
|
|
OFFSET
|
0,2
|
|
|
COMMENT
|
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.
|
|
FORMULA
|
a_n = 1 if n even a_n = 1 + a_{floor[n/2]} + a_{floor[n/2^{a_{floor[n/2]}+1}]} if n 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.
|
|
MATHEMATICA
|
T:=If[Mod[ #, 2]==0, 1, 1+T[Floor[ #/2]]+T[Floor[ #/2^(T[Floor[ #/2]]+1)]]]&
|
|
CROSSREFS
|
Sequence in context: A016475 A037227 A056753 this_sequence A001051 A046730 A002972
Adjacent sequences: A114564 A114565 A114566 this_sequence A114568 A114569 A114570
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
Michael Stay (metaweta(AT)gmail.com), Feb 15 2006
|
|
|
Search completed in 0.002 seconds
|
