Unfolding an integer Given the functions

L: (x, y) =&gt; (2x - y, y)
R: (x, y) =&gt; (x, 2y - x)


and a number N generate a minimal sequence of function applications which take the initial pair (0, 1) to a pair which contains N (i.e. either (x, N) or (N, y)).

Example: N = 21. The minimal sequence is of length 5, and one such sequence is

          (  0,  1)
1. L ---&gt; ( -1,  1)
2. L ---&gt; ( -3,  1)
3. R ---&gt; ( -3,  5)
4. L ---&gt; (-11,  5)
5. R ---&gt; (-11, 21)


Write the shortest function or program you can which generates a minimal sequence in O(lg N) time and O(1) space. You may output / return a string in either application order (LLRLR) or composition order (RLRLL), but document which.
Ruby, 55 or 39 characters
f=-&gt;n{(n&gt;0?n-1:-n).to_s(2).tr'01',n&gt;1?'LR':n&lt;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=-&gt;n{n&lt;n*n ?f[(n-1)/2+1]+'RL'[n%2]:''}