Code Golf Asked on January 4, 2022
A ripoff of this challenge. Go upvote it!
Given a rational number amongst $[0,1]$, apply the Cantor function to it and output the rational number that’s produced.
The Cantor function is continuous everywhere and constant almost everywhere, but has an average slope of 1:
The Cantor function $f(x)$ can be expressed as a limit $f(x)=limlimits_{ntoinfty} 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)&xin[0,frac{1}{3})\ frac{1}{2}&xin[frac{1}{3},frac{2}{3})\ frac{1}{2}+frac{1}{2}f_n(3x-2)&xin[frac{2}{3},1] end{matrix}right.$
Your task is to compute $f(x)$ for the rational $x in [0,1] cap mathbb{Q}$ given as input.
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}$:
Ternary-expand $x$ to $0.t_1t_2t_3cdots$.
Write "0.".
Set $n=1$.
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.
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}$.
$$
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.1overline{0} & 0.overline{02} & 0.overline{0121} & 0.2overline{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}
$$
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.
Answered by LegionMammal978 on January 4, 2022
-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)
Same idea as below, but as a lambda function instead.
-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)
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).
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.
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, ...)
d == 0
, we append 0 to the result and continue: f(r, q, P*2, Q*2, ...)
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- leftlfloor{frac{P}{2^n}}rightrfloor right)frac{2^n}{2^n-1}$$
and the final result is: $$frac{P'}{Q} = frac{left( P- leftlfloor{frac{P}{2^n}}rightrfloor right) 2^n}{Q(2^n-1)}$$
Edit: @Neil found a better simplification: $$frac{P-leftlfloorfrac{P}{2^n}rightrfloor}{Q-leftlfloorfrac{Q}{2^n}rightrfloor}$$
Answered by Surculose Sputum on January 4, 2022
ＮθＮη≔⟦⟧ζＷ¬№ζθ«⊞ζθ≧×³θ⊞υ÷⊕÷θη²≔∧⊖÷θη﹪θηθ»ＩＥ⟦↨υ²Ｘ²Ｌυ⟧⁻ι÷ιＸ²⊕⌕⮌ζθ
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:
ＮθＮη
Input the numerator and denominator.
≔⟦⟧ζ
Start a list of partial remainders.
ζＷ¬№ζθ«
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.
»ＩＥ⟦↨υ²Ｘ²Ｌυ⟧
Get the raw binary fraction.
⁻ι÷ιＸ²⊕⌕⮌ζθ
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.)
Answered by Neil on January 4, 2022
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.
The program separately identifies the repeating and non-repeating portions of the ternary representation of a/b
, then splits into 2 cases:
If there is a 1 in either portion, then the numerator is (converted from binary with 2
→1
) the concatenation of the two portions up to the 1, and the denominator is 2 to the power of the length of that section
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_2ldots x_koverline{y_1y_2ldots 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)
Answered by fireflame241 on January 4, 2022
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])
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
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
Answered by Arnauld on January 4, 2022
22 Asked on October 4, 2020 by user9207
Get help from others!
Recent Answers
Recent Questions
© 2023 AnswerBun.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP