cp's OEIS Frontend

A114567 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.

%I A114567 #37 Sep 30 2024 10:22:15
%S A114567 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 A114567 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 A114567 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 A114567 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 A114567 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 A114567 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 A114567 Antti Karttunen, <a href="/A114567/b114567.txt">Table of n, a(n) for n = 0..65537</a>
%H A114567 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%F A114567 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 A114567 a(37) = 1 + a(floor(37/2)) + a(floor(37/2^(a(floor(37/2)) + 1)))
%e A114567   = 1 + a(18) + a(floor(37/2^(a(18) + 1)))
%e A114567   = 1 + 1 + a(floor(37/2^(1 + 1)))
%e A114567   = 2 + a(9)
%e A114567   = 2 + 1 + a(floor(9/2)) + a(floor(9/2^(a(floor(9/2)) + 1)))
%e A114567   = 3 + a(4) + a(floor(9/2^(a(4) + 1)))
%e A114567   = 3 + 1 + a(floor(9/4))
%e A114567   = 4 + a(2)
%e A114567   = 5.
%e A114567 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 A114567 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 A114567 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 A114567 (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 A114567 (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 A114567 Cf. A036991.
%K A114567 nonn,base,easy,look
%O A114567 0,2
%A A114567 _Mike Stay_, Feb 15 2006