Problem Solving Episode

For my problem, I have selected the "DiagonalCount" problem.

Step 1: Understand
The problem asks for a formula that will return the numbers of squares intersected by the diagonal of a rectangle made of m rows and n columns.

Step 2: Devise a plan
Let the formula be D(m, n). I will start by finding D(m, n) for a lot of rectangles, and finding a formula that fits them. If I can explain WHY this formula works, then it should be true.

Step 3: Carry out the plan
I found that a lot of rectangles had D(m, n) = ceil(max(m, n) / min(m, n)) * max(m, n). However, this did not work for rectangles where all rows did not have the same number of intersected squares, like 3*5 and 5*8. My rationale was that ceil(max(m, n) / min(m, n)) would give the number of squares intersected on each row (or column, whichever is larger), and multiplying it by max(m, n) gives the total. However, this doesn't work for rectangles  where all rows did not have the same number of intersected squares.

Trying another method, I found that for some rectangles D(m, n) = m + n - 1. This was because there are m  intersected squares, and on every row but the first, there is a sort of "extra" square, caused by the diagonal coming through the bottom of the above square.

This still doesn't work for 2*2, 4*6, and infinite other rectangles. However, the (m, n) pairs of these rectangles all have common factors. Dividing out the GCF from m & n, calculating m + n - 1, and multiplying the result by the GCF gives D(m, n).

Therefore:
GCF(m, n) * ((m + n ) / GCF(m, n) - 1) =
m + n - GCF(m, n) =
D(m, n)