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.

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

Author

Mike Stay, Feb 15 2006

Keywords

• nonn
• base
• easy
• look

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

Examples

			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.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 0..65537
• Index entries for sequences related to binary expansion of n

Crossrefs

Cf. A036991.

Programs

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

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

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.