21
\$\begingroup\$

Here is Minkowski's question mark function:

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.

Task

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
Improve this question
\$\endgroup\$
1
  • 2
    \$\begingroup\$ 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! \$\endgroup\$
    – lesobrod
    May 9 at 20:45

13 Answers 13

Reset to default
6
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
5
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Haskell, 186 bytes

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!

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Does it work with negative numbers, as in some test cases? \$\endgroup\$
    – lesobrod
    May 9 at 20:36
  • 2
    \$\begingroup\$ It does. That is what i used floor for. \$\endgroup\$
    – Roman Czyborra
    May 9 at 20:43
3
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ 63 \$\endgroup\$
    – att
    May 18 at 0:18
3
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ I have no idea what happens in this post but here is a 4 byte improvement \$\endgroup\$
    – MarcMush
    May 18 at 19:19
2
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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
                      Ʋ      - last four links as a monad - f(Parts=that):
            Ḣ                -   head -> remove and yield the integer part
             W               -   wrap (the integer part) in a list
                     Ɗ       -   last three links as a monad - f(remaining parts):
               Ṭ€            -     untruth each (e.g. 4 -> [0,0,0,1])
                 NÐe         -     negate those at even indices (the 2nd, 4th, ...)
                    F        -     flatten
              +              -   ([integer part]) add (that) (vectorises) - adds the integer
                                     part to the first one. If none just gets [integer part]
                           Ʋ - last four links as a monad - f(A=that):
                       L     -   length (A)
                        ’    -   decrement -> the denominator's exponent
                          Ḅ  -   convert (A) from base two -> the numerator
                         ṭ   -   tack -> [numerator, denominator's exponent]
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Scala 3, 238 186 bytes

Modified from @loopy walt's answer.

\$ \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")
    }
  }
}
Improve this answer
\$\endgroup\$
0
0
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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
        +                          # add to this
            ^2J                    # 2 ^ j
         *hK                       # times K[0]
                              J    # print(J)
Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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