A ripoff of this challenge. Go upvote it!


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_{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.\$

iteration limit

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


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.

  1. 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}\$.


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


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

  • \$\begingroup\$ Input and output must be exact rational numbers. I think this implicitly bans a usage of floating-point numbers. \$\endgroup\$ Jul 24, 2020 at 21:00
  • \$\begingroup\$ ''If your language doesn't natively support rational number arithmetic, use a pair of integers.'' Must the pair of integers be relative prime? \$\endgroup\$
    – Abigail
    Jul 24, 2020 at 21:58
  • \$\begingroup\$ You may want to add some test cases that cannot be expressed as 1/x. For instance: 1/787 ~> 7/512. \$\endgroup\$
    – Arnauld
    Jul 24, 2020 at 21:58
  • \$\begingroup\$ I found the "How?" section kind-of confusing. Taken literally, going digit by digit is an endless process that doesn't terminate. As you say, the idea is to, for rationals, notice that the repeating pattern of ternary digits creates a repeating pattern of binary digits, and so creates a rational. But that's not what the written algorithm is doing. Working only with the ternary up to the repeating block of digits would make this clearer. \$\endgroup\$
    – xnor
    Jul 24, 2020 at 22:01
  • 2
    \$\begingroup\$ "Bad news": Mathematica has a built-in for this. \$\endgroup\$
    Jul 25, 2020 at 3:34

5 Answers 5


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
  • \$\begingroup\$ Can 3*(p%q) be p%q*3 for -2 bytes? \$\endgroup\$
    – Ada
    Jul 25, 2020 at 14:34
  • \$\begingroup\$ @Ada Indeed! Thank you. \$\endgroup\$
    – Arnauld
    Jul 25, 2020 at 16:37

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

  • 1
    \$\begingroup\$ I just came up with a similar formulation to golf a further 15 bytes from my answer, although I noted that \$\frac{Q(2^n-1)}{2^n}=Q-\frac Q{2^n}=Q-\left\lfloor\frac Q{2^n}\right\rfloor\$ so my final formula is \$\frac{P'}{Q'}=\frac{\left(P-\left\lfloor\frac P{2^n}\right\rfloor\right)}{\left(Q-\left\lfloor\frac Q{2^n}\right\rfloor\right)}\$. \$\endgroup\$
    – Neil
    Jul 26, 2020 at 0:24
  • \$\begingroup\$ @Neil thanks for the formula! \$\endgroup\$ Jul 26, 2020 at 2:24
  • \$\begingroup\$ I think you can actually use Q-Q/i; I only added in the integer division because I was mapping over both P and Q, so it made sense to use integer division both times. \$\endgroup\$
    – Neil
    Jul 26, 2020 at 10:08

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):
 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 21) 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)
        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))
        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)
  • \$\begingroup\$ You don't actually guarantee to return relatively prime integers, e.g. for an input of 9,10 (the ratio is still correct). \$\endgroup\$
    – Neil
    Jul 25, 2020 at 0:27
  • \$\begingroup\$ @Arnauld Fixed for -10 bytes (The non-repeating portion was not padded) \$\endgroup\$ Jul 25, 2020 at 0:35
  • \$\begingroup\$ @Neil Whoops, the output is not actually relatively prime \$\endgroup\$ Jul 25, 2020 at 0:36

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.