Iterate your way to a fraction

Question

I recently learned from a comment by MathOverflow user pregunton that it is possible to enumerate all rational numbers using iterated maps of the form \$f(x) = x+1\$ or \$\displaystyle g(x) = -\frac 1x\$, starting from \$0\$.

For example, $$0 \overset{f}{\mapsto} 1 \overset{f}{\mapsto} 2 \overset{g}{\mapsto} -\frac12 \overset{f}{\mapsto} \frac12 \overset{f}{\mapsto} \frac 32 \overset{g}{\mapsto} -\frac23 \overset{f}{\mapsto} \frac 13.$$

That is, $$ \frac13 = f(g(f(f(g(f(f(0))))))) = f\circ g\circ f\circ f\circ g\circ f\circ f(0).$$ This is an example of a shortest path of iterated maps to reach \$\frac13\$; every path from \$0\$ to \$\frac13\$ requires at least seven steps.

---

Challenge

Your challenge is to take two integers, n and d, and return a string of f's and g's that represents a shortest path of iterated maps from \$0\$ to \$\displaystyle\frac nd\$.

This is a code-golf, so shortest code wins.

Example

  n |  d | sequence of maps
----+----+-----------------
  1 |  3 | fgffgff
  3 |  1 | fff
  8 |  2 | ffff
  1 | -3 | gfff
  2 |  3 | fgfff
  0 |  9 | [empty string]
  1 |  1 | f
  2 |  1 | ff
  1 | -2 | gff
 -1 | -2 | fgff
  6 |  4 | ffgff
 -2 |  3 | gffgff
  8 |  9 | fgfffffffff

Answer 1

Python, 54 bytes (-1 @Jonathan Allan, -1 me)

f=lambda n,d:n and'gf'[p:=n*d>0]+f(p*n-d,[n,d][p])or''

Attempt This Online!

Old Python, 56 bytes (@tsh)

f=lambda n,d:n*d<0and'g'+f(-d,n)or n and'f'+f(n-d,d)or''

Attempt This Online!

Old Python, 57 bytes

f=lambda n,d:n//d<0and'g'+f(-d,n)or n and'f'+f(n-d,d)or''

Attempt This Online!

Not 100% sure this is correct. Works on all test cases, though. It's kind of a Euclidean algorithm with overshoot.

Towards a proof of correctness

The group of transformations generated by f and g is called the Modular group. There is quite a bit of interesting theory but the one thing that seems relevant to us is that gg and gfgfgf are a "complete set of relations" and that the modular group is the "free product of the cyclic groups generated by g and h:=gf". This means that any element of the modular group can be uniquely written as g's alternating with either h or hh. Transforming back to f's and g's gh becomes f and ghh becomes fgf, so except for the left end which can be h or hh, i.e. gf or gfgf all valid representations are exactly the words with g's separated by at least 2 f's. And we can check that the algorithm indeed produces such words.

So, are we done? I'm not sure. What's missing is that I don't know how exactly the rationals and the modular group are related. It may well be that two distinct group elements move 0 to the same rational which would send us back quite a bit if not all the way to square 1.

Answer 2

JavaScript (Node.js), 53 bytes

f=(n,d,p='',...e)=>n?f(...e,-d,n,p+'g',n-d,d,p+'f'):p

Try it online!

Stackoverflow on last testcase.

Answer 3

Ruby, 45 bytes

f=->n,d{n==0?"":n/d<0??g+f[-d,n]:?f+f[n-d,d]}

Try it online!

Use as f[n,d]

basically a port of loopy walt's python answer

Answer 4

Haskell,  44  42 bytes

0#d=[]
n#d|n*d<0='g':(-d)#n|m<-n-d='f':m#d

adaption of the python solution, using guards. Ungolfing barely changes it, just adding whitespace:

0#d          = []
n#d | n*d<0  = 'g':(-d)#n
    | m<-n-d = 'f':m#d

Try it online!

-2 Bytes thanks to xnor, TIO link also thanks to xnor

Answer 5

Nibbles, 15.5 bytes

`.~$@?*@$~-@__*~@$$=`$*@$"fg "

That's 31 nibbles at half a byte each in the binary form.

This is based on the python answer although I found an iterative solution shorter. It felt kind of awkward still though.

`. ~$@      Iterate while unique, starting with the tuple $ @ (which is the input arguments)
  ? *@$     if product of values > 0
    ~-@_ _  then ($-@, @) since true clause has condition's value put in $ (unused here though)
    *~@ $   else (-1*@, $)
  $         the second value of the tuple from the if (tuple's aren't returned as first class things but splat into the context and must be reconstructed, normally very concise but here a bit awkward

The above code computes the sequences of numerators and denominators, now we just need to convert it to f and g. Note that it has a few extra terms since it didn't stop being unique until after the solution was found. Luckily n*d is 0 in that case so we can use that to map it to a space. The below code is implicitly done via a map.

= `$ *@$   subscript using signum of n*d
  "fg "    into this list (0 is the last since 1 based).

Call it like nibbles filename.nbl 1 3 (Nibbles isn't on TIO yet).

Note that this will also output 4 spaces after the answer, you could remove it by doing a filter, this would add two nibbles or 1 byte.

Answer 6

JavaScript (ES6), 90 bytes

A naive algorithm trying all sequences of length \$k\$, starting with \$k=0\$ and incrementing \$k\$ until a solution is found.

Expects (n)(d). Returns an empty array instead of an empty string.

n=>F=(d,k)=>(g=(k,o=[],N=n,D=d)=>k--?g(k,o+'f',N-D,D)||g(k,o+'g',-D,N):!N&&o)(k)||F(d,-~k)

Try it online!

---

JavaScript (ES6), 44 bytes

Assuming loopy walt's method is valid (and it most probably is).

Expects (n,d).

f=(n,d)=>n*d<0?'g'+f(-d,n):n?'f'+f(n-d,d):''

Try it online!

Answer 7

C (gcc), 104 bytes

n=1;d=3;o;main(){if(d<0){n=-n;d=-d;}while(n){if(n<0){o=d;d=-n;n=o;printf("g");}else{n-=d;printf("f");}}}

Try it online!

Answer 8

Pari/GP, 52 bytes

t(n,d)=if(n/d>0,Str(f,t(n-d,d)),n,Str(g,t(-d,n)),"")

Try it online!

A port of @loopy walt's Python answer.

Shorter (46 bytes) if we can take a rational number as input:

t(r)=if(r>0,Str(f,t(r-1)),r,Str(g,t(-1/r)),"")

Try it online!

Answer 9

05AB1E, 33 bytes

∞ε„fg©sã}˜õš.Δ®'>„z(‚‡0s.VI`/α₄z‹

Naive brute-force approach. Outputs in reversed order. If this is not allowed, a trailing }R will have to be added and it would be 35 bytes instead, making the approach below 1 byte shorter.

Try it online or verify all test cases.

A port of @loopyWalt's second Python answer is 34 bytes, but it outputs in the correct order:

"ÐPdi¬ĀiÆ0ǝ®.V'fìëõë`s(‚®.V'gì"©.V

Try it online or verify all test cases.

Explanation:

∞                     # Push an infinite positive list: [1,2,3,...]
 ε                    # Map over each integer:
  „fg                 #  Push string "fg"
     ©                #  Store it in variable `®` (without popping)
      s               #  Swap so the current integer is at the top
       ã              #  Get the cartesian product
  }˜                  # After the map: flatten the list of lists
    õš                # Prepend an empty string
.Δ                    # Then find the first value which is truthy for:
  ®                   #  Push "fg" from variable `®`
   '>                '#  Push string ">"
     „z(              #  Push string "z("
        ‚             #  Pair them together: [">","z("]
         ‡            #  Transliterate all "f" to ">" and "g" to "z("
          0           #  Push 0
           s          #  Swap so the string is at the top again
            .V        #  Evaluate as 05AB1E code:
                      #   `>`: Increase the value by 1
                      #   `z(`: `z` will push 1/value, `(` will negate it
              I       #  Push the input-pair: [n,d]
               `      #  Pop and push `n` and `d` separated to the stack
                /     #  Divide `n` by `d`
                 α    #  Get the absolute difference between the two values
                    ‹ #  Check if this is smaller than
                  ₄z  #  1/1000
                      #  (`α₄z‹` can't be `Q` due to floating point inaccuracies)
                      # (after which the result is output implicitly)

"..."                 # Push the recursive string defined below
     ©                # Store this string in variable `®` (without popping)
      .V              # Evaluate it as 05AB1E code

Ð                     # Triplicate the current pair [n,d]
                      # (which will be the implicit input in the first call)
   i                  # If
 P                    # n*d (product of the pair)
  d                   # is >= 0:
      i               #  If
    ¬                 #  n (without popping the pair)
     Ā                #  is not 0:
       Æ              #   Push n-d (reduce by subtracting)
         ǝ            #   And insert this n-d back into the pair
        0             #   at index 0: [n-d,d]
          ®.V         #   Then do a recursive call
             'fì     '#   And prepend "f" to that
      ë               #  Else:
       õ              #   Push an empty string ""
   ë                  # Else:
    `                 #  Pop and push `n` and `d` separated to the stack
     s                #  Swap the two values on the stack
      (               #  Negate `n`
       ‚              #  Pair them back together: [d,-n]
        ®.V           #  Then do a recursive call
           'gì       '#  And prepend "g" to that
                      # (after which the result is output implicitly)

Answer 10

Charcoal, 65 62 52 48 bytes

ＮθＮη¿θＷφ«≔θφ≔ηζ⊞υωＰ←⍘ＬυgfＦ⮌↨Ｌυ²¿κ≧⁻ζφ«≔ζε≔φζ≔±εφ

Try it online! Link is to verbose version of code. Feels like it should be a bit shorter. Explanation:

ＮθＮη

Input n and d.

¿θＷφ«

Do nothing if n=0, otherwise loop until a reverse path to zero is found. (This loop uses the variable f which is predefined to 1000, thus ensuring the loop happens at least once; it saves a byte over saving n and using while (n).)

≔θφ≔ηζ

Make new copies of n and d.

⊞υω

Increment the length of the predefined empty list.

Ｐ←⍘Ｌυgf

Replace the canvas with the length interpreted as a base 2 string of fs and gs (with f=1 and g=0). The string is reversed so that the last letter is always f.

Ｆ⮌↨Ｌυ²

Loop over the base 2 digits in reverse.

¿κ≧⁻ζφ

For 1s undo the f step.

«≔ζε≔φζ≔±εφ

Otherwise undo the g step.

Switching to undoing steps saved me 10 bytes. It's possible that deciding whether to undo an f or g step based on the sign of the current fraction suffices to produce a minimal result. If that's true then the solution would only be 31 bytes:

ＮθＮηＷθ¿›×θη⁰«f≧⁻ηθ»«g≔ηζ≔θη≔±ζθ

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

ＮθＮη

Input n and d.

Ｗθ

Repeat until n=0.

¿›×θη⁰«

If n/d is positive, then...

f≧⁻ηθ

... output an f and subtract d from n.

»«

Otherwise...

g≔ηζ≔θη≔±ζθ

... output a g, switch n and d, and negate n.

Answer 11

Stax, 18 16 bytes

ÿ☺╨K▼▓¡s'↓♫[╣♥╬╩

Run and debug it

Pretty convenient with the rational type.

Answer 12

Python3, 192 bytes:

lambda n,d:f([(0,n/float(d),'')])
f=lambda d:r[0][-1]if(r:=[i for i in d if round(i[0],4)==round(i[1],4)])else f([j for a,b,c in d for j in[(a+1,b,'f'+c)]+([(-1/(1.0*a),b,'g'+c)]if a else[])])

Try it online!

Answer 13

APL (Dyalog Extended), 48 bytes

Basic bruteforce approach, expects index origin 0.

f←-⍨\⍢⌽
g←-@0⌽
⌽o⊣1+⍣{0=⊃⍎⍕t,⍨↓⍪o∘←'gf'[⊤⍵]}⍱t←⎕

Try it online!

Answer 14

C (clang), ^{59 \$\cdots\$ 53} 52 bytes

z;f(n,d){z=n*d>=0;n&&f(z*n-d,z?d:n,putchar(103-z));}

Try it online!

Port of loopy walt's Python answer.
Saved 5 6 bytes thanks to ceilingcat!!!
Saved a byte thanks to dingledooper!!!

Inputs integers \$n\$ and \$d\$.
Outputs string of f's and g's that represents a shortest path of iterated maps from \$0\$ to \$\frac{n}{d}\$.