How many lines are larger lines made of in a dotted grid?

Question

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?

Answer 1

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$.