arctan (1/u)

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
temper_3243
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am

arctan (1/u)

Post by temper_3243 »

Code: Select all

arctan(1/x) + arctan(1/y) = arctan(1/u)

u will be given, find the minimal sum x+y , x,y,u are all positive
integers

1/x + 1/y
---------  =  1/u
1 - 1/xy

u*(x+y) = xy-1

let x+y = k ,

then u*k = x*(k-x) -1 ,
     x^2 -x*k +u*k +1 =0
     x should i have real roots
     x={-k+- sqrt(k^2 - 4u*k -4)}/2

     so k^2 -4u*k -4 should be a perfect square , minimal k for which
k^2 -4u*k -4 is a perfect square

we have iterate through k to find out, for k=3072 or some number close
3000 i couldn't find k until 10^7 , how do we solve this

am i going in the right direction 

Quantris
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
Location: Edmonton AB Canada

Post by Quantris »

Sorry, you're not even close....

Why do you assume "k" has to be an integer? There is no reason that k^2-4uk-4 should be a perfect square, you only need it to be positive.

If this is homework, have you done Lagrange multipliers? Or any calculus at all??

I can tell you that you'll probably need a derivative. Or appeal to intuition to say that the minimum x+y happens when x = y.

You can get this from your expression by solving for "k" in terms of "x", and taking the derivative to find an extremum (you should get an extremum at x = k/2, so x = y = k/2).

Then you'll find that the min. value of k is 2u+2sqrt(u^2+1), keeping in mind that k > 0.

7erry
New poster
Posts: 6
Joined: Wed Feb 21, 2007 7:40 pm

Post by 7erry »

This problem is not a homework, it's from SPOJ. I don't know what you mention, k must be an integer (for this problem) and I think temper_3243 can easily solve this if k is not (without anything called Lagrange multipliers...). What he needs is that someone can help him to solve the problem.

Post Reply

Return to “Algorithms”