Existe una sencilla regla para comprobar si un número natural es divisible entre 7, que es la siguiente:
Separamos la cifra de las unidades del número inicial, la multiplicamos por 2 y se la restamos al resto del número (lo que quedó sin las unidades). Si obtenemos un múltiplo de 7 entonces el número inicial es múltiplo de 7, y si obtenemos un número que no es múltiplo de 7 pues el inicial tampoco lo es. Si obtenemos un número demasiado grande y no sabemos si es múltiplo de 7 o no, repetimos el proceso anterior las veces necesarias hasta que lleguemos a un número del que sepamos si es o no múltiplo de 7.
Pongamos un ejemplo:
- Número:
- Como
no es múltiplo de 7 entonces
no es múltiplo de 7
Particularmente veo que este algoritmo es algo lento si el número es demasiado grande, pero bueno, al menos tenemos uno, ¿no?
Uhmmm…¿no habrá alguna otra forma? Pues sí, el mundo de la divisibilidad nos tiene guardada una sorpresa en lo que al 7 se refiere…
El grafo de la divisibilidad entre 7
…en forma de grafo.
El blog de Tanya Khovanova es uno de esos sitios en los que muy a menudo pueden encontrarse auténticas perlas matemáticas. La que os os voy a presentar aquí la he encontrado allí, aunque no es de ella, sino de David Wilson. Es un grafo a partir del cual no sólo podemos saber si un número es divisible entre 7 de manera algo más rápida que con el algoritmo anterior (al menos bajo mi punto de vista) sino también el resto que deja dicha división en el caso de no serlo. Vamos a verlo:
Para saber si un número natural es divisible entre 7 comenzamos en el cero, recorremos desde él tantas flechas negras como indique la primera cifra del número y después seguimos la flecha blanca que salga del punto al que hemos llegado. Tomamos la segunda cifra y hacemos lo mismo: desde el punto donde nos encontramos recorremos tantas flechas negras como indique la segunda cifra y después la flecha blanca que nos encontramos en el destino. Y así sucesivamente. Cuando lleguemos a la última cifra recorremos desde el punto donde nos encontremos tantas flechas negras como ella indique y el punto al que lleguemos nos dice el resto de dividir el número inicial entre 7.
Tomemos un número grande, digamos el . Con el método anterior posiblemente tardaríamos un buen rato en comprobar si nuestro número es divisible entre 7 o no (podéis comprobarlo). Además no conoceríamos el resto de dicha división. Probemos con nuestro grafo:
- Desde el 0 dos flechas negras, llegando al 2; ahora una flecha blanca y llegamos al 6
- Desde el 6 tres flechas negras, llegando al 2; ahora una flecha blanca y llegamos otra vez al 6
- Desde el 6 nueve flechas negras, llegando al 1; ahora una flecha blanca y llegamos al 3
- Desde el 3 no recorremos ninguna flecha negra, por lo que nos quedamos en el 3; ahora una flecha blanca y llegamos al 2
- Desde el 2 cinco flechas negras, llegando al 0; ahora una flecha blanca, por lo que nos quedamos en el 0
- A para finalizar, desde el 0 ocho flechas negras, llegando al 1.
Por tanto, el resto de dividir entre 7 es
(y por tanto no es divisible entre 7).
¿Alguien nos podría explicar por qué funciona este método?
Este grafo es una mejora de otro grafo del propio David Wilson que sólo nos indicaba si el número escogido era o no divisible entre 7.
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
[…] Sigue el camino…módulo 7 (criterio de divisibilidad para el 7) gaussianos.com/sigue-el-camino-modulo-7/ por Borquez hace 2 segundos […]
Información Bitacoras.com…
Valora en Bitacoras.com: Existe una sencilla regla para comprobar si un número natural es divisible entre 7, que es la siguiente: Separamos la cifra de las unidades del número inicial, la multiplicamos por 2 y se la restamos al resto del número (l……
¡Genial! El primer método, en el peor de los casos exigirá acarrear el resíduo de la resta (para cada dígito procesado), y en el mejor de los casos exigirá realizar una única resta (el último dígito). El peor caso por tanto exige procesar dígitos en total, es decir O(n^2). El segundo método está perfectamente acotado y existen muchas alternativas, por ejemplo: 1. iterar. 2. sumar y calcular módulo. 3. sumar y asignar nuevo índice. La tercera opción por ejemplo requiere prácticamente el coste del mejor caso del primer método (es decir O(n)), por lo que parece claro que es mucho… Lee más »
[…] » noticia original […]
Creo que funciona porque, las flechas negras van acumulando el resto de la división por siete.
Mientras que las flechas blancas representan ese resto multiplicado por diez (al procesar cada dígito el resto se multiplica por diez, por eso en el último dígito no seguimos flecha blanca).
Ejemplo:
1-> 10 mod 7 = 3
2-> 20 mod 7 = 6
3-> 30 mod 7 = 2
4-> 40 mod 7 = 5
5-> 50 mod 7 = 1
6-> 60 mod 7 = 4
0-> 0 mod 7 = 0
que coinciden con los saltos de flechas blancas..
Es exactamente eso. Si escribimos el número 3245= (((3×10)+2)x10+4)x10+5 se entiende perfectamente lo que estamos haciendo al seguir el grafo. Las flechas negras «manejan» los restos de los dígitos en la expresión decimal del número y las flechas blancas «manejan» las multiplicaciones por 10 que se ven en esta expresión.
Hola Creo que ese método funciona porque, por una parte, la flecha negra simboliza el resto (o módulo) al dividir una cifra decimal por 7 y además la flecha blanca simboliza el resto de dividir una potencia entera de 3 () por 7: Sea N el número y las n cifras decimales que lo componen: Entonces el resto al dividirlo por 7 es: Como en una suma (o en un producto) los sumandos (o los factores) pueden ser sustituidos por sus restos, vamos a calcular los para : la secuencia obtenida es 1,3,2,6,4,5,1… que COINCIDE con los saltos de las… Lee más »
[…] This post was mentioned on Twitter by gaussianos, redes sociales web. redes sociales web said: #hispaciencia Sigue el camino…módulo 7: Existe una sencilla regla para comprobar si un número natural es divisible… http://bit.ly/aQ974T […]
Hola Creo que ese método funciona porque, por una parte, la flecha negra simboliza el resto (o módulo) al dividir una cifra decimal por 7 y además la flecha blanca simboliza el resto de dividir una potencia entera de 3 () por 7: Sea N el número y las n cifras decimales que lo componen: Entonces el resto al dividirlo por 7 es: Como en una suma (o en un producto) los sumandos (o los factores) pueden ser sustituidos por sus restos, podemos sustituir las potencias de 3 por sus restos ( para ): la secuencia obtenida es 1,3,2,6,4,5… que… Lee más »
A me enseñaron el año pasado otro criterio, que es fácil de demostrar usando congruencias:
Sea a un entero positivo cuya expresión decimal tiene
cifras, de manera que podemos escribir
, permitiendo que la primera cifra no-nula empezando por la izquierda no sea necesariamente
. Entonces a es divisible por 7 si, y sólo si,
es múltiplo de 7.
El método está bien como curiosidad, sólo por eso se merece esta entrada, de hecho, voy a intentar descubrir sus secretos. Pero ninguno de los dos métodos es mejor que hacer la división mentalmente ignorando el cociente. Al ser un número tan pequeño es muy fácil ir obteniendo los restos hasta llegar al último dígito. El método funciona porque se cumple que: (10 * a + b) mod 7 = ((10 * a) mod 7 + b) mod 7 Lo cual no precisa demostración. El grafo está hecho de modo que las flechas blancas apuntan a n*10 mod 7, siendo… Lee más »
@Sive «…Pero ninguno de los dos métodos es mejor que hacer la división mentalmente ignorando el cociente…»
No lo entiendo. 🙁
Por otra parte, la única pega que veo es que (al menos así como está) no es paralelizable, mientras que el método expuesto en http://es.wikipedia.org/wiki/Divisibilidad sí.
Si tuviera que revisar la divisibilidad para un único número muy grande usaría el método de wikipedia paralelizándolo, pero si tuviera que revisar muchos números (al menos tantos como procesadores disponibles) usaría el expuesto aquí.
¿Hay otra forma más rápida?
En realidad lo que hace el grafo es exactamente lo mismo que cuando nosotros hacemos una división a mano.
Por ejemplo, si dividimos ABCDE entre siete, tomaríamos la cifra A, la dividimos por el 7, el resto (lo llamamos Ra) de esta división lo colocamos debajo, y «bajamos» la B. El número que nos queda es 10*Ra + B, y con él hacemos lo mismo.
Obviamente, se podrían hacer otros grafos, igual de válidos pero probablemente menos prácticos para otros primos.
@josejuan
(Todo esto sería mentalmente)
239058 mod 7
Las dos primeras cifras son 23, el múltiplo más cercano por debajo es 21, a 2. Por tanto hago lo mismo con el 29. El múltiplo más cercano es 28, a 1. Ahora toca el 10, a 3. El 35, a 0. El 8 a 1.
Lo mismo que dividir sobre el papel, pero haciendo caso sólo a los restos.
Casualmente, es lo mismo que hace el grafo.
Gracias @Sive, ahora está clarísimo. De todos modos, a la hora de dividir por 7 «manualmente» debemos conocer la tabla de división del 7 desde el 1 al 69 y del 7 al 9 (72 elementos) cuando la tabla del grafo son sólo 7 elementos. Es decir, son la misma operación, pero con el grafo se ha comprimido la máquina de estado. Uhm… ¿cual será el tamaño mínimo (del grafo) para cualquier número N?, ¿N? (parece que sí debería poderse, pues los resíduos son únicos [de 0 a N-1]). Y en cuanto a generar el grafo, ¿es siempre el indicado… Lee más »
Ah, no había visto el comentario de avm.
Sí, siempre sería igual, no se me ocurre ninguna razón por la que no deba funcionar con cualquier número.
Yo no lo veo práctico porque, para empezar, debes llevar el grafo pintado contigo, y para eso llevo una calculadora jeje.
Saludos.
«Yo no lo veo práctico porque…»
Ja, ja, claro, … me refería usándolo en un ordenador.
Lo más rápido es exigir al interlocutor que el número esté en base 7 y, entonces, si termina en 0 es que es divisible y si no, pues no. Chupao. Pero para ello es necesario disponer de algún objeto contudente, de lo contrario no podremos exigirlo y nos tocaría calcularlo a nosotros. En caso de que no tengamos el objeto contundente, entonces lo más efectivo es hacer el siguiente cálculo: el número … NO es divisible por 7. Y acertamos 6 de cada 7 veces. Si es posible, inténtese colar este método con divisores más grandes que será más efectivo,… Lee más »
en serio no ves mas facil dividir?
es entre 7 ,se puede hacer de cabeza (si fuera entre 13 ya seria algo mas complicado, ¿pero del 7?)
me parece poco menos que inmediata
239058
23 resto 2
29 resto 1
10 resto 3
35 resto 0
8 resto 1
una pregunta ¿por que el numero lo poneis como imagen?
No es mas rápido y sencillo hacerlo con una calculadora? que ganas de complicarse la vida…
Hombre, pero hay un método para reducir el estudio de la divisibilidad por 7 de un número a la de otro de tres cifras. 1001 es múltiplo de 7, como todos sabemos o al menos podemos comprobar rápidamente. Eso significa que 1000 es congruente con -1, módulo 7; así que basta con coger el número y partirlo en cachitos de 3 en 3, empezando por la derecha (como si estuviéramos haciendo una raíz cúbica). Luego, vamos sumando cada «cachito» impar y restando los pares. Si el resultado final tiene más de 3 cifras, se vuelve a repetir el proceso (salvo… Lee más »
@Ñbrevu,
el método que expones es al que hago referencia en https://gaussianos.com/sigue-el-camino-modulo-7/#comment-37034 y que explican en Wikipedia.
Como decía, éste método únicamente es mejor (salvo error mío, claro) que el expuesto por @^DiAmOnD^ en que es paralelizable, en otro caso (no merezca/se pueda paralelizar) es mejor el del grafo, al tener una constante de complejidad mucho menor.
Tal y como comenté en https://gaussianos.com/sigue-el-camino-modulo-7/#comment-37026
Podemos olvidarnos del grafo, si seguimos la regla de las flechas blancas:
El número del cual parte lo multiplicamos por 3, y al producto así obtenido le calculamos su mod 7.
Sé que llego algo tarde para comentar, pero me he quedado boquiabierto y ojiplático a falta de 2 horas para mi primera clase universitaria.
[…] colaboración con Amazings), hablamos sobre un intento de demostración de P ? NP, os enseñé un grafo sobre la divisibilidad entre 7, os presenté la historia de Gödel y la posible dictadura en EEUU y os hablé sobre fracciones […]
Hola. Encontré una forma no sé si alguién la sepa. Para saber si un número es divisible entre siete, se divide el número en bloques de seis cifras emprezando por la derecha. Luego a cada bloque se le sobrepone el número 546231. Esto es a cada primera cifra se le multiplica por 1, a la segunda por 3, a la tercera por 2 y así. Luego se suman estos resultados y si la suma es múltiplo de 7 entonces el número lo es. Por ejemplo el número 127353786 es divisible entre 7. Se se divide en dos bloques 127 y… Lee más »
Ah. Y los felicito por su blog, es muy interesante y gracias por todo lo que publican
Hola a todos, el grafo a pesar de ser algo… extraño (por eso de flechas blancas y negras) lo que esconde detrás es la idea de AUTÓMATA FINITO DETERMINISTA, alguien preguntaba cuál sería el «menor» grafo para determinar la divisibilidad por 7, existe un algoritmo para reducir un autómata finito determinista a su «autómata mínimo». Esto es algo bastante estudiado en ciencias de la computación, al fin y al cabo un ATF no deja de ser una Máquina de Turing.