Counting integral lattice points in a triangle that may not have integer coordinates?

I have a triangle with one vertex on 0,0, another at 0,Y, and the third at X,Y, where Y is a positive integer and and X is any positive number (can be irrational/decimal/integral/etc).

I tried using Pick's Theorem but it requires all integer vertices. Is there any way to count lattice points otherwise?

Solution 1:

As I mentioned in my comment above, the simple formula is:

$$\sum_{y=0}^{Y}\left(1+\left\lfloor \frac{yX}{Y}\right\rfloor\right)$$

If you use Pick's formula to count the points in $(0,0)-(0,Y)-(\left\lfloor X \right\rfloor,Y)$ with result $N$, then your result is $$N + \sum_{y=1}^Y \left(\left\lfloor\frac{yX}{Y}\right\rfloor - \left\lfloor \frac{y\left\lfloor X\right\rfloor}Y \right\rfloor\right)$$

The values in the sum are always $0$ and $1$.

Basically, this sum counts the number of values $y=1,..,Y$ such that there is a natural number $n$ such that $\frac{y\left\lfloor X\right\rfloor}{Y} < n \leq \frac{yX}{Y}$

I've had some time to consider the continued fraction approach, and it might improve the computation in some instances.

Expand $\frac X Y$ as a continued fraction, choosing one with an odd number of terms if $X$ is rational. Let $R_k=\frac{P_k}{Q_k}$ be the $k$th continue fraction. Then the number of positive lattice points such that $y\leq Y$ and $R_{2n}<\frac{x}{y}\leq R_{2n+2}$ can be computed as the number of pairs of positive integers $(u,v)$ such that $uQ_{2n} + vQ_{2n+1}\leq Y$ and $ua_{2n+2} \geq v$. Letting $v_1=\left\lfloor \frac{v-1}{a_{2n+2}}\right\rfloor$, this count is:

$$\sum_{v=1}^{\left\lfloor \frac {a_{2n+2}Y}{Q_{2n+2}}\right\rfloor}\sum_{u=v_1+1}^{\left\lfloor \frac{Y-vQ_{2n+1}}{Q_{2n}}\right\rfloor} 1 $$

The inner sum can be written as $\max\left(0,\left\lfloor \frac{Y-vQ_{2n+1}}{Q_{2n}}\right\rfloor - \left\lfloor \frac{v-1}{a_{2n+2}}\right\rfloor\right)$.

Note that when $a_{2n+2}=1$, this term simplifies to:

$$\left\lfloor \frac{Y-vQ_{2n+1}}{Q_{2n}}\right\rfloor - (v-1) = \left\lfloor\frac{Y-v(Q_{2n+1}+Q_{2n})}{Q_{2n}}\right\rfloor +1 = \left\lfloor \frac{Y-vQ_{2n+2}}{Q_{2n}}\right\rfloor + 1$$

But $R_0=P_0$ is an integer, so the number of non-negative lattice points $(x,y)$ with $y\leq Y$ and $x\leq R_0y$ is $1+Y+\sum_{j=1}^Y P_0j = 1+Y+P_0\frac{Y(Y+1)}2$.

So the total number of points is:

$$1+Y+P_0\frac{Y(Y+1)}2 + \sum_{n=1}^\infty \sum_{v=1}^{\left\lfloor \frac {a_{2n}Y}{Q_{2n}}\right\rfloor} \max(0,\left\lfloor \frac{Y-vQ_{2n-1}}{Q_{2n-2}}\right\rfloor - \left\lfloor \frac{v-1}{a_{2n}}\right\rfloor)$$

But note that the number of terms in the inner sum is zero if $\frac{Q_{2n}}{a_{2n}}>Y$, and $\frac{Q_{2n}}{a_{2n}}>Q_{2n-1}$so we can always write this as a finite sum, and, in particular, since $Q_k$ grows exponentially (at minimum, $Q_k$ is the $k$th Fibonacci number), the number of $n$ values is actually $O(\log Y)$.

The total pairs $n,v$ in this sum is about $\frac{2Y}{a_1}$, maximum. When $a_1=1$, this is more terms than the $Y+1$ terms for the "simple formula" above. However, notice the simple formula requires you to know $X$ to an unspecified level of precision, while this formula only requires integer arithmetic with values less than $Y$.

For example, if $X=\frac{Y}{N}$ for some integer $N>1$, then the continued fraction for $\frac{1}{N}$ we would choose is: $$0+\frac{1}{N-1+\frac{1}{1}}$$ to ensure the odd number of terms, and we would have $P_0=0$, $Q_0=1$, $Q_2=N$. This also gives us the case of $a_2=1$, so we can use the easier formula for the terms. Then this result would yield (remembering that $X=\frac{Y}{N}$:) $$1+Y+\sum_{v=1}^{\left\lfloor \frac{Y}{N}\right\rfloor} (1+Y-vN) = (1+Y)( 1+\left\lfloor X\right\rfloor) - \frac{N\left\lfloor X\right\rfloor(\left\lfloor X\right\rfloor +1)}2$$

The only test I've given this formula is $Y=10$ and $N=3$ (so $X=\frac{10}{3}$.) Both this formula and simple counting yields $26$, but I'd want some more testing for this in general.

An alternative formula came to me today.

$$1+Y+P_0\frac{Y(Y+1)}2 + \sum_{n=1}^\infty \sum_{v=1}^{\left\lfloor \frac Y {Q_{2n-1}}\right\rfloor}\left( \left\lfloor \frac{Y-vQ_{2n-1}}{Q_{2n-2}}\right\rfloor-\left\lfloor \frac{Y-vQ_{2n-1}}{Q_{2n}}\right\rfloor\right)$$

In particular, then, if $Q_2+Q_1>Y$, then this total is:

$$1+Y+P_0\frac{Y(Y+1)}2 + \sum_{v=1}^{\left\lfloor \frac Y {Q_1}\right\rfloor} Y-vQ_1 =$$ $$1+Y+P_0\frac{Y(Y+1)}2 + YY_0 - Q_1\frac{Y_0(Y_0+1)}2$$

Where $Y_0=\left\lfloor \frac Y {Q_1}\right\rfloor$.

For example, if $\frac X Y=\pi$, then $Q_1=7$, $Q_2=106$, so if $Y<113$, the total is:

$$1+Y+3\frac{Y(Y+1)}2 + YY_0 - 7\frac{Y_0(Y_0+1)}2$$

Where $Y_0=\left\lfloor \frac Y {7}\right\rfloor$.