¿Contar puntos de retícula integral en un triángulo que puede no tener coordenadas enteras?

Question

Tengo un triángulo con un vértice en 0,0, otro en 0, Y, y el tercero en X, Y, donde Y es un número entero positivo yy X es cualquier número positivo (puede ser irracional / decimal / integral / etc) .

Intenté usar el teorema de Pick pero requiere todos los vértices enteros. ¿Hay alguna manera de contar puntos de red de otra manera?

Answer 1

Como mencioné en mi comentario anterior, la simple fórmula es:

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

Si el uso de la selección de la fórmula para contar los puntos en $(0,0)-(0,Y)-(\left\lfloor X \right\rfloor,Y)$ resultado $N$, entonces el resultado es $$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)$$

Los valores de la suma son siempre $0$$1$.

Básicamente, esta suma cuenta el número de valores de $y=1,..,Y$ que no es un número natural $n$ tal que $\frac{y\left\lfloor X\right\rfloor}{Y} < n \leq \frac{yX}{Y}$

He tenido un poco de tiempo para considerar la continuación de la fracción enfoque, y podría mejorar el cálculo en algunos casos.

Expandir $\frac X Y$ como una continuación de la fracción, la elección de uno con un número impar de términos, si $X$ es racional. Deje $R_k=\frac{P_k}{Q_k}$ $k$th continuar fracción. A continuación, el número de positivos entramado de puntos tales que $y\leq Y$ $R_{2n}<\frac{x}{y}\leq R_{2n+2}$ puede ser calculada como el número de pares de enteros positivos $(u,v)$ tal que $uQ_{2n} + vQ_{2n+1}\leq Y$$ua_{2n+2} \geq v$. Dejando $v_1=\left\lfloor \frac{v-1}{a_{2n+2}}\right\rfloor$, esta cuenta es:

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

El interior de la suma puede ser escrito como $\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)$.

Tenga en cuenta que cuando se $a_{2n+2}=1$, este término se simplifica a:

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

Pero $R_0=P_0$ es un número entero, por lo que el número de no-negativo celosía puntos de $(x,y)$$y\leq Y$$x\leq R_0y$$1+Y+\sum_{j=1}^Y P_0j = 1+Y+P_0\frac{Y(Y+1)}2$.

Por lo que el número total de puntos es:

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

Pero tenga en cuenta que el número de términos en el interior de la suma es cero si $\frac{Q_{2n}}{a_{2n}}>Y$, e $\frac{Q_{2n}}{a_{2n}}>Q_{2n-1}$, por lo que siempre podemos escribir esto como una suma finita, y, en particular, desde la $Q_k$ crece exponencialmente (como mínimo, $Q_k$ $k$ésimo número de Fibonacci), el número de $n$ de los valores es en realidad $O(\log Y)$.

El total de los pares de $n,v$ de esta suma se acerca a $\frac{2Y}{a_1}$, como máximo. Al $a_1=1$, esto es más que el $Y+1$ términos para la "fórmula simple". Note, sin embargo, la simple fórmula requiere que conozca $X$ a un no especificado nivel de precisión, mientras que esta fórmula sólo requiere aritmética de enteros con valores de menos de $Y$.

Por ejemplo, si $X=\frac{Y}{N}$ para algunos entero $N>1$, entonces la continuación de la fracción de $\frac{1}{N}$, vamos a seleccionar es: $$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$$

La única prueba que he dado a esta fórmula es $Y=10$ $N=3$ (por lo $X=\frac{10}{3}$.) Tanto esta fórmula y simple recuento de los rendimientos $26$, pero me gustaría más pruebas de esto en general.

Una fórmula alternativa me llegó hoy.

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

En particular, entonces, si $Q_2+Q_1>Y$, entonces el total es:

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

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

Por ejemplo, si $\frac X Y=\pi$, luego $Q_1=7$, $Q_2=106$, así que si $Y<113$, el total es:

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

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