# Iterate your way to a fraction

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 , 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

• Jan 10 at 1:18
• May we return output reversed, i.e. in the order of function application? Jan 10 at 1:26
• May we take input as a rational number $\frac nd$, if our language supports them?
– att
Jan 10 at 1:52
• @att but then, we should only allow reduced fractions input for other answers, imo. Since most languages only support 1/4 but not 2/8.
– tsh
Jan 10 at 2:27
• For anyone interested: This can also be visualized and demonstrated in a classroom, using two ropes that get twisted together. A nice introduction to "Conway's Rational Tangles" is here: geometer.org/mathcircles/tangle.pdf Jan 12 at 18:38

# 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.

• Maybe n//d<0 -> n*d<0
– tsh
Jan 10 at 1:42
• @alephalpha I can see how this shows that it will always find a representation, but does it also guarantee that it's a shortest representation? Jan 10 at 2:21
• @loopywalt Sorry, I didn't see the word "shortest" in the challenge. Jan 10 at 2:24
• @loopywalt Although I don't know how it can be proved. But it seems that no counterexample exists for fractions may reached within 20 operators.
– tsh
Jan 10 at 6:54
• @loopywalt Try it online!
– tsh
Jan 10 at 6:55

# 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.

# 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

# 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

• 42 bytes by tweaking the guards
– xnor
Jan 10 at 12:43

# 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.

# 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!

# 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!

• As it stands your submission isn't valid as it hard-codes the input. You should write this as a function and then call it from main in the TIO footer (which would allow you to show off several test cases).
– Neil
Jan 10 at 13:43
• You can use n<0^d<0 to avoid the first if block. You can also probably use the comma operator to avoid some of the {}s.
– Neil
Jan 10 at 13:45
• 73 bytes Jan 11 at 17:03
• @Neil : Yes, it is a good idea to code it in TIO. Jan 18 at 13:08
• @ceilingcat well done! I will study it. Jan 18 at 13:08

# 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!

# 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.

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


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)


# Charcoal, 656252 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.

# Stax, 18 16 bytes

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


Run and debug it

Pretty convenient with the rational type.

# 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!

# 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!

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

• The printf is neat, but putchar('g'-z) is one shorter, surely? Jan 12 at 1:18
• @dingledooper Nice one - thanks! :D Jan 12 at 9:59