Finding the GCD of two numbers using Euclid’s algorithm is much faster than factoring.
If the line is defined by floating point numbers, isn’t it possible that the line comes almost infinitessimally close to an integer point, but you won’t see it because of the resolution in the original numbers?
Seems to me that this is the kind of problem where even when you solve it correctly from a math standpoint, you’ll miss points you should hit due to quantization error. Using a method like ultrafilter’s, you could replace “is an integer” with “is within delta of an integer”.
Is that the hardest part?
If all you want to do is figure out whether any point on a line (ax + by = c, where a, b and c are rational) intersects an integer point, yes. Constraining it to a segment is somewhat harder. The ILP solution ultrafilter suggested works, though in the general case, ILP is NP-complete.
I’ve been assuming we want the solution, not just whether one exists.
An ILP solver will give the solution if one exists.
All numbers expressible as floating point numbers are rational, and hence one can in principle determine absolutely, yes or no, whether the line passes through a lattice point (though it might take longer to do it if your numbers are expressed to high precision). Alternately, if you meant a number that can’t be expressed exactly as a floating point number, but only approximated as one, well, then we’ve got a loss of information, with no way of recovering it, so of course we can’t be certain of getting the right answer.
ZenBeam, actually finding the solution is somewhat harder, but not by very much. In fact, it mostly consists of the same method you use to find out if the solution exists, except you keep a little closer track of what you’re doing.
I just realized that some of the constraints in my original problem formulation are redundant. This is the simpler version:
minimize 1
subject to x = (1 - t)*x_left + t*x_right
y = (1 - t)*y_left + t*y_right
t <= 1
t >= 0
x is an integer
y is an integer
There’s actually an embarrassingly simple algorithm for solving this problem that I should have thought of first:
[ol]
[li]Enumerate all the integers z with x_left <= z <= x_right.[/li][li]For each integer in this list, set t = (z - x_left)/(x_right - x_left) and see if (1 - t)y_left + ty_right is an integer.[/li][/ol]
Sage Rat suggested exactly that in the OP 
That’s fine and probably quite practical for a line segment of reasonable length.
I am actually more interested in the unbounded case. What is the proof that the line never passes through a lattice point.
And I concede that the solution depends entirely on the framing of the question: that is, how the line is defined.
I visualise a case where the line passes through the two points (a,b) and (c,d) where a, b, c and d are all irrational – say, the solution to a fifth order polynomial or the solution to a trig or exponential function or perhaps defined by an infinite series.
Presented with one of these, I would intuitively guess that no lattice points would be touched. But there is a remote chance of my being wrong. It is theoretically possible.
The question that then arises is where did the values a, b, c and d come from. Presumably they would have come from the same context – solutions to the same set of equations. And in unpacking that lies the answer to the question. I don’t doubt that arbitrary reals give rise to lines that never pass through lattice points – for the same reason that real numbers outnumber rationals.
Line is: y=mx+b
It seems to me if m is rational, then y=mx obviously has other points besides 0,0 that are integer.
If m=a/d then y=ax/d or dy=ax, so d,a would be a solution?
Then - if I translate the line upward by “b” can we show it must still intercept a integer pair?
I don’t think so, since the result adds an irrational to the y value.
If y=ax/d + b, but b is irrational - I can’t make a/d irrational and still have x integer.
You’re assuming that b is an integer. Suppose m = 1 and b = .5:
y = x + .5
It should be obvious that there is no way to pass through lattice points (if y is an integer, then x cannot be, and vice-versa).
I don’t know what universe you live in, but in my Euclidean one, a straight line is one dimensional, a curved one isn’t. I’ll conceded the error on hyperbola. OTOH, as to “told you a million times”, cite?
I think that was a joke. Hyperbole, even.
Here goes (this is pretty much what Saint Cad posted, just written up slightly differently).
Let’s start by proving that if a and b are relatively prime (their GCD is 1), there exist some integer i and j such that:
ai + bj = 1
If a and b are relatively prime, then there must exist some k such that a * k mod b = 1. Thus, if we set i = k, and j = -(a * k - 1)/b, we have integer i and j that satisfy the equation.
We can extend this a little bit and say there must be integer i and j such that ai + bj = z for any integer z (which you can get by multiplying through on the original equation).
Now let’s turn to the original question. Suppose we have a line, whose equation can be rewritten as:
ax + by = c
Where a, b and c are rational. We can assume, without loss of generality, that a, b and c are integers (by multiplying through by the LCM of the denominators of a, b and c).
Let g be the GCD of a and b. We can rewrite the equation as:
a’*x + b’*y = c/g
Where a’ = a/g and b’ = b/g. Note that by definition, a’ and b’ are relatively prime. Thus, as long as c/g is an integer, we know there must exist some integer x and y that satisfy the equation by our earlier proof. Moreover, if c/g is not an integer, there cannot be any integer x and y that satisfy the equation.
To show that there are an infinite number of possible solutions, note that for a’ and b’, there are an infinite number of non-zero, integer p and q such that:
a’ * p + b’ * q = 0
Which you can get by setting p to kb and q to -ka for some integer k. Thus if you find an (x, y) that solves the equation, (x + kb, y - ka) also solves it.
You can specify a position along a curve by a single number. That’s the definition of one-dimensional.
Uh, as opposed to being actually one dimension? You know, like a straight line?
And a “single number” is sort of useless. The position of any point in a two dimensional plane can be given by a single number by one of Cantor’s old trick. Saying a plane is one dimensional isn’t what most people would agree with. It’s a lousy metric, but it’s a single number.
Most people don’t think in terms of metrics when they talk about 1, 2 or 3-d. They think line, plane, space.
A curve is a one-dimensional object, but it exists within a two-dimensional space (the plane).
Cites:
Or, you know, like a curved line.
And the actual definition for dimensionality is of course a bit more rigorous, as it gets into matters of topology (the mapping of a plane to a line isn’t continuous). But that’s the gist of it. If you’d prefer, you could also say that a thing is one-dimensional if there’s a continuous one-to-one function between it and a line.