Minkowski's ?(x) for rational x

It is a strictly increasing and continuous function from the reals to themselves that, among other unusual properties, maps rational numbers to dyadic rationals (those with a power-of-two denominator). Specifically, suppose the continued fraction representation of a rational number $$\x\$$ is $$\[a_0;a_1,\dots,a_n]\$$, then $$?(x)=a_0+\sum_{i=1}^n\frac{\left(-1\right)^{i+1}}{2^{a_1+\cdots+a_i-1}}$$ For example, 58/27 has continued fraction representation $$\[2;6,1,3]\$$, so $$?(58/27)=2+\frac1{2^{6-1}}-\frac1{2^{6+1-1}}+\frac1{2^{6+1+3-1}}=2+2^{-5}-2^{-6}+2^{-9}=\frac{1033}{2^9}$$ so the pair (1033, 9) should be returned in this case. Similarly for 30/73 with expansion $$\[0;2,2,3,4]\$$: $$?(30/73)=2^{-1}-2^{-3}+2^{-6}-2^{-10}=\frac{399}{2^{10}}$$ and (399, 10) should be returned here. Note that it does not matter whether the form ending in 1 is used or not.

Given a rational number $$\x\$$, determine $$\?(x)=a/2^b\$$ as a rational number in lowest terms (so that $$\b\$$ is a non-negative integer, as small as possible, and $$\a\$$ is odd unless $$\b=0\$$) and output $$\a\$$ and $$\b\$$ (not $$\2^b\$$). $$\x\$$ may be taken in any reasonable format, and if you take a pair of integers you may assume the corresponding fraction is in lowest terms.

This is ; fewest bytes wins.

Test cases

x -> a, b
0/1 -> 0, 0
1/1 -> 1, 0
1/2 -> 1, 1
-1/2 -> -1, 1
2/1 -> 2, 0
1/3 -> 1, 2
1/8 -> 1, 7
2/5 -> 3, 3
8/5 -> 13, 3
58/27 -> 1033, 9
30/73 -> 399, 10
144/89 -> 853, 9
-17/77 -> -767, 13
-17/99 -> -133, 12
355/113 -> 12648447, 22
16000/1 -> 16000, 0

• In fact, all the definitions of ?(x) I’ve seen only deal with positive numbers. Of course I turned on the negative validation, but I think it’s unnecessary! May 9, 2023 at 20:45

Python, 95 bytes

lambda n,d:g(d-n%d,n%d,1,n//d,0)
g=lambda n,d,s,N,D:d and g(d,n%d,-s,(N<<n//d)+s,D+n//d)or(N,D)


Attempt This Online!

Rather verbose implementation. Essentially calculates the cf (by Euclidean algo) and converts the terms on the fly.

Python 3.8, 95 bytes

q=lambda x,y,k=0:y>=2*x>0and q(x,y-x,k+1)or(x and-(-x//y<<(r:=q(-x%y,y))[1])-r[0],x and r[1]+k)


Try it online!

How it works

Uses the recurrence

\begin{align*} ?(0) &= 0, \\ ?(x) &= \frac{?{\left(\frac{x}{1 - x}\right)}}{2} \quad\text{if }0 < x ≤ \frac12, \\ ?(x) &= ⌈x⌉ - {?(⌈x⌉ - x)}. \end{align*}

import Data.Ratio
c r=let f=floor r;d=r-f%1 in if d==0 then[f]else f:c(1/d)
m(a:b)=a%1-2*sum[(-1)^i/2^sum(take i b)|i<-[1..length b]]
p x=(numerator x,until((denominator x==).(2^))(1+)0)


Try it online!

• Does it work with negative numbers, as in some test cases? May 9, 2023 at 20:36
• It does. That is what i used floor for. May 9, 2023 at 20:43

Wolfram Language (Mathematica), 77 or 124 bytes

(s=Sign@#;{s Numerator@#,Log[2,Denominator@#]}&@MinkowskiQuestionMark@Abs@#)&


Try it online!

Or without overkill builtin:

(s=Sign@#;c=ContinuedFraction@Abs@#;{s Numerator@#, Log[2,Denominator@#]}&@(r=c[[1]];t=-1;Do[t=-t/2^e;r+=2t,{e,Rest@c}];r))&


Try it online!

• 63
– att
May 18, 2023 at 0:18

julia, 111 bytes

Expects a single argument of type Rational{Int64}

This approach traverses the Stern-Brocot tree for $$\\mathrm{mod}(p,1)\$$, adding $$\1/2^k\$$ at the $$\k\$$-th recursion whenever we take a right branch in the tree.

The case where $$\p \notin (0, 1]\$$ is handled in the default arguments.

m(p,L=[0,1],U=[1,0],q=mod1(p,1),r=p-q,s=0,M=//(L+U...),g=q>=M,l=r+g)=q==M ? (l,s) : m(0,L+g*U,U+L-g*L,q,2l,s+1)


Attempt This Online!

• I have no idea what happens in this post but here is a 4 byte improvement May 18, 2023 at 19:19

JavaScript (ES6), 88 bytes

Expects (p)(q) for $$\x=p/q\$$. Returns [a,b].

This is heavily based on loopy walt's answer.

p=>g=(q,s=p<(b=0)?p/(p=-p):1,a=p/q,d=p%=q,n=q-p)=>d?g(b+=n/d|0,-s,s+=a<<n/d,n%d,d):[a,b]


Try it online!

PARI/GP, 67 bytes

x->s=0;[(x\1+2*sum(i=2,#r=contfrac(x),(-1)^i/2^s+=r[i]))<<s-=!!s,s]


Attempt This Online!

Jelly, 28 bytes

Ḋ;%/ƊẠÐ¿Ṗ:/€ḢW+Ṭ€NÐeFƊƲL’ṭḄƲ


A monadic Link that accepts a pair of integers, [numerator, denominator], and yields a pair of integers, [numerator, denominator's exponent].

Try it online!

How?

Ḋ;%/ƊẠÐ¿Ṗ:/€ḢW+Ṭ€NÐeFƊƲL’ṭḄƲ - Link: pair of integers = [N, D]
Ð¿                     - collect while...
Ạ                       - ...condition: all truthy - i.e. while no zero present
Ɗ                        - ...do: last three links as a monad - f(current=[n, d]):
Ḋ                            -          dequeue -> [d]
/                         -          reduce ([n, d]) by:
%                          -            modulo -> n%d
;                           -          concatenate -> [d, n%d]
Ṗ                    - pop - remove the final result (with a zero in)
/€                 - reduce each by:
:                   -   integer division -> continued fraction part list
Ḣ                -   head -> remove and yield the integer part
W               -   wrap (the integer part) in a list
Ṭ€            -     untruth each (e.g. 4 -> [0,0,0,1])
NÐe         -     negate those at even indices (the 2nd, 4th, ...)
F        -     flatten
part to the first one. If none just gets [integer part]
L     -   length (A)
’    -   decrement -> the denominator's exponent
Ḅ  -   convert (A) from base two -> the numerator
ṭ   -   tack -> [numerator, denominator's exponent]


Charcoal, 63 bytes

ＮθＮη≔÷θηζＷ﹪θη«≔ηθ≔ιη⊞υ⁻÷θη¬υ»Ｆ﹪Ｌυ²⊞⊞Ｏυ⊖⊟υ¹Ｉ⟦⁺×ζＸ²Συ⍘⭆υ×Ｉ﹪κ²ι²Συ


Try it online! Link is to verbose version of code. Explanation:

ＮθＮη


Input the numerator and denominator.

≔÷θηζ


Calculate the integer part of the fraction.

Ｗ﹪θη«≔ηθ≔ιη⊞υ⁻÷θη¬υ»


Calculate the rest of the continued fraction, except decrement the first value.

Ｆ﹪Ｌυ²⊞⊞Ｏυ⊖⊟υ¹


If the fraction has odd length then decrement the last value and append a 1.

Ｉ⟦⁺×ζＸ²Συ⍘⭆υ×Ｉ﹪κ²ι²Συ


Transform the fraction into run-length-encoded binary and convert from binary to decimal, adding on the original integer part with an appropriate shift, which is also the second output value.

Factor + koszul math.continued-fractions, 156 154 bytes

[ dup sgn swap abs 1vector [ dup last ratio? ] [ dup next-approx ] while
unclip -rot cum-sum vneg [ -1^ 2 rot 1 + ^ * ] map-index sum * + >fraction log2 ]


Try it online!

                      ! -17/99
dup                   ! -17/99 -17/99
sgn                   ! -17/99 -1
swap                  ! -1 -17/99
abs                   ! -1 17/99
1vector               ! -1 V{ 17/99 }
[ dup last ratio? ]   ! -1 V{ 17/99 } [ dup last ratio? ]
[ dup next-approx ]   ! -1 V{ 17/99 } [ dup last ratio? ] [ dup next-approx ]
while                 ! -1 V{ 0 5 1 4 1 2 }
unclip                ! -1 V{ 5 1 4 1 2 } 0
-rot                  ! 0 -1 V{ 5 1 4 1 2 }
cum-sum               ! 0 -1 V{ 5 6 10 11 13 }
vneg                  ! 0 -1 V{ -5 -6 -10 -11 -13 }
[ -1^ 2 rot 1 + ^ * ] ! 0 -1 V{ -5 -6 -10 -11 -13 } [ -1^ 2 rot 1 + ^ * ]
map-index             ! 0 -1 { 1/16 -1/32 1/512 -1/1024 1/4096 }
sum                   ! 0 -1 133/4096
*                     ! 0 -133/4096
+                     ! -133/4096
>fraction             ! -133 4096
log2                  ! -133 12


Scala 3, 238 186 bytes

$$\ \color{black}{\text{In scala, it's weird to mimic % // of python}} \$$

/*
Python's % operator returns a result with the same sign as the divisor, and // rounds towards negative infinity.

In Scala, % and / don't behave the same way. The % operator returns a result with the same sign as the dividend, and / performs truncating division, rounding towards zero.
*/

def pythonMod(a: Int, b: Int): Int = ((a % b) + b) % b

def pythonDiv(a: Int, b: Int): Int = {
if ((a > 0 && b > 0) || (a < 0 && b < 0)) a / b
else if (a % b == 0) a / b
else a / b - 1
}



Golfed version. Attempt this online!

Saved 52 bytes thanks to the comment of @ceilingcat

type T=Int;def f(n:T,d:T)={@annotation.tailrec def g(n:T,d:T,s:T,N:T,D:T):(T,T)=if(d!=0)g(d,n%d,-s,(N<<n/d)+s,D+n/d)else(N,D);val r=(n%d+d)%d;g(d-r,r,1,if(n*d>0|n%d==0)n/d else n/d-1,0)}


Ungolfed version. Attempt this online!

import scala.io.Source
object Main {
def f(n: Int, d: Int) = {
@annotation.tailrec
def g(n: Int, d: Int, s: Int, N: Int, D: Int): (Int, Int) = {
// println(s"$n$d $s$N $D") if (d != 0) g(d, n % d, -s, (N << (n / d)) + s, D + (n / d)) else (N, D); } def pythonMod(a: Int, b: Int): Int = ((a % b) + b) % b def pythonDiv(a: Int, b: Int): Int = { if ((a > 0 && b > 0) || (a < 0 && b < 0)) a / b else if (a % b == 0) a / b else a / b - 1 } val q = pythonDiv(n, d); val r = pythonMod(n, d); g(d - r, r, 1, q, 0) } def main(args: Array[String]): Unit = { val lines = Source.stdin.getLines().toList for (line <- lines) { val Array(i, o) = line.split("->") val nums = i.split("/").map(_.trim.toInt) val result = f(nums(0), nums(1)) println(s"${nums.mkString("/")}, $result,$o")
}
}
}



Python3, 217 bytes:

C=lambda n,d:[n//d]+C(d,n-d*(n//d))if d else[]
def f(N,d):n=abs(N);c=C(n,d);k=[(c[0],0)]+[(pow(-1,i+1),sum(c[1:i+1])-1)for i in range(1,len(c))];b=max(B for _,B in k);return([1,-1][N<0]*sum(2**(b-B)*N for N,B in k),b)


Try it online!

Pyth, 46 bytes

M?tH+/GHgH%GH]GJtstKgEE+*hK^2JaF_m^2-Jtsd._tKJ


Try it online!

Explanation

First we define g(G,H) to find the continued fraction of its input.

M                  # define g(G,H)
?tH               # if (H != 1):
+/GH           #   prepend floor(G/H) to
gH%GH      #   recurse on g(H, G%H)
# else:
]G    #   return [G]


Then we compute the function

    KgEE                           # assign K to g applied to two inputs
Jtst                               # assign J to sum(K[:-1]) - 1
._tK     # all prefixes of K[:-1]
m                # map on lambda d
^2              #   2 to the power of
-J            #   J minus
tsd         #   sum(d) - 1
aF_                 # take the alternating sum