3
$\begingroup$

So assuming we have a $X \times Y$ lattice, Say for example a $3 \times 5$ like so

* * *
* * *
* * *
* * *
* * *

I need to find the number of points that each diagonal passes through. In this example, each diagonal passes through 3 points. Any help is much appreciated!

$\endgroup$
  • 1
    $\begingroup$ Wouldn't it just be $\min(X,Y)$? $\endgroup$ – naslundx Mar 19 '14 at 17:10
  • $\begingroup$ Take a 4*3 one, it doesn't work in that case. $\endgroup$ – Veritas Mar 19 '14 at 17:11
  • $\begingroup$ What is a diagonal in this case then? I assumed you meant a straight line from the corner that's not horizontal or vertical? $\endgroup$ – naslundx Mar 19 '14 at 17:13
  • $\begingroup$ I am talking about the top-left/bottom-right and top-right/bottom-left diagonals. Sorry for the ambiguous wording. $\endgroup$ – Veritas Mar 19 '14 at 17:17
  • 3
    $\begingroup$ Hmm...maybe it's: $$ 1 + \gcd(X - 1, Y - 1) $$ $\endgroup$ – Adriano Mar 19 '14 at 17:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.