7
\$\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\$
7
  • \$\begingroup\$ Related: Determining the continued fractions of square roots \$\endgroup\$
    – mbomb007
    May 5, 2016 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, 2016 at 22:05
  • 1
    \$\begingroup\$ Mathematica wins >:| \$\endgroup\$ May 5, 2016 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, 2016 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, 2016 at 22:37

9 Answers 9

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\$
6
  • 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, 2016 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, 2016 at 22:33
  • \$\begingroup\$ @KevinLau-notKenny Oh hey I learned a thing! \$\endgroup\$
    – Doorknob
    May 5, 2016 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, 2016 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, 2016 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\$
2
  • \$\begingroup\$ s.floor -> s.to_i should save a byte. \$\endgroup\$
    – Doorknob
    May 6, 2016 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, 2016 at 4:37
2
\$\begingroup\$

Jelly, 16 13 12 bytes

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

Try it online!

\$\endgroup\$
2
\$\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\$
4
  • \$\begingroup\$ What... f=(n,d)=> is allowed?? \$\endgroup\$
    – Leaky Nun
    May 6, 2016 at 14:12
  • \$\begingroup\$ @KennyLau That's a lambda. \$\endgroup\$
    – Bálint
    May 6, 2016 at 14:16
  • \$\begingroup\$ I mean, it is allowed to only take fraction? \$\endgroup\$
    – Leaky Nun
    May 6, 2016 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, 2016 at 14:18
2
\$\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\$
4
  • \$\begingroup\$ Don't catch errors, throw them. \$\endgroup\$
    – Bálint
    May 6, 2016 at 14:08
  • \$\begingroup\$ Why is each test case output four times? \$\endgroup\$
    – mbomb007
    May 6, 2016 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, 2016 at 17:16
  • \$\begingroup\$ @mbomb007 Done. \$\endgroup\$
    – Leaky Nun
    May 6, 2016 at 17:22
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\$

Pyth, 15 bytes

M+]/GH?J%GHgHJY

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

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

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

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

\$\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.