10
\$\begingroup\$

Your challenge is to convert a positive rational number into a finite simple continued fraction., in 2D, with horizontal fraction bars separating numerator from denominator. [A simple continued fraction only has numerators equal to 1.] Your solution should be able to represent a continued fraction with up to 8 terms.

Input: The rational number 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]
  • decimal number: 0.657

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)

Input 2D Output
\$\frac 5 4\$ \$1 + \cfrac 1 4\$
\$\frac 5 3\$ \$1 + \cfrac 1 {1 + \cfrac 1 2}\$
\$\frac 5 7\$ \$0 + \cfrac 1 {1 + \cfrac 1 {2 + \cfrac 1 2}}\$
\$\frac 9 {16}\$ \$0 + \cfrac 1 {1 + \cfrac 1 {1 + \cfrac 1 {3 + \cfrac 1 2}}}\$
\$\frac {89} {150}\$ \$0 + \cfrac 1 {1 + \cfrac 1 {1 + \cfrac 1 {2 + \cfrac 1 {5 + \cfrac 1 {1 + \cfrac 1 {1 + \cfrac 1 2}}}}}}\$
\$\endgroup\$
5
  • \$\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
    Commented Dec 3, 2013 at 22:35
  • \$\begingroup\$ I was presupposing that the only acceptable numerator was 1. I'll add that. \$\endgroup\$
    – DavidC
    Commented Dec 3, 2013 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
    Commented Dec 3, 2013 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
    Commented Dec 3, 2013 at 23:02
  • 2
    \$\begingroup\$ I know this is an old challenge but there are a couple of close votes now, so I'd like to say that "A continued fraction, in 2D, with horizontal fraction bars separating numerator from denominator." would need further specification by our modern standards. \$\endgroup\$
    – Wheat Wizard
    Commented Feb 12, 2022 at 10:40

14 Answers 14

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
  • 1
    \$\begingroup\$ +1 Good idea! Though there are problems if numbers greater than 9 are produced. Check, e.g., 40,3 as input. \$\endgroup\$ Commented Dec 5, 2013 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\$
1
  • \$\begingroup\$ I LOVE this solution. Nice work! \$\endgroup\$
    – Cruncher
    Commented Dec 5, 2013 at 17:51
5
\$\begingroup\$

Mathematica, 40 36 chars

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

Example:

f[89/150]

Output:

Output

\$\endgroup\$
0
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\$
6
  • \$\begingroup\$ @DavidCarraher Ok, then it works. Edited \$\endgroup\$
    – Doorknob
    Commented Dec 3, 2013 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
    Commented Dec 3, 2013 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
    Commented Dec 3, 2013 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
    Commented Dec 3, 2013 at 23:02
  • \$\begingroup\$ Great. I look forward to seeing the results of your effort. \$\endgroup\$
    – DavidC
    Commented Dec 3, 2013 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\$
1
  • \$\begingroup\$ Wow, we may have a winner in one of the least likely languages to win a CG! Impressive! :-) \$\endgroup\$
    – Doorknob
    Commented Dec 4, 2013 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\$
4
  • 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
    Commented Dec 3, 2013 at 23:54
  • \$\begingroup\$ @Doorknob You're right, I meant to give that to c. \$\endgroup\$
    – Timtech
    Commented Dec 4, 2013 at 11:53
  • \$\begingroup\$ It still doesn't output anything... \$\endgroup\$
    – Doorknob
    Commented Dec 4, 2013 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
    Commented Dec 4, 2013 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\$

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