login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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; 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

Table of n, a(n) for n=0..100.

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: A300893 A325249 A208239 * A001051 A214737 A046730

Adjacent sequences:  A114564 A114565 A114566 * A114568 A114569 A114570

KEYWORD

easy,nonn

AUTHOR

Mike Stay, Feb 15 2006

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 22 14:32 EDT 2019. Contains 323480 sequences. (Running on oeis4.)