Cantor Function, Cruel

Code Golf Asked on January 4, 2022

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)=limlimits_{ntoinfty} 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)&xin[0,frac{1}{3})\ frac{1}{2}&xin[frac{1}{3},frac{2}{3})\ frac{1}{2}+frac{1}{2}f_n(3x-2)&xin[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_3cdots$.

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


x & 0 & ½ & ⅓ & ¼ & ⅕ & ⅚ & 1 \ hline
text{Ternary expansion of }x & 0.overline{0} & 0.overline{1} & 0.1overline{0} & 0.overline{02} & 0.overline{0121} & 0.2overline{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


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

5 Answers

Wolfram Language (Mathematica), 15 bytes


Try it online! Just a built-in function.

Answered by LegionMammal978 on January 4, 2022

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- leftlfloor{frac{P}{2^n}}rightrfloor right)frac{2^n}{2^n-1}$$

and the final result is: $$frac{P'}{Q} = frac{left( P- leftlfloor{frac{P}{2^n}}rightrfloor right) 2^n}{Q(2^n-1)}$$

Edit: @Neil found a better simplification: $$frac{P-leftlfloorfrac{P}{2^n}rightrfloor}{Q-leftlfloorfrac{Q}{2^n}rightrfloor}$$

Answered by Surculose Sputum on January 4, 2022

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

Answered by Neil on January 4, 2022

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_2ldots x_koverline{y_1y_2ldots 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 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)

Answered by fireflame241 on January 4, 2022

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

Answered by Arnauld on January 4, 2022

Add your own answers!

Related Questions

What’s my PPCG ID?

8  Asked on December 3, 2020 by musicman523


The bouncing sequence

8  Asked on November 28, 2020 by wheat-wizard


Zero sum covers

16  Asked on November 10, 2020 by zgarb


Swapping “Good” and “Bad”

74  Asked on October 15, 2020 by ishaq-khan


Pi to the power y, for small y’s

22  Asked on October 4, 2020 by user9207


The Third String

36  Asked on September 5, 2020 by stephen


Compress your code in an image

11  Asked on August 17, 2020 by blint


Ask a Question

Get help from others!

© 2023 All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP