14
\$\begingroup\$

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:

fncantor

The Cantor function \$f(x)\$ can be expressed as a limit \$f(x)=\lim\limits_{n\to\infty} 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)&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.\$

iteration limit

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

  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.1\overline{0} & 0.\overline{02} & 0.\overline{0121} & 0.2\overline{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.

\$\endgroup\$
  • \$\begingroup\$ Input and output must be exact rational numbers. I think this implicitly bans a usage of floating-point numbers. \$\endgroup\$ – Dannyu NDos Jul 24 '20 at 21:00
  • \$\begingroup\$ ''If your language doesn't natively support rational number arithmetic, use a pair of integers.'' Must the pair of integers be relative prime? \$\endgroup\$ – Abigail Jul 24 '20 at 21:58
  • \$\begingroup\$ You may want to add some test cases that cannot be expressed as 1/x. For instance: 1/787 ~> 7/512. \$\endgroup\$ – Arnauld Jul 24 '20 at 21:58
  • \$\begingroup\$ I found the "How?" section kind-of confusing. Taken literally, going digit by digit is an endless process that doesn't terminate. As you say, the idea is to, for rationals, notice that the repeating pattern of ternary digits creates a repeating pattern of binary digits, and so creates a rational. But that's not what the written algorithm is doing. Working only with the ternary up to the repeating block of digits would make this clearer. \$\endgroup\$ – xnor Jul 24 '20 at 22:01
  • 2
    \$\begingroup\$ "Bad news": Mathematica has a built-in for this. \$\endgroup\$ – user202729 Jul 25 '20 at 3:34
7
\$\begingroup\$

Wolfram Language (Mathematica), 15 bytes

CantorStaircase

Try it online! Just a built-in function.

\$\endgroup\$
8
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Can 3*(p%q) be p%q*3 for -2 bytes? \$\endgroup\$ – Ada Jul 25 '20 at 14:34
  • \$\begingroup\$ @Ada Indeed! Thank you. \$\endgroup\$ – Arnauld Jul 25 '20 at 16:37
5
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ I just came up with a similar formulation to golf a further 15 bytes from my answer, although I noted that \$\frac{Q(2^n-1)}{2^n}=Q-\frac Q{2^n}=Q-\left\lfloor\frac Q{2^n}\right\rfloor\$ so my final formula is \$\frac{P'}{Q'}=\frac{\left(P-\left\lfloor\frac P{2^n}\right\rfloor\right)}{\left(Q-\left\lfloor\frac Q{2^n}\right\rfloor\right)}\$. \$\endgroup\$ – Neil Jul 26 '20 at 0:24
  • \$\begingroup\$ @Neil thanks for the formula! \$\endgroup\$ – Surculose Sputum Jul 26 '20 at 2:24
  • \$\begingroup\$ I think you can actually use Q-Q/i; I only added in the integer division because I was mapping over both P and Q, so it made sense to use integer division both times. \$\endgroup\$ – Neil Jul 26 '20 at 10:08
4
\$\begingroup\$

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_2\ldots x_k\overline{y_1y_2\ldots 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)
\$\endgroup\$
  • \$\begingroup\$ You don't actually guarantee to return relatively prime integers, e.g. for an input of 9,10 (the ratio is still correct). \$\endgroup\$ – Neil Jul 25 '20 at 0:27
  • \$\begingroup\$ @Arnauld Fixed for -10 bytes (The non-repeating portion was not padded) \$\endgroup\$ – fireflame241 Jul 25 '20 at 0:35
  • \$\begingroup\$ @Neil Whoops, the output is not actually relatively prime \$\endgroup\$ – fireflame241 Jul 25 '20 at 0:36
3
\$\begingroup\$

Charcoal, 92 77 62 bytes

NθNη≔⟦⟧ζW¬№ζθ«⊞ζθ≧׳θ⊞υ÷⊕÷θη²≔∧⊖÷θη﹪θηθ»IE⟦↨υ²X²Lυ⟧⁻ι÷ιX²⊕⌕⮌ζθ

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:

NθNη

Input the numerator and denominator.

≔⟦⟧ζ

Start a list of partial remainders.

ζW¬№ζθ«

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.

»IE⟦↨υ²X²Lυ⟧

Get the raw binary fraction.

⁻ι÷ιX²⊕⌕⮌ζθ

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

\$\endgroup\$

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.