last day (17 days later) » 

22:15
Hello.
I suspect there's a smarter solution for that special 3SUM problem. I mean, the numbers are rather special, not random. The sum of x=ab/p² and y=cd/q² has denominator (pq)², so we could look for numbers with just that denominator. Something like that. I feel like it should be more efficient. If only one of us was a mathematician...
;-)
I thought about it too, specifically if you multiply through by all the denominators so that it's an integer equation
Wouldn't that make the numbers very large? Also, I think if you do that, you lose the advantage. The denominators give use classes that we could exploit. At least that's my gut feeling.
Well, if you're looking for a mathematical advantage then having integers might beat having small numbers. Lets you do things like modular arithmetic. I didn't come up with anything that beats O(n^2), though.
The thing is, to reduce that 2 to something lower, you have to not just take advantage of the fact that they're fractions, you have to take advantage of them coming from Pythagorean triples, because if they're just fractions then it is essentially the full 3SUM problem.
One potential is that (ab)/(c^2) = (a/c)(b/c) = sin t cos t for some angle t. Not sure what to do with that, though.
If there's some trick that turns it into an angle addition formula, then suddenly instead of 3SUM you have 3SUM modulo 2*pi, which is potentially an easier problem.
22:43
I'm thinking of Patrick's way. Let's say the current target is ab/c². Patrick would search for two numbers that add up to it. But he'd consider all numbers for it. But we want ab/c² = pq/r² + xy/z², so we're only interested in numbers from "classes" r and z such that rz=c (or something like rz|c, haven't thought cancellations through). You're right, I haven't explicitly exploited Pythagorean triples yet, although they might give me "good" denominators.
With "good" meaning diverse, giving me small classes.

  last day (17 days later) »