Cantor Function, Cruel
JavaScript (ES7), 141 ... 128 125 bytes
Saved 2 bytes thanks to @Ada
Expects the fraction \$p/q\$ as (p)(q). Returns \$P/Q\$ as [P,Q].
p=>q=>(k='0b'+(n=0,g=p=>(r=n-g[p])?'':p/q&1||[p/q>>1]+g(p%q*3,g[p]=n++))(p),r?[((k>>r)*(m=2**r-1)+(k&m))*2,m<<n-r]:[+k,1<<n])
Try it online!
How?
Ternary and binary expansions
k = // build a binary string
'0b' + ( // append the binary prefix
n = 0, // n is a bit counter
g = p => // g is a recursive function taking the numerator p
(r = n - g[p]) ? // if p was already encountered, we have a repeating
// pattern, whose length is stored in r; in that case:
'' // stop the recursion
: // else:
p / q & 1 || // if p/q = 1, append a '1' and stop the recursion
[p / q >> 1] + // otherwise, append '1' if p/q = 2 or '0' if p/q = 0
g( // append the result of a recursive call to g:
3 * (p % q), // update p to 3 * (p modulo q)
g[p] = n++ // store the position of p in g and increment n
) // end of recursive call
)(p) // initial call with the numerator provided in the input
Turning the binary expansion into a decimal fraction
If \$r\$ is NaN after the first step, it means that the binary expansion has no repeating pattern. In that case, the numerator is \$k\$ and the denominator is \$2^n\$.
If \$r\$ is defined, we compute the following bitmask:
m = 2 ** r - 1
The numerator is:
((k >> r) * m + (k & m)) * 2
and the denominator is:
m << n - r
Wolfram Language (Mathematica), 15 bytes
CantorStaircase
Try it online! Just a built-in function.
Python 3.8 (pre-release), 120 119 117 bytes
-2 bytes thanks to @Neil!
f=lambda p,q,P=0,Q=1,*R:p in R and(P-P//(i:=1<<R.index(p)+1),Q-Q//i)or f((d:=p*3//q+1)%2*(p*3%q),q,P*2+d//2,Q*2,p,*R)
Try it online!
Same idea as below, but as a lambda function instead.
Python 2, 133 131 125 122 bytes
-3 bytes thanks to @Neil!
def f(p,q,P=0,Q=1,*R):
if p in R:i=1<<R.index(p)+1;return P-P/i,Q-Q/i
d=p*3/q+1;return f(d%2*(p*3%q),q,P*2+d/2,Q*2,p,*R)
Try it online!
A recursive function that takes input as 2 integers p and q. Outputs 2 integers (P,Q) representing the fraction \$P/Q\$ (might not be reduced to lowest term).
Explanation
This solution follows the suggested algorithm in the question.
Ternary expansion
To ternary expand p/q, we divide 3p by q, resulting in the quotient d and remainder r. d is the next ternary digit. To get the digits after that, we simply recurs on r/q.
d, r = p*3/q, p*3%q
Get the binary result
P/Q represents the current result, with Q always be a power of 2.
- If
d == 1, we append 1 to the result, aka(P*2+1, Q*2). To stop the recursion, we set the remainder to 0:f(0, q, P*2+1, Q*2, ...) - If
d == 0, we append 0 to the result and continue:f(r, q, P*2, Q*2, ...) - If
d == 2, we append 1 to the result and continue:f(r, q, P*2+1, Q*2, ...)
We can compress all cases into a single expression. For additional golf, first we increase d by 1: d=p*3/q+1. The 4 cases above become:
return f(
d%2*r, # 0 if d==2, else r
q,
P*2+d/2, # P*2 if d==1, else P*2+1
Q*2,
...)
This happens to also work for when the input fraction is 1 (p == q), in which case d == 4, and f(0, q, 2, 2, ...) is called, which results in the fraction 4/4.
Termination
The function has to terminate once it finds a repeating block of digits in the ternary expansion. In order to do this, we keep track of all previous numerators in the tuple R. After each iteration, we prepend p to the list of seen numerators: f(..., p, *R).
At the start of each iteration, we check if p is in R. If so, every digit after that will be repeated. The length of the repeated block of ternary digits can be calculated from the position of the previous occurrence of p: n = R.index(p)+1
Let's say that currently, the binary form of P is \$XXXabc\$, where \$abc\$ is the repeated block of digits (aka n = 3). Then
$$P' = XXXabc.abcabc... = \left(P- \left\lfloor{\frac{P}{2^n}}\right\rfloor \right)\frac{2^n}{2^n-1}$$
and the final result is: $$\frac{P'}{Q} = \frac{\left( P- \left\lfloor{\frac{P}{2^n}}\right\rfloor \right) 2^n}{Q(2^n-1)}$$
Edit: @Neil found a better simplification: $$\frac{P-\left\lfloor\frac{P}{2^n}\right\rfloor}{Q-\left\lfloor\frac{Q}{2^n}\right\rfloor}$$