Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
I don't think you'll do better than $\sum_{y=0}^{Y}(1+\lfloor \frac{yX}{Y}\rfloor)$, assuming you want to count points on the boundary. –  Thomas Andrews Mar 5 '12 at 14:43

1 Answer 1

up vote 4 down vote accepted

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

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

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\lfloor\frac{yX}{Y}\right\rfloor - \left\lfloor \frac{y\left\lfloor X\right\rfloor}Y \right\rfloor)$$

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(0,\left\lfloor \frac{Y-vQ_{2n+1}}{Q_{2n}}\right\rfloor - \left\lfloor \frac{v-1}{a_{2n+2}}\right\rfloor)$.

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$.

share|improve this answer
    
That's what I've been using unfortunately, and it's quite slow for my purposes, but thanks anyway. I will likely need a new approach entirely. –  John Smith Mar 5 '12 at 15:10
    
It seems like it might vary based on the continued fraction approximations for $X/Y$. –  Thomas Andrews Mar 5 '12 at 15:37
    
If $X$ is not an integer, and $\frac{P_k}{Q_k}$ is one of the continued fraction expansions of $\frac{X}{Y}$ with $P_k/Q_k\geq X/Y$ and $Q_k>Y$, then you can replace $X$ with $\frac{P_k}{Q_k}$, I think, but I haven't quite proven that. If so, continued fractions at the very least let you reduce to $X$ being a rational number. –  Thomas Andrews Mar 5 '12 at 15:58
    
@ThomasAndrews: I have been thinking about this kind of problems for sometime. But unfortunately I am not comfortable with the Continued Fractions. Can you tell me what will be your expression if the coordinates be $(0,0)$, $(\frac{a}{2},0)$ and $(\frac{a}{2},\frac{b}{2})$ where $a$ and $b$ are odd positive integers each greater than $1$? –  user 170039 Sep 2 at 13:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.