Math question

[Milldawg]

Suppose you have a curve in R2, and you suspect there might be one or more points (a, b) on the curve where a and b are both integers. Is there a quick and easy way to confirm whether there are any such points, and if so, where?

I am imagining in my mind a giant grid of sensitive dots that light up whenever the curve hits one, but I don't know how to represent that mathematically, if it's even possible. Is there a known way?

For example, the curve y=4/x. We know if we graph it that the points (1, 4), (2, 2), and (4, 1) have integers for both x- and y-coordinates, but what about a curve that's considerably more difficult to evaluate visually?

[IskatuMesk]

the answer is clearly 42

[Zilla-]

/thread

[coko]

Milldawg, are you asking whether or not a curve will go through integer points? (By integer I believe you imply {1, 2, 3, 4, ..,n})

So you are wondering for a sufficiently complex equation without brute-forcing every possible number can you identify integer points?

http://books.google.co.uk/books?id=HGqrZLQQwfcC

Chapter 4 should cover this conversation perfectly for you, though depends on your ability with maths, however it should be possible to just follow the proof as written to get the answer.

[Milldawg]

Nice, that at least seems to suggest that there exists a method, though I can't really follow it since I'm too rusty on the math.

Is there a general formula for finding the integer points on the curve y=n/x, in terms of n?

[mAc Chaos]

Where's Negi?  Isn't he a math genius?

[AA7Dragoon]

^ He's polishing my knob.

[Negi]

It depends on the type of function.  With a simple rational function like the above, you only need to evaluate at x such that x divides 4.  If it is a polynomial rational function, split the polynomial into irreducible parts, but if the function is too complicated you have to look at harder things like varieties, etc.  But isn't this number theory?

[Milldawg]

SURE IS

You see, I am trying to crack the age-old problem of prime factorization of extremely large numbers

[Negi]

um. How do you propose to do that without knowing the basics?  I mean some of the greatest minds in history have  worked on said problem and haven't been able to do it in less than exponential time. 

[Milldawg]

I don't expect to SUCCEED I'm just bored.

Anyway, my idea formed into another one. If there's an easy way to find the points of intersection of three surfaces, then it can be done. (Except I don't think there is such a way.) Consider the surfaces y=cos x and y=cos z in R3. The intersection of these two surfaces intersects the xz plane (at y=1) in a grid-like pattern of dots. If I could then intersect my curve z=2(pi)n/x with these surfaces and find the points of intersection when y=1, those points will reveal all the factors of n.

The problem with the method is that arc cos x has infinity solutions, and it seems you'd have to check them one by one, which is no faster than brute forcing it (in fact, slower).

[IskatuMesk]

^ He's polishing my knob.

That's what I like about this guy. He doesn't just beat around the bush. He beats the bush.

[coko]

Well, the best way is to build a list of impossible areas where you know no solutions can lie. Then this greatly reduces your shape space. But yes for sufficiently complicated equations no direct method can give you the xy because no formula exists to solve that equation itself.

[Hercanic]

^ He's polishing my knob.

That's what I like about this guy. He doesn't just beat around the bush. He beats the bush.

No. I don't think he's ever touched a bush in his life.

[tipereth]

Well, the best way is to build a list of impossible areas where you know no solutions can lie. Then this greatly reduces your shape space. But yes for sufficiently complicated equations no direct method can give you the xy because no formula exists to solve that equation itself.

This is basically the sieve catalog idea I was talking to Milldawg about earlier. It wouldn't work because the numbers would get too big to deal with. (or big enough to make computers take for fucking ever to find primes)