Path in the Stern-Brocot Tree

The Stern-Brocot tree holds every positive fraction exactly once. Each node sits between two bounds, starting with 0/1 on the left and 1/0 (infinity) on the right, and its fraction is the mediant of those bounds: for a/b and c/d that is (a + c)/(b + d). So the root is (0 + 1)/(1 + 0) = 1/1.

To find a fraction x, start at the root. If x is smaller than the node, go Left, and the node becomes the right bound. If x is bigger, go Right, and the node becomes the left bound. Stop when the node equals x. To reach 3/7 you go Left to 1/2, Left to 1/3, Right to 2/5 and Right to 3/7, so the path is LLRR.

Write stern_brocot_path(p, q) that returns the path to p/q compressed into runs: a list of (letter, count) tuples, where letter is 'L' or 'R', count is a positive int, and neighbouring runs have different letters. The path to 1/1 is the empty list.

Examples

stern_brocot_path(3, 7)    # returns [('L', 2), ('R', 2)]
stern_brocot_path(1, 1)    # returns []
stern_brocot_path(5, 2)    # returns [('R', 2), ('L', 1)]

Constraints

• 1 <= p, q <= 10^18
• If p/q is not in lowest terms, find the node with the same value: 6/4 is at the node 3/2.
• A path can be a billion billion steps long (10^18/1 is reached by going Right again and again), so walking one step at a time is far too slow.