22
\$\begingroup\$

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

fncantor

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)\$:

iteration limit

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 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
\$\endgroup\$
4
  • 2
    \$\begingroup\$ Related (draw \$f_n\$ in ASCII art) \$\endgroup\$ – Luis Mendo Jul 22 '20 at 22:08
  • \$\begingroup\$ The average slope is actually 0. \$\endgroup\$ – PyRulez Jul 23 '20 at 18:44
  • 1
    \$\begingroup\$ Using the average slope formula m=(y2-y1)/(x2-x1) and the points (0,0) and (1,1) one can see the average slope is 1 @PyRulez \$\endgroup\$ – golf69 Jul 23 '20 at 18:47
  • \$\begingroup\$ In any case, the slope is 0 almost everywhere. \$\endgroup\$ – Alexis Olson Jul 24 '20 at 21:11

14 Answers 14

8
\$\begingroup\$

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
\$\endgroup\$
3
  • \$\begingroup\$ @LuisMendo He doesn't; I was just checking that myself, in case it helped me golf more bytes from my answer. (To be specific, 3 f 0.72 is returning 0.68 instead of the correct 0.625 that your answer gives.) \$\endgroup\$ – Neil Jul 23 '20 at 11:07
  • \$\begingroup\$ @LuisMendo Ah, so 1∘≠⍛×\ works for the first n-1 base 3 digits; it's only the case of when the nth digit is a 1 that his answer doesn't work. \$\endgroup\$ – Neil Jul 23 '20 at 11:15
  • \$\begingroup\$ Thanks for pointing out the error. I think I have a +2 bytes fix; I'll update the post when I get to my PC. \$\endgroup\$ – Bubbler Jul 23 '20 at 13:13
7
\$\begingroup\$

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
\$\endgroup\$
5
  • \$\begingroup\$ So, much like my second approach, but without the bug... I'd better go back and fix my answer. \$\endgroup\$ – Neil Jul 23 '20 at 10:11
  • 1
    \$\begingroup\$ @Neil Nah. Your current 34 byte count is perfect :-P \$\endgroup\$ – Luis Mendo Jul 23 '20 at 10:16
  • \$\begingroup\$ Sadly it didn't work for x=1. (In a deleted comment, @Bubbler pointed out that @fireflame241 had the same problem with his answer.) \$\endgroup\$ – Neil Jul 23 '20 at 10:44
  • \$\begingroup\$ (But the good news is that I can use @Bubbler's adjustment to your method, and this actually saves me 2 bytes overall, which is almost back down to the original byte count.) \$\endgroup\$ – Neil Jul 23 '20 at 10:46
  • \$\begingroup\$ Yeah, pity that MATL's base conversion cannot handle non-integer values \$\endgroup\$ – Luis Mendo Jul 23 '20 at 11:07
6
\$\begingroup\$

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
\$\endgroup\$
3
  • \$\begingroup\$ @Bubbler Fixed. \$\endgroup\$ – fireflame241 Jul 22 '20 at 23:14
  • \$\begingroup\$ Shouldn't u < 1 in your explanation be u ≥ 1? \$\endgroup\$ – Neil Jul 23 '20 at 9:55
  • \$\begingroup\$ If n>0 or x≠1 - you mean and? you can avoid x≠1 by replacing ⊢-⌊ with 2|⊢ \$\endgroup\$ – ngn Jul 31 '20 at 7:00
5
\$\begingroup\$

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

\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
2
  • \$\begingroup\$ I was just about to suggest 69 bytes before your edit. \$\endgroup\$ – Arnauld Jul 23 '20 at 13:23
  • \$\begingroup\$ That's a much better direction to golf in. Was just think how on earth do I factor out the /2 and the x<2, and there you have it: call recursively from two places. Since your golf is based on the original gave you -4 bytes - thanks! :D \$\endgroup\$ – Noodle9 Jul 23 '20 at 13:31
3
\$\begingroup\$

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!

\$\endgroup\$
1
  • \$\begingroup\$ @FryAmTheEggman thanks \$\endgroup\$ – Uriel Jul 22 '20 at 21:22
3
\$\begingroup\$

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!

\$\endgroup\$
2
  • \$\begingroup\$ Using a condition of x<2/3 and swapping the branches would save a byte. Can you place 3x in a variable, say y, in five bytes (or less)? If so you can save a byte (or more) by then replacing 1/3 with 1, 2/3 with 2 and the two occurrences of 3x with y. \$\endgroup\$ – Jonathan Allan Jul 22 '20 at 21:39
  • \$\begingroup\$ 57 bytes \$\endgroup\$ – att Jul 23 '20 at 0:44
3
\$\begingroup\$

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!

\$\endgroup\$
1
  • \$\begingroup\$ Nice again! You can save a few bytes using my($a,$b)=@_; instead of the pops though! \$\endgroup\$ – Dom Hastings Jul 23 '20 at 15:57
3
\$\begingroup\$

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
    } 
}
\$\endgroup\$
11
  • \$\begingroup\$ 72 bytes by avoiding some ifs. \$\endgroup\$ – Robin Ryder Jul 23 '20 at 9:32
  • 1
    \$\begingroup\$ Thanks! I managed to removed some more bytes in the meantime! \$\endgroup\$ – Dominic van Essen Jul 23 '20 at 9:50
  • \$\begingroup\$ ...but combining this with your approach managed to shave-off another 2! Thanks again! \$\endgroup\$ – Dominic van Essen Jul 23 '20 at 9:58
  • \$\begingroup\$ floor(y) can be y%/%1 for -3 bytes. \$\endgroup\$ – Robin Ryder Jul 23 '20 at 9:59
  • \$\begingroup\$ Super! Thanks again! \$\endgroup\$ – Dominic van Essen Jul 23 '20 at 10:02
2
\$\begingroup\$

Charcoal, 35 bytes

Nθ≔↨×NX³θ³ηI∕↨²Eη∧¬№…ηκ¹§⟦ι¹⊖ι⟧ιX²θ

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:

Nθ

Input n.

≔↨×NX³θ³ηI∕

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

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

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.

I∕↨²...X²θ

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:

Nθ≔×NX³θη≔⁻η⌊ηζFθ≔⊘§⟦ζ¹⊕ζ⟧∕ηX³ιζIζ

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

Nθ

Input n.

≔×NX³θη

Multiply x by 3ⁿ.

≔⁻η⌊ηζ

Take the decimal part of that.

Fθ

Loop n times.

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

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.

Iζ

Output the final decimal as a string.

\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$
1
  • \$\begingroup\$ If I put in 3 0.72 then I get 0.875 which seems wrong; I think it should be 0.625. \$\endgroup\$ – Neil Jul 23 '20 at 11:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.