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

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 5

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 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}\$.

Answer 15

Wolfram Language (Mathematica), 139 bytes

(m=1;f=If[#3<m,If[#1!=0,Do[#0[{#1-1,-1/#1}[[k]],Append[#2,k],#3+1],{k,2}],Throw@#2]]&;While[(r=Catch[f[#1/#2,{},1]])==Null&&#1!=0,m+=1];r)&

Try it online!

Reverse recursive approach.
We start with given fraction and recursively apply reverse operations until we reach 0.
Output is array with 1 for \$f\$ and 2 for \$g\$ or Null if n==0.

The code is not optimal (the same results are used several times), but optimization will increase the length of the code.
I'll try golfing it more, sure it's possible.

Ungolfed version self-explained:

Clear[recurse, main];
recurse[x_, arr_, i_, max_] :=
  If[i < max,
   If[x != 0,
    Do[recurse[{x - 1, -1/x}[[k]], Append[arr, k], i + 1, max],
     {k, 2}],
    Throw@arr
    ]];

main[n_, d_] := Module[{max = 1, res = Null},
   While[res == Null && n != 0,
    res = Catch[recurse[n/d, {}, 1, max]];
    max += 1
    ]; res];

Answer 16

Scala, 83 78 bytes

Saved 5 bytes thanks to the comment of @ceilingcat

---

Golfed version. Try it online!

def c(n:Int,d:Int):String=if(n*d<0)'g'+c(-d,n)else if(n*d<1)""else'f'+c(n-d,d)

Ungolfed version. Try it online!

object Main extends App {
  def calc(n: Int, d: Int): String = {
    if (n == 0 || d == 0) ""
    else {
      (n * d) match {
        case x if x < 0 => 'g' + calc(-d, n)
        case _ => {
          val m = n - d
          'f' + calc(m, d)
        }
      }
    }
  }

  println(calc(9, 7))
}

Answer 17

SAS 101,

"Generating Ratinal Numbers in SAS 4GL - 101" :-D

Inspired by loopy walt answer I decided to make SAS 4GL version.

The code:

data;set;do while(n);t=d;if(n*d<0)then do;put"g"@;d=n;n=-t;end;else do;put"f"@;n=n-d;end;end;put;run;

SAS is quite "talkative" by all those ifs, thens, dos, ends and elses so, even tough I did my best to "boil" bytes down, I ended up on 101.

Explanation:

I don't like stack overflows so instead recursion I went with iterative approach.

It is SAS 4GL so the the standard input in form of a SAS dataset is expected (I added some extra test cases):

data i;
input n d;
cards;
1     3
3     1
16    4
8     2
4     1
1    -3
2     3
0     9
0     3
0     1
1     1
2     1
1    -2
-1    -2
6     4
-2     3
8     9
17    42 
17   -42 
17    303
42    303
99    100
990   1000
999   1002
999  -1002
1 11111
1 2
2 4
4 8
;
run;

Human readable code:

data _null_; /* 0) */
  set i; /* expect input data set 1) */
  put n= d= @; /* added just for printing */

  do while(n); /* while numerator is not 0 */
    x=d;
    if (n*d<0) 
      then /* for negative print "g", then negate and flip fraction  */
        do;
          put "g" @;
          d = n;
          n = -x;
        end;
      else /* for positive print "f", then substract 1 from fraction  */
        do;
          put "f" @;
          n = n-d;
        end;
  end;
  put; /* add new line character at the end of printout 2) */
run;

Footnotes:

0) turn of production of output dataset

1) the set statement takes as input the last created data set, so code generating dataset i has to be executed just before.

2) the last put; can be skipped if the input dataset has only 1 observation what reduces length by 4 bytes to 97.

Log output:

n=1 d=3 fgffgff
n=3 d=1 fff
n=16 d=4 ffff
n=8 d=2 ffff
n=4 d=1 ffff
n=1 d=-3 gfff
n=2 d=3 fgfff
n=0 d=9
n=0 d=3
n=0 d=1
n=1 d=1 f
n=2 d=1 ff
n=1 d=-2 gff
n=-1 d=-2 fgff
n=6 d=4 ffgff
n=-2 d=3 gffgff
n=8 d=9 fgfffffffff
n=17 d=42 fgffgffffgffgffgffgffgffgffgff
n=17 d=-42 gfffgffgfffffffff
n=17 d=303 fgffgffgffgffgffgffgffgffgffgffgffgffgffgffgffgffgfffgffgffgffgfffgff
n=42 d=303 fgffgffgffgffgffgffgffffffgfff
n=99 d=100 fgffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
n=990 d=1000 fgffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
n=999 d=1002 fgf[ 332 "f" hidden for readability ]f
n=999 d=-1002 gff[ 331 "gff" hidden for readability ]gff
n=1 d=11111 f[ 11109 "gff" hidden for readability ]gff
n=1 d=2 fgff
n=2 d=4 fgff
n=4 d=8 fgff
NOTE: There were 29 observations read from the data set WORK.I.
NOTE: DATA statement used (Total process time):
      real time           0.02 seconds
      cpu time            0.03 seconds

A small comment at the end:

We are in a group of functions with composition.

Function: \$ z(x) = g(f(g(f(g(x))))) = x{-}1 \$ is an inverse of \$f\$ (\$f(z(x))=x\$, \$z(f(x))=x\$) and \$g\$ is inverse of itself (\$g(g(x))=x\$)

So a path from \$0\$ to \$\frac{n}{d}\$ (assuming frac is reduced) of the form:

$$ \frac13 = f(g(f(f(g(f(f(0))))))) $$

can be "walked back" using inverses of \$f\$ and \$g\$

$$ 0 = z(z(g(z(z(g(z(\frac13))))))) $$

Which is "base" for the algorithm: "1) take a fraction, 2) if the fraction is negative "flip it"(negate and inverse) else subtract 1 from it, 4) if fraction is 0 stop else got to 1)"