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.
Equivalently, the number of bits of n, starting from the least significant, in which the number of 0's first exceeds the number of 1's (including 0's above the most significant bit of n if necessary). - Kevin Ryde, Sep 30 2024
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
(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
(PARI) a(n) = my(delta=1); for(i=0, oo, if(bittest(n, i), delta++, delta--||return(i+1))); \\ Kevin Ryde, Sep 30 2024
CROSSREFS
KEYWORD
AUTHOR
Mike Stay, Feb 15 2006
STATUS
approved