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, 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

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

Antti Karttunen, Table of n, a(n) for n = 0..65537

Index entries for sequences related to binary expansion of n

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

(PARI) A114567(n) = if(!(n%2), 1, 1+A114567(n\2) + A114567(n>>(1+A114567(n\2)))); \\ Antti Karttunen, Mar 30 2021, after the Maple-program

Crossrefs

Sequence in context: A325249 A352453 A208239 * A001051 A214737 A348161

Adjacent sequences: A114564 A114565 A114566 * A114568 A114569 A114570

Keyword

nonn,base,easy,look

Author

Mike Stay, Feb 15 2006

Status

approved