9
\$\begingroup\$

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 five fourths

5/3 five thirds

5/7 five sevenths

9/16 nine sixteenths

89/150 eighty nine two hundred fiftieths

\$\endgroup\$

migrated from codegolf.meta.stackexchange.com Dec 3 '13 at 22:09

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

  • \$\begingroup\$ 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? \$\endgroup\$ – Doorknob Dec 3 '13 at 22:35
  • \$\begingroup\$ I was presupposing that the only acceptable numerator was 1. I'll add that. \$\endgroup\$ – DavidC Dec 3 '13 at 22:37
  • \$\begingroup\$ 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? \$\endgroup\$ – Doorknob Dec 3 '13 at 22:40
  • 1
    \$\begingroup\$ 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). \$\endgroup\$ – DavidC Dec 3 '13 at 23:02

14 Answers 14

5
\$\begingroup\$

Mathematica, 40 36 chars

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

Example:

f[89/150]

Output:

Output

\$\endgroup\$
10
\$\begingroup\$

Python 2, 158 155 147 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
\$\endgroup\$
  • 1
    \$\begingroup\$ +1 Good idea! Though there are problems if numbers greater than 9 are produced. Check, e.g., 40,3 as input. \$\endgroup\$ – Sven Hohenstein Dec 5 '13 at 0:40
7
\$\begingroup\$

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>
        <td valign="top" rowspan="2" style="padding-top:12px">
          <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"/>

89/150

\$\endgroup\$
  • \$\begingroup\$ I LOVE this solution. Nice work! \$\endgroup\$ – Cruncher Dec 5 '13 at 17:51
4
\$\begingroup\$

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

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.

enter image description here

\$\endgroup\$
4
\$\begingroup\$

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 
\$\endgroup\$
  • \$\begingroup\$ Wow, we may have a winner in one of the least likely languages to win a CG! Impressive! :-) \$\endgroup\$ – Doorknob Dec 4 '13 at 18:05
3
\$\begingroup\$

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 
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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

Latex Picture

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

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

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
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.