¿Primer número $\ge n$ que es divisible por $k$?

Question

¿Hay una buena manera de calcular el primer valor $\ge n$ que es divisible por $k$?

Ahora que soy informática $\left\lfloor\frac{n}{k}\right\rfloor k$ pero no siempre funciona.

Answer 1

¿Qué $(n-(n\mod k))\mod k$? Esto debe hacer el trabajo.

Answer 2

Bueno, si $n \equiv 0\pmod k$, luego entonces $n$ obras, como las divisiones de $k$$n - 0 = n$.

Si divide a $n \equiv 1 \pmod k$, que significa $k$ $n - 1$, $n - 1 +k$ funciona así.

Si divide a $n \equiv 2 \pmod k$, que significa $k$ $n - 2$, $n - 2 + k$ funciona así.

¿Crees que se podría generalizar esto, suponiendo que tiene la capacidad para encontrar el residuo de $n$, modulo $k$?

Answer 3

Comienzo con $u (n, k) = k\lceil \frac{n}{k} $ \rceil siendo el múltiplo más pequeño de $k$ $\ge n$.

Ahora utilizamos $\lceil \frac{n}{k} \rceil = \lfloor \frac{n+k-1}{k} $ \rfloor. Para ver esto, escriba $n = ak+b$ donde $0 \le b \le k-1$. \Rceil entonces $\lceil \frac{n}{k} = a $ si $b=0$ y $a+1$ si $b > 0$. Pero $\lfloor \frac{n+k-1}{k} \rfloor = \lfloor \frac{ak+b+k-1}{k} \rfloor = a + \lfloor \frac{b+k-1}{k} \rfloor = a$ si $b=0$ y $a+1$ si $b > 0$

Por lo tanto $u (n, k) = k \lfloor \frac{n+k-1}{k} $ \rfloor.

Answer 4

Reclamación $m=\left\lfloor\frac{n+k-1}{k}\right\rfloor k$ obras.

Prueba de Esto es obviamente un múltiplo de $k$. Para demostrar que es el más pequeño mayor que $n$ debemos mostrar $$m-k < n \leq m$$

Para ver esto, hacemos uso de $$\frac{n+k-1}{k}-1 < \left\lfloor\frac{n+k-1}{k}\right\rfloor \leq \frac{n+k-1}{k}$$

Así $$\frac{n-1}{k} < \left\lfloor\frac{n+k-1}{k}\right\rfloor \leq \frac{n+k-1}{k}\\ n-1< k \left\lfloor\frac{n+k-1}{k}\right\rfloor \leq n+k-1 \\ n-1< m \leq n+k-1 \\ $$

Ahora, desde la $n,m $ son enteros obtenemos las implicaciones $$n-1< m \Rightarrow n \leq m$$ y $$ m \leq n+k-1 \Rightarrow m-k \leq n-1 <n$$

Por lo tanto $$m-k < n \leq m$$ como se reivindica.