Cantor Function, Cruel

Question

A ripoff of this challenge. Go upvote it!

Objective

Given a rational number amongst \$[0,1]\$, apply the Cantor function to it and output the rational number that's produced.

The Cantor function

The Cantor function is continuous everywhere and constant almost everywhere, but has an average slope of 1:

The Cantor function \$f(x)\$ can be expressed as a limit \$f(x)=\lim\limits_{n\to\infty} f_n(x)\$ of a sequence of functions \$f_0, f_1, f_2, \dots\$, which are defined recursively as:

\$f_0(x)=x\$

\$f_{n+1}(x)=\left\{\begin{matrix}\frac{1}{2}f_n(3x)&x\in[0,\frac{1}{3})\\ \frac{1}{2}&x\in[\frac{1}{3},\frac{2}{3})\\ \frac{1}{2}+\frac{1}{2}f_n(3x-2)&x\in[\frac{2}{3},1] \end{matrix}\right.\$

Your task is to compute \$f(x)\$ for the rational \$x \in [0,1] \cap \mathbb{Q}\$ given as input.

How?

Though this task might seem impossible, this is actually possible, for the Cantor function is computable.

A step-by-step solution for \$x \in \mathbb{R}\$:

1. Ternary-expand \$x\$ to \$0.t_1t_2t_3\cdots\$.

2. Write "0.".

3. Set \$n=1\$.

4. If \$t_n = 1\$, write "1" and halt.

• Otherwise, if \$t_n = 0\$, write "0", increment \$n\$, then continue doing step #4.

• Otherwise (\$t_n = 2\$), write "1", increment \$n\$, then continue doing step #4.

5. Parse the resulting string as a binary expansion of a real number.

As \$x\$ actually is in \$\mathbb{Q}\$ in this challenge, you should exploit the fact that the ternary expansion of \$x\$ repeats. It follows that the output is also in \$\mathbb{Q}\$.

Examples

$$ \begin{array}{r|c|c|c|c|c|c|c|c|c|c} x & 0 & ½ & ⅓ & ¼ & ⅕ & ⅚ & 1 \\ \hline \text{Ternary expansion of }x & 0.\overline{0} & 0.\overline{1} & 0.1\overline{0} & 0.\overline{02} & 0.\overline{0121} & 0.2\overline{1} & 0.\overline{2} \\ \hline \text{Binary expansion of } f(x) & 0.\overline{0} & 0.1 & 0.1 & 0.\overline{01} & 0.01 & 0.11 & 0.\overline{1} \\ \hline f(x) & 0 & ½ & ½ & ⅓ & ¼ & ¾ & 1 \end{array} $$

Rules

• Invalid inputs fall in don't care situation. In particular, you don't need to deal with numbers outside of \$[0,1]\$.

• Input and output must be exact rational numbers. If your language doesn't natively support rational number arithmetic, use a pair of integers.

Answer 1

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

Answer 2

Wolfram Language (Mathematica), 15 bytes

CantorStaircase

Try it online! Just a built-in function.

Answer 3

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

Answer 4

Python 2, 347 337 bytes

exec"B=L,d:B(x/3,d-1)+[x%3]if d else[];V=L:0if x%3else 1+V(x/3);r=L,b,n=1:(3**n-1)%b and r(x,b,n+1)or[n,B((3**n-1)*x/b,n)];F=L:x>[]and(x[-1]>0)+2*F(x[:-1])".replace("L","lambda x")
def c(a,b):
 v=V(b);b/=3**v;N=B(a/b,v);n,R=r(a%b,b);D=N+R
 if 1in D:d=D[:D.index(1)+1];print F(d),2**len(d)
 else:print F(N)*(2**n-1)+F(R)or a,2**v*(2**n-1)

Try it online! (modified to return statements for verification)

Takes and returns pairs of integers (numerator, denominator). The input pair must be relatively prime.

How it works

The program separately identifies the repeating and non-repeating portions of the ternary representation of a/b, then splits into 2 cases:

1. If there is a 1 in either portion, then the numerator is (converted from binary with 2→1) the concatenation of the two portions up to the 1, and the denominator is 2 to the power of the length of that section

2. If there is no 1, then the number retains the repeating portion, so in base 2 (after converting 2s to 1s),

   $$\frac{a}{b}=0.x_1x_2\ldots x_k\overline{y_1y_2\ldots y_n}=0.\mathbb{x}\overline{\mathbb{y}}$$

   Then $$\frac{a}{b}=\frac{1}{2^k}\left(\mathbb{x} + \frac{1}{2^n-1}\mathbb{y}\right)=\frac{(2^n-1)\mathbb{x}+\mathbb{y}}{(2^n-1)(2^k)}$$

# Most-significant ternary digit first
base3 = lambda x, d: base3(x//3, d-1)+[x%3] if d else []
# Largest exponent of a power of 3 that divides x
v3 = lambda x: 0 if x%3 else 1+v3(x//3)
# Base 3 representation of a/b as 0.xyz repeating, where b contains no factors of 3
def rep3(a,b,n=1):
    if (3**n-1)%b==0:
        return n, base3((3**n-1)*a//b,n)
    else:
        return rep3(a,b,n+1)

# Base 2 to int, including converting '2's to '1's
from_base2 = lambda l: eval('0b0'+''.join(map(str,l)).replace('2','1'))

def cantor(a, b):
    # Extract the non-repeating portion of the ternary expansion of a/b
    v = v3(b)
    b //= 3**v
    non_repeating = base3(a//b,v)
    # Repeating portion
    n, repeating = rep3(a%b, b)
    digs = non_repeating + repeating
    if 1 in digs:
        # Take only the part up to/including the first 1, and use it as a binary decimal
        d = digs[:digs.index(1)+1]
        return from_base2(d), 2**(len(d))
    else:
        x = from_base2(non_repeating)
        y = from_base2(repeating)
        # `or a` accounts for the a=b=1 case, which gets treated otherwise as 0.0
        return y+x*(2**n-1) or a, 2**v*(2**n-1)

Answer 5

Charcoal, 92 77 62 bytes

ＮθＮη≔⟦⟧ζＷ¬№ζθ«⊞ζθ≧׳θ⊞υ÷⊕÷θη²≔∧⊖÷θη﹪θηθ»ＩＥ⟦↨υ²Ｘ²Ｌυ⟧⁻ι÷ιＸ²⊕⌕⮌ζθ

Try it online! Link is to verbose version of code. I/O is a pair of integers. Does not reduce the output to lowest terms, in particular 1 1 outputs as 2 2 as that needed fewer hacks than before, which helped to save 15 bytes. Explanation:

ＮθＮη

Input the numerator and denominator.

≔⟦⟧ζ

Start a list of partial remainders.

ζＷ¬№ζθ«

Repeat while the current partial remainder has not been seen before.

⊞ζθ

Push the current partial remainder to the list.

≧׳θ

Triple it.

⊞υ÷⊕÷θη²

Push the next bit of the result. (Note that an input of 1 is treated as the illegal ternary 0.3 and massaged into the illegal binary 0.2.)

≔∧⊖÷θη﹪θηθ

Get the next partial remainder, unless the current ternary digit is 1, in which case the next partial remainder is zero.

»ＩＥ⟦↨υ²Ｘ²Ｌυ⟧

Get the raw binary fraction.

⁻ι÷ιＸ²⊕⌕⮌ζθ

Adjust it for the recurring part of the binary fraction. (In the case of a terminating fraction, this is detected a bit after the fraction terminates, effectively doubling the numerator and denominator, but the adjustment here simply halves both values again.)