[Question]
  [
Here is [Minkowski's question mark function](https://en.wikipedia.org/wiki/Minkowski%27s_question-mark_function):
[![](https://upload.wikimedia.org/wikipedia/commons/thumb/1/1b/Minkowski_question_mark.svg/960px-Minkowski_question_mark.svg.png)](https://en.wikipedia.org/wiki/File:Minkowski_question_mark.svg)
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](https://en.wikipedia.org/wiki/Continued_fraction#Finite_continued_fractions) 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 [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'"); 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
```
  
[Answer]
# [Python](https://www.python.org), 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!](https://ato.pxeger.com/run?1=RY9LasMwFEXnXoUIFOTmqfrZkRySjDLOCgrFxXEqcCQTu4WupZNAafeUdXQD1a90ILj33aP3-fge3-cXZ6-f_fbx63Xuib49De35uWuRhW59wh2xdx2Ex8FS2gEri9P2H4EJDrBfd6i1HfJ4RMkE-LDZBL5cTrBfRuUu2KNlHjP07oIGY4_IWOTGo8WsXBcIGXBoG4OHaRzMjBdktyh9cG_AB-d2xMbOYP5SuihDGj4d39oBu-DGi2ewgR7fmxJcnnm9_TDKEdkhBogVPGmetMiaFyQbEp1IlEiUzJTwWmetPFMHLQHJQifNo6k1FSpaJn2hKSSjKvaQTeO7-5ZVRXUTKrqOBOGKqviHqJXyjIylpkkrhTZcFLKuKedpG7GqdFV5VPitVozlG6P0W6fbfwE)
Rather verbose implementation. Essentially calculates the cf (by Euclidean algo) and converts the terms on the fly.
[Answer]
# 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!](https://tio.run/##VZDLDoIwEEX3fsXExKTVNrQ8BInwI4QFxhgNyqNx0Qnh23F8INDVuXfuzLRt8HmtKy9qzDC0yb14nM4FWIGiTFSMaeJubaqK6gwtI1daUe40rw2zQKZk0joOHo/MxElLYoMCOc90zqXJVC4@KTBk7Eo@XGpDowHhVkG2AjpMCdBcfFkv2R1ZzoW7DHkzjmaZYORoxgEJNxyVR7vDqd/3acJh2hlSNVzIw7/qBQFdQ0/Ne6V@L8njj9WYW/Vkl3Vne6fDHmQK3fsHAXm/5qvhBQ "Python 3.8 (pre-release) – 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\*}
[Answer]
# [Haskell](https://www.haskell.org/), 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!](https://tio.run/##Jc3PaoQwEIDxu08xhxWStmY3QmnZdm59gl5FIeqkDps/EkfYQ9/dLvT4/S7f4rYbhXAcHNdcBL6cOPPthHM1QcFAAh59yLlA@ZixNL62wAnYw4x4AVkodb6nsBH466TsedZVVO46anS1bdqnbY@daqwe@NwOj1DibgQMo/7lz6azxgRKP7LA2PfVCndUaY9UnDyW95c9CQelZko5cvpHRG1UO2it7LO@6CM6TrgWTnJaTTTT6fW9bt@OPw "Haskell – Try It Online")
[Answer]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), 77 or 124 bytes
```
(s=Sign@#;{s Numerator@#,Log[2,Denominator@#]}&@MinkowskiQuestionMark@Abs@#)&
```
[Try it online!](https://tio.run/##y00syUjNTSzJTE78n2b7X6PYNjgzPc9B2bq6WMGvNDe1KLEkv8hBWccnPz3aSMclNS8/NzMPIhZbq@bgm5mXnV9enJ0ZWJpaXJKZn@ebWJTt4JhU7KCsqfY/oCgzr8QhLVrX0Fzf3DyWC8Y3NjXVNzQ0jv0PAA "Wolfram Language (Mathematica) – 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!](https://tio.run/##NYlBC8IgGEDv/YrBYCxyDDfGDiIYjU4RUUcxMHPLgwr67TT2220QnR7vPSvho60Eo2QaaSojfZjJsZwoevIOjJv1@xykAuMdO77idpaYXWergwQfWI6yi594gwbtvDXuF8VasDJQxTkWggCtMBk83wh189QkHGgDaNHoriMwtQoS9vsi3YJxwEZe4b7ue7H7e9t1NcatSF8 "Wolfram Language (Mathematica) [Dash] Try It Online")
[Answer]
# [julia](https://julialang.org/), 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!](https://ato.pxeger.com/run?1=bZE9DsIwDIXFyikyJsRtk_7QguQysaVjJ8SAhKiKWmgKbNyEpQuHgtMQgViSrp-f_fzsx_N4a-rdMDxv14OXvc4t7UDhRoDcQokbCWILGtvzXpqCZNBj52m4oIACg4AqXvq-z6BCnWMBDfa8YqgRC7IitIELI0vSUgGKV7MSSq68aqZAQ2hqXLKf7XuyNpogkIzcc9L19enanKYtlaMotJA3wsLRzshFmduYWChzUWJYmFowMglSxyKOjcnCWTk1WnvAly5sbZQkJox0Bs-FsE_2u-b_mR8)
[Answer]
# JavaScript (ES6), 88 bytes
Expects `(p)(q)` for \$x=p/q\$. Returns `[a,b]`.
This is heavily based on [loopy walt's answer](https://codegolf.stackexchange.com/a/260818/58563).
```
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!](https://tio.run/##bdLdboMgFAfw@z2FN00ghcmHiDae9kGWXWhpzZZGcS672ru7w9KmQeEO8sv/HA58tj/tfP768N98GN1lucLi4dgDmdgMviEdCHryOfHAPT1I1oLPJ@bA72BiA0x4Ckd36km3hyF3v4Lxmc17aJsGt2zYOebo4a1l3ftyHod5vF1eb2NPrkRQIinNwsrzTLBMvMRARkAmgYqAXAH@FAh4QqiohkrW0FENtQVVBOy2hHkCzTK9AlUEZEIYJMr@myCERlOvjMZ5Wv0wuq7xspvLFAV2WweEpjKJGC4t5tg74ba0mKNTqH7kcBn6kevBaGNwuDK0FJpWZVEVBaapzQRLIe6fIcCww3dY/gA "JavaScript (Node.js) – Try It Online")
[Answer]
# [PARI/GP](https://pari.math.u-bordeaux.fr), 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!](https://ato.pxeger.com/run?1=LY5NCsIwEIWvMuom0YT81JqIxo3HqFWKUAn4E5IK9QbewU1BxDN5Gxvj5nvzmJk383i7ytvdwXXPGszr2tRUf9YtXQXDFwVqN2Iix-F6QtZIMvJmfzk3ta_2qMUEUYG3lsltmBhf2BLj5TJQMxgEEsp_1L1y7nhDLdAVOG_PTV8OoxlC3WdgAgVngoBIkATojzL5LEJHmxPQEblmUhHIOFOxOZ0yPY9LiimVdN77LM-ZEHFgxnl_oMTpn65L-gU)
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 28 [bytes](https://github.com/DennisMitchell/jelly/wiki/Code-page)
```
Ḋ;%/ƊẠÐ¿Ṗ:/€Ḣ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!](https://tio.run/##y0rNyan8///hji5rVf1jXQ93LTg84dD@hzunWek/alrzcMeicO2HO9cAmX6HJ6S6Hes6tsnnUcPMhzvXPtzRcmzT/6xHDXP1dQ63H530cOcMFSBvjoKunQJQUDPy///oaAMdBcNYHYVoQwRtBKJ1YQwjhIQxlLaAipuCaAsobQpkGJmDWMZAM80hak1MgKotIeaZA0XN4UxLsKixqSnQeEOIYjMDA7BrYgE "Jelly – 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]
```
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), 63 bytes
```
ＮθＮη≔÷θηζＷ﹪θη«≔ηθ≔ιη⊞υ⁻÷θη¬υ»Ｆ﹪Ｌυ²⊞⊞Ｏυ⊖⊟υ¹Ｉ⟦⁺×ζＸ²Συ⍘⭆υ×Ｉ﹪κ²ι²Συ
```
[Try it online!](https://tio.run/##ZY9LT8MwEITP5FfscS2ZQ1r1xAnopRIpkcoNcTDJNrZI7NSPVirit4fNA4TExfZodr4dV1r5yql2GHa2T3GfunfyeBJ32V@tWd@HYBqLOxu35mxqwpMELSRc2bto0xJg4erUutkQ8JndLBktYST@SDP6LMsUNCYJhbEp/AfvXcQkBE9@ZUfnf/FPZJvIQR5Z8ZqJMh7PPXkVnR@RW6o8dWQj1Vi6fuJIyJlVemMjPqoQ8bVsee@L6SjgVULpLvzVlYRD6pbAgwp0iJxocL4K1Y/4OTNBllIfUxkJRojlNVPeuP8wrDcbyPP1cHtuvwE "Charcoal – 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.
[Answer]
# [Factor](https://factorcode.org/) + `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!](https://tio.run/##TZJPb5wwEMXvfIpppL2k64ANLNBKyTHKJZcqp/yRXDC7qGA7tklWqfLZNwMYbzhY8u/Ne@OxaXntlDk9/Lm7v/0FrTIDd66Te7DidRSyFhb@CSNFDygc5uWqVhJLRtGQ1qC9U9IugnXcddZ1td@/iSkcE5T9GJeEq3aU3rKqv6PofwT4JTGFH0CuIdlCMhO6EnomLBA6ExIQCYytPnb2pcHHPCkDKbwrX0i6hXQm5UpoQHkZs8LDJEVczThN4sJ3SKsKz@HbZllcVgsv81BNaBEXPoUUuwLr0yBU1TrOFE@X06Z5HlO6zsB2WZllaGN@ll2ShNubN9Pcn9HpEZpRg91LsO9cA/9rgS73DovUc@vA4LOpG3j2TIqjI1xro47I3g9dLyJ8tb7TQIxyUI8DseMAb1Ls0ULoCzCYBAo/4QUu0TRwTTrZiCNMhZfIr9d/BXq1Z/Dsj3bGF5sm3jTTABegTSddiznaCK2swC4ob2HTPMlvaq2GWRW8Ppy@AA "Factor – 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
```
[Answer]
# [Scala 3](https://www.scala-lang.org/), ~~238~~ 186 bytes
Modified from [@loopy walt's answer](https://codegolf.stackexchange.com/a/260818/110802).
---
\$ \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!](https://ato.pxeger.com/run?1=PVDNjtowEL7nKVzKSnZxHJsAoQGjVuJSiXLYpadVVaU4idwmdmR7V1pRnqSXvew-RN-EJ-hr1DFQySPNjL-fmfn9avdFU6TPp7ey7bRxINREanKnH8y-jPT3H-Xegc-FVIeXB1fF89Mf99SVYMc_KbcQZQUqqPIdFvkO8cOHQintCie1Iq6QjSn3oMfUVwy2PrY-1h6fwx32LFlB8YZTVEOB1Y3AscVwu1yqRKCRxetRn5SNLeEWr9HisWiA4dADRwLdiIVnxQYbzLDXUe_Eiv7yf9zreR7oecAnMcMUHS8b_A0ztX4nWJja5h-NKZ7u75yRqv6K8i9KOn6IAOitNvx8CWKdkIrUpdtIVVqIiNMbaZ2HVdrAZhlvUM8JpCAIJdaIN8R2jXRwEK8G6PrfcnltJwNE2qKD34i3b72oP-t_3C2vYAspwi1kKHQ7P6NrFLSD4aEl7c_z0EHmiIe3eKiDyzHy77Lu8-meJgzEK0AxoNF0noyzvmI0TTF4H8UsS7LQibNZhgFLo3Q6TRhLA2o8m8wnE98fjyM2o_SiFVKvd_b4Bw)
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!](https://ato.pxeger.com/run?1=dVPNjtMwED5wy1MMVVjZIv9pm2RpV6zUC9JuLytOCCG3SYshdbqJu9Kq7ZNw6QXeCV6DF2D8025ZhFTV48_ffPONPfn2o5uzmqWHw_eNXPj5rxc7vlo3rQSNB7wJ7ppNO6-cZvalmku4ZVzA1gEoqwUsiLiEd0J6UOqVwlifAbxlQjSSSd6IQDJet9Vc4ypr-SzLg86uU7tOjNolEL39SxkgDGHdciFrQbqeK8Atwe3AnYI76VHL4QsgJbwcQ0SxXumBgFeAi995QKYwGgEREEJJKbwGxCa4nJCq7ipkIUrfaL39yfv6UX5uxG1TEma9zo5e8R9NEsKw0kzJ4h9GzrPcCX_4X-72zDzKXEEEFxcwUwGF3Q4QGx0xDNApQ8czm6Vdq1RtAMa6938IGgAfYtuYXh5YDfdo4MmhwMexzavD9nSoWj87xLtFsdZTv9iDew-LOlZX9bzCcSGsXeILX7cte_xwJ_Hplh-x5_eCPzWtitRcVB0iZuCCTpZcBMtK3iic0EA2N7yTxvGiaYGoBBj5JpGerk9p6WKEe9CoyVGEoFvXXJKef3UaEkUUm5WqyY_HYY8GK7YmnwI0usKa6oHO-G3VbWrlG2cfU0lEPa1BYnqknQ3nVh0Fq6-ma62-98A1Ihg01ste39neMR-h_RYPP39HYQw-Pj9eqxObODZxYuPY8e3G17vEsBLDSi0rwTi3cYacgYpTD1InN3GsN4M8TDK9jVIECieNwkxrpEWB6ijZ74d5oZB8oBl-nIWZzvGzYYacVENFYSwpmThx0sEgjGPjJhn2834fqQm6GkaR7VGH6Nr0_gc)
```
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")
    }
  }
}
```
[Answer]
# 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!](https://tio.run/##PZFNspswEITX0SmmvEGDpSDxY8AOWdh7LkCoFBg5oR6WKcCV5PSOJPDbdbc@tWZK47/l90NH2Ti9XpdiaO5t14Bm3bHSQdDV@wvtmOadT61F7G/QgRpmVdWkUze40ZJ1eNRF0860xNO1uFBzG08fRUWvlaiZwHpf0fHxh3LJ@r1ENj/v5kgejamRS7w9Juih1zA1@peikg1K0ytifWqLe/OXnsESP9nZMh94mtTynDStJOOyrspvovZtZej7tOVn9EvHl2@etfj6fGK324lAAv8OgoEgctVy1eGmJeGb4c6FKxWuVLRRodHZplPDJFZHDCKSrVo6k2RBmDorIhPkJBJB6jqiPDftpjKOgyy3SZY4gss0SN0dnh5Sw0QuyvN1JFsjQxIlSSDlOk14iLM4NmhopjoIse3opJnabP11Hod@od4P7eGRfGkYtFBA/44t7aHJ51lNi/lW/96MtNcLg@bNBB4iQlHA8hwHRT@B9g0wsAQh42Ry6i1qXmYYbWXn4es/)
[Answer]
# [Pyth](https://github.com/isaacg1/pyth), 46 bytes
```
M?tH+/GHgH%GH]GJtstKgEE+*hK^2JaF_m^2-Jtsd._tKJ
```
[Try it online!](https://tio.run/##K6gsyfj/39e@xENb390j3UPV3SPW3aukuMQ73dVVWyvDO87IK9EtPjfOSBcomqIXX@Lt9f@/qQWXkTkA "Pyth – 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)
```
]