Unfolding an integer

Question

Given the functions

L: (x, y) => (2x - y, y)
R: (x, y) => (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 ---> ( -1,  1)
2. L ---> ( -3,  1)
3. R ---> ( -3,  5)
4. L ---> (-11,  5)
5. R ---> (-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.

Answer 1

Perl, 82 81 Characters (complete program)

$n=<>;@_=(R,L);if($n<0){$n=1-$n;$a--}while($n>1){print$_[$n%2+$a];$n+=$n%2;$n/=2}

It takes one number as input, and it outputs the sequence in application order.

Edit: Instead of redefining the array in the if statement, set a number to negative one and add it to the index when the array is referenced. It achieves the same effect.

Answer 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]:''}

Answer 3

Jelly, 15 bytes

“”HĊß;ị⁾LR$ƲḂƑ?

Try it online!

This uses the same allowance in Howard's answer, in that we can use recursion, despite it violating the \$O(1)\$ memory requirement. If this isn't allowed, then the following 20 byte solution works instead:

ḶȯAṀ©Bị⁾LRUAƑ}¡$®aḟ0

Try it online!

Both output the composition order

How they work

“”HĊß;ị⁾LR$ƲḂƑ? - Main link f(N). Takes N on the left
              ? - If statement:
             Ƒ  -   If: Invariant under:
            Ḃ   -     Bit; Yields 1 for 0/1, else 0
“”              -   Then: Return the empty string
           Ʋ    -   Else:
  H             -     N÷2
   Ċ            -     Ceiling
    ß           -     f(⌈N÷2⌉)
          $     -     Group the previous 2 links together as a monad g(N):
       ⁾LR      -       "LR"
      ị         -       Modular index N into "LR"
     ;          -     Append to f(⌈N÷2⌉)

The 20 byte version (+6 bytes to handle \$N = 0, 1\$):

ḶȯAṀ©Bị⁾LRUAƑ}¡$®aḟ0 - Main link. Takes N on the left
Ḷ                    - [0, 1, ..., N-1] for N > 0 else []
  A                  - abs(N)
 ȯ                   - Replace [] with abs(N)
   Ṁ                 - Max; N-1 if N > 0 else abs(N)
    ©                - Save this to the register R
     B               - Convert R to binary
               $     - Group the previous 2 links into a monad f(N):
       ⁾LR           -   "LR"
             }       -   To N:
            Ƒ        -     Invariant under:
           A         -       Absolute value; 1 if N ≥ 0 else 0
              ¡      -   Do the following that many times:
          U          -     Reverse "LR"
                         This yields "RL" if N ≥ 0 else "LR" 
      ị              - For each bit in R, index into "RL" or "LR",
                       yielding a list of Rs and Ls, S
                ®    - Yield R
                 a   - Replace all but R = 0 with S
                  ḟ0 - Change R = 0 to []