12
\$\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].
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!

Improve this question
\$\endgroup\$
5
  • 1
    \$\begingroup\$ Does the output have to be in the same format as the test cases? \$\endgroup\$ – grc Jun 18 '12 at 7:36
  • \$\begingroup\$ No. As long as you have the semicolons, it's fine. \$\endgroup\$ – beary605 Jun 18 '12 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 '12 at 18:28
  • \$\begingroup\$ Yep, that's the limit. \$\endgroup\$ – beary605 Jun 22 '12 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 '12 at 12:35
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.

Improve this answer
\$\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 '12 at 20:54
  • 1
    \$\begingroup\$ @boothby, don't be crazy. Your life won't be complete without GS ;) \$\endgroup\$ – Peter Taylor Jun 21 '12 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.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ What is the purpose of *(c*c-n)? \$\endgroup\$ – Peter Taylor Jun 21 '12 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 '12 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;
Improve this answer
\$\endgroup\$
6
  • \$\begingroup\$ x-int(x) -> x%1. I am impressed :) \$\endgroup\$ – beary605 Jun 18 '12 at 20:30
  • \$\begingroup\$ Gives the wrong result for √139 according to Wolfram Alpha \$\endgroup\$ – breadbox Jun 18 '12 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 '12 at 4:32
  • \$\begingroup\$ I find it incredibly interesting that it always ends in 2*int(sqrt(a)). \$\endgroup\$ – beary605 Jun 19 '12 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 '12 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}}
Improve this answer
\$\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 '12 at 14:38
  • \$\begingroup\$ @beary605 Fair enough. \$\endgroup\$ – DavidC Jun 19 '12 at 17:41
  • 2
    \$\begingroup\$ +1 Better yet (25 chars) ContinuedFraction@Sqrt@#& \$\endgroup\$ – Dr. belisarius Jun 20 '12 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\$ – Peter Taylor Jun 20 '12 at 13:19
  • \$\begingroup\$ @Peter Taylor Please see the amendment. \$\endgroup\$ – DavidC Jun 20 '12 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]
Improve this answer
\$\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 '12 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 '12 at 15:22
  • \$\begingroup\$ ^^ Yep. Fixed my code. \$\endgroup\$ – beary605 Jun 18 '12 at 20:24
  • \$\begingroup\$ This version gives the wrong result for 139. \$\endgroup\$ – breadbox Jun 19 '12 at 16:46
  • \$\begingroup\$ @boothby Then I'll delete mine and we'll call it a draw :) \$\endgroup\$ – JoeFish Jun 21 '12 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;
Improve this answer
\$\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.

Improve this answer
\$\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()...

Improve this answer
\$\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 '19 at 7:00
  • \$\begingroup\$ Q←Q÷⍨ - does nars support Q÷⍨←? \$\endgroup\$ – ngn Jul 28 '19 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 '19 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.