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

.

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

## Wolfram Language (Mathematica), 15 bytes

```
CantorStaircase
```

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

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