# Cantor Function, Cruel

Code Golf Asked on January 4, 2022

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)=limlimits_{ntoinfty} 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)&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.$$ 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_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}$$.

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

# Wolfram Language (Mathematica), 15 bytes

CantorStaircase


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

### 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- 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, 9277 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):
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 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 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)


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

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


Answered by Arnauld on January 4, 2022

## 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

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