login
a(n) is the number 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

%I #37 Sep 30 2024 10:22:15

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

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

%U 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

%N a(n) is the number 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.

%C 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.

%C 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

%H Antti Karttunen, <a href="/A114567/b114567.txt">Table of n, a(n) for n = 0..65537</a>

%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>

%F 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.

%e a(37) = 1 + a(floor(37/2)) + a(floor(37/2^(a(floor(37/2)) + 1)))

%e = 1 + a(18) + a(floor(37/2^(a(18) + 1)))

%e = 1 + 1 + a(floor(37/2^(1 + 1)))

%e = 2 + a(9)

%e = 2 + 1 + a(floor(9/2)) + a(floor(9/2^(a(floor(9/2)) + 1)))

%e = 3 + a(4) + a(floor(9/2^(a(4) + 1)))

%e = 3 + 1 + a(floor(9/4))

%e = 4 + a(2)

%e = 5.

%e 37 mod 2^5 = 5 = 00101, which is the postorder traversal of the binary tree with a root node and a single left child.

%p 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

%t 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 *)

%o (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

%o (PARI) a(n) = my(delta=1); for(i=0,oo, if(bittest(n,i), delta++, delta--||return(i+1))); \\ _Kevin Ryde_, Sep 30 2024

%Y Cf. A036991.

%K nonn,base,easy,look

%O 0,2

%A _Mike Stay_, Feb 15 2006