La evaluación de la suma de $\sum_{k = 0}^{\lfloor a/b \rfloor} \left \lfloor \frac{a - kb}{c} \right \rfloor$

Question

Deje $a, b$ $c$ ser enteros positivos. Recordemos que el máximo común divisor (mcd) la función tiene la siguiente representación: \begin{eqnarray} \textbf{gcd}(b,c) = 2 \sum_{k = 1}^{c- 1} \left \lfloor \frac{kb}{c} \right \rfloor + b + c - bc \end{eqnarray} como se muestra por Polezzi, donde $\lfloor \cdot \rfloor$ denota la función del suelo. En el intento de generalizar la fórmula que me llegó a través de la siguiente sumatoria \begin{eqnarray} \sum_{k = 0}^{\lfloor a/b \rfloor} \left \lfloor \frac{a - kb}{c} \right \rfloor. \end{eqnarray} Puedo demostrar la siguiente identidad real $x$, \begin{eqnarray} \sum_{k = 0}^{c-1} \left \lceil \frac{x - kb}{c} \right \rceil = d \left \lceil \frac{x}{d} \right \rceil - \frac{(b-1)(c-1)}{2} - \frac{d-1}{2}, \end{eqnarray} donde $\lceil \cdot \rceil$ denota el techo de la función y $d = \text{gcd}(b,c)$. (Tenga en cuenta que la primera suma la parte superior del índice es, en general, independiente de $c$.) Ideas de referencia o sugerencias son ciertamente apreciado. Gracias de antemano!

Actualización puedo probar la identidad \begin{eqnarray} \sum_{k = 0}^{c-1} \left \lfloor \frac{x - kb}{c} \right \rfloor = d \left \lfloor \frac{x}{d} \right \rfloor - \frac{(b+1)(c-1)}{2} + \frac{d-1}{2}, \end{eqnarray} donde $d = \text{gcd}(b,c)$. Hay otra identidad que pueden ser útiles. Si $n = c \ell +r$$0 \leq r < c$, luego \begin{eqnarray} \sum_{k = 1}^{n} \left \lfloor \frac{k}{c} \right \rfloor = c \binom{\ell}{2} + (r + 1) \ell. \end{eqnarray}

Actualización 2 Ok, así que no puedo demostrar que por real $x, y > 0$, \begin{eqnarray} \sum_{k = 0}^{\lfloor y \rfloor} \left \lfloor x + \frac{k}{y} \right \rfloor = \lfloor xy + (\lceil y \rceil - y) \lfloor x + 1 \rfloor \rfloor + \chi_{\mathbb{N}}(y)(\lfloor x \rfloor + 1), \end{eqnarray} donde $\chi_{\mathbb{N}}$ denota la función característica de los enteros positivos. Mi problema original (y una buena generalización) será en mano si me pueden evaluar los siguientes menor generalización: real $x, y > 0$$n \in \mathbb{Z}_{\geq 0}$, \begin{eqnarray} \sum_{k = 0}^{n} \left \lfloor x + \frac{k}{y} \right \rfloor. \end{eqnarray} De nuevo, cualquier ayuda es, sin duda apreciada!

Answer 1

Me gustaría resumir y ampliar los resultados de mi respuesta anterior en una nueva respuesta, como yo prefiero mantener el original en su forma actual para evitar que se convierta en mi magnum opus.

Teorema 1:

Para enteros positivos $a, b$ $c$ donde $ d=\text{gcd}(b,c), $ $u=c/d,$ $t= \lfloor a/b \rfloor $ $ a \equiv \lambda \textrm{ mod } d, $ donde $ 0 \le \lambda < d,$ $ u \, | \, (t+1) $ hemos

$$ \sum_{k=0}^{t} \left \lfloor \frac{a - kb}{c} \right \rfloor = \frac{t+1}{c} \left \lbrace a - \frac{tb}{2} - \frac{c, d}{2} - \lambda \right \rbrace . $$

Hasta ahora, el teorema anterior y su prueba se incluyen en mi respuesta anterior. El resto es nuevo.

Teorema 2:

Junto con las definiciones dadas en el teorema 1, vamos a $ a \equiv r \textrm{ mod } c, $ donde $ 0 \le r < c $ $ u \, | \, t $

$$ \sum_{k=0}^{t} \left \lfloor \frac{a - kb}{c} \right \rfloor = \frac{t+1}{c} \left \lbrace a - \frac{tb}{2} \right \rbrace - \frac{1}{c} \left \lfloor \frac{t+1}{u} \right \rfloor \left \lbrace \frac{u(c-d)}{2} + \lambda u \right \rbrace - \frac{r}{c} . $$

Por ejemplo, con $a=1019,b=33$ $c=55$ tenemos $d=\text{gcd}(33,55)=11,$ $u=c/d=55/11=5,$ $t= \lfloor 1019/33 \rfloor = 30$ y $ 1019 \equiv 29 \textrm{ mod } 55, $ y $ 1019 \equiv 7 \textrm{ mod } 11. $ Por lo tanto $ r = 29 $ $\lambda = 7.$

Tenga en cuenta que la condición de $ u \, | \, t $ está satisfecho, y así teorema 2 da

$$ \sum_{k=0}^{30} \left \lfloor \frac{1019 - 33k}{55} \right \rfloor = \frac{31}{55} \left \lbrace 1019 - \frac{ 30 \cdot 33}{2} \right \rbrace - \frac{6}{55} \left \lbrace \frac{5(55-11)}{2} + 7 \cdot 5 \right \rbrace - \frac{29}{55} = 279.$$

Esto se comprueba fácilmente con WolframAlpha, o similar.

Ambos de estos teoremas son casos especiales ( $ \mu=0$ $\mu=1$ ) del resultado general:

Teorema 3: Junto con las anteriores definiciones, teoremas 1 y 2, vamos a $ t+1 \equiv \mu \textrm{ mod } u,$ donde $ 0 \le \mu < u $

$$ \sum_{k=0}^{t} \left \lfloor \frac{a - kb}{c} \right \rfloor = \frac{t+1}{c} \left \lbrace a - \frac{tb}{2} \right \rbrace - \frac{1}{c} \left \lfloor \frac{t+1}{u} \right \rfloor \left \lbrace \frac{u(c-d)}{2} + \lambda u \right \rbrace $$ $$ - \frac{1}{c} \sum_{k=0}^{\mu - 1} \left \lbrace r+k \left \lbrace \left( \left \lfloor \frac{b}{c} \right \rfloor + 1 \right) c - b \right \rbrace \textrm{ mod } c \right \rbrace .$$

Hay $ \mu $ términos en la última suma, por lo que se entiende cero al $ \mu =0.$ Los términos en la final de la sumatoria de la ecuación son todos los $ \ge 0 $ y la reducción de modulo $c.$

Un esbozo de la prueba se ejecuta de la siguiente manera. En la adición de hasta el $t+1$ ecuaciones en el inicio de mi respuesta anterior, sumamos $ \lfloor (t+1)/u \rfloor $ "completa" conjuntos de residuos modulo $c$ (no debe confundirse con una completa residuo sistema modulo $c$) que son congruentes a $ \lambda $ modulo $c.$ El plazo $ \sum_{k=0}^{\mu - 1} \lbrace r+k \lbrace \cdots \rbrace \textrm{ mod } c \rbrace $ (equivalent, of course, to $ \sum_{k=0}^{\mu - 1} \lbrace (r-kb) \textrm{ mod } c \rbrace $ ) es la suma de la "izquierda sobre residuos."

Reordenando la ecuación obtenida de la suma demuestra el teorema.

Nota: En el texto $ \lbrace \cdot \rbrace $ sólo se utiliza para mejorar la legibilidad, y no indica la parte fraccionaria (me parece doble-up curva soportes difícil de leer).

Sólo por diversión, aquí es lo que tenemos cuando ponemos a $ \mu = 2 $ en el teorema 3.

Teorema 2(b): Junto con las definiciones anteriores, ya que $ \mu = 2 $ nuestra condición aquí es que $ u \, | \, (t-1) .$ $ r \ge b $ obtenemos

$$ \sum_{k=0}^{t} \left \lfloor \frac{a - kb}{c} \right \rfloor = \frac{t+1}{c} \left \lbrace a - \frac{tb}{2} \right \rbrace - \frac{1}{c} \left \lfloor \frac{t+1}{u} \right \rfloor \left \lbrace \frac{u(c-d)}{2} + \lambda u \right \rbrace - \frac{2r-b}{c} . \quad (1) $$

Por ejemplo, con $a=1037,b=33$ $c=55$ tenemos $d=\text{gcd}(33,55)=11,$ $u=c/d=55/11=5,$ $t= \lfloor 1037/33 \rfloor = 31$ y $ 1037 \equiv 47 \textrm{ mod } 55, $ y $ 1037 \equiv 3 \textrm{ mod } 11. $ Por lo tanto $ r = 47 $ $\lambda = 3.$

Tenga en cuenta que la condición de $ u \, | \, (t-1) $ está satisfecho, y así teorema 2(b) da

$$ \sum_{k=0}^{31} \left \lfloor \frac{1037 - 33k}{55} \right \rfloor = \frac{32}{55} \left \lbrace 1037 - \frac{ 31 \cdot 33}{2} \right \rbrace - \frac{6}{55} \left \lbrace \frac{5(55-11)}{2} + 3 \cdot 5 \right \rbrace - \frac{2 \cdot 47 - 33}{55} = 291.$$

Esto se comprueba fácilmente con WolframAlpha, o similar.

Para $ r < b $ el término final en $(1)$ $ - \frac{2r+c-b}{c}.$

(Continuará... el tiempo y el entusiasmo de los permisos :-) )

Answer 2

Aquí está una observación/resultado parcial. Por razones de brevedad escribir $t = \lfloor a/b \rfloor .$ Al $\text{gcd}(b,c)=1$ $c \, | \, (t+1) $ hemos

$$ S = \sum_{k=0}^{t} \left \lfloor \frac{a - kb}{c} \right \rfloor = \frac{t+1}{c} \left \lbrace a - \frac{tb}{2} - \frac{c-1}{2} \right \rbrace . $$

Prueba:

Supongamos que

$$\begin{align} a &= m_0 c + r_0 \\ a- b &= m_1 c + r_1 \\ a - 2b &= m_2 c + r_2 \\ \cdots &= \cdots \\ a - tb &= m_t c + r_t \end{align}$$

para un entero $m_i$ $r_i$ donde $ 0 \le r_i < c $ a continuación, añadir las ecuaciones anteriores,

$$(t+1)a - \frac{t(t+1)}{2}b = Sc + \sum_{k=0}^t r_k . \quad (1)$$

Ahora si $\text{gcd}(b,c)=1$ $k$ ejecuta a través de un sistema completo de residuos módulo $c$ $a-kb,$ donde $a$ es cualquier entero, también se ejecuta sobre un sistema completo de residuos módulo $c$. Así que cuando $ c \, | \, (t+1) $ tenemos que $a-kb$ ejecuta a través de $(t+1)/c$ completa de sistemas de residuos modulo $c$. Por lo tanto $$\sum_{k=0}^t r_k = \frac{(t+1)(c-1)}{2}.$$

Sustituir esto en $(1)$ para obtener el resultado.

EDIT: Aquí es una generalización para el caso de $\text{gcd}(b,c)>1,$ que se reduce a la anterior, cuando se $b$ $c$ son coprime.

Escribir $d=\text{gcd}(b,c)$ y supongamos $ a \equiv \lambda \textrm { mod } d $ donde $ 0 \le \lambda < d.$

Ahora $a-kb$ ejecuta a través de todos los residuos modulo $c$ que son congruentes a $ \lambda $ modulo $c$ $k$ se ejecuta a través de $0,1,2,\ldots,u-1$ donde $u=c/d.$ Al $ u \, | \, (t+1) $ tenemos que $r_0,r_1,\ldots,r_t$ se ejecuta a través de $(t+1)/u$ tales sistemas de residuos. Por lo tanto

$$ \sum_{k=0}^t r_k = \frac{t+1}{u} \left \lbrace \frac{du(u-1)}{2} + \lambda u \right \rbrace = (t+1) \left \lbrace \frac{c, d}{2} + \lambda \right \rbrace .$$

Y así

$$ \sum_{k=0}^{t} \left \lfloor \frac{a - kb}{c} \right \rfloor = \frac{t+1}{c} \left \lbrace a - \frac{tb}{2} - \frac{c, d}{2} - \lambda \right \rbrace . $$

EDIT2: Aquí hay un par de ejemplos numéricos. Con $a=91,b=15 \textrm{ and } c=21$ hemos $d=\text{gcd}(15,21)=3,$ $t=\lfloor 91/15 \rfloor = 6,$ $u=c/d=21/3=7$ y $91 \equiv 1 \textrm{ mod } 3,$ $\lambda=1.$ tenga en cuenta que la condición de $ u \, | \, (t+1)$ está satisfecho. La fórmula que da la suma como

$$\frac{7}{21} \left \lbrace 91 - \frac{6 \cdot 15}{2} - \frac{21-3}{2} - 1 \right \rbrace = 12.$$

Este es lo suficientemente pequeño como para comprobar con la mano.

$$ \sum_{k=0}^7 \left \lfloor \frac{91-15k}{21} \right \rfloor = 4+3+2+2+1+0+0=12.$$

Con $a=703,b=35 \textrm{ and } c=49$ hemos $d=\text{gcd}(35,49)=7,$ $t=\lfloor 703/35 \rfloor = 20,$ $u=c/d=49/7=7$ y $703 \equiv 3 \textrm{ mod } 7,$ $\lambda=3.$ tenga en cuenta que la condición de $ u \, | \, (t+1)$ está satisfecho. La fórmula que da la suma como

$$\frac{21}{49} \left \lbrace 703 - \frac{20 \cdot 35}{2} - \frac{49-7}{2} - 3 \right \rbrace = 141.$$

Se puede comprobar con WolframAlpha, o similar, que

$$ \sum_{k=0}^{20} \left \lfloor \frac{703-35k}{49} \right \rfloor = 141.$$

Answer 3

Esto no es una solución completa, sino una reformulación de un gran número de casos relacionados con el problema anterior. Escribir $n = m \lfloor y \rfloor + r$ donde$0 \leq r < \lfloor y \rfloor$$n, m , r \in \mathbb{Z}_{\geq 0}$. A continuación, para el real $x, y > 0$, tenemos \begin{eqnarray} \sum_{k = 0}^{n} \left \lfloor x + \frac{k}{y} \right \rfloor & = & \lfloor x \rfloor + \sum_{\ell = 0}^{m-1} \left \lfloor x y + \ell \lfloor y \rfloor + ( \lceil y \rceil - y) \left \lfloor x + \frac{\ell \lfloor y \rfloor}{y} + 1 \right \rfloor \right \rfloor + \end{eqnarray} \begin{eqnarray} & & \sum_{k = 1}^{r} \left \lfloor x + \frac{m \lfloor y \rfloor}{y} + \frac{k}{y} \right \rfloor + \chi_{\mathbb{N}}(y) \sum_{\ell = 0}^{m-1} \left \lfloor x + \frac{\ell \lfloor y \rfloor}{y} + 1 \right \rfloor - \sum_{\ell = 0}^{m-1} \left \lfloor x + \frac{ \ell \lfloor y \rfloor }{y} \right \rfloor . \end{eqnarray} Esto se deriva al dividir el intervalo de $[0,n]$ en subintervalos y el uso de la última identidad en la descripción del problema.

Para el problema original, escribir \begin{eqnarray} \sum_{k = 0}^{\lfloor a /b \rfloor} \left \lfloor \frac{a - k b}{c} \right \rfloor = \sum_{k = 0}^{\lfloor a /b \rfloor} \left \lfloor \frac{\text{mod}(a,b) + k b}{c} \right \rfloor \end{eqnarray} donde $\text{mod}(a,b) = a - b \lfloor \frac{a}{b} \rfloor$. Si $\lfloor \frac{a}{b} \rfloor \gg c$, a continuación, utilizar la identidad de arriba para reducir enormemente el número de términos en la suma.