Continued Fraction of a Rational Number

Question

The continued fraction of a number n is a fraction of the following form:


which converges to n.

The sequence a in a continued fraction is typically written as: [a₀; a₁, a₂, a₃, ..., a_n].

Your goal is to return the continued fraction of the given rational number (positive or negative), whether it is an:

• integer x
• fraction x/y
• decimal x.yz

Input

May be a string representation, or numbers. For fractions, it may be a string, or some native data type for handling fractions, but you may not take it as a decimal.

Output

May be a delimited list or string of the convergents (the resulting numbers). The output does not have to have a semi-colon between a₀ and a₁, and may use a comma instead.

Note that although [3; 4, 12, 4] and [3; 4, 12, 3, 1] are both correct, only the first will be accepted, because it is simpler.

Examples:

860438      [860438]
3.245       [3; 4, 12, 4]
-4.2        [-5; 1, 4]
-114.7802   [-115; 4, 1, 1, 4, 1, 1, 5, 1, 1, 4]
0/11        [0]
1/42        [0; 42]
2/7         [0; 3, 2]
-18/17056   [-1; 1, 946, 1, 1, 4]
-17056/18   [-948; 2, 4]

Rules

• Shortest code wins.
• Built-ins are allowed, but I'd also like you to post in the same answer what it would be without built-ins, so that you have to know how to do it.

Answer 1

Ruby, 45 43 46 bytes

f=->n{x,y=n.to_r.divmod 1;[x,*y==0?[]:f[1/y]]}

Accepts input as a string.

All test cases pass:

llama@llama:~$ for n in 860438 3.245 -4.2 -114.7802 0/11 1/42 2/7 -18/17056 -17056/18; do ruby -e 'f=->n{x,y=n.to_r.divmod 1;[x,*y==0?[]:f[1/y]]}; p f["'$n'"]'; done
[860438]
[3, 4, 12, 4]
[-5, 1, 4]
[-115, 4, 1, 1, 4, 1, 1, 5, 1, 1, 4]
[0]
[0, 42]
[0, 3, 2]
[-1, 1, 946, 1, 1, 4]
[-948, 2, 4]

Thanks to Kevin Lau for 2 bytes!

Answer 2

Ruby, 50 48 bytes

I noticed @Doorknob♦ beat me to a Ruby answer right before posting, and theirs is also shorter! As such this is just here for posterity now. Takes in a string or an integer (floats have rounding issues, so decimal values need to be put in as strings)

f=->s{s=s.to_r;[s.floor]+(s%1!=0?f[1/(s%1)]:[])}

Answer 3

Nekomata, 7 bytes

ᶦ{1%ŗ}k

Attempt This Online!

A port of @Parcly Taxel's Mathematica answer.

ᶦ{1%ŗ}k
ᶦ{   }        Iterate the following function until it fails
  1%            Modulo 1
    ŗ           Reciprocal
      k       Floor

Answer 4

Jelly, 16 13 12 bytes

:;ç%@¥@⁶Ṗ¤%?

Try it online!

Answer 5

JavaScript (ES6), 52 bytes

f=(n,d)=>n%d?[r=Math.floor(n/d),...f(d,n-r*d)]:[n/d]

Accepts numerator and denominator and returns an array, e.g. f(-1147802, 1e4) returns [-115, 4, 1, 1, 4, 1, 1, 5, 1, 1, 4].

Answer 6

Java, 85 83 bytes

String f(int n,int d){return n<0?"-"+f(2*(d+n%d)-n,d):n/d+(n%d<1?"":","+f(d,n%d));}

Takes integer or fraction or decimal as String, 311 bytes

String c(String i){try{return""+Integer.decode(i);}catch(Exception e){int o=i.indexOf(46);if(o>=0)return c((i+"/"+Math.pow(10,i.length()-o-2)).replaceAll("\\.",""));String[]a=i.split("/");int n=Integer.decode(a[0]),d=Integer.decode(a[1]);return n<0?"-"+c(2*(d+n%d)-n+"/"+d):n%d<1?""+n/d:n/d+","+c(d+"/"+(n%d));}}

Sample input/output:

860438
860438

3.245
3,4,12,4

-4.2
-5,1,4

-114.7802
-115,4,1,1,4,1,1,5,1,1,4

0/11
0

1/42
0,42

2/7
0,3,2

-18/17056
-1,1,946,1,1,4

-17056/18
-948,2,4

Actual input/output from full program:

860438
860438
860438
860438
860438
3.245
3,4,12,4
3,4,12,4
3,4,12,4
3,4,12,4
-4.2
-5,1,4
-5,1,4
-5,1,4
-5,1,4
-114.7802
-115,4,1,1,4,1,1,5,1,1,4
-115,4,1,1,4,1,1,5,1,1,4
-115,4,1,1,4,1,1,5,1,1,4
-115,4,1,1,4,1,1,5,1,1,4
0/11
0
0
0
0
1/42
0,42
0,42
0,42
0,42
2/7
0,3,2
0,3,2
0,3,2
0,3,2
-18/17056
-1,1,946,1,1,4
-1,1,946,1,1,4
-1,1,946,1,1,4
-1,1,946,1,1,4
-17056/18
-948,2,4
-948,2,4
-948,2,4
-948,2,4

Full program (including ungolfed functions):

import java.util.Scanner;

public class Q79483 {
    String cf_ungolfed(String input){
        try{
            int result = Integer.parseInt(input);
            return Integer.toString(result);
        }catch(Exception e){
            if(input.indexOf('.')>=0){
                int numerator = Integer.parseInt(input.replaceAll("\\.",""));
                int denominator = (int) Math.pow(10, input.length()-input.indexOf('.')-1);
                return cf_ungolfed(numerator+"/"+denominator);
            }
            int numerator = Integer.parseInt(input.substring(0,input.indexOf('/')));
            int denominator = Integer.parseInt(input.substring(input.indexOf('/')+1));
            if(numerator%denominator == 0){
                return Integer.toString(numerator/denominator);
            }
            if(numerator < 0){
                return "-"+cf_ungolfed((denominator-numerator+(denominator+2*(numerator%denominator)))+"/"+denominator);
            }
            return (numerator/denominator) + "," + cf_ungolfed(denominator+"/"+(numerator%denominator));
        }
    }
    String c(String i){try{return""+Integer.decode(i);}catch(Exception e){int o=i.indexOf(46);if(o>=0)return c((i+"/"+Math.pow(10,i.length()-o-2)).replaceAll("\\.",""));int n=Integer.decode(i.split("/")[0]),d=Integer.decode(i.split("/")[1]);return n<0?"-"+c(2*(d+n%d)-n+"/"+d):n%d<1?""+n/d:n/d+","+c(d+"/"+(n%d));}}
    String f_ungolfed(int numerator,int denominator){
        if(numerator%denominator == 0){
            return Integer.toString(numerator/denominator);
        }
        if(numerator < 0){
            return "-"+f_ungolfed((denominator-numerator+(denominator+2*(numerator%denominator))),denominator);
        }
        return (numerator/denominator) + "," + f_ungolfed(denominator,(numerator%denominator));
    }
    String f(int n,int d){return n<0?"-"+f(2*(d+n%d)-n,d):n/d+(n%d<1?"":","+f(d,n%d));}
    public static int[] format(String input){
        if(input.indexOf('.') != -1){
            int numerator = Integer.parseInt(input.replaceAll("\\.",""));
            int denominator = (int) Math.pow(10, input.length()-input.indexOf('.')-1);
            return new int[]{numerator,denominator};
        }
        if(input.indexOf('/') != -1){
            int numerator = Integer.parseInt(input.substring(0,input.indexOf('/')));
            int denominator = Integer.parseInt(input.substring(input.indexOf('/')+1));
            return new int[]{numerator,denominator};
        }
        return new int[]{Integer.parseInt(input),1};
    }
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            String input = sc.next();
            System.out.println(new Q79483().cf_ungolfed(input));
            System.out.println(new Q79483().c(input));
            int[] formatted = format(input);
            System.out.println(new Q79483().f_ungolfed(formatted[0], formatted[1]));
            System.out.println(new Q79483().f(formatted[0], formatted[1]));
        }
        sc.close();
    }
}

Answer 7

MATL, 29 bytes

`t1e7*Yo5M/kwy-t1e-5>?-1^T}xF

Try it online!

This works by repeatedly rounding and inverting (which I think is what Doorknob's answer does too). There may be numerical issues due to using floating point, but it works for all the test cases.

`         % Do...while
  t       %   Duplicate. Takes input implicitly the first time
  1e7*    %   Multiply by 1e7
  Yo      %   Round
  5M/     %   Divide by 1e7. This rounds to the 7th decimal, to try to avoid
          %   numerical precision errors
  k       %   Round
  w       %   Swap top two elements of stack
  y       %   Copy the secomnd-from-bottom element
  -       %   Subtract
  t       %   Duplicate
  1e-5>   %   Is it greater than 1e-5? (1e-5 rather than 0; this is again to 
          %   try to avoid numerical precision errors)          
  ?       %   If so
    -1^   %     Compute inverse
    T     %     Push true as loop condition (to start a new iteration)
  }       %   Else
    xF    %     Delete and push false (to exit loop)
          %   End if implicitly
          % End do...while implicitly
          % Display implicitly

Answer 8

Wolfram Language (Mathematica), 43 bytes

-4 from alephalpha

Floor@NestWhileList[1/t&,#,(t=#~Mod~1)>0&]&

Try it online!

Answer 9

Pyth, 15 bytes

M+]/GH?J%GHgHJY

Try it online! (The g.* at the end is to fetch the input.)

Answer 10

APL(NARS), 107 chars, 214 bytes

dd←{⍵=0:0⋄0>k←1∧÷⍵:-k⋄k}⋄nn←{1∧⍵}⋄f←{⍵=0:0x⋄m←⎕ct⋄⎕ct←0⋄z←{0=(d←dd⍵)∣n←nn⍵:n÷d⋄r←⌊n÷d⋄r,∇d÷n-r×d}⍵⋄⎕ct←m⋄z}

The function of the exercise f, should have as input one rational number (where 23r33 means as "23/33" in math) ...The algo is the same of the one Neil posted as JavaScript solution... test

  f 860438r1
860438 
  f 3245r1000
3 4 12 4 
  f ¯42r10
¯5 1 4 
  f ¯1147802r10000
¯115 4 1 1 4 1 1 5 1 1 4 
  f 0r11
0 
  f 1r42
0 42 
  f 2r7
0 3 2 
  f ¯18r17056
¯1 1 946 1 1 4 
  f ¯17056r18
¯948 2 4 
  f 17056r¯18
¯948 2 4  
  f 18r¯17056
¯1 1 946 1 1 4 
  f 123r73333333333333333333333333373
0 596205962059620596205962059 1 16 1 1 3 
  +∘÷/f 123r73333333333333333333333333373
123r73333333333333333333333333373

Answer 11

Python 3, 46 bytes

f=lambda n,d:[n//d]+(n%d*[0]and f(d,n-n//d*d))

Try it online!

Port of Neil's javascript answer

Answer 12

Scala, 72 bytes

Golfed version. Try it online!

(n,d)=>if(n<0)"-"+f(2*(d+n%d)-n,d)else n/d+(if(n%d<1)""else","+f(d,n%d))

Answer 13

C# (Visual C# Interactive Compiler), 222 bytes/75 bytes

A function that takes a string, 222 bytes

(a,o)=>{var@b=$"{a}/1".Split("/");var@c=$"{b[0]}.0".Split(".");int@n=int.Parse(c[0]),m=int.Parse(c[1]),d=1,r;for(;d<m;d*=10);for(n=n*d+(n>0?1:-1)*m,d*=int.Parse(b[1]);d>0;(n,d)=(d,n-r*d))o.Add(r=(int)Math.Floor(1m*n/d));};

Try it online!

Just the part that takes numerator and denominator, 75 bytes

(n,d,o)=>{for(int@r;d>0;(n,d)=(d,n-r*d))o.Add(r=(int)Math.Floor(1m*n/d));};

Try it online!

Un-golfed code:

(input, output) =>
{
	var fracStr = $"{input}/1".Split("/"); // append "/1" so we never get an array out of bounds
	var decStr = $"{fracStr[0]}.0".Split("."); // append ".0" so we never get an array out of bounds

	// parse the decimal number first,
	// if we weren't passed a decimal, m will be 0
	int n = int.Parse(decStr[0]);
	int m = int.Parse(decStr[1]);
	int d = 1;

	// denominator will be the next power of 10 larger than m:
	for (; d < m; d *= 10);

	// scale the numerator by the denominator, and add the decimal part:
	n = n * d + (n > 0 ? 1 : -1) * m;

	// now handle the fraction case
	// if we weren't passed a fraction then fracStr[1] will be "1"
	// if we were passed a fraction, d will be 1
	d *= int.Parse(fracStr[1]);

	// now actually calculate the continued fraction:
	for (; d > 0; )
	{
		int r = (int)Math.Floor(1m * n / d);
		output.Add(r);
		(n, d) = (d, n - r * d);
	}
};