# Continued Fraction of a Rational Number

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: [a0; a1, a2, a3, ..., an].

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 a0 and a1, 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.
• – mbomb007 May 5 '16 at 22:02
• Can the input be required to be a fraction/rational type (which would require inputting the decimal 3.245 as 3245/1000 or similar)? – Doorknob May 5 '16 at 22:05
• Mathematica wins >:| – Conor O'Brien May 5 '16 at 22:14
• What if there are several solutions? Is '3' '2' '3' '-6' acceptable for 3.245? Also, are leading 0 convergents accepted? – Luis Mendo May 5 '16 at 22:17
• @LuisMendo What method is used to find alternate solutions? The program I created only finds positive convergents. – mbomb007 May 5 '16 at 22:37

# Jelly, 1613 12 bytes

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


Try it online!

## Ruby, 4543 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!

• It hurts, to be beaten by 5 minutes and with a better solution in the same language... Hadn't thought of n%1, have a +1 – Value Ink May 5 '16 at 22:28
• At any rate, here's a tip for you: a<<n.floor should save you 2 bytes. – Value Ink May 5 '16 at 22:33
• @KevinLau-notKenny Oh hey I learned a thing! – Doorknob May 5 '16 at 22:39
• Rational("3.245") is not allowed, you need to include Rational in the code as the OP requested on my answer. – orlp May 5 '16 at 22:51
• Correct. The internal representation of a rational is as a numerator and a denominator, so this wouldn't count as handling decimal. As a user, I would want to literally be able to pass the decimals or their string representations in the examples as the input. – mbomb007 May 6 '16 at 0:07

# 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)]:[])}

• s.floor -> s.to_i should save a byte. – Doorknob May 6 '16 at 2:19
• @Doorknob♦ It won't. floor rounds towards -∞ while to_i truncates towards 0, so the negative test cases give the wrong results. – Value Ink May 6 '16 at 4:37

## 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].

• What... f=(n,d)=> is allowed?? – Leaky Nun May 6 '16 at 14:12
• @KennyLau That's a lambda. – Bálint May 6 '16 at 14:16
• I mean, it is allowed to only take fraction? – Leaky Nun May 6 '16 at 14:17
• @KennyLau Input may be as a string or numbers, but not a decimal. So that was the best that I could do. – Neil May 6 '16 at 14:18

# 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();
}
}

• Don't catch errors, throw them. – Bálint May 6 '16 at 14:08
• Why is each test case output four times? – mbomb007 May 6 '16 at 17:15
• @mbomb007 Because I called four functions. Look at the last few lines of the full program. – Leaky Nun May 6 '16 at 17:16
• @mbomb007 Done. – Leaky Nun May 6 '16 at 17:22

# 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


# Pyth, 15 bytes

M+]/GH?J%GHgHJY


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

# 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


# Python 3, 46 bytes

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


Try it online!