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].


Try it online!


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


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).


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
  P*2+d/2,   # P*2 if d==1, else P*2+1

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.


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}$$