4
$\begingroup$

Given a point $(a,b)$ with positive coordinates, I'd like to count the number of lattice points $(x,y)$ with the same parity (i.e., $x \equiv y \ (mod \ 2)$) inside the triangle $(0,0)(a,0)(a,b)$. How to compute it fast?

Note that without the parity requirement, it can be done using Pick's theorem directly.

$\endgroup$
5
  • $\begingroup$ When $a,b$ are both even we can use Pick's theorem because it puts the vertices $(a,0)$ and $(0,b)$ on the lattice rotated at a 45 degree angle. Might be possible to extend it from there, maybe considering the complement of the lattice helps. $\endgroup$
    – Merosity
    Jun 29, 2022 at 12:02
  • $\begingroup$ It suffices to count the lattice points $(2\mathbb{Z})^2$. If we let $T(c)$ be the number of non-negative integer solutions $(x,y)$ to the inequality $2ay+2bx\leq c$, then the solution to the original question is gotten as $T(ab)+T(ab-a-b)$. This is because the points $(2\mathbb{Z}+1)^2$ become points of $(2\mathbb{Z})^2$ by translation with $(-1, -1)$ and that changes the $c$-value by $-a-b$. I have asked this another question: math.stackexchange.com/questions/4482961/… if it could aid in the count. $\endgroup$
    – ploosu2
    Jun 29, 2022 at 15:50
  • $\begingroup$ This is perhaps getting too long for a comment but my idea is to break the triangle into a rectangle (which is easy to count) and two other triangles (which are smaller versions of the same problem with a smaller $c$-value), by finding the next smaller $c$-value that has a solution, picking a solution and then breaking from that point (Here's a picture if it clarifies: desmos.com/calculator/ri6zepdcuh ) $\endgroup$
    – ploosu2
    Jun 29, 2022 at 15:52
  • $\begingroup$ By scaling by $1 \over 2$ we see that $T$ counts the integer lattice points inside the rational polytope $ P = \text{conv}((0,0), (\frac{a}{2}, 0), (0, \frac{b}{2}))$. Its Ehrhart quasi-polynomial $q$ gives the solution but the constant coefficient and the linear coefficient might have period two. But I don't see a way to solve those coefficients since we can only easily count (with Pick) the values of $q(2n)$. So we can only get the sum of the period. And the value we actually want is $q(1)$. I don't know, maybe it's actually easier to count the (even, even)s and (odd, odd)s together somehow $\endgroup$
    – ploosu2
    Jun 29, 2022 at 16:23
  • 1
    $\begingroup$ Do you have context for this problem? Is it some programming puzzle? $\endgroup$
    – ploosu2
    Jun 29, 2022 at 16:25

1 Answer 1

1
$\begingroup$

After some trials, I come up with a solution similar to the Euclidean algorithm.

We want to calculate $\sum_{0 \leq x \leq a}\lfloor \frac{\frac{b}{a}x+(x\%2)}{2} \rfloor$ where $\%$ means the standard modulo operator. We separate into two parts: $x$ is odd and $x$ is even. For the first case, we write as $\sum_{0 \leq 2t+1 \leq a}\lfloor \frac{2bt+a+b}{2a} \rfloor$; for the second case, we write as $\sum_{0 \leq 2t \leq a}\lfloor \frac{bt}{a} \rfloor$. Therefore, it is suffice to compute $f(a,b,c,n)=\sum_{0 \leq x \leq n}\lfloor\frac{ax+b}{c} \rfloor$ fast.

If $a \geq c$ or $b \geq c$, we can write $a=q_1 c+r_1$ and $b=q_2 c+r_2$ where $r_1$ and $r_2$ are remainders. Hence, $f(a,b,c,n)=\sum_{0 \leq x \leq n}\lfloor q_1 x + q_2 + \frac{r_{1}x + r_{2}}{c} \rfloor=(\sum_{0 \leq x \leq n}q_1 x + q_2) +\sum_{0 \leq x \leq n}\lfloor \frac{r_1 x + r_2}{c} \rfloor$. The first part can be calculated directly, so we just need to consider the case $a \lt c$ and $b \lt c$.

In this case, it turns out that $f(a,b,c,n)=\sum_{0 \leq x \leq n}\lfloor\frac{ax+b}{c} \rfloor=\sum_{0 \leq x \leq n}\sum_{0 \leq j \leq \lfloor\frac{ax+b}{c} \rfloor-1}1=\sum_{0 \leq j \leq \lfloor\frac{an+b}{c} \rfloor-1}\sum_{0 \leq x \leq n}[j<\lfloor\frac{ax+b}{c} \rfloor]=\sum_{0 \leq j \leq \lfloor\frac{an+b}{c} \rfloor-1}\sum_{0 \leq x \leq n}[cj<ax+b-c+1]=\sum_{0 \leq j \leq \lfloor\frac{an+b}{c} \rfloor-1}(n-\lfloor\frac{cj+c-b-1}{a} \rfloor)=n\lfloor\frac{an+b}{c} \rfloor-\sum_{0 \leq j \leq \lfloor\frac{an+b}{c} \rfloor-1}\lfloor\frac{cj+c-b-1}{a} \rfloor=n\lfloor\frac{an+b}{c} \rfloor-f(c,c-b-1,a,\lfloor\frac{an+b}{c} \rfloor-1)$.

The above runs similar to the Euclidean algorithm, and we solve the problem in $O(log(max(a,b)))$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .