Wikipedia:Reference desk/Archives/Mathematics/2009 October 4

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

October 4

Math

3^x-2^x+5^x=30 —Preceding unsigned comment added by THKhamosh (talk • contribs) 04:42, 4 October 2009 (UTC)

Just to rewrite this: 3^x − 2^x + 5^x = 30. ~~ Dr Dec (Talk) ~~ 11:11, 4 October 2009 (UTC)

x = 2. I don't know how to solve such a problem but it's easy to guess easy solutions and x = 2 works. StatisticsMan (talk) 04:50, 4 October 2009 (UTC)

...and no other real solution exists, for the LHS is strictly increasing in x. --84.221.208.114 (talk) 09:20, 4 October 2009 (UTC)

There appear to be a whole bunch of complex solutions. Newton-Raphson gives 2.310309-7.566221i, 2.35323-19.4722i, 1.90159+11.73987i, etc etc depending on starting value. HTH, Robinh (talk) 10:09, 4 October 2009 (UTC)

• This is probably best solved graphically, if x is real and you don't want to be guessing. I don't know of an algebraic method, and neither do the people I asked on IRC. —Anonymous Dissident^Talk 12:06, 4 October 2009 (UTC)

Newton-Raphson method would only yield approximation (2.0000...)and such is not needed in this case, you probably better follow the advise of StatisticsMan-it's not too elegant or sophisticated, but here it's very obvious that placing 2 instead of the Xs would give you the solution.--Gilisa (talk) 12:37, 4 October 2009 (UTC)

Hi guys. I used Newton-Raphson with complex arithmetic. Seems that the real part of the answer is always close to 2.0 (at least, I failed to find any roots with real part far away from 2.0). Comments anyone? Robinh (talk) 20:05, 4 October 2009 (UTC)

That makes sense. The real part corresponds to moduli of the terms and the imaginary part to the arguments. You can choose the imaginary part to get pretty much whatever arguments you want for each of the three terms since ln2, ln3 and ln5 don't have rational ratios. The real part is is bounded by the real solution to 5^x + 2^x + 3^x = 30 and the real solution to 5^x - 2^x - 3^x = 30. Those are both around 2. In fact the real parts of all the solutions should be dense in that interval. Rckrone (talk) 21:22, 4 October 2009 (UTC)

A good way to find exact solutions of difficult equations is to apply Newton-Raphson, plug the result in Plouffe's inverter, and validate. Of course, in this case, once we get to 2.000000000, we don't need Plouffe's. -- Meni Rosenfeld (talk) 20:34, 5 October 2009 (UTC)

The transcendental function 3^x-2^x+5^x-30 can be expanded as a taylor series, truncated to say 9 terms, and the roots of the resulting polynomial computed by standard methods. Using the J (programming language) you write p.(_30 + (3&^) + (5&^) - (2&^)) t. i. 9 and get the answer

┌───────┬────────────────────────────────────────────────────────────────────────────┐
│0.00117│_3.96 _2.93j2.62 _2.93j_2.62 _0.452j3.79 _0.452j_3.79 1.83j3.24 1.83j_3.24 2│
└───────┴────────────────────────────────────────────────────────────────────────────┘

The last root in the list is x=2. The other roots in the list are no good because the degree of the polynomial is too small to provide a good approximations out there. Bo Jacoby (talk) 23:33, 4 October 2009 (UTC).

In this specific case I think that better way than using numerical analysis would be to think on P^x space as a vectorial space and to dismantl and compare the coordinates of the measured vector.--Gilisa (talk) 07:36, 5 October 2009 (UTC)

Interesting! Could you elaborate on that? Bo Jacoby (talk) 14:23, 5 October 2009 (UTC).

trigonometry

what is sin cos and tan in a triangle —Preceding unsigned comment added by Ashishsihora (talk • contribs) 08:19, 4 October 2009 (UTC)

See Trigonometry. They are the ratios of sides of a triangle. -- SGBailey (talk) 08:46, 4 October 2009 (UTC)

Best way to calculate if a line crosses another line, or a polygon.

Dealing with X,Y coordinates, I have two lines within a large rectangle, with the x,y coordinates of all four ends of the lines being known. Neither of the lines extend from side to side of the rectangle. What would be the best way of calculating if they cross each other or not? This is for a computer program. And a more advanced question, how can I calculate if a line crosses a polygon or not? Thanks. 89.242.93.56 (talk) 11:36, 4 October 2009 (UTC)

• How are you defining the lines and the polygons? If you have equations then solve the equations simultaneously. Consider lines in the real xy-plane. If you have the lines given by the equations a₁x + b₁y + c₁ = 0 and a₂x + b₂y + c₂ = 0 where a_i, b_j, c_k ∈ R then there are three cases. Assume that a₁ and b₁ are not both zero and that a₂ and b₂ are not both zero. (This means the solutions are actually lines!)

1. If a₁b₂ − a₂b₁ ≠ 0 then x = (b₁c₂ − b₂c₁) / (a₁b₂ − a₂b₁) and y = (a₁c₂ − a₂c₁) / (a₁b₂ − a₂b₁).
2. If a₁b₂ − a₂b₁ = 0 then a₂ = λa₁ and b₂ = λb₁ for some non-zero λ ∈ R. If c₂ ≠ λc₁ then the lines are parallel; there is no solution.
3. If a₁b₂ − a₂b₁ = 0 and c₂ = λc₁ then the lines are the same line and all points are solutions.

If you have a polygon then the sides of the polygon are line segments and so will have equations. Just check that the intersection occur in these line segments, and not outside. So one side of the polygon might be the segment of the line x − y = 0 where 0 ≤ x ≤ 1 and so 0 ≤ y ≤ 1 too. Just check that the solution, if there is one, has 0 ≤ x ≤ 1 and 0 ≤ y ≤ 1. ~~ Dr Dec (Talk) ~~ 12:03, 4 October 2009 (UTC)

• If you're doing this in practice you have to be careful with parallel lines and horizontal and vertical lines, in fact avoid divides. 'Graphics Gems' is a nice introduction to computer code for things like this. Or just do a google of 'line segment intersection' and look around for reasonable code. Dmcq (talk) 12:13, 4 October 2009 (UTC)

Copying the code introduce you to the holy mantra of programmming Reduce reuse recycle ;-) Dmcq (talk) 12:24, 4 October 2009 (UTC)

• This might not be the easiest way, but you can define the orientation of three points in a specific order to positive if when you go from point to point you go counterclockwise and negative if you go clockwise. This is easy to do on a computer since the orientation can be computed as

$\operatorname {sgn} \left({\begin{vmatrix}x_{1}&y_{1}&1\\x_{2}&y_{2}&1\\x_{3}&y_{3}&1\end{vmatrix}}\right)$

So if your line segments are P₁ = (x₁, y₁) to P₂ = (x₂, y₂) and P₃ = (x₃, y₃) to P₄ = (x₄, y₄) then they cross iff

1. (P₁P₂P₃) and (P₁P₂P₄) have opposite orientations
2. (P₁P₃P₄) and (P₂P₃P₄) have opposite orientations.

You need to find four determinants with this method; if any of these are 0 then one of the endpoints lies on the other line, though not necessarily on the line segment, and it depends on what you mean by "cross" in that case.--RDBury (talk) 12:39, 4 October 2009 (UTC)

I do not have equations for the lines, just the x,y coordinates for the end points. I am not a mathematician, and neither myself or the computer language I am using understand matrices. I've just now thought that I could use a two-stage process to check for crossing lines - I could assume the lines are of unrestricted length, a) calculate where they cross, and then b) check if this crossing point is within the parts of the line that actually exist. Is there a simple equation to do a) please? This would I think work for polygons as well. 89.242.93.56 (talk) 12:47, 4 October 2009 (UTC)

• If a line segment has endpoints (p₁,q₁) and (p₂,q₂) then it is a segement of the line (q₁ − q₂)x − (p₁ − p₂)y + p₁q₂ − p₂q₁ = 0. Now re-apply my method from above. ~~ Dr Dec (Talk) ~~ 13:13, 4 October 2009 (UTC)

The determinant above is just x₁(y₂-y₃)-x₂(y₁-y₃)+x₃(y₁-y₂). Like I said it's easy to put it in a computer. Really though, it you want to know how to do geometry on a computer you pretty much have to learn matrices.--RDBury (talk) 13:27, 4 October 2009 (UTC)

Here's a C++ implementation of RDBury's solution. This is a better approach than the one below using slope-intercept form because it is more numerically stable and it avoids special cases. Even better is Dmcq's suggestion to use code from Graphics Gems, which can be found here. I didn't see code there for this particular problem, though (somewhat surprisingly).

            typedef SOME_NUMERIC_TYPE Coord;
            struct Point { Coord x, y; };
            struct LineSegment { Point p, q; };
            
            Coord TripleProduct(Point p, Point q, Point r) {
                return (q.x - p.x) * (r.y - p.y) - (q.y - p.y) * (r.x - p.x);
            }
            
            bool DoLineSegmentsIntersect(LineSegment a, LineSegment b) {
                return (TripleProduct(a.p, a.q, b.p) >= 0) != (TripleProduct(a.p, a.q, b.q) >= 0)
                    && (TripleProduct(b.p, b.q, a.p) >= 0) != (TripleProduct(b.p, b.q, a.q) >= 0);
            }

That code assumes that your line segments are closed (include the endpoints). To make them open or half-open, change >= to > just to the right of the points that you want to exclude. For example, to exclude b.p, change ... b.p) >= 0 ... by removing the = sign. -- BenRG (talk) 21:49, 4 October 2009 (UTC)

BenRG, please make me a bit smarter and explain me how exactly the ability to consider special cases is a disadvantage?--Gilisa (talk) 22:04, 4 October 2009 (UTC)

The solution above works in the special cases, they just aren't special—all cases are treated in the same way. The problem with slope-intercept form is that there's a danger of catastrophic precision loss in borderline cases. For example if the segment goes from (100, 100) to (100, 200) then you're fine (you can treat it as a special case) but if the segment goes from (100, 100) to (100.00001, 200) then the slope-intercept form is y = -999999900 + 10000000 x. When intermediate quantities change that dramatically with tiny changes to the input it's usually a problem because of roundoff error. With the solution above the numbers used in the calculation only change slightly when one of the input coordinates changes slightly. -- BenRG (talk) 22:38, 4 October 2009 (UTC)

So you see, as you wrote yourself my solution works aside for special cases, but they just aren't special ;-). I still think that for him/her it would be easier solution to implement as he/she don't know how to workout or to read matrix (unless you already wrote the code, and that's kind). Also, I chcked it, my solution work always. Cheers--Gilisa (talk) 06:51, 5 October 2009 (UTC)

There you go :

line A: from pixel P1 (x1,y1) to pixel P2 (x2,y2) line B: from pixel P3 (x3,y3) to pixel P4 (x4,y4)

line A can be described by the linear equation: Y = a1 * X + b1 given that pixels P1 and P2 are on this line, we will get the following equations:

1) y1 = a1 * x1 + b1 => b1 = y1 - a1 * x1 2) y2 = a1 * x2 + b1 => b1 = y2 - a1 * x2

two equations with two unknown parameters (a1, b1)

=> y1 - a1 * x1 = y2 - a1 * x2 => a1 * (x1 - x2) = y1 - y2 => (3) a1 = (y1-y2)/(x1-x2)

from eq. (1) we will get:

b1 = y1 - x1*(y1-y2)/(x1-x2)

=> b1 = [y1*(x1-x2)-x1*(y1-y2)]/(x1-x2)

=> (4) b1 = (x1*y2-x2*y1)/(x1-x2)

in a similar way we will get the next equations for line B:

(5) a2 = (y3-y4)/(x3-x4) (6) b2 = (x3*y4-x4*y3)/(x3-x4)

step 2) now, we will find the cross point (Xc,Yc):

a1* Xc + b1 = a2 * Xc + b2

=> Xc = (b2-b1)/(a1-a2) => Yc = a1*Xc + b1

all that left now is to find if the cross point apears on one of the lines , for example line A:

lets assume that X2 >= X1:

if X1<=Xc<=X2 the lines cross each other, otherwise they don't.

(if X1>=X2 we should check if X2<=Xc<=X1)

This is not the full solution, there are several cases that should be checked first, this is the full solution:

1. if x1=x2 and x3=x4:

          in that case, if max(y1,y2)>=max(y3,y4)  and min(y1,y2)<=max(y3,y4) the lines cross
          otherwise if max(y3,y4)>=max(y1,y2)  and min(y3,y4)<=max(y1,y2) the lines cross
          otherwise they don't.

2. otherwise, if x1=x2 (and x3 != x4)

           in that case: first we have to find a2, b2 as described above.
           then: Xc = X1, Yc = a2*X1 + b2
           if Yc<=max(y1,y2) and Yc>=(min(y1,y2) the lines cross
          otherwise the don't.

3. otherwise, if x3=x4 (and x1 != x2)

           in that case: first we have to find a1, b1 as described above in the regular solution.
           then: Xc = X3, Yc = a2*X3 + b2
           if Yc<=max(y3,y4) and Yc>=(min(y3,y4) the lines cross
          otherwise the don't.

4. otherwise:

   first we have to calculate a1, b1, a2, b2 as described above in the regular solution:
   4.1)   if a1=a2 (parallel lines)
                   if b1 != b2 the lines don't cross
                   otherwise (b1=b2)
                       if min(x1,x2)<=min(x3,x4) and max(x1,x2)>=min(x3,x4) the lines cross
                       otherwise if min(x3,x4)<=min(x1,x2) and max(x3,x4)>=min(x1,x2) the lines cross
                       otherwise they don't
   4.2) otherwise (a1!=a2), continue with the regular solution (from step 2).

definitions:

min(X,Y):

   if (X<Y) min(X,Y) = X
   otherwise min(X,Y) = Y

max(X,Y):

   if (X>Y) max(X,Y) = X
   otherwise max(X,Y) = Y

--Gilisa (talk) 14:07, 4 October 2009 (UTC)

What programming language are you using? There might well be a build in function for this (which will be easier to use than writing it yourself and will also be optimised so will run faster and with less memory than your own implementation is likely to). --Tango (talk) 20:36, 4 October 2009 (UTC)

C, what built in function you know for this? If you know better way feel free to write it, I'm sure it would help 89.242.93.56 alot--Gilisa (talk) 20:50, 4 October 2009 (UTC)

Sorry, my question was meant for the OP. There probably isn't a built in function in C, it's a pretty minimalist language. --Tango (talk) 23:33, 4 October 2009 (UTC)

And I was thinking that in this last reply you meant to OOP for some reason I couldn't realy get to, and only now understand that you meant to Open Protocal. --Gilisa (talk) 08:29, 5 October 2009 (UTC)

That's highly unlikely, he probably meant OP = original poster (i.e., 89.242.93.56). — Emil J. 12:11, 5 October 2009 (UTC)

Well, this is the kind of difficulties I have to face with as a non native English editor. This time I was refering to the link the OP (now I understand what the acronyms stand for) posted here, even it didn't include Open Protocol just few equations-as I couldn't find any other association in this context I get it hard to see how my post connecting to anything here now (probably confused it with Open Source)..Well, I'm hasty indeed.--Gilisa (talk) 12:18, 5 October 2009 (UTC)

Thanks. Sorry, I do not understand any of the above. But this webpage here http://geometryatlas.com/entries/41 seems to give a simple formula for the x.y coordinates. Is it correct please? I would check that the formulas would not be divided by zero - but would that indicate the lines were parallel, or what? (Edit - they would be parallel so can be disregarded). Would lines at right angles a problem? 78.146.166.105 (talk) 22:29, 4 October 2009 (UTC)

It looks correct but it's not a good choice for software implementation (see my replies above). I recommend using the code I wrote. -- BenRG (talk) 22:38, 4 October 2009 (UTC)

It is a very good choice, because it is simple to program and I can understand it. Speed is not an issue here. 78.149.191.96 (talk) 17:45, 5 October 2009 (UTC)

BenRG When I think again about what you wrote om my solution, it have a little sense. First, the screen resolution is limited to produce a case such as (100,100) and (100.0001, 200). And more, if we use variables which have enough bits (float, doubles) then my solution will always work.--Gilisa (talk) 08:50, 5 October 2009 (UTC)

There's code for 'Intersection of Line Segments' by Prasad, Mukesh in Graphics Gems II called xlines.c Dmcq (talk) 11:55, 5 October 2009 (UTC)

And I've just noticed it has another in Graphics Gems III 'Faster Line Segment Intersection' by Antonio Franklin. I must have a good study of those gems again. Perhaps I better get some more money too looking at the price of vol V and the way I buy books up. 12:06, 5 October 2009 (UTC)

Thinking about it; maybe the computing reference desk would have been a better place to post this computing based question. They deal with "Computing, information technology, electronics, software and hardware." ~~ Dr Dec (Talk) ~~ 17:58, 5 October 2009 (UTC)

The original question was about maths but the answers given have been computer related, and of no use to the OP regretably thanks for the effort / good intentions anyway. 78.144.240.57 (talk) 20:21, 5 October 2009 (UTC)

The OP said "This is for a computer program", I'm surprised if computer related answers are of no use. Dmcq (talk) 09:01, 6 October 2009 (UTC)

Powerful numbers

I don't understand the wikipedia article on powerful numbers.

Part 1 says (I think) m is powerful if its prime factors all come as at least squares. eg if a,b,c are all prime them we have a^2, a^3, a^77, a^2*b^2, a^3*b^4*c^77 as examples of powerful numbers. The list given appears to confirm this understanding.

Part 2 'rabbits on' about a^2*b^3, but 4 is powerful and that is only 2^2.

What is all this stuff about cubes for? Makes no sense (to me). -- SGBailey (talk) 22:47, 4 October 2009 (UTC)

The a²b³ part only requires a and b to be positive integers, not necessarily primes, so 4 = 2² × 1³ is fine. —JAO • T • C 22:54, 4 October 2009 (UTC)

Indeed. If n is a powerful number then any prime factors of n with odd exponents will have an exponent of 3 or greater. Make b the product of these prime factors with odd exponents (there may be none, in which case set b equal to 1). Then all the prime factors of n/b³ have even exponents and so n/b³ is a perfect square, which we can call a². For example, to put p³q⁴r⁷⁷ into the a²b³ form, we have b = pr, so

$p^{3}q^{4}r^{77}=(q^{2}r^{37})^{2}(pr)^{3}$ Gandalf61 (talk) 23:05, 4 October 2009 (UTC)