¿Puede un número entero positivo x ser escrito como la suma de y enteros positivos consecutivos?

Question

He visto en otros lugares que todo entero positivo mayor que 1 que no es una potencia de 2 se puede escribir como la suma de cierto número de enteros positivos consecutivos; sin embargo, dada una x y y específicas, donde x e y son enteros positivos, ¿se puede encontrar una fórmula para determinar si x se puede escribir como la suma de y enteros positivos consecutivos?

Por ejemplo, 15 se puede componer de 3 enteros positivos consecutivos, 4 + 5 + 6, pero 14 no puede. Sin embargo, 14 se puede componer de 4 enteros positivos consecutivos, 2 + 3 + 4 + 5, mientras que 15 no puede.

Al observar algunos ejemplos, noté que un x dado se puede expresar como la suma de y enteros positivos consecutivos si x - (la suma de los primeros y - 1 enteros positivos) es divisible uniformemente por y. Ese último término es el número triangular (y-1), por lo que podemos simplificar a $y|(x - {y \choose 2})$, o $x - {y \choose 2} \pmod y \equiv 0$.

Trabajando nuevamente a través de esos ejemplos anteriores, tenemos:

$x = 15, y = 3 \rightarrow 15 - {3 \choose 2}\pmod 3 = 15 - 3 \pmod 3 = 12 \pmod 3 \equiv 0$;

$x = 14, y = 4 \rightarrow 14 - {4 \choose 2}\pmod 4 = 14 - 6 \pmod 4 = 8 \pmod 4 \equiv 0$;

$x = 15, y = 4 \rightarrow 15 - {4 \choose 2}\pmod 4 = 15 - 6 \pmod 4 = 9 \pmod 4 \equiv 1$;

$x = 14, y = 3 \rightarrow 14 - {3 \choose 2}\pmod 3 = 14 - 3 \pmod 3 = 11 \pmod 3 \equiv 2$.

He mencionado todo esto, pero no he proporcionado una prueba formal para nada de eso. Entonces, finalmente llegando a la parte de pregunta de esta pregunta: ¿alguien puede pensar en una prueba de que, para enteros positivos x, y, x se puede expresar como la suma de y enteros positivos consecutivos si y solo si $x - {y \choose 2} \pmod y \equiv 0$? Además, ¿es posible simplificar eso aún más, tal vez debido a algunas propiedades compartidas de coeficientes binomiales y aritmética modular?

Escribí una publicación sobre esto en mi sitio web aquí con algunos ejemplos adicionales y mi proceso de pensamiento.

Answer 1

Su condición no es correcta. Como lo demuestra el comentario de @peterwhy, su condición es una condición necesaria para que $x$ pueda ser escrito como la suma de $y$ enteros positivos consecutivos, pero no es una condición suficiente. Por ejemplo, tomemos $x=14$ y $y=7$. Entonces, tenemos $$ 14-\binom{7}{2}=-7\equiv 0\pmod{7} $$ Sin embargo, $14$ no puede ser escrito como $7$ enteros positivos consecutivos, porque, dado que el entero positivo de inicio mínimo posible es $1$, el valor mínimo posible para $7$ enteros positivos consecutivos es $1+2+\cdots+7=28$ y $14 < 28$.

Por lo tanto, tenemos otra condición suficiente para que $x$ pueda ser escrito como $y$ enteros consecutivos: $x$ necesita ser al menos $1+2+\cdots+y$. Usando la fórmula bien conocida para sumas de secuencias aritméticas, en otras palabras, necesitamos que: $$ x\geq \frac{y(y+1)}{2} $$

Ahora tenemos dos condiciones necesarias, $y \mid (x-\binom{y}{2})$ y $x \geq [y(y+1)]/2$, para que $x$ pueda ser escrito como la suma de $y$ enteros positivos consecutivos. Mi afirmación es que estas dos condiciones también son suficientes, es decir, si estas dos condiciones se cumplen, entonces $x$ puede ser escrito como la suma de $y$ enteros consecutivos. Específicamente, podemos escribir $x$ como la siguiente suma: $$ \frac{x-\binom{y}{2}}{y} + \left(\frac{x-\binom{y}{2}}{y}+1\right) + \cdots + \left(\frac{x-\binom{y}{2}}{y}+y-1\right) $$ Primero, sabemos que $(x-\binom{y}{2})/y$ es un entero porque $y \mid (x-\binom{y}{2})$. Además, $(x-\binom{y}{2})/y$ es un entero positivo porque, por nuestra segunda condición: $$ \begin{align*} & x \geq \frac{y(y+1)}{2} \\ \implies & x-\binom{y}{2} \geq \frac{y(y+1)}{2}-\frac{y(y-1)}{2}=\frac{2y}{2}=y \\ \implies & \frac{x-\binom{y}{2}}{y} \geq 1 \end{align*} $$ Por lo tanto, dado que el primer número en nuestra suma es un entero positivo y cada número siguiente en la suma es simplemente $1$ más el número anterior, nuestra suma es claramente la suma de $y$ enteros positivos consecutivos.

Finalmente, solo hace falta mostrar que nuestra suma es igual a $x$. Dado que cada número en nuestra suma tiene a $(x-\binom{y}{2})/y$ como término, esencialmente podemos sacar los $y$ copias de ese número de la suma, y luego nos queda: $$ \begin{align*} & y\left(\frac{x-\binom{y}{2}}{y}\right)+1+2+\cdots + (y-1) \\ = & \left(x-\binom{y}{2}\right)+\binom{y}{2} \\ = & \ x \end{align*} $$ como se quería demostrar. Con esto, hemos terminado de demostrar que las dos condiciones necesarias que encontramos también son suficientes para que $x$ pueda ser escrito como la suma de $y$ enteros consecutivos.