# Display Continued Fractions

Your challenge is to convert a fraction into its continued fraction form.

Input: The fraction may be input in any format, including (but not restricted to)

• string: "7/16"
• list: {7, 16}, (7, 16), [7, 16]
• simple ordered pair: 7 16
• function: f[7,16]

Output: A continued fraction, in 2D, with horizontal fraction bars separating numerator from denominator. Only continued fractions with numerators equal to 1 are valid. It is not necessary to make the font size vary according to depth. A leading zero (for proper fractions) is optional.

Depth: Your code must be able to display at least 8 levels of depth.

Winning criterion: Shortest code wins. You must include several test cases showing input and output.

Test Examples (Input followed by output)

5/4

5/3

5/7

9/16

89/150

## migrated from meta.codegolf.stackexchange.comDec 3 '13 at 22:09

This question came from our discussion, support, and feature requests site for programming puzzle enthusiasts and code golfers.

• what's the criteria for how deep you must go? for example, why can't we just do 0 + 89 / 250 for the last one? – Doorknob Dec 3 '13 at 22:35
• I was presupposing that the only acceptable numerator was 1. I'll add that. – DavidC Dec 3 '13 at 22:37
• ah okay, don't have much of a math background :) Wikipedia helped. How about languages that can't display things in this format? Is it okay if we do something like 0 + 1 / (1 + 1 / (1 + 1 / (2 + 1 / (3 + 1 / (1 + 1 / (1 + 1 / (2)))))))? What about without the parenthesis? Or if we just display the blue numbers, like 0 1 1 2 5 1 1 2? – Doorknob Dec 3 '13 at 22:40
• Your notation appears to be mathematically correct. But the main point of the challenge is to figure out a way to display the fraction in column and row format (which I referred to above loosely as 2D). – DavidC Dec 3 '13 at 23:02

# Mathematica, 40 36 chars

f=If[⌊#⌋≠#,⌊#⌋+"1"/#0[1/(#-⌊#⌋)],#]&


Example:

f[89/150]


Output:

## Python 2, 158155147 142

a,b=input()
c=[]
while b:c+=[a/b];a,b=b,a%b
n=len(c)
while b<n-1:print'  '*(n+b),'1\n',' '*4*b,c[b],'+','-'*(4*(n-b)-7);b+=1
print' '*4*b,c[b]


Test:

$python cfrac.py (89,150) 1 0 + ------------------------- 1 1 + --------------------- 1 1 + ----------------- 1 2 + ------------- 1 5 + --------- 1 1 + ----- 1 1 + - 2  ## Python 2, alt. version, 95 Basically a port of breadbox's answer. Safer output. a,b=input();i=2 while a%b:print'%*d\n%*d + ---'%(i+5,1,i,a/b);a,b=b,a%b;i+=5 print'%*d'%(i,a/b)  Test: $ python cfrac2.py
(98,15)
1
6 + ---
1
1 + ---
1
1 + ---
7

• +1 Good idea! Though there are problems if numbers greater than 9 are produced. Check, e.g., 40,3 as input. – Sven Hohenstein Dec 5 '13 at 0:40

## XSLT 1.0

I thought it'd be nice to display the fractions with HTML, so here's an XSLT solution.

<?xml version="1.0" encoding="utf-8"?>
<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
xmlns:msxsl="urn:schemas-microsoft-com:xslt" >
<xsl:template match="/f">
<xsl:variable name="c" select="floor(@a div @b)"/>
<xsl:variable name="next">
<f a="{@b}" b="{@a mod @b}"/>
</xsl:variable>
<table>
<tr>
<xsl:value-of select="c"/>+ </td> <td align="center" style="border-bottom:1px solid black">1</td> </tr> <tr> <td> <xsl:apply-templates select="msxsl:node-set(next)"/>
</td>
</tr>
</table>
</xsl:template>
<xsl:template match="/f[@a mod @b=0]">
<xsl:value-of select="@a div @b"/>
</xsl:template>
</xsl:stylesheet>


To test it, save the xslt as fraction.xslt and open the following file in IE:

<?xml version="1.0" encoding="utf-8"?>
<?xml-stylesheet  href="fraction.xslt" type="text/xsl"?>
<f a="89" b="150"/>


• I LOVE this solution. Nice work! – Cruncher Dec 5 '13 at 17:51

# Ruby, 175 (with ASCII art) or 47 (without)

## Without ASCII art, 47

n,d=eval gets
while d!=0
puts n/d
n,d=d,n%d
end


Since Ruby can't really do graphics like that, I just output the blue numbers in your examples.

c:\a\ruby>cont
[5,4]
1
4

c:\a\ruby>cont
[5,3]
1
1
2

c:\a\ruby>cont
[5,7]
0
1
2
2

c:\a\ruby>cont
[9,16]
0
1
1
3
2

c:\a\ruby>cont
[89,150]
0
1
1
2
5
1
1
2


## With ASCII Art, 181178 175

n,d=eval gets
a=[]
n,d=d,n%d,a.push(n/d)while d!=0
i=0
j=2*a.size-3
k=a.size-2
a.map{|x|puts' '*i+"#{x}+"+' '*k+?1
i+=2
k-=1
puts' '*i+?-*j
j-=2}rescue 0
puts' '*i+a.last.to_s


Wow, that ASCII art took up a lot of code, and I was even being evil and using rescue 0 :P Sample:

c:\a\ruby>cont
[89,150]
0+      1
-------------
1+     1
-----------
1+    1
---------
2+   1
-------
5+  1
-----
1+ 1
---
1+1
-
2

• @DavidCarraher Ok, then it works. Edited – Doorknob Dec 3 '13 at 22:56
• You output the partial quotients. Although they are essential for formulating a continued fraction, they are only part of the requirement. – DavidC Dec 3 '13 at 22:58
• @DavidCarraher I suppose I could try some kind of ASCII art... there's really not much of a way to do this in Ruby. – Doorknob Dec 3 '13 at 22:59
• @DavidCarraher Okay, I have to leave, but I'll work on making an ASCII representation of the fraction soon. – Doorknob Dec 3 '13 at 23:02
• Great. I look forward to seeing the results of your effort. – DavidC Dec 3 '13 at 23:03

## Sage Notebook, 80

c=continued_fraction(n)
LatexExpr('{'+'+\\frac{1}{'.join(map(str,c))+'}'*len(c))


Here n can be anything Sage can approximate by a rational / floating point number. Default precision is 53 bits, unless n is a Rational. Gotta love MathJax.

## C, 119 characters

n,d,r;main(i){for(scanf("%d%d",&n,&d);r=n%d;n=d,d=r,i+=5)
printf("%*d\n%*d + ---\n",i+5,1,i,n/d);printf("%*d\n",i,n/d);}


Here are some examples of output:

$echo 15 98 | ./cfrac 1 0 + --- 1 6 + --- 1 1 + --- 1 1 + --- 7$ echo 98 15 | ./cfrac
1
6 + ---
1
1 + ---
1
1 + ---
7
$echo 98 14 | ./cfrac 7  While the truncated fraction line isn't as pretty-looking as some of the examples here, I wish to point out that this was a common technique for formatting continued fractions back in the days before desktop computers were ubiquitous. Okay, here's a much longer version (247 characters) that does full-on formatting of the output: c,h,i,j,n,d,w[99];char s[99][99];main(r){for(scanf("%d%d",&n,&r);d=r;n=d) h+=w[c++]=sprintf(s[c],"%d + ",n/d,r=n%d);for(;j+=w[i],i<c-1;puts("")) for(printf("%*d\n%*s",j+(r=h-j)/2,1,j,s[i++]);--r;printf("-")); s[i][w[i]-2]=0;printf("%*s\n",j-1,s[i]);}  Some examples of its output: $ echo 89 150 | ./cfr
1
0 + ---------------------------
1
1 + -----------------------
1
1 + -------------------
1
2 + ---------------
1
5 + -----------
1
1 + -------
1
1 + ---
2
$echo 151 8919829 | ./cfr 1 0 + ---------------------------- 1 59071 + -------------------- 1 1 + ---------------- 1 2 + ------------ 1 1 + -------- 1 1 + ---- 21$ echo 293993561 26142953 | ./cfr
1
11 + ---------------------
1
4 + -----------------
1
14 + ------------
1
4410 + -----
104

• Wow, we may have a winner in one of the least likely languages to win a CG! Impressive! :-) – Doorknob Dec 4 '13 at 18:05

## APL (78)

{(v↑' '⍪⍉⍪⍕⍺),(' +'↑⍨v←⊃⍴x),x←('1'↑⍨⊃⌽⍴v)⍪v←'─'⍪⍕⍪⍵}/⊃{⍵≤1:⍺⋄a w←0⍵⊤⍺⋄a,⍵∇w}/⎕


Example:

      {(v↑' '⍪⍉⍪⍕⍺),(' +'↑⍨v←⊃⍴x),x←('1'↑⍨⊃⌽⍴v)⍪v←'─'⍪⍕⍪⍵}/⊃{⍵≤1:⍺⋄a w←0⍵⊤⍺⋄a,⍵∇w}/⎕
⎕:
89 150
1
0+─────────────
1
1+───────────
1
1+─────────
1
2+───────
1
5+─────
1
1+───
1
1+─
2


## Mathematica, 77

Fold[#2+1/ToString[#1]&,First[#1],Rest[#1]]&[Reverse[ContinuedFraction[#1]]]&


Just learned Mathematica for this. Takes a surprisingly long program to do this.

### Perl 128 114 chars

($a,$b)=split;$_=" "x7;until($b<2){$==$a/$b;($a,$b)=($b,$a%$b);$_.="1\e[B\e[7D$= + ---------\e[B\e[4D"}$_.="$a\n"


But as this use console placement, you have to clear console in order before run:

clear
perl -pe '($a,$b)=split;$_=" "x7;until($b<2){$==$a/$b;($a,$b)=($b,$a%$b);$_.= "1\e[B\e[7D$= + ---------\e[B\e[4D"}$_.="$a\n"' <<<$'5 7 \n189 53 \n9 16 \n89 150 '  output:  1 0 + --------- 1 1 + --------- 1 2 + --------- 2 1 3 + --------- 1 1 + --------- 1 1 + --------- 1 3 + --------- 1 3 + --------- 2 1 0 + --------- 1 1 + --------- 1 1 + --------- 1 3 + --------- 2 1 0 + --------- 1 1 + --------- 1 1 + --------- 1 2 + --------- 1 5 + --------- 1 1 + --------- 1 1 + --------- 2  ### First post: 128 chars ($a,$b)=split;$c=7;while($b>1){$==$a/$b;($a,$b)=($b,$a%$b);printf"%s1\n%${c}d + %s\n"," "x($c+=5),$=,"-"x9}printf" %${c}d\n",$=


Splitted for cut'n paste:

perl -ne '($a,$b)=split;$c=7;while($b>1){$==$a/$b;($a,$b)=($b,$a%$b);printf
"%s1\n%${c}d + %s\n"," "x($c+=5),$=,"-"x9}printf" %${c}d\n",$a' \ <<<$'5 7 \n189 53 \n9 16 \n89 150 '


Will render:

            1
0 + ---------
1
1 + ---------
1
2 + ---------
2
1
3 + ---------
1
1 + ---------
1
1 + ---------
1
3 + ---------
1
3 + ---------
2
1
0 + ---------
1
1 + ---------
1
1 + ---------
1
3 + ---------
2
1
0 + ---------
1
1 + ---------
1
1 + ---------
1
2 + ---------
1
5 + ---------
1
1 + ---------
1
1 + ---------
2


### Same using LaTeX:

perl -ne 'END{print "\\end{document}\n";};BEGIN{print "\\documentclass{article}\\pagestyle".
"{empty}\\begin{document}\n";};($a,$b)=split;$c="";print "$a / b = ";while(b>1){==a /b;(a,b)=(b,a%b);printf"%s + \\frac{1}{",=;c.="}";}printf"%d%s$\n\n",$a,$c' \ <<<$'5 7 \n189 53 \n9 16 \n89 150 ' >fracts.tex

pslatex fracts.tex

dvips -f -ta4 <fracts.dvi |
gs -sDEVICE=pnmraw -r600 -sOutputFile=- -q -dNOPAUSE - -c quit |
pnmcrop |
pnmscale .3 |
pnmtopng >fracts.png


# Perl : 140 ,133 121 chars

($a,$b)=<STDIN>;while($b>1) {$g=$i+++4;print" "x$g."1\n"." "x$i,int($a/$b)."+---\n";($a=$b)=($b,$a%$b)}
print" "x$g."$a\n"


example :
#perl fraction.pl
5
7

   1
0+---
1
1+---
1
2+---
2


## Razor Leaf on Firefox, 108 127

%r=(i,n,d)=>
mn"#{n/d|0}"
if i<8&&n%d
mo"+"
mfrac
mn"1"
me%r(i+1,d,n%d)
math%[a,b]=data;r(0,a,b)


The prompt really hurts there… Oh, you mean I get to pick? Okay, it’s a list. Anyways, good luck getting this to run.

## Game Maker Language (Script), 61 71

a=argument0;b=argument1;while b!=0{c+=string(a/b)a,b=b,a mod b}return c


Compile with all uninitialized variables as 0.

• does this output anything? also, it seems to be wrong; you're appending a string to a number. did you try it? – Doorknob Dec 3 '13 at 23:54
• @Doorknob You're right, I meant to give that to c. – Timtech Dec 4 '13 at 11:53
• It still doesn't output anything... – Doorknob Dec 4 '13 at 12:59
• @Doorknob Yeah, it doesn't return anything, and I had some syntax errors. It should return the correct value now. – Timtech Dec 4 '13 at 21:17

Assuming the input numbers as co-prime, call this process function with numerator and denominator. It can go to any depth until it finds the continued form, no limit

Written in JAVA (238 characters)

String space = "";
private void process(int n, int d) {
System.out.println(space+(n/d)+" + 1");
space += "    ";
System.out.println(space+"------");
if((n % d)==1)
System.out.println(space+d);
else
process(d,(n % d));
}


process(89,150);

0 + 1
------
1 + 1
------
1 + 1
------
2 + 1
------
5 + 1
------
1 + 1
------
1 + 1
------
2


process(973,13421);

0 + 1
------
13 + 1
------
1 + 1
------
3 + 1
------
1 + 1
------
5 + 1
------
3 + 1
------
1 + 1
------
1 + 1
------
4


# K, 136

{-1@((!#j)#\:" "),'j:(,/{(x,"+ 1";(" ",(2*y)#"-"),"\t")}'[a;1+|!#a:$-1_i]),$*|i:*:'1_{(i;x 2;x[1]-(i:x[1]div x 2)*x@2)}\[{~0~*|x};1,x];}


.

k)f:{-1@((!#j)#\:" "),'j:(,/{(x,"+ 1";(" ",(2*y)#"-"),"\t")}'[a;1+|!#a:$-1_i]),$*|i:*:'1_{(i;x 2;x[1]-(i:x[1]div x 2)*x@2)}\[{~0~*|x};1,x];}
k)f[5 4]
1+ 1
--
4

k)f[5 3]
1+ 1
----
1+ 1
--
2

k)f[5 7]
0+ 1
------
1+ 1
----
2+ 1
--
2

k)f[9 16]
0+ 1
--------
1+ 1
------
1+ 1
----
3+ 1
--
2

k)f[89 150]
0+ 1
--------------
1+ 1
------------
1+ 1
----------
2+ 1
--------
5+ 1
------
1+ 1
----
1+ 1
--
2