In a dotted 2d grid, lines can be drawn between the dots. But every dot that the line touches breaks the line up into smaller lines. I want to be able to work out how many lines this bigger line is made of, assuming the line starts at origin (0,0) and ends at the given x&y co-ordinates.
For example:
2 o o o
/
1 o o o
/
0 o o o
0 1 2
A line drawn to the point (2,2) crosses one point and splits into 2 different lines.
The table below shows how many lines a line splits into when drawn to the relevant point:
x y 0 1 2 3 4 5 6 7
0 0 1 2 3 4 5 6 7
1 1 1 1 1 1 1 1 1
2 2 1 2 1 2 1 2 1
3 3 1 1 3 1 1 3 1
4 4 1 2 1 4 1 2 1
5 5 1 1 1 1 5 1 1
6 6 1 2 3 2 1 6 1
7 7 1 1 1 1 1 1 7
Note that the top and left edges of the table are the x/y co-ordinates.
As you can see, there are many patterns in the table, but I cannot work out a formula of method to work out the value.
Any ideas?
So, if integers $X$ and $Y$ are relatively prime, i.e. they have no common factors other than 1, then a line from $(0,0)$ to $(X,Y)$ will not go through any other integer lattice points. (If there were a lattice point $(A,B)$ on that line, then there's a method to find an integer larger than 1 that divides both $X$ and $Y$)
If $X$ and $Y$ aren't realtively prime, then find their greatest common factor (GCF). That's how many segments the lattice points will divide the line into. (Think of similar triangles, where $X$ along the X-axis, $Y$ along the Y-axis, and your line from $(0,0)$ to $(X,Y)$ form a right triangle. Dividing $X$ and $Y$ by their GCF gives you the smallest triangle with integer sides along the X and Y axes whose hypotenuse lies on your line. Then every multiple of that triangle gives you another point on the line, until you finally reach $(X,Y)$.
For example, if $X=6$ and $Y=3$ then the GCF$=3$, and there's a point at $(2,1)$ and $(4,2)$, giving you 3 line segments.
Oh, and please note, in your table, when one of $X$ or $Y=7$ and the other is $1, 2, 3, 4, 5,$ or $6$, the value should be $1$, never $4$ or $3$.