¿Cuál es el algoritmo más eficiente para averiguar si un entero es divisible por 7?

Answer 1

1. Invierta el orden de los dígitos.
2. Multiplique cada dígito sucesivamente por 1, 3, 2, 6, 4, 5 y luego vuelva a 1, repitiendo la secuencia hasta que haya alcanzado el último dígito.
3. Suma todos los productos que obtuviste en el paso 2.
4. Si la suma es divisible por 7, entonces el número original es divisible por 7.

Por ejemplo, verifiquemos el número 282475249. Invierta los dígitos para obtener 942574282. Luego calcule:
9 * 1 + 4 * 3 + 2 * 2 + 5 * 6 + 7 * 4 + 4 * 5 + 2 * 1 + 8 * 3 + 2 * 2 = 133.
Esto sigue siendo un gran número, así que repitamos el proceso. Invierta los dígitos para obtener 331, luego calcule:
3 * 1 + 3 * 3 + 1 * 2 = 14.
14 es divisible por 7, por lo que el número original, 282475249, también es divisible por 7. (En realidad, ese número es solo [matemática] 7 ^ {10} [/ matemática]).

Este es el algoritmo más eficiente que conozco, pero hay otros. Muchos se enumeran aquí: ¿Cómo se determina si un número es divisible por 7?

Answer 2

Comience desde el último dígito hasta el primero, y multiplique cada uno de ellos por 1, 3, 2, 1, 3, 2, 1, 3, 2, … y así sucesivamente. Ahora resume las primeras tres respuestas, resta las siguientes tres, suma las siguientes tres, resta las siguientes tres, y así sucesivamente. Si el número final es divisible por 7, entonces el número original era divisible por 7.

Por ejemplo, considere el número 3489567284.

[matemáticas] 4 \ veces 1 = 4, 8 \ veces 3 = 24, 2 \ veces 2 = 4 [/ matemáticas]
[matemáticas] 7 \ veces 1 = 7, 6 \ veces 3 = 18, 5 \ veces 2 = 10 [/ matemáticas]
[matemáticas] 9 \ veces 1 = 9, 8 \ veces 3 = 24, 4 \ veces 2 = 8 [/ matemáticas]
[matemáticas] 3 \ veces 1 = 3 [/ matemáticas].

Ahora

[matemáticas] (4 + 24 + 4) – (7 + 18 + 10) + (9 + 24 + 8) -3 [/ matemáticas]
[matemáticas] = 32-35 + 41-3 = 35 [/ matemáticas]

que es divisible por 7. Por lo tanto, 3489567284 es divisible por 7 también.

EDITAR: Estoy abrumado por la respuesta a esta respuesta, ¡nunca lo esperé! Esta edición es en respuesta a varios comentarios a esta pregunta. Gracias por tus comentarios.

1) Este algoritmo es una implementación de ‘n mod 7’ usando solo [math] + [/ math], [math] – [/ math] y [math] \ times [/ math]. Si ya tiene implementada la función [math] \ mod [/ math], utilícela por todos los medios (aunque todavía creo que este algoritmo es más eficiente).

2) Para responder la pregunta ‘¿cómo sé que 35 es divisible por 7?’, Simplemente aplique este algoritmo al número 35. Continúe hasta que termine con solo un dígito. Ver punto 3) a continuación.

3) Para modificar este algoritmo para implementar ‘n mod 7’, haga lo siguiente a su entrada [math] n [/ math]:

[matemática] n \ mod 7 = n, [/ matemática] si [matemática] 0 \ leq n \ leq 6 [/ matemática]
[matemática] n \ mod 7 = n-7, [/ matemática] if [matemática] 7 \ leq n \ leq 9 [/ matemática]
[matemática] n \ mod 7 = – ((- n) \ mod 7), [/ matemática] si [matemática] n <0 [/ matemática]
[matemáticas] n \ mod 7 = reducir (n) \ mod 7, [/ matemáticas] de lo contrario
donde [math] shrink (n) [/ math] devuelve el número obtenido en los pasos escritos antes de la edición.

P.ej
[matemáticas] -36124706 \ mod 7 [/ matemáticas]
[matemáticas] = – (36124706 \ mod 7) [/ matemáticas]
[matemáticas] = – ((1 \ veces 6 + 3 \ veces 0 + 2 \ veces 7-1 \ veces 4 [/ matemáticas]
[matemáticas] -3 \ veces 2-2 \ veces 1 + 1 \ veces 6 + 3 \ veces 3) \ mod 7) [/ matemáticas]
[matemáticas] = – (23 \ mod 7) [/ matemáticas]
[matemáticas] = – ((1 \ veces 3 + 3 \ veces 2) \ mod 7) [/ matemáticas]
[matemáticas] = – (9 \ mod 7) [/ matemáticas]
[matemáticas] = -2 [/ matemáticas]

Answer 3

En la página vinculada por Barak Shoshany, algunas personas mencionaron el siguiente algoritmo: cortar el último dígito, duplicarlo, restarlo del resto del número y repetir hasta que solo queden uno o dos dígitos. El número final será divisible por 7 si y solo si el original era.

La razón por la que esto funciona es que 2 * 10 es congruente con -1 (mod 7). Esto sugiere un método para crear dicho algoritmo de divisibilidad para cualquier número entero N que sea relativamente primo para 10:

1. Encuentre k tal que 10k sea congruente con -1 (mod N)
2. El algoritmo deseado es: cortar el último dígito, multiplicarlo por k, restar el resultado del resto del número y repetir.

Tenga en cuenta que k puede ser negativo. Veamos cómo funciona esto para algunas otras opciones de N:

• N = 3 o N = 9: elija k = -1. El algoritmo resultante nos dice que cortemos el último dígito y lo agreguemos al resto del número, repetidamente.
• N = 11: elija k = 1. El algoritmo resultante nos dice que cortemos el último dígito y lo restemos del resto del número, repetidamente.
• N = 13: elija k = -4. El algoritmo resultante nos dice que cortemos el último dígito, lo cuadrupliquemos y lo agreguemos al resto del número, repetidamente.

Pero esto es solo por interés. Estoy de acuerdo con Ray Li; El método más eficiente a mano realmente es por división larga, en lugar de trucos ingeniosos como este.

Answer 4

De: Divisibility by 7 es un Walk on a Graph.

Para encontrar el resto al dividir un número entre 7, comience en el nodo 0, para cada dígito D del número, muévase a lo largo de las flechas negras D (para el dígito 0 no se mueva en absoluto), y al pasar de un dígito al siguiente , mueva a lo largo de una sola flecha blanca.

Por ejemplo, sea n = 325 . Comience en el nodo 0, avance a lo largo de 3 flechas negras (al nodo 3), luego 1 flecha blanca (al nodo 2), luego 2 flechas negras (al nodo 4), luego 1 flecha blanca (al nodo 5) y finalmente 5 negras flechas (al nodo 3). Terminar en el nodo 3 muestra que el resto al dividir 325 por 7 es 3.

Me parece una carita de animal.

Answer 5

¿Puedes verificar si el número es divisible por 7 o no?

Pseudocódigo:
Sea ‘n’ el número que debemos verificar:

  mientras que (n> = 10)
                  representar n = 10 * q + r
                  n = | r - 2 * q |
           si (n == 7 || n == 0)
                  print 'No es divisible por 7'

Prueba:
Por ejemplo: (n mod 7) = rem (rem es el resto después de dividir n entre 7)

n = 10 * q + r
((10 * q + r) mod 7) = rem
((7 * q + 3 * q + r) mod 7) = rem
(3 * q + r) mod 7 = rem ———— eq. 1

n = 10 * q + r
((10 * q + r) mod 7) = rem
((9 * q + 3 * r + q – 2 * r) mod 7) = rem
(3 * (3 * q + r) + q – 2 * r) mod 7) = rem

Entonces de la ec. 1:
(3 * rem + q – 2 * r) mod 7 = rem
Por lo tanto para rem = 0
(q – 2 * r) mod 7 = 0

Answer 6

La pregunta de si el número n representado en la base b es divisible por k siempre se puede resolver en el tiempo O (log n) para las constantes b y k. Solo necesita construir un Autómata determinista de estado finito con k estados que representen las clases de enteros módulo k. Las transiciones del DFA marcadas por el siguiente b-git de n corresponden a multiplicar el número de estado por b y sumar el siguiente b-git de n módulo k.

Consulte las páginas 86-104 de http://crypto.cs.mcgill.ca/~crep …
para la construcción explícita de tal autómata para k = 7 yb = 10.

Una vez que tenga este autómata, para cualquier número n en la base b, comience en el estado “0” y lea n, b-git por b-git, pasando de un estado a otro según cada b-git. Cuando llegue al final de los b-gits de n, el estado final determina la divisibilidad por k exactamente si termina en el estado “0”. Su tiempo de ejecución es exactamente el número de b-gits de su número n. Este es el mejor tiempo de ejecución posible ya que se deben considerar todos los b-gits (siempre que byk sean relativamente primos). Por supuesto, algunos casos pueden ser mejores cuando byk no son relativamente primos como b = 10 yk = 2 o b = 10 yk = 5 (mire solo el último dígito).

Como la pregunta no especifica una base b particular para la representación de los enteros de entrada, me vi obligado a proporcionar una solución para cualquier b …

Answer 7

considere un número A = 10b + c
(A tiene c en el lugar de la unidad y el número que excluye el lugar de la unidad es b)
ahora resta dos veces el número de lugar de la unidad del número restante (es decir, b-2c)
definamos esto como D
ahora D = 10e + f
repita el proceso mencionado anteriormente hasta obtener un número de un solo dígito (puede ser positivo o negativo)
si ese número de un solo dígito es -7, 0, 7 (es decir, divisible por 7), entonces el número original también es divisible por 7

por ejemplo: 13384
1338-8 = 1330
133-0 = 133
13-6 = 7
por lo tanto, 13384 es divisible por 7

pero si consideramos 1562 entonces,
156-4 = 152
15-4 = 11
1-2 = -1
-1 no es divisible por 7
por lo tanto 1562 no es divisible por 7

Answer 8

Hay una manera muy simple de encontrar esto si ya está en binario (como en una computadora) a través de sumas repetidas.

(Además, no es nada difícil convertir la base 10 a binario. Solo vea si el número es par o impar mirando el último dígito. Si es impar, ponga 1 como dígito menos significativo, de lo contrario ponga 0. , divida el número entre 2, ignorando el resto, y hágalo nuevamente, escribiendo el siguiente número a la izquierda del anterior. Cuando finalmente llegue a 0 después de una división (es decir, tenía 1 antes), deténgase. Esa es su número en binario!)

Si el número ya está en binario, puede convertir fácilmente el número a base 8. (De hecho, binario es como la base 8 en algún sentido ya: solo trate cada 3 bits como un dígito octal). A partir de ahí, solo tiene para sumar repetidamente todos los dígitos octales hasta obtener 1 dígito. Si terminas con 7, el número original es divisible por 7. De lo contrario, obtienes el resto cuando divides el original entre 7 (al igual que encontrar el resto de un número base 10 dividido por 9).

Entonces, por ejemplo, digamos que tenemos el número binario 1010001110101010100. (Esto es 335188 en decimal) Convirtiendo esto a octal (agrupando los bits en 3), encontramos que el número es 1 010 001 110 101 010 100 -> 1216524. Luego, sume repetidamente todos los dígitos en la aritmética de base 8 hasta llegar a 1 dígito octal. Entonces, 1 + 2 + 1 + 6 + 5 + 2 + 4 = 25, 2 + 5 = 7. Como terminamos con 7, el número original también es divisible por 7. Wohoo!

Answer 9

Gracias por la A2A
Para ambos 7 y 13:

Divida el número en trozos de 3 dígitos comenzando desde el dígito más a la derecha, como:

413512 significa 413512
4231 significa 4231
6432145213 significa 6432145213

Ahora, comenzando desde la derecha, agregue las partes en lugares impares y reste la parte en lugares pares como:

413512 significa −413 + 512 => 99 => resto 1
4231 significa −4 + ​​231 => 227 => resto 3
6432145213 significa −6 + 432−145 + 213 => 494 => resto 4

El resto sería el mismo incluso si dividimos el resultado de la parte de cálculo como se sugirió anteriormente en lugar del número en sí, encuentro este método más fácil que el sugerido en todas las otras respuestas hasta ahora.

Para el 13 les dejo la parte de cálculo.

Answer 10

La regla que funciona para mí es “restar dos veces el décimo dígito del resto del número restante si el resultado es un número que es divisible por 7 o cero, entonces el número es divisible por 7, siga el proceso recursivamente”.

Número xyz es divisible por 7
si xy – 2z es divisible por 7

Por ejemplo,
14 -> 1 – 2 * 4 = -7 (divisible por 7)
21 -> 2 – 2 * 1 = 0 (divisible por 7)
133 -> 13 – 2 * 3 = 7 (divisible por 7)
de manera similar para un número mayor
3489567284 -> 348956720 -> 34895672 -> 3489563 -> 348950 -> 34895-> 3479 -> 329 -> 14 (divisible por 7)

Answer 11

Hice una prueba para ver que 758115172386169 (número aleatorio en mi calculadora) es divisible por 7.

75811517238616–18 = 75811517238598

7581151723859–16 = 7581151723843

758115172384–6 = 758115172378

75811517237–16 = 75811517221

Humbug, ya ha pasado un minuto. No me importa si 7 lo divide.

Lo hice a mano, a la antigua usanza, y descubrí que el cociente era 108302167483738 con el resto 3. Uf. No es divisible por 7. Eso tomó 30 segundos.

Le pregunté a Siri y en su nuevo acento irlandés me dio la respuesta en unos 10 segundos (incluido el tiempo de consulta).

Conclusión, pregunta a Siri.

Answer 12

Déjame explicarte los pasos junto con un ejemplo.

Prueba : para encontrar el resto del número “845435497” cuando se divide por 7. (Claramente, si el resto es 0, entonces el número es divisible por 7)

PASO 1: Comience desde el final y divida los números en grupos de 2 dígitos.
8 | 45 | 43 | 54 | 97

PASO 2: Divida cada uno de estos grupos de números de 2 dígitos entre 7 y escriba el resto a continuación.
8 | 45 | 43 54 97

1 3 1 5 6

PASO 3: multiplique cada número por 2 y agréguelo al siguiente número.

1 * 2 = 2
2 + 3 = 5
5 * 2 = 10
10 + 1 = 11
11 * 2 = 22
22 + 5 = 27
27 * 2 = 54
54 + 6 = 60

PASO 4: Divida el número final entre 7 y obtenga el resto.
El resto de 60/7 es 4. Por lo tanto, 4 es el resto cuando “845435497” se divide por 7.

Answer 13

Hay un truco simple si restringe la pregunta a enteros con menos de cuatro dígitos en su representación decimal. Tal número se puede escribir como [matemática] a_210 ^ 2 + a_110 ^ 1 + a_010 ^ 0 [/ matemática] con cada [matemática] a_i [/ ​​matemática] siendo un dígito en [matemática] \ {0, \ ldots, 9 \}[/matemáticas]. Tenga en cuenta que [matemáticas] 10 ^ 0 \ equiv 1 \ mod 7 [/ matemáticas], [matemáticas] 10 ^ 1 \ equiv 3 \ mod 7 [/ matemáticas] y [matemáticas] 10 ^ 2 \ equiv 2 \ mod 7 [ /matemáticas]. A partir de esto, puede mostrar que un número entero de tres dígitos [matemática] m = a_210 ^ 2 + a_110 ^ 1 + a_010 ^ 0 [/ matemática] es divisible por [matemática] 7 [/ matemática] (es decir, [matemática] m \ equiv 0 \ mod 7 [/ math]) si y solo si [math] (2a_2 + 3a_1 + a_0) \ equiv 0 \ mod 7 [/ math].

Answer 14

Creé una regla para la divisibilidad entre siete, once y trece cuyo algoritmo para la divisibilidad entre siete es este:
N = a, bcd; a ‘≣ (- cd mod 7 + a) mod 7; cd se elimina y si 7 | a’b entonces 7 | N. El procedimiento se aplica de derecha a izquierda repetidamente hasta que se alcanza el par de dígitos más a la izquierda. Si el par más a la izquierda está incompleto, considere a = 0.
Ejemplo: N = 382,536, usando lenguaje simple:
36 a 42 = 6; 6 + 2 – 7 = 1 → 15; 15 a 21 = 6; 6 + 3 – 7 = 2 → 28; 7 | 28 y 7 | N.
Esta regla se menciona en mi libro no publicado (oficialmente registrado): ¿Divisibilidad entre 7, el final de un mito?
Para ilustrar la aplicación de mi algoritmo inserto este video:

Answer 15

Suma los lugares. Si este es un múltiplo de 7 o 17, también lo es el número.

Por ejemplo, 1.20 es un múltiplo de 7, porque 1 + 20 = 21 es un múltiplo de 7. Del mismo modo, 9.85.10.15 da 9 + 85 + 10 + 15 = E9, es un múltiplo de 7 y 17.

Supongamos que esto funciona solo con números largos.

Answer 16

Quite el último dígito, duplíquelo, reste el número original truncado y si el resultado es un múltiplo de siete, entonces también lo es el número original, siga repitiendo hasta que el número sea lo suficientemente pequeño.

Ejemplo:
1) 133 sea la entrada.
13- (2 * 6) = 7 (divisible por 7)

2) 861 sea la entrada
86- (2 * 1) = 84
8- (2 * 4) = 0 (divisible por 7)

3) 952 sea la entrada
95- (2 * 2) = 91
9- (2 * 1) = 7 (divisible por 7)

Answer 17

Multiplica el último dígito por dos y restarlo de los dígitos restantes. Si obtienes un múltiplo de siete, entonces el número entero también es divisible por siete:
322
32-4 = 28 que es divisible por siete
por lo tanto, 322 es divisible por 7 (7 * 46)

Answer 18

Probemos con el número [math] 282475249 [/ math]. La mayoría debería poder mirarlo y ver rápidamente que dividir entre [matemáticas] 7 [/ matemáticas] da como resultado [matemáticas] 40353607 [/ matemáticas] sin resto. Si hubiera un resto, entonces no sería divisible por [matemáticas] 7 [/ matemáticas].

Answer 19

El algoritmo más eficiente es tenerlo escrito en la base 7 y ver si el último dígito es cero.

Answer 20

Bueno, estos dos enlaces pueden ser suficientes:

http://en.wikipedia.org/wiki/Div …

y

Comprobar divisibilidad por 7 – GeeksforGeeks