|
| |
|
|
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, 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; 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.
|
|
|
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: A037227 A056753 A154723 * A001051 A046730 A002972
Adjacent sequences: A114564 A114565 A114566 * A114568 A114569 A114570
|
|
|
KEYWORD
| easy,nonn
|
|
|
AUTHOR
| Michael Stay (metaweta(AT)gmail.com), Feb 15 2006
|
| |
|
|
