Simplify a continued fraction

Question

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

$$ a_0 +\cfrac 1 {a_1 + \cfrac 1 {a_2 + \cfrac 1 {\ddots + \cfrac 1 {a_n} } } } $$

Or they can be represented as a list of values: \$[a_0 ; a_1, a_2, \dots, a_n]\$

The challenge:

take a base number: \$a_0\$ and a list of denominator values: \$[a_1, a_2, \dots, a_n]\$ and simplify the continued fraction to a simplified rational fraction: return or print numerator and denominator separately.

Examples:

• \$\sqrt 19\$: [4;2,1,3,1,2]: 170/39
• \$e\$: [1;0,1,1,2,1,1]: 19/7
• \$\pi\$: [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--

Answer 1

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.

Answer 2

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

Answer 3

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.
}*

Answer 4

LabVIEW, 36 equivalent bytes

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

Answer 5

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

Answer 6

Dyalog APL, 10 bytes

Does not even use a build-in for rationals.

Takes {a₀,a₁,a₂,a₃,...} 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!

Answer 7

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.

Answer 8

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

Answer 9

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.

Answer 10

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.

Answer 11

 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                

Answer 12

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.

Answer 13

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]));

Answer 14

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

Answer 15

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!

Answer 16

JavaScript (ES6), 44 bytes

a=>a.reduceRight(([n,d],v)=>[v*n+d,n],[1,0])

Answer 17

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 ]

Answer 18

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)

Answer 19

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

Answer 20

Ruby, 34 bytes

->a{a.reverse.inject{|b,i|i+1r/b}}

This performs a right fold (by reversing and then left folding), adding each element to 1 over the running total (the elements to the right). Ruby has the Rational type, which is really nice. And literal rationals are a number suffixed with r.

Answer 21

Stax, 4 bytes

╣╩┼►

Run and debug it

As small as it is, it's not a built-in. The built-in rationals help quite a bit though. Unpacked to ascii, the program is rksu+.

1. Reverse the array.
2. Fold the array using (a, b) => (a + 1/b).

Answer 22

APL(NARS), 15+1 chars, 30+2 bytes

{1=≢⍵:↑⍵⋄+∘÷/⍵}

Translation in Apl(Nars) from Adam J solution... the input allowed for that function will be all list of integer numbers, where the first element will be of type rational. Test:

  f←{1=≢⍵:↑⍵⋄+∘÷/⍵}      
  f 4x 2 1 3 1 2
170r39 
  f 1x 0 1 1 2 1 1
19r7 
  f 3x 7 15 1 292 1
104348r33215 
  f 1x 1 1 1 1 1
13r8 
  f 3x 89 888 999 11 222 373 7282 9272 3839 2828 
158824716824887954093160207727r52744031585005490644982548907 
  f ,0x
0 
  f ,9x
9 

so it would be 15 chars as length of function and 1 char for "x" for enter the type of input I want and exit the type I want...

Answer 23

Husk, 4 bytes

Ḟ·+\

Try it online!

pretty simple with TNum being a rational type.

Answer 24

Vyxal, 6 5 bytes

‡Ė+ḭƒ

Try it Online!

I added foldr lol.

Explained

‡Ė+ḭƒ
‡Ė+    # lambda x, y: 1 / x + y
   ḭ   # reduce input by ↑, going right-to-left
    ƒ  # fractionify the result