The Cantor Function

Question

The Cantor function is continuous everywhere and constant almost everywhere, but has an average slope of 1:

The function can be found recursively:

\$f_0(x)=x\$

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

The Cantor function is the limit of this process, \$\lim\limits_{n\to\infty} f_n(x)\$:

The Challenge

Given real x (which can assume the form of a float or rational number) of the interval \$[0,1]\$ and nonnegative integer n, return \$f_n(x)\$.

Rules

• This is code-golf so the shortest answer in bytes wins.

• Assume only valid input will be given.

• Error should be under one ten-thousandth (±0.0001) for the test cases.

Test Cases

In: 0.3 3
Out: 0.3875

In: 0.1 0
Out: 0.1

In: 0.29 4
Out: 0.375

In: 0.11 5
Out: 0.2415625

Answer 1

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

Answer 2

MATL, 33 bytes

3y^i*1&\3_YAt1=f"O@QJh(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:

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

Answer 3

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

Answer 4

Python 3, 54 bytes

f=lambda n,x:n and(1<x*3<2or x//.5+f(n-1,3*x%1))/2or x

Try it online!

Python 3 is used just for the /2 to do float division; Python 2 would be a byte longer with /2..

Answer 5

Python 3.8 (pre-release), 62 bytes

f=lambda n,x:n and[f(n-1,e:=3*x),1+e//2*f(n-1,e-2)][e>1]/2or x

Try it online!

Answer 6

Jelly, 30 bytes

_2çH+.
ñH¥.ç<2$?<1$?
×3çɗ⁸⁹?’}

A full program accepting \$x\$ and \$n\$ which prints a floating-point representation of \$f_n(x)\$

Try it online!

Answer 7

Wolfram Language (Mathematica), 69 bytes

of course mathematica has a built-in for this: CantorStaircase[x] but you cannot choose n

x_~f~0:=x
x_~f~n_:=If[(y=3x)<1,f[y,n-1]/2,If[y<2,.5,.5+f[y-2,n-1]/2]]

Try it online!

@JonathanAllan saved 2 bytes

Here is also another approach from @att which is great!

Wolfram Language (Mathematica), 57 bytes

If[#2<1,#,If[1<3#<2,1,(s=Boole[2#>1])+#0[3#-2s,#2-1]]/2]&

Try it online!

Answer 8

JavaScript (ES6), 45 bytes

Expects (n)(x).

n=>g=x=>n--?((x*=3)<1?g(x):x<2||1+g(x-2))/2:x

Try it online!

Commented

n =>                   // outer function taking n
  g = x =>             // inner recursive function taking x
    n-- ?              // decrement n; if it was not equal to 0:
      (                //   compute f_n(x):
        (x *= 3) < 1 ? //     multiply x by 3; if the result is less than 1:
          g(x)         //       use g(x)
        :              //     else:
          x < 2 ||     //       use 1 if x is less than 2
          1 + g(x - 2) //       otherwise, use 1 + g(x - 2)
      ) / 2            //   in all cases, divide the result by 2
    :                  // else:
      x                //   stop recursion and return f_0(x) = x

Answer 9

C (gcc), ^{73 \$\cdots\$ 71} 69 bytes

Saved 4 bytes thanks to the man himself Arnauld!!!

float f(n,x)float x;{x*=3;x=n--?(x<1?f(n,x):x<2?1:1+f(n,x-2))/2:x/3;}

Try it online!

Answer 10

Python 3.8, 70 74 bytes

1 byte saved thanks to @FryAmTheEggman

f=lambda n,x:n and((1<=(t:=x*3))+f(n-1,t-2*(t>=2))*(t>=2or 1>t))/2or x

Try it online!

Answer 11

Perl 5, 78 bytes

sub f{my$b=pop;my$a=pop;$b--?($a<1/3?f(3*$a,$b):$a<2/3?1:1+f(3*$a-2,$b))/2:$a}

Try it online!

Answer 12

R, 76 ... 60 58 bytes

-6 bytes thanks to Robin Ryder, +1 byte to fix bug spotted by Neil, -2 bytes thanks to Giuseppe

f=function(x,n,y=x*3)`if`(n,(min(f(y%%2,n-1),1)+!y<2)/2,x)

Try it online!

Un-golfed:

cantor=f=function(x,n){
    y=3*x                               # define y=3*x
                                        # to save characters later.
    if(n==0){ x }                       # if n==0 just return x
    else {                              # otherwise
        (
         min(                           # whichever is smaller of:
            cantor(y%%2,n-1),           # - call self using y mod 2
                                        #   (this works for the first & last thirds
                                        #   but gives a result >1 for middle third)
            1)                          # - 1 (to fix the middle third)
         +(y>=2)                        # for the top third we need to add 1 to 
                                        # the result of the self call
        )
        /2                              # finally, we divide all above results by 2
    } 
}

Answer 13

Charcoal, 35 bytes

Ｎθ≔↨×ＮＸ³θ³ηＩ∕↨²Ｅη∧¬№…ηκ¹§⟦ι¹⊖ι⟧ιＸ²θ

Try it online! Link is to verbose version of code. Based on the Wikipedia entry, I convert the 3ⁿx to base 3, then massage the digits so that the result can be interpreted as base 2 and divided by 2ⁿ. Takes input in the order n, x. Explanation:

Ｎθ

Input n.

≔↨×ＮＸ³θ³ηＩ∕

Multiply x by 3ⁿ and convert it to base 3. The last entry includes any remaining fractional part.

Ｅη∧¬№…ηκ¹§⟦ι¹⊖ι⟧ι

Map over the digits. If there was a previous 1 then set this digit to zero, otherwise map the digit to itself, 1, or subtract 1, depending on the floor of the digit. This ensures that the last digit (with the remaining fractional part) is converted correctly.

Ｉ∕↨²...Ｘ²θ

Convert from base 2, divide by 2ⁿ, and output the final decimal as a string.

Previous 34-byte solution did not work for x=1, as it only considered the decimal part of x:

Ｎθ≔×ＮＸ³θη≔⁻η⌊ηζＦθ≔⊘§⟦ζ¹⊕ζ⟧∕ηＸ³ιζＩζ

Try it online! Link is to verbose version of code. Takes input in the order n, x. Explanation:

Ｎθ

Input n.

≔×ＮＸ³θη

Multiply x by 3ⁿ.

≔⁻η⌊ηζ

Take the decimal part of that.

Ｆθ

Loop n times.

≔⊘§⟦ζ¹⊕ζ⟧∕ηＸ³ιζ

Depending on the next base 3 digit of the above product, replace the decimal part with half of itself, half of 1, or half of the sum.

Ｉζ

Output the final decimal as a string.

Answer 14

05AB1E, 31 bytes

3Im*1‰`s3в¹£εTYèsi1V]2βY≠i+}¹o/

Takes the loose inputs in the order \$n,x\$.

Port of @LuisMendo's MATL answer, so make sure to upvote him as well!

Try it online or verify all test cases.

Explanation:

3Im              # Push 3 to the power of the first input-integer
   *             # Multiply it by the (implicit) input-decimal
    1‰           # Get the divmod-1 to split the integer and decimal parts
      `s         # Pop and push them separated to the stack in reversed order
3в               # Convert the integer part to base-3 as list
  ¹£             # Only leave the first input-integer amount of base-3 digits
    ε            # Map this list to:
     T           #  Push 10
      Yè         #  Index `Y` into this
                 #  (`Y` is 2 by default, which wraps modulair indices into the 1)
     si          #  If the current digit we're mapping over is 1:
       1V        #   Set `Y` to 1
    ]            # Close both the if-statement and map
     2β          # Convert the resulting list from base-2 to an integer
       Y≠i }     # If `Y` is NOT 1:
          +      #  Add the decimal part that's still on the stack
            ¹o/  # And divide this by 2 to the power the first input-integer
                 # (after which the result is output implicitly)