###Ruby, 55 or 39 characters###

f=->n{(n>0?n-1:-n).to_s(2).tr'01',n>1?'LR':n<0?'RL':''}

The function returns the function sequence in composition order.

Usage:

puts f[21]     # RLRLL
puts f[-6]     # LLR

Edit: If we allow recursion (which violates the O(1) memory constraint but such does any function since the return value itself is O(lg n)) we can shrink the code to 39 characters.

f=->n{n<n*n ?f[(n-1)/2+1]+'RL'[n%2]:''}

Ruby, 55 or 39 characters

f=->n{(n>0?n-1:-n).to_s(2).tr'01',n>1?'LR':n<0?'RL':''}

The function returns the function sequence in composition order.

Usage:

puts f[21]     # RLRLL
puts f[-6]     # LLR

Edit: If we allow recursion (which violates the O(1) memory constraint but such does any function since the return value itself is O(lg n)) we can shrink the code to 39 characters.

f=->n{n<n*n ?f[(n-1)/2+1]+'RL'[n%2]:''}

###Ruby, 55 characters###

f=->n{(n>0?n-1:-n).to_s(2).tr'01',n>1?'LR':n<0?'RL':''}

The function returns the function sequence in composition order.

Usage:

puts f[21]     # RLRLL
puts f[-6]     # LLR

###Ruby, 55 or 39 characters###

f=->n{(n>0?n-1:-n).to_s(2).tr'01',n>1?'LR':n<0?'RL':''}

The function returns the function sequence in composition order.

Usage:

puts f[21]     # RLRLL
puts f[-6]     # LLR

Edit: If we allow recursion (which violates the O(1) memory constraint but such does any function since the return value itself is O(lg n)) we can shrink the code to 39 characters.

f=->n{n<n*n ?f[(n-1)/2+1]+'RL'[n%2]:''}