Author |
Topic: Non-integer colouring (Read 7304 times) |
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 2084
|
 |
Re: Non-integer colouring
« Reply #25 on: Jul 31st, 2007, 11:03am » |
 Quote  Modify
|
on Jul 31st, 2007, 10:31am, Barukh wrote:these are not exactly hyperbolas.  |
|
No? 
Each is the locus of points (x,y) where the difference of the distances to two fixed points, (0, 0) and either (u, v) or (p, q), is a constant, either i or j. I thought that was the definition of a hyperbola.
Edit: Oops! I'm an idiot. You mean you can't square an equation by just squaring each of the terms... dang it. I'm sure that wasn't Eigenray's mistake (his version has it right). Fixed, now. 
--SMQ
|
| « Last Edit: Jul 31st, 2007, 7:44pm by SMQ » |
 IP Logged |
--SMQ
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Non-integer colouring
« Reply #26 on: Jul 31st, 2007, 2:42pm » |
Quote Modify
|
on Jul 31st, 2007, 7:38am, SMQ wrote:
To restate, just to be sure I'm understanding: |
|
Yes, exactly. Thanks for summarizing.
Quote:| Although the fact that the triangles are Heronian is interesting, I'm not sure it's helpful. What if instead of generating Heronian triples, you generate Pythagorean triples? |
|
That'll work, I guess. But for example, with M=300, there are 209 Pythagorean triples, meaning 21945 possible triangles to check, 557 of which are integral, with the third side also no more than 300. On the other hand, using a list of 991 primitive Heronian triplets, there are 2080 non-primitive triplets; I try to embed 1037 of them, and end up with 582 distinct embeddings. I'm not sure where the discrepancy lies, but in both cases there are 517 congruence classes of triangles embedded.
[Heuristically, I'd guess that there are ~ 1/(2 ) M log M Pythagorean triples with hypotenuse < M, but I don't know how many pairs of triples give an integral triangle (and each triangle takes O(M2) to find a 4th point).]
I haven't really been trying to optimize my program; it's still written in Mathematica.
Quote:| Eigenray, how do compute this intersection? Again using Mathematica? |
|
I used Mathematica's Solve to find (x,y) as a function of u,v,p,q,i,j, and copy and pasted that expression (rather long, but of the form f+ g, where f,g are rational functions) into the code, but right now it still resorts to the Solve function when the denominator of the expression vanishes. The relevant discriminant here that needs to be a perfect square is
(a2-i2)(b2-j2)[(p-u)2 + (q-v)2 - (i-j)2]
but I haven't thought too much about why that is.
Perhaps I should try to contact Jock and ask for a bound on the triangle. If it's big, I'd probably need to rewrite the program in C for speed.
|
| « Last Edit: Jul 31st, 2007, 2:43pm by Eigenray » |
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Non-integer colouring
« Reply #27 on: Jul 31st, 2007, 7:47pm » |
Quote Modify
|
on Jul 31st, 2007, 2:42pm, Eigenray wrote:| I used Mathematica's Solve to find (x,y) as a function of u,v,p,q,i,j, and copy and pasted that expression (rather long, but of the form f+g, where f,g are rational functions) |
|
Could you post that expression? I have a C++ program already for generating Pythagorean triples and checking for the appropriate triangles, but I don't have access to Mathematica (not worth the price tag just for solving riddles... ), and working it through by hand is a bit, shall we say, daunting...
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
on Jul 31st, 2007, 7:47pm, SMQ wrote:
Could you post that expression? |
|
I'm sorry to say I've never discovered how to copy formulas out of Mathematica in a readable way. I just want the sequence of characters I would type to get it! I tried copy as plain text, formated text, text, mathml, CForm, FortranForm, TexForm, and sed'ing, but I think it's easier to just attach the picture. It should probably be simplified by hand some more too (Mathematica can be kinda dumb sometimes).
SOLVE[u,v,p,q,i,j] finds (x,y) as described when ip \neq ju (this condition seems to be sufficient, but no guarantees). The second solution, SOLVE[...][[2]], is the same as the first except changing the sign of the radicals in x,y.
If j=ip/u, then use the second formula. Again, the second solution is the same except for the sign of the radical (note that the y value remains unchanged).
I've never needed to, but if j=ip/u, and |i|=|u|, then you can use the third one (apparently the second solution is independent of the sign of i, which doesn't seem quite right, but I guess it doesn't matter if the (x,y) it finds isn't the one you were looking for).
Quote:| but I don't have access to Mathematica (not worth the price tag just for solving riddles... ) |
|
Does anyone buy it with real (i.e., not grant or corporate) money? I always use it to play around with stuff because it's so high level, but I've noticed from Project Euler that it's not uncommon for an equivalent C program to be 100 times faster. (But then, I've learned it through trial and error so I don't really know how to do things efficiently with it.)
|
| « Last Edit: Jul 31st, 2007, 9:21pm by Eigenray » |
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Non-integer colouring
« Reply #29 on: Aug 1st, 2007, 3:57am » |
Quote Modify
|
Isn't there an easier way to solve this system of DEs?
Maybe, Dave Rusin knows?
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Non-integer colouring
« Reply #30 on: Aug 1st, 2007, 8:41am » |
Quote Modify
|
Assuming my program is working, after eliminating all 2526 candidates with a  b < c, b 578, the triple/triangle a = 197 = (282+1952), b = 579 = (2852+5042), c = 676 = ((504-28)2+(285+195)2) appears to be a solution! 
(I'm certain that the program is finding all candidate triangles with a b < c, b N, and that the points (x,y) it's finding truely are an integer distance from all of (0,0), (u,v) and (p,q). I'm less certain that it didn't miss an (x,y) for the apparent solution.)
--SMQ
|
| « Last Edit: Aug 1st, 2007, 9:43am by SMQ » |
IP Logged |
--SMQ
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Non-integer colouring
« Reply #31 on: Aug 1st, 2007, 9:53am » |
Quote Modify
|
!
Awesome, SMQ!
Did you use the formulas in the last row of Eigenray's post?
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Non-integer colouring
« Reply #32 on: Aug 1st, 2007, 11:07am » |
Quote Modify
|
I'm afraid it may be a false positive. 
It looks like the denominator of the "big" equations can also go to 0 when iq = jv, and if those cases were ever to generate the only disqualifying point(s) for a candidate triangle, my program would erroneously flag it as a solution...
Eigenray, do you have/can you generate formulas for iq = jv (and presumably for iq = jv with |i| = |v|)?
Thanks.
on Jul 31st, 2007, 9:20pm, Eigenray wrote:| I'm sorry to say I've never discovered how to copy formulas out of Mathematica in a readable way. |
|
My Mathematica skills are more-than-a-bit rusty, but if memory serves, if you run the kernel directly, and not through the workbook frontend, do you still get a text-based interface?
--SMQ
|
| « Last Edit: Aug 1st, 2007, 1:34pm by SMQ » |
IP Logged |
--SMQ
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Non-integer colouring
« Reply #33 on: Aug 1st, 2007, 4:42pm » |
Quote Modify
|
on Aug 1st, 2007, 8:41am, SMQ wrote:| Assuming my program is working, after eliminating all 2526 candidates with a b < c, b 578, the triple/triangle a = 197 = (282+1952), b = 579 = (2852+5042), c = 676 = ((504-28)2+(285+195)2) appears to be a solution! |
|
Sorry, but SOLVE[[195, 28, -285, 504, -197, 205]] gives me the solution {-26520, -3808}. And the denominator is 37581796560, not zero.
on Aug 1st, 2007, 11:07am, SMQ wrote:| It looks like the denominator of the "big" equations can also go to 0 when iq = jv, |
|
Substituting j=iq/v into the big equation, the only thing in the denominator that could possibly be 0 is v2-i2. Setting i=v, j=q, I get
X = [q u^2 - p^2 v]/[2(qu-pv)],
Y = [(pu(p-u))^2 - (q u^2 - p^2 v)^2] / [4pu(p-u)(qu-pv)],
and the same result when i=-v, j=-q.
Quote:| My Mathematica skills are more-than-a-bit rusty, but if memory serves, if you run the kernel directly, and not through the workbook frontend, do you still get a text-based interface? |
|
Yes, with ascii-art output. So all the exponents appear a row above, and yabb eats half the spaces, so you can't tell what goes with what. I'm sure there's a way to turn that off though. Or I could do it in Maple. Copying from there, the last formula shows up as
{x = 1/2*(u^2*q-v*p^2)/(u*q-v*p), y = 1/4*(u^2*q-p*u^2-v*p^2+p^2*u)*(u^2*q+p*u^2-p^2*u-v*p^2) / (u*p*(u-p)*(u*q-v*p))}.
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Non-integer colouring
« Reply #34 on: Aug 1st, 2007, 7:40pm » |
Quote Modify
|
on Aug 1st, 2007, 4:42pm, Eigenray wrote:| Sorry, but SOLVE[[195, 28, -285, 504, -197, 205]] gives me the solution {-26520, -3808}. |
|
Hmm, there must be a memory issue or something with my prog. If I run just that set it finds it no problem, but if I let it run all the way up to it it's missed... strange.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Non-integer colouring
« Reply #35 on: Aug 2nd, 2007, 9:06am » |
Quote Modify
|
Fixed my program. In the last half-hour it's now searched all   <  for to well-over 8000 without finding any solutions. What's more, the average per-candidate-triangle time to find a single disqualifying point seems to be getting smaller as the size of the triangles considered grows, perhaps because the number of Pythagorean triples with a given hypotenuse trends generally upward with larger hypotenuses.
If a solution exists, it doesn't look like a computer search is likely to find it. On the one hand, that's reasonably to be expected of a "hard" problem around here. On the other hand, given the apparent ease with which a computer search can disqualify every candidate, I think it's more likely that JocK was either misinformed or mistaken...
(edit: a faster version has now checked all < somewhat over 21000 with similar results, and is still going steadily along...)
(edit 2: just past 33,000 before running out of memory, with no solution and no change in average behavior.)
--SMQ
|
| « Last Edit: Aug 2nd, 2007, 11:35pm by SMQ » |
IP Logged |
--SMQ
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Non-integer colouring
« Reply #36 on: Aug 3rd, 2007, 4:05pm » |
Quote Modify
|
I received an email from JocK that (a,b,c)=(505, 1803, 2066) works! My program has confirmed this, with the points (0,0), (377, 336) and (-1653, 720). What does your program give?
Edit: Googling for that triplet turns up this.
|
| « Last Edit: Aug 3rd, 2007, 4:13pm by Eigenray » |
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Non-integer colouring
« Reply #37 on: Aug 4th, 2007, 3:43am » |
Quote Modify
|
on Aug 3rd, 2007, 4:05pm, Eigenray wrote:| Edit: Googling for that triplet turns up this. |
|
Well, now we know that what JocK asked for, is called an Erdos-Diophantine triangle.
The paper treats exactly that problem in section 2.2. Note that they don't describe the way they solve the 2 hyperbolas intersection system.
It is probably not a bad idea to ask the authors?
|
|
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Non-integer colouring
« Reply #38 on: Aug 4th, 2007, 6:23am » |
Quote Modify
|
Hi folks, long time no see...
Nice to see some of the problems I posted here still keep some of you busy! 
http://en.wikipedia.org/wiki/Erd%C5%91s-Diophantine_Graph
Busy with some other projects, but might be visiting this forum again in the near future.
Cheers,
JocK
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Non-integer colouring
« Reply #39 on: Aug 4th, 2007, 6:53am » |
Quote Modify
|
on Aug 4th, 2007, 6:23am, JocK wrote:Busy with some other projects, but might be visiting this forum again in the near future. Cheers,
JocK |
|
Please come! We really miss you here!
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Non-integer colouring
« Reply #40 on: Aug 4th, 2007, 9:11am » |
Quote Modify
|
on Aug 3rd, 2007, 4:05pm, Eigenray wrote:| What does your program give? |
|
If you must know, my program gives (210123, -91523) as a disqualifying point, which is clearly a load of hooey as it's not even Pythagorean. I swear, one of these days I'm going to learn to program a computer.
Once I fixed my program -- the problem was in checking for perfect squares in numbers > 32-bits -- it now reports that as a solution.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Non-integer colouring
« Reply #41 on: Aug 4th, 2007, 11:26pm » |
Quote Modify
|
on Aug 4th, 2007, 3:43am, Barukh wrote:
The paper treats exactly that problem in section 2.2. Note that they don't describe the way they solve the 2 hyperbolas intersection system.
It is probably not a bad idea to ask the authors? |
|
This isn't too bad, just a bit tedious. Squaring
|(x,y)| - i = |(x-u,y-v)|
|(x,y)| - j = |(x-p,y-q)|
we get
{x2+y2} = [2(ux + vy) + i2 - a2]/(2i)
= [2(px + qy) + j2 - b2)/(2j),
so if iq  jv, then
y = 1/[2(iq-jv)] [ i(b2-j2) - j(a2-i2) +2(ju - ip)x ],
and substituting this back gives a quadratic in x. And if iq=jv, then ip ju (or else (p,q) and (u,v) would be collinear), and we can solve for x in terms of y.
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Non-integer colouring
« Reply #42 on: Aug 6th, 2007, 8:01am » |
Quote Modify
|
Eigenray, can you confirm that (0,0), (1204, 1653), (3360, -2907) with sides of 2045, 4443 and 5044 is a solution? My now-apparently-working program returns this as the first solution with a side > 5000 (and therefore not given in the above paper).
Thanks.
Edit: the next few triangles appear to be (0, 0), (44, 240), (-240, -4797) with sides 244, 4803 and 5045 and (0, 0), (407, 624), (4437, -2640) with sides 745, 5163 and 5186. The first "new" triangle found by my program (the one having the least middle side) was (0, 0), (228, 3245), (-3120, -2035) with sides 3253, 3725 and 6252, found in only about 10 minutes on a Pentuim 4.
--SMQ
|
| « Last Edit: Aug 6th, 2007, 8:36am by SMQ » |
IP Logged |
--SMQ
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Non-integer colouring
« Reply #43 on: Aug 6th, 2007, 9:07am » |
Quote Modify
|
Yes, I can confirm those four triangles.
|
| « Last Edit: Aug 6th, 2007, 9:58am by Eigenray » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print