# The Cantor Function

## APL (Dyalog Extended), ~~25~~ 27 bytes

```
{⊥1⊥1⌊⊤1∘≠⍛×\0,3⊤⍵×3*⍺}÷2*⊣
```

Try it online!

Inline tacit function, which can be used as `n f x`

.

Uses the method described in Luis Mendo's MATL answer. I changed one part of the algorithm:

- This one doesn't consider integer and fractional parts separately; rather, the fractional part is included in the last digit. (e.g. the base-3 representation of 8.1 is
`[2, 2.1]`

.) Later, at the step where 2s are changed into 1s, all digits`≥2`

are reduced by 1 instead, and**(+2 bytes)**the fractional part of the last digit is removed if its integer part is 1.

```
{⊥1⊥1⌊⊤1∘≠⍛×\0,3⊤⍵×3*⍺}÷2*⊣ ⍝ Left: n, Right: x
{ ⍵×3*⍺} ⍝ 3^n*x
3⊤ ⍝ Convert to base 3; last digit may have fractional part
0, ⍝ Prepend 0 to avoid error on ⊤ over an empty array
1∘≠⍛×\ ⍝ Keep each digit unless at least one 1 appears somewhere on its left
⊤ ⍝ Convert each digit to binary
1⌊ ⍝ Clamp all digits >1 to 1 (effectively cuts the fractional part of
⍝ the last digit if its integer part is 1)
1⊥ ⍝ Treat the binary of each digit as base 1 and convert back to a number
⍝ Since all numbers are <3, effectively "decrement if ≥2"
⊥ ⍝ Treat as base 2 and convert to single number
÷2*⊣ ⍝ Divide by 2^n
```

## MATL, 33 bytes

```
3y^i*1&\3_YAt1=f"[email protected](wkw]XB+wW/
```

Inputs are `n`

, then `x`

.

Try it online! Or verify all test cases.

### Approach

The code uses a non-recursive approach, based on the procedure for computing the Cantor function \$f_\infty(x)\$ that appears in Wikipedia, modified so that it computes \$f_n(x)\$ instead:

- Multiply \$x\$ by \$3^n\$.
- Decompose the result into integer part \$M\$ and decimal part \$F\$.
- Express \$M\$ in base \$3\$. Let \$B\$ be the resulting sequence of up to \$n\$ digits from the set \$\{0, 1, 2\}\$.
- If \$B\$ contains a \$1\$, replace every digit after the first \$1\$ by \$0\$.
- Replace any remaining \$2\$s with \$1\$s.
- Interpret the result as a binary number.
- If \$B\$ didn't contain \$1\$s, add \$F\$.
- Divide by \$2^n\$.

### Some golfing tricks

- Using a
`for`

loop instead of an`if`

branch for step 4 saved quite a few bytes. The value for the branch condition (index of first \$1\$) needed to be used within the branch code (to replace subsequent digits by \$0\$). This is cumbersome in MATL, as the`if`

branch consumes (pops) its condition. Instead, the loop solves this more elegantly: since the branch condition was either empty or a vector of indices of \$1\$s in \$B\$, it can be looped over: if it's empty the loop is simply not entered. And then the loop variable can be used within the loop code. The fact that the loop, unlike the conditional branch, may iterate*several*times (if there are more than one \$1\$ digit) is not harmful here, because the substitutions in step 4 are idempotent: they simply overwrite some of the previous \$0\$s with new \$0\$s. - Step 7 is partly handled within the
`for`

loop. Specifically, if the loop is entered, the decimal part \$F\$ should not be added later on. To implement this, the loop iteration replaces \$F\$ (previously stored in the stack) by \$0\$. This is done by a round-down operation (`k`

), which is convenient because it uses only 1 byte and is, again, idempotent: the result remains equal to \$0\$ in all iterations after the first. - The MATL function that converts from binary to decimal (
`XB`

) treats any digit other than \$0\$ as if it were \$1\$, which is useful for steps 5 and 6.

### Commented code

```
3 % Step 1. Push 3
y % Implicit input: n. Duplicate from below: pushes n below and
% above the 3
^ % Power: gives 3^n
i* % Input: x. Multiply: gives x*3^n
1 % Step 2. Push 1
&\ % Two-output modulus: gives modulus (F) and quotient (M)
3_YA % Step 3. Convert to base 3, with digis 0, 1, 2
t1= % Step 4 and part of step 7. Duplicate. Compare each entry with 1
f % Vector (possibly empty) of indices of true values; that is,
% positions of digit 1
" % For each index k
O % Push 0
@Q % Push k+1
Jh( % Write 0 at positions k+1, k+2, ..., end
wkw % Swap, round down, swap. This replaces F by 0
] % End
XB % Steps 5 and 6. Convert from binary to decimal, with digit 2
% interpreted as 1
+ % Part of step 7. Add F, or 0
wW/ % Step 8. Swap (brings n to top), 2 raised to that, divide
% Implicit display
```

## APL (Dyalog Unicode), 38 bytes

```
{×⍺×1-⍵:2÷⍨(1∘≤+(1≠⌊)×(⍺-1)∇⊢-⌊)3×⍵⋄⍵}
```

Try it online!

Combines the cases of the recurrence using

$$ f_{n+1}(x) = \frac{1}{2}\begin{cases} 0+1×f_n(3x-0), x\in[0,1/3) \\ 1+0×f_n(3x-1), x\in[1/3,2/3)\\ 1+1×f_n(3x-2), x\in[2/3,1] \end{cases} $$

which can be condensed (note \$u=3x\$) to

$$
f_{n+1}\left(\frac{1}{3}u\right) = \frac{1}{2}\big(
(u<1)+(\lfloor u\rfloor\neq 1)×f_n(u-\lfloor u \rfloor)\big)
$$ (since comparisons resolve to True=1 or False=0). This fails for `x=1`

since then `⌊u`

is 3 instead of 2. Using ceiling instead of floor would then fail for `x=0`

, so it ends up shorter to check specifically for `x=1`

.

```
{ ... } ⍺=n; ⍵=x
×⍺×1-⍵: ⍝ If n>0 or x≠1:
3×⍵ ⍝ Let u=3x
(⍺-1)∇⊢-⌊ ⍝ f(n-1, u-floor(u)) (`1∘|` ←→ `⊢-⌊`)
(1≠⌊)× ⍝ Multiply by 1 unless floor(u)=1
1∘≤+ ⍝ Add 1 unless 1 > u
2÷⍨ ⍝ Half of this
⋄ ⍝ Else:
⍵ ⍝ x
```