# Number of lattice points with the same parity inside a triangle

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.

• 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. Commented Jun 29, 2022 at 12:02
• 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. Commented Jun 29, 2022 at 15:50
• 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 ) Commented Jun 29, 2022 at 15:52
• 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 Commented Jun 29, 2022 at 16:23
• Do you have context for this problem? Is it some programming puzzle? Commented Jun 29, 2022 at 16:25

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.
The above runs similar to the Euclidean algorithm, and we solve the problem in $$O(log(max(a,b)))$$.