4
\$\begingroup\$

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

Jelly, 16 13 12 bytes

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

Try it online!

\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
  • 1
    \$\begingroup\$ 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 \$\endgroup\$ – Value Ink May 5 '16 at 22:28
  • \$\begingroup\$ At any rate, here's a tip for you: a<<n.floor should save you 2 bytes. \$\endgroup\$ – Value Ink May 5 '16 at 22:33
  • \$\begingroup\$ @KevinLau-notKenny Oh hey I learned a thing! \$\endgroup\$ – Doorknob May 5 '16 at 22:39
  • 1
    \$\begingroup\$ Rational("3.245") is not allowed, you need to include Rational in the code as the OP requested on my answer. \$\endgroup\$ – orlp May 5 '16 at 22:51
  • \$\begingroup\$ 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. \$\endgroup\$ – mbomb007 May 6 '16 at 0:07
3
\$\begingroup\$

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)]:[])}
\$\endgroup\$
  • \$\begingroup\$ s.floor -> s.to_i should save a byte. \$\endgroup\$ – Doorknob May 6 '16 at 2:19
  • \$\begingroup\$ @Doorknob♦ It won't. floor rounds towards -∞ while to_i truncates towards 0, so the negative test cases give the wrong results. \$\endgroup\$ – Value Ink May 6 '16 at 4:37
2
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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

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

Pyth, 15 bytes

M+]/GH?J%GHgHJY

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

\$\endgroup\$
1
\$\begingroup\$

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();
    }
}
\$\endgroup\$
  • \$\begingroup\$ Don't catch errors, throw them. \$\endgroup\$ – Bálint May 6 '16 at 14:08
  • \$\begingroup\$ Why is each test case output four times? \$\endgroup\$ – mbomb007 May 6 '16 at 17:15
  • \$\begingroup\$ @mbomb007 Because I called four functions. Look at the last few lines of the full program. \$\endgroup\$ – Leaky Nun May 6 '16 at 17:16
  • \$\begingroup\$ @mbomb007 Done. \$\endgroup\$ – Leaky Nun May 6 '16 at 17:22

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.