13
\$\begingroup\$

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

$$a_0 + \cfrac 1 {a_1 + \cfrac 1 {a_2 + \cfrac 1 {a_3 + \cfrac 1 {a_4 + \ddots}}}}$$

which converges to \$n\$.

The sequence \$a\$ in a continued fraction is typically written as: \$[a_0; a_1, a_2, a_3, ... a_n]\$.
We will write ours in the same fashion, but with the repeating part between semicolons.

Your goal is to return the continued fraction of the square root of \$n\$.

Input: An integer, \$n\$. \$n\$ will never be a perfect square.
Output: The continued fraction of \$\sqrt n\$.

Test Cases:
2 -> [1; 2;]
3 -> [1; 1, 2;]
19 -> [4; 2, 1, 3, 1, 2, 8;]

Shortest code wins. Good luck!

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Does the output have to be in the same format as the test cases? \$\endgroup\$
    – grc
    Jun 18, 2012 at 7:36
  • \$\begingroup\$ No. As long as you have the semicolons, it's fine. \$\endgroup\$
    – beary605
    Jun 18, 2012 at 20:30
  • \$\begingroup\$ Hm, getting the right answers, having trouble knowing when the fraction is rational to stop. Is it really as simple as when a<sub>0</sub> is double the sqrt of the original input? \$\endgroup\$
    – JoeFish
    Jun 21, 2012 at 18:28
  • \$\begingroup\$ Yep, that's the limit. \$\endgroup\$
    – beary605
    Jun 22, 2012 at 5:27
  • \$\begingroup\$ @beary605 thanks. Been doing a lot more reading, and now I see that the continued fraction of a square root is a bit of a special case. Fascinating stuff! Still working on a non-floating point version. \$\endgroup\$
    – JoeFish
    Jun 22, 2012 at 12:35

8 Answers 8

4
\$\begingroup\$

GolfScript (66 60 chars)

~:^,{.*^>}?(:?';'[1?{^1$.*-@/?@+.2$/@@1$%?\- 1$(}do;;]','*1$

Warning: most of the ? in there are the variable representing floor(sqrt(input)) rather than the builtin. But the first one is the builtin.

Takes input on stdin and outputs to stdout.

Psuedocode of the algorithm (proof of correctness currently left as an exercise for the reader):

n := input()
m := floor(sqrt(n))
output(m)
x := 1
y := m
do
  x := (n - y * y) / x
  output((m + y) / x)
  y := m - (m + y) % x
while (x > 1)

Yet again I find myself wanting a single operator which takes a b on the stack and leaves a/b a%b on the stack.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ I'd say that I really need to learn GS... but need is a bit too strong a word here ;) \$\endgroup\$
    – boothby
    Jun 21, 2012 at 20:54
  • 1
    \$\begingroup\$ @boothby, don't be crazy. Your life won't be complete without GS ;) \$\endgroup\$ Jun 21, 2012 at 22:15
3
\$\begingroup\$

Python, 95 97 (but correct...)

This uses only integer arithmetic and floor division. This will produce correct results for all positive integer inputs, though if one wants to use a long, they'd have to add a character; for example m=a=0L. And of course... wait for a million years for my poor man's floor sqrt to terminate.

z=x=m=1
while n>m*m:m+=1
m=y=m-1
l=()
while-z<x:x=(n-y*y)/x;y+=m;l+=y/x,;y=m-y%x;z=-1
print c,l

Output:

n=139
11 (1, 3, 1, 3, 7, 1, 1, 2, 11, 2, 1, 1, 7, 3, 1, 3, 1, 22)

edit: now using Peter Taylor's algorithm. That do...while was fun.

\$\endgroup\$
2
  • \$\begingroup\$ What is the purpose of *(c*c-n)? \$\endgroup\$ Jun 21, 2012 at 16:27
  • \$\begingroup\$ @PeterTaylor, I hadn't read the challenge carefully enough, and made the code work for perfect squares. \$\endgroup\$
    – boothby
    Jun 21, 2012 at 18:41
2
\$\begingroup\$

Python, 87 82 80

x=r=input()**.5
while x<=r:print"%d"%x+",;"[x==r],;x=1/(x%1)
print`int(r)*2`+";"

It takes one integer and gives output like:

4; 2, 1, 3, 1, 2, 8;
\$\endgroup\$
6
  • \$\begingroup\$ x-int(x) -> x%1. I am impressed :) \$\endgroup\$
    – beary605
    Jun 18, 2012 at 20:30
  • \$\begingroup\$ Gives the wrong result for √139 according to Wolfram Alpha \$\endgroup\$
    – breadbox
    Jun 18, 2012 at 21:41
  • \$\begingroup\$ I've updated it to work for √139. However, if the length of the sequence gets much longer (√139 has a sequence of 18 numbers), then the result will probably start to lose accuracy. \$\endgroup\$
    – grc
    Jun 19, 2012 at 4:32
  • \$\begingroup\$ I find it incredibly interesting that it always ends in 2*int(sqrt(a)). \$\endgroup\$
    – beary605
    Jun 19, 2012 at 14:42
  • \$\begingroup\$ Further interesting is now 3 of us have broken code for 139 (mine is still un-golfed and un-posted). \$\endgroup\$
    – JoeFish
    Jun 21, 2012 at 18:50
2
\$\begingroup\$

Mathematica 33 31

c[n_]:=ContinuedFraction@Sqrt@n

Output is in list format, which is more appropriate for Mathematica. Examples:

c[2]
c[3]
c[19]
c[139]
c[1999]

(* out *)
{1, {2}}
{1, {1, 2}}
{4, {2, 1, 3, 1, 2, 8}}
{11, {1, 3, 1, 3, 7, 1, 1, 2, 11, 2, 1, 1, 7, 3, 1, 3, 1, 22}}
{44, {1, 2, 2, 4, 1, 1, 5, 1, 5, 8, 1, 3, 2, 1, 2, 1, 1, 1, 1, 1, 1, 
  1, 14, 3, 1, 1, 29, 4, 4, 2, 5, 1, 1, 17, 2, 1, 12, 9, 1, 5, 1, 43, 
  1, 5, 1, 9, 12, 1, 2, 17, 1, 1, 5, 2, 4, 4, 29, 1, 1, 3, 14, 1, 1, 
  1, 1, 1, 1, 1, 2, 1, 2, 3, 1, 8, 5, 1, 5, 1, 1, 4, 2, 2, 1, 88}}
\$\endgroup\$
9
  • 1
    \$\begingroup\$ Oh man, I totally expected this answer. I won't consider it as an actual answer, unless you generate the continued fraction yourself. \$\endgroup\$
    – beary605
    Jun 19, 2012 at 14:38
  • \$\begingroup\$ @beary605 Fair enough. \$\endgroup\$
    – DavidC
    Jun 19, 2012 at 17:41
  • 2
    \$\begingroup\$ +1 Better yet (25 chars) ContinuedFraction@Sqrt@#& \$\endgroup\$ Jun 20, 2012 at 0:55
  • \$\begingroup\$ What exactly are you counting here? Is this a program which takes input from stdin? Because the way you use it looks like it's a function body without the function definition. \$\endgroup\$ Jun 20, 2012 at 13:19
  • \$\begingroup\$ @Peter Taylor Please see the amendment. \$\endgroup\$
    – DavidC
    Jun 20, 2012 at 13:58
1
\$\begingroup\$

Python (136 133 96)

The standard method for continued fractions, extremely golfed.

a=input()**.5
D=c=int(a);b=[]
while c!=D*2:a=1/(a%1);c=int(a);b+=[c]
print D,";%s;"%str(b)[1:-1]
\$\endgroup\$
5
  • \$\begingroup\$ You can save a few chars by using while 1:. You could also put most of the statements in the while loop on a single line. \$\endgroup\$
    – grc
    Jun 18, 2012 at 7:34
  • \$\begingroup\$ When I run your script, I get an output of 8 ;1; for 74 and for 75; that doesn't seem right. It hangs on 76. \$\endgroup\$
    – breadbox
    Jun 18, 2012 at 15:22
  • \$\begingroup\$ ^^ Yep. Fixed my code. \$\endgroup\$
    – beary605
    Jun 18, 2012 at 20:24
  • \$\begingroup\$ This version gives the wrong result for 139. \$\endgroup\$
    – breadbox
    Jun 19, 2012 at 16:46
  • \$\begingroup\$ @boothby Then I'll delete mine and we'll call it a draw :) \$\endgroup\$
    – JoeFish
    Jun 21, 2012 at 18:42
1
\$\begingroup\$

C, 137

Including the newline, assuming I don't have to roll my own square root.

#include<math.h>
main(i,e){double d;scanf("%lf",&d);e=i=d=sqrt(d);while(i^e*2)printf("%d%c",i,e^i?44:59),i=d=1.0/(d-i);printf("%d;",i);}

It breaks for sqrt(139) and contains the occasional extra semicolon in the output, but I'm too tired to work on it further tonight :)

5
2;4;
19
4;2,1,3,1,2,8;
111
10;1,1,6,1,1,20;
\$\endgroup\$
1
\$\begingroup\$

Perl, 99 chars

Does not screw up on 139, 151, etc. Tested with number ranging from 1 to 9 digits.

$"=",";$%=1;$==$-=($n=<>)**.5;
push@f,$==(($s=$=*$%-$s)+$-)/($%=($n-$s*$s)/$%)until$=>$-;
say"$-;@f;"

Note: $%, $=, and $- are all integer-forcing variables.

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

APL(NARS), 111 chars, 222 bytes

r←f w;A;a;P;Q;m
m←⎕ct⋄Q←1⋄⎕ct←P←0⋄r←,a←A←⌊√w⋄→Z×⍳w=0
L: →Z×⍳0=Q←Q÷⍨w-P×P←P-⍨a×Q⋄r←r,a←⌊Q÷⍨A+P⋄→L×⍳Q>1
Z: ⎕ct←m

The f function is based on the algo one find in the page http://mathworld.wolfram.com/PellEquation.html for solve Pell equation. That f function has its input all not negative number (type fraction too). Possible there is something goes wrong, I remember that √ has, in how I see it, problem for big fraction numbers, as

  √13999999999999999999999999999999999999999999999x
1.183215957E23 

so there would be one function sqrti(). For this reason fraction input (and integer input) has to be <10^15. test:

 ⎕fmt (0..8),¨⊂¨f¨0..8
┌9───────────────────────────────────────────────────────────────────────────────────────────────────────┐
│┌2─────┐ ┌2─────┐ ┌2───────┐ ┌2─────────┐ ┌2─────┐ ┌2───────┐ ┌2─────────┐ ┌2─────────────┐ ┌2─────────┐│
││  ┌1─┐│ │  ┌1─┐│ │  ┌2───┐│ │  ┌3─────┐│ │  ┌1─┐│ │  ┌2───┐│ │  ┌3─────┐│ │  ┌5─────────┐│ │  ┌3─────┐││
││0 │ 0││ │1 │ 1││ │2 │ 1 2││ │3 │ 1 1 2││ │4 │ 2││ │5 │ 2 4││ │6 │ 2 2 4││ │7 │ 2 1 1 1 4││ │8 │ 2 1 4│││
││~ └~─┘2 │~ └~─┘2 │~ └~───┘2 │~ └~─────┘2 │~ └~─┘2 │~ └~───┘2 │~ └~─────┘2 │~ └~─────────┘2 │~ └~─────┘2│
│└∊─────┘ └∊─────┘ └∊───────┘ └∊─────────┘ └∊─────┘ └∊───────┘ └∊─────────┘ └∊─────────────┘ └∊─────────┘3
└∊───────────────────────────────────────────────────────────────────────────────────────────────────────┘
  f 19
4 2 1 3 1 2 8 
  f 54321x
233 14 1 1 3 2 1 2 1 1 1 1 3 4 6 6 1 1 2 7 1 13 4 11 8 11 4 13 1 7 2 1 1 6 6 4 3 1 1 1 1 2 1 2 3 1 1 14 466 
  f 139
11 1 3 1 3 7 1 1 2 11 2 1 1 7 3 1 3 1 22 
  +∘÷/f 139
11.78982612
  √139
11.78982612

if the argument is a square of a number it would return one list of 1 only element, the sqrt of that number

  f 4
2 

If it would depend from me, in one exercise without "codegolf" I would prefer the previous edit that use function sqrti()...

\$\endgroup\$
3
  • 1
    \$\begingroup\$ surely you can use single-letter names instead of fq and a0. also: (a×Q)-P -> P-⍨a×Q \$\endgroup\$
    – ngn
    Jul 28, 2019 at 7:00
  • \$\begingroup\$ Q←Q÷⍨ - does nars support Q÷⍨←? \$\endgroup\$
    – ngn
    Jul 28, 2019 at 7:01
  • \$\begingroup\$ @ngn : I don't like to use " Q÷⍨←" in a chain of multiple assignment formula...for the remain agree... Possible I say that because I saw C Undefined Behavior \$\endgroup\$
    – user58988
    Jul 28, 2019 at 7:30

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.