Inverse of Conway base 13 function in \$\mathbb{Q}\$

Question

(The \$\mathbb{Q}\$ in the title means rational numbers.)

Background

Conway base 13 function is an example of a strongly Darboux function, a function that takes every real number on any open interval \$(a,b)\$. In other words, for any given real numbers \$a, b, y\$, you can find a value \$x\$ between \$a\$ and \$b\$ such that \$f(x) = y\$.

The function is defined as follows:

1. Write the input value x in base 13 using thirteen symbols 0 .. 9, A, B, C, without any trailing infinite stream of Cs. (It is related to the fact 0.9999... = 1 in base 10, or 0.CCC... = 1 in base 13.)
2. Delete the sign and decimal point, if present.
3. Replace As with +, Bs with -, Cs with ..
4. Check if some (possibly infinite) suffix of the sequence starts with a sign (+ or -) and contains exactly one . and no extra signs. If such a suffix exists, interpret it as a decimal number; it is the value of \$f(x)\$. Otherwise, \$f(x) = 0\$.

Some examples:

• \$f(123B45.A3C14159\dots _{13}) = f(0.A3C14159\dots _{13}) = 3.14159\dots \$
• \$f(B1C234 _{13}) = -1.234\$
• \$f(1C234A567 _{13}) = 0\$

Task

Given three rational numbers \$a = \frac{a_n}{a_d}, b = \frac{b_n}{b_d}, y = \frac{y_n}{y_d}\$ given as integer fractions, find a value of \$x = \frac{x_n}{x_d}\$ between \$a\$ and \$b\$ (exclusive) such that \$f(x) = y\$ (where \$f\$ is the Conway base 13 function). There are infinitely many values of \$x\$ that satisfy the condition for any input; just output one of them.

You can assume \$a < b\$, \$a_d, b_d, y_d > 0\$, \$y \ne 0\$, and the fractions are given in the reduced form. Negative input numbers are represented using negative numerators. You don't need to reduce the output fraction.

Standard code-golf rules apply. The shortest code in bytes wins.

Examples

a = 0/1, b = 1/1, y = 1/3

Decimal representation of \$y\$ is \$0.\overline{3}\$ (where the overline is the notation for repeating decimal). To get this value, the minimal base-13 suffix of \$x\$ is \$+.\overline{3}\$ or \$AC\overline{3}\$. An example of such an \$x\$ would be \$0.AC\overline{3}_{13} = 569/676\$. Proof by Wolfram|Alpha.

a = 2017/2197, b = 2018/2197, y = -1/5

The minimal base-13 suffix of \$x\$ is \$-.2 = BC2_{13}\$. But the value of a is exactly \$0.BC2_{13}\$, so we can't use that. And the value of b is \$0.BC3_{13}\$, so we're forced to begin with \$0.BC2\$. One possible value of \$x\$ is \$0.BC2BC2_{13} = 4433366 \; / \; 4826809\$.

a = 123/10 = c.3b913b91..., b = 27011/2196 = c.3b93b9..., y = 987/1

One possible answer is \$x = c.3b92a987c_{13} = 130435909031 \; / \; 10604499373\$.

a = -3/2, b = -4/3, y = -1/7

One possible answer is \$x = -1.5bc\overline{142857}_{13} = -28108919 \; / \; 19316024\$.

Answer 1

Python 2, 254 237 219 216 207 bytes

-3 bytes thanks to @KevinCruijssen !

Can save 1 more byte by replacing X=e**(A+B) with X=e**A**B, but the result will be humongous, and the time taken to run will be very long.

e=13
a,A,b,B,y,Y=input()
X=e**(A+B)
x=a*X/A+2
r=abs(y)
s="AB"[y<0]+`r/Y`+"C"
R=[]
exec"R=[r]+R;r=r%Y*10;s+=`r/Y`;"*-~Y
n=~R.index(r)
T=e**-n-1
S=e**len(s)*T
print(int(s,e)*T+int(s[n:],e))*((x>0)*2-1)+x*S,X*S

Try it online! or Check all test cases!

A program that takes in 6 integers from STDIN, and prints out the numerator and denominator of the result.

Big idea

• First, find a number \$c\$ such that \$a < c < b\$ and \$c\$ has finite base-13 representation. Note that \$c\$ should be "sufficiently far away" from \$a\$ and \$b\$. This will be the prefix of \$x\$.
  For example: \$a = 1.1..._{13}, b = 1.3..._{13}\$ then \$c = 1.2_{13}\$. We say that \$c\$ is sufficiently far away from \$a\$ and \$b\$, since we can add any suffix to \$c\$ and it is guaranteed to stay in the range \$(a,b)\$.

• Then find the suffix of \$x\$ by finding the base-10 representation of \$y\$, then replacing +-. with ABC. E.g with \$y = 1/3\$, the suffix is \$+0.(3)=A0C(3)\$

• Join the prefix and suffix together. E.g \$x = 1.2A0C(3)\$.

Details

Finding the prefix:

The prefix has the form \$x/X\$, where \$X\$ is a power of 13.

Consider the integers \$\Bigl \lfloor \frac{aX}{A} \Big \rfloor \$ and \$\Bigl \lfloor \frac{bX}{B} \Big \rfloor \$ (where \$X = 13^i\$), which are the truncations of \$a/A\$ and \$b/B\$ to a certain base-13 precision. If there is an integer \$x\$ between those 2 numbers such that \$x\$ is at least 2 away from both numbers, then \$x/X\$ can be the prefix. This is because no matter what suffix is added, the value of \$x/X\$ won't change by more than \$1/X\$.

\$X=13^{A+B}\$ is guaranteed to be large enough to see a large gap between the truncation of \$a/A\$ and \$b/B\$.

This is the part that finds the prefix:

X=e**(A+B)
x=a*X/A+2

Finding the suffix:

First, the long division \$y/Y\$ is performed to find the decimal representation (with repeated digit). r is the current remainder, and R keeps track of the seen remainder after each digit division, in order to detect repeating decimals. \$y/Y\$ is calculated until \$Y+1\$ digits after the decimal point, which is sufficient to detect repeating groups of digits.

r=abs(y)
s="AB"[y<0]+`r/Y`+"C"
R=[]
exec"R=[r]+R;r=r%Y*10;s+=`r/Y`;"*-~Y

The suffix has the form \$stttt... = s(t)\$, where \$s\$ is the result of truncated \$y/Y\$ above, and \$t\$ is the repeating decimals found in \$s\$.

n=~R.index(r)
t = s[n:]

Thus, our result should have the form \$\frac{x + 0.sttt..._{13}}{X}\$ (or \$\frac{x - 0.sttt..._{13}}{X}\$ if \$x\$ is negative)

To convert 0.s(t) in base 13 to fraction, the following formula is used: $$ 0.s(t) = 0.sttt... = \frac{s.(t)}{13^i} $$ $$ s.(t) = s.ttt... = s + \frac{t}{13^j-1} $$ where \$i, j\$ are the number of digits in \$s, t\$.

Answer 2

Wolfram Language (Mathematica), 156 bytes

a=13;b=Floor;c=RealDigits@#~FromDigits~a&;(d=b[+##2/2,e=a^b@Log[a,#3-#2]/a])+If[d<0,-e,e]/a(If[#<0,11,10]+(c[f=b[g=Abs@#]]a+12+c[g-f])/a^IntegerLength@f/a)&

Try it online! Pure function. Takes the rational numbers \$y\$, \$a\$, and \$b\$ (in that order) as input and returns the rational number \$x\$ as output. The function directly uses rational arithmetic; I wrote another algorithm which manipulates the individual digits, but it took 192 bytes. I'm pretty sure that another few bytes can be squeezed out of this one, though, since the negative-number handling is somewhat sloppy. Also, here's an ungolfed version to clarify the logic:

Block[{y = #, a = #2, b = #3, conv = FromDigits[RealDigits[#], 13] &, 
   pref, prefexp, ipart, sign},
  prefexp = 13^Floor[Log[13, b - a]]/13;
  pref = Floor[(a + b)/2, prefexp];
  ipart = Floor[Abs[y]];
  pref + If[pref < 0, -1, 1] prefexp/
     13 (If[y < 0, 11, 10] + 
      13^-(IntegerLength[ipart] + 1) (13 conv[ipart] + 12 + 
         conv[Abs[y] - ipart]))] &