18
\$\begingroup\$

Continued fractions are expressions that describe fractions iteratively. They can be represented graphically:

enter image description here

Or they can be represented as a list of values: [a0; a1, a2, a3, ... an]

The challenge:

take a base number: a0 and a list of denominator values: [a1, a2, a3, ... an] and simplify the continued fraction to a simplified rational fraction: return or print numerator and denominator separately.

Examples:

  • √19 : [4;2,1,3,1,2]: 170/39
  • ℯ: [1;0,1,1,2,1,1]: 19/7
  • π: [3;7,15,1,292,1]: 104348/33215
  • ϕ: [1;1,1,1,1,1]: 13/8

Example implementation: (python)

def foo(base, sequence):
    numerator = 1
    denominator = sequence[-1]
    for d in sequence[-2::-1]:
        temp = denominator
        denominator = d * denominator + numerator
        numerator = temp
    return numerator + base * denominator, denominator

Winning:

shortest code in bytes: --no builtins that do the entire problem allowed--

|improve this question
\$\endgroup\$
  • \$\begingroup\$ You should make this sentence more clear, "and simplify the continued fraction to a single fraction"; unless you intended the wording to mean a result of 2.002 can be expressed as 2002/1000. That's technically a "single fraction", you probably want to say, "a single fraction, in its most simple form." \$\endgroup\$ – Magic Octopus Urn Sep 14 '16 at 20:29
  • \$\begingroup\$ @carusocomputing point taken.. although I wouldn't feel too bad about 2/4 (or similar) as it has still simplified the multiple fraction structure to a single fraction \$\endgroup\$ – Aaron Sep 14 '16 at 20:47
  • \$\begingroup\$ Hmm... I think there's a way to exploit that, but with the 13 byte golfscript answer, I'd have to probably use MATL to win. \$\endgroup\$ – Magic Octopus Urn Sep 14 '16 at 21:00
  • \$\begingroup\$ @carusocomputing I'd say go for it... If you can beat the 13 byte answer, that'd be awesome \$\endgroup\$ – Aaron Sep 14 '16 at 21:29
  • \$\begingroup\$ You can make the pi stop earlier - 355/113. \$\endgroup\$ – Thorbjørn Ravn Andersen Sep 14 '16 at 21:54

19 Answers 19

13
\$\begingroup\$

J, 8 5 bytes

Same as this, but uses a build-in for rationals.

Argument is {a0,a1,a2,a3,...} as a list of J extended precision rational numbers. Result is the fraction as a J extended precision rational number.

(+%)/

(+%) the plus-the-reciprocal-of

/ reduction over

Try it online!

-3 thanks to miles.

|improve this answer
\$\endgroup\$
  • \$\begingroup\$ If you take the input as a list of extended integers, you could save 3 bytes. Also you used APL division in the explanation. \$\endgroup\$ – miles Sep 14 '16 at 23:32
  • \$\begingroup\$ @miles Thanks. Can't get closer to the built-in prohibition than that. Too bad J doesn't have a hook composition character like Dyalog APL's ∘. \$\endgroup\$ – Adám Sep 14 '16 at 23:43
  • \$\begingroup\$ The try J online link is broken \$\endgroup\$ – Chiel ten Brinke Feb 27 '18 at 13:56
  • \$\begingroup\$ @ChieltenBrinke Thanks. Fixed. \$\endgroup\$ – Adám Feb 27 '18 at 14:03
11
\$\begingroup\$

Haskell, 37 36 18 bytes

foldr1$(.(1/)).(+)

This function expects Haskell's Ratio type as input. Usage example:

Prelude Data.Ratio> ( foldr1$(.(1/)).(+) )  [4%1,2,1,3,1,2] 
170 % 39

Note: one explicit Ratio in the input list (4%1) is enough, the type systems figures out that the others have to be Ratios, too.

Edit: @Lynn saved a byte. Thanks!

Edit II: removed the import (see this discussion on meta).

|improve this answer
\$\endgroup\$
  • 1
    \$\begingroup\$ Oooh, nice edge case. The function itself is polymorphic, so it doesn't need the import. However to call it, you have to feed Ratios to it which does need the import. Should I add the import to the byte count or not? \$\endgroup\$ – nimi Sep 14 '16 at 20:47
  • 1
    \$\begingroup\$ That sounds like a good question for meta. \$\endgroup\$ – Martin Ender Sep 14 '16 at 20:48
  • \$\begingroup\$ I've never used Haskell, so correct me if I'm wrong, but if the python equivelent would be: from fractions import Fraction to do operations with Fraction objects, the import statement is counted as well. \$\endgroup\$ – Aaron Sep 14 '16 at 20:54
  • \$\begingroup\$ .. we had that before. \$\endgroup\$ – nimi Sep 14 '16 at 20:54
  • \$\begingroup\$ @Aaron: the problem is: the definition of the function doesn't need the import, because it's polymorphic. When you want to call it, you need to provide numbers of type Ratio which can only be constructed via %, which requires the import. Usually we don't count bytes for calling overhead, just for the function itself. \$\endgroup\$ – nimi Sep 14 '16 at 20:59
10
\$\begingroup\$

GolfScript, 13 bytes

~]-1%{\-1?+}*

Try it online!

Yay for GolfScript's hidden rationals. :)

Explanation

GolfScript's only "official" number type is integers. But the exponentiation operator doesn't cast its result to integer and conveniently the native result of an integer exponentiation in Ruby (the language of GolfScript's interpreter) is a rational number. So we can easily get fractions by raising something to the power of -1. Conveniently, we want reciprocals anyway...

~]     # Evaluate input and wrap all a_i in a list.
-1%    # Reverse the list so that a_n is at the start and a_0 at the end.
{      # Fold... (apply this block to each element from a_n-1 down to a_0, with
       # the previous result on the stack)
  \    #   Swap previous result with current a_i.
  -1?  #   Raise previous result to the power of -1, computing its reciprocal
       #   as a rational number.
  +    #   Add a_i.
}*
|improve this answer
\$\endgroup\$
9
\$\begingroup\$

Mathematica, 23 22 bytes

Fold[#2+1/#&]@*Reverse

Essentially a port of my GolfScript answer. Here are some alternatives:

For 24 bytes, we can write a recursive variadic function:

f@n_=n
n_~f~m__:=n+1/f@m

For 21 bytes, we can even define a "variadic operator", but its calling convention would be so weird, that I'm reluctant to count this one:

±n_=n
n_ ±m__:=n+1/±m

You would have to call this with a sequence of the input values, e.g. ±Sequence[3, 7, 15, 1, 292, 1] or ±##&[3, 7, 15, 1, 292, 1].

And also for 21 bytes, there would be the (forbidden) built-in:

FromContinuedFraction
|improve this answer
\$\endgroup\$
8
\$\begingroup\$

LabVIEW, 36 equivalent bytes

Fairly straight forward naive implementation using OP's algorithm. Is there a nicer way to do this?

enter image description here

|improve this answer
\$\endgroup\$
  • 5
    \$\begingroup\$ Your electrical engineering degree is showing. \$\endgroup\$ – Magic Octopus Urn Sep 15 '16 at 11:52
  • 1
    \$\begingroup\$ @ijustlovemath Props, but..... relevant \$\endgroup\$ – Aaron Sep 15 '16 at 13:30
  • \$\begingroup\$ Yeah it's a contentious language to be sure. I see LabVIEW as the "I hate math" of the programmers world. The problem is not math itself, but how it's taught (or often the lack of teaching at all). \$\endgroup\$ – ijustlovemath Sep 15 '16 at 14:02
6
\$\begingroup\$

Dyalog APL, 10 bytes

Does not even use a build-in for rationals.

Takes {a0,a1,a2,a3,...} as argument, returns {denominator,numerator}.

1(,÷∨)+∘÷/

1(,÷∨) 1-prepended-to divided by the GCD of 1 and

+∘÷ plus-the-reciprocal-of

/ reduction over

TryAPL online!

|improve this answer
\$\endgroup\$
6
\$\begingroup\$

Python 2, 62 bytes

a=d=0
b=c=1
for n in input():a,b=b,n*b+a;c,d=d,n*d+c
print b,d

It's unfortunately not as golfy (see @xnor's answer for shorter), but it calculates the fraction without needing to reverse the input. This uses the "magic table" approach for convergents – given the last two fractions a/c and b/d, the next fraction is (n*b+a)/(n*c+d).

For instance, for pi:

          3    7    15     1      292        1

  0   1   3   22   333   355   103993   104348
  1   0   1    7   106   113    33102    33215

We can see that 15*22 + 3 = 333, 15*7 + 1 = 106, 1*333 + 22 = 355, 1*106 + 7 = 113, etc.

|improve this answer
\$\endgroup\$
4
\$\begingroup\$

M, 5 bytes

Ṛİ+¥/

The input is a list of the values [a0, a1, ..., aN] and it outputs a rational number.

Try it online! or Verify all test cases.

Explanation

Ṛİ+¥/  Input: list A
Ṛ      Reverse A
    /  Reduce A from left to right using
   ¥     A dyadic chain
 İ         Take the reciprocal of the left value
  +        Add the reciprocal to the right value
       Return and print implicitly
|improve this answer
\$\endgroup\$
  • 1
    \$\begingroup\$ What is this? Some new Jelly dialect? \$\endgroup\$ – Adám Sep 15 '16 at 12:41
  • \$\begingroup\$ @miles actually 9 bytes sorry :( \$\endgroup\$ – Aaron Sep 15 '16 at 13:42
  • \$\begingroup\$ @Adám It's an old fork of Jelly meant for math and symbolics. Here's its Github repo. \$\endgroup\$ – miles Sep 15 '16 at 14:00
  • 1
    \$\begingroup\$ @Aaron M uses the same code page as Jelly, and it can be encoded using a byte for each character. \$\endgroup\$ – miles Sep 15 '16 at 14:01
  • \$\begingroup\$ @miles OK, added. \$\endgroup\$ – Adám Sep 15 '16 at 15:21
4
\$\begingroup\$

Haskell, 30 bytes

foldr(\h(n,d)->(h*n+d,n))(1,0)

Recursively adds each layer going outward, updating n/d to h+(1/(n/d)), which equals h+d/n or (h*n+d)/n. The fraction is stored as a tuple of (num,denom). The initial fraction of (1,0) flips to 0/1 which is 0.

|improve this answer
\$\endgroup\$
3
\$\begingroup\$

Python, 50 bytes

f=lambda l,n=1,d=0:l and f(l,l.pop()*n+d,n)or(n,d)

Builds the continued fraction from the end of the list going backwards, repeatedly updating the fraction n/d on the last element x as n/d -> 1+1/(n/d) == (x*n+d)/n.

|improve this answer
\$\endgroup\$
2
\$\begingroup\$

Julia (53 Bytes)

This is my first time ever using Julia, if I overlooked an iterator I could have used to lose some more bytes, let me know. Here's a hint to anyone who doesn't know what language to choose for this specific challenge: https://en.wikipedia.org/wiki/Rational_data_type

f(x,c)=(a=0;for b in x[end:-1:1];a=1//(b+a);end;a+c;)
  • Reverse the input array.
  • Iterate through it with rational division.
  • Add c to the decimal result.
|improve this answer
\$\endgroup\$
  • \$\begingroup\$ you can save two bytes by defining an operator (e.g. ∘) instead of a function \$\endgroup\$ – Tasos Papastylianou Sep 15 '16 at 0:44
  • \$\begingroup\$ also, change the for loop for a while and pop: x∘c=(a=0;while x!=[];a=1//(pop!(x)+a);end;a+c;) \$\endgroup\$ – Tasos Papastylianou Sep 15 '16 at 0:55
  • 1
    \$\begingroup\$ 25: x->foldr((x,y)->x+1//y,x) (same as Haskell solution). usage: (x->foldr((x,y)->x+1//y,x))([4//1,2,1,3,1,2]) \$\endgroup\$ – Fengyang Wang Sep 15 '16 at 3:04
  • \$\begingroup\$ Ooo... A reverse folding function? That's beautiful! I don't deserve to take credit for that though haha. \$\endgroup\$ – Magic Octopus Urn Sep 15 '16 at 11:52
2
\$\begingroup\$

Javascript (ES6), 55 bytes

s=>eval('for(F=[1,0];s+"";)F=[s.pop()*F[0]+F[1],F[0]]')

Test cases

var f =
s=>eval('for(F=[1,0];s+"";)F=[s.pop()*F[0]+F[1],F[0]]')

console.log(f([4, 2, 1, 3, 1, 2]));
console.log(f([1, 0, 1, 1, 2, 1, 1]));
console.log(f([3, 7, 15, 1, 292, 1]));
console.log(f([1, 1, 1, 1, 1, 1]));

|improve this answer
\$\endgroup\$
2
\$\begingroup\$

CJam, 18 16 bytes

XUq~W%{2$*+\}/]p

Online interpreter.

XU                  Push 1 and 0 to the stack
  q~W%              Push input, eval and reverse it
      {     }/      For each n in the reversed input...
       2$             Copy numerator
         *+           Calculate n*denominator + numerator
           \          Swap numerator and denominator
              ]p   Wrap in array and output
|improve this answer
\$\endgroup\$
2
\$\begingroup\$

05AB1E, 19 17 bytes

R¬V¦vyY*X+YUV}YX)

Explanation

Input taken as a list of numbers

                     # variable X is initialized as 1
R¬V¦                 # reverse the list, remove the first item and store it in variable Y
    v        }       # for each item N left in list
     yY*X+  V        # store N*Y+X in Y
          YU         # store Y in X
              YX)    # wrap X and Y in a list

Try it online!

|improve this answer
\$\endgroup\$
2
\$\begingroup\$

 Common Lisp, 54

A somewhat verbose fold-right:

(lambda(s)(reduce(lambda(a r)(+(/ r)a))s :from-end t))

Tests

PASS  NAME  ACTUAL               EXPECTED
===============================================
T     √19   170/39               170/39              
T     ℯ     19/7                 19/7                
T     π     104348/33215         104348/33215        
T     ϕ     13/8                 13/8
|improve this answer
\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 44 bytes

a=>a.reduceRight(([n,d],v)=>[v*n+d,n],[1,0])
|improve this answer
\$\endgroup\$
1
\$\begingroup\$

Javascript (ES6), 50 bytes

f=(s,n=1,d=s.pop())=>s+""?f(s,d,s.pop()*d+n):[d,n]

It's thanks to Arnauld's answer, before seeing it I was stuck to 66 bytes:

f=(b,s,i=s.length-1,n=1,d=s[i])=>i?f(b,s,--i,d,s[i]*d+n):[n+b*d,d]

Example:
Call: f([1, 0, 1, 1, 2, 1, 1])
Output: Array [ 19, 7 ]

|improve this answer
\$\endgroup\$
0
\$\begingroup\$

Perl 6, 24 bytes

{[R[&(1/*+*)]](@_).nude}

Explanation:

  • 1 / * + * is a lambda with two parameters (*) which takes the reciprocal of the first, and adds the second. ( returns a Rat )

  • R[&(…)] uses that as if it was an infix operator and reverses it.
    ( including making it right associative )

  • […](@_) takes that and uses it to reduce the input.

  • … .nude returns the numerator and denominator of the Rat.

  • { … } make it a bare block lambda with implicit parameter @_.

Usage:

say {[R[&(1/*+*)]](@_).nude}(3,7,15,1,292,1) #*/# (104348 33215)

my &code = {[R[&(1/*+*)]](@_).nude}; # stupid highlighter */

say code 4,2,1,3,1,2;    # (170 39)
say code 1,0,1,1,2,1,1;  # (19 7)
say code 1,1,1,1,1,1;    # (13 8)
|improve this answer
\$\endgroup\$
0
\$\begingroup\$

Zephyr, 145 bytes

input n as Integer
set a to Array(n)
for i from 1to n
input a[i]as Integer
next
set r to a[n]
for i from 1to n-1
set r to(/r)+a[n-i]
next
print r

Zephyr is the first programming language I ever created. It was designed to be intuitive and have clean syntax--rather at the expense of brevity. Why am I golfing with it, you ask? Because, unlike any language I've written since, it has a built-in Fraction type. You can even use the division operator / as a unary operator for "inverse" (a feature I borrowed for Pip).

Now, there are significant limitations. The biggest problem for this challenge is that arrays must be defined with fixed size, which means that the program starts by reading the size of the array from the user. (I hope this is ok; the alternative is hardcoding the size.) There's also the minor problem that operator precedence doesn't exist, meaning multi-operator expressions have to have parentheses.

Here's an example run:

C:\Zephyr> python zephyr.py contfrac.zeph
6
1
1
1
1
1
1
13/8
|improve this answer
\$\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.