Sigue el camino…módulo 7

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: 432
  • 2 \cdot 2=4
  • 43-4=39
  • Como 39 no es múltiplo de 7 entonces 432 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:

Divisibilidad entre 7Para 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 239058. 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 239058 entre 7 es 1 (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.

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

23 Comentarios

  1. ¡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 \frac{n(n-1)}{2} 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 mejor el segundo método.

    En C# sería

    private static int [] newPos = new int [] { 0, 3, 6, 2, 5, 1, 4, 0, 3, 6, 2, 5, 1, 4, 0, 3 };
    private static int div7( string bigN ) {
    int p = 0, q = 0;
    foreach( char c in bigN.Reverse() )
    p = newPos [ ( q = p ) + ( c – ‘0’ ) ];
    return q;
    }

    El coste para n dígitos son n iteraciones, pero se puede reducir el número de iteraciones tantas veces como se desee e ir procesando por bloques de dígitos (haciendo el grafo para pares, trios, cuartetos, … de dígitos), dividiendo así el número de iteraciones en 2, 3, 4, …

    Vaya, que el segundo método efectivamente es mucho más eficiente que el primero (de ir restando).

    Publica una respuesta
  2. 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..

    Publica una respuesta
    • 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.

      Publica una respuesta
  3. 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 ( 3^k  ) por 7:

    Sea N el número y { a_k } las n cifras decimales que lo componen:

    N = sum_{k=0}^n a_k 10^k

    Entonces el resto al dividirlo por 7 es:

    \displaystyle{N \mod  7 = \left ( \sum_{k=0}^n a_k 10^k  \right ) \mod  7 = \sum_{k=0}^n  [ \left ( a_k 10^k  \ight ) \mod   7 ] =  \sum_{k=0}^n  [ \left ( a_k \mod  7  \right ) \left ( 10^k \mod   7  \right ) ] = \sum_{k=0}^n  [ \left ( a_k \mod  7  \right ) \left ( 10  \mod 7  \right ) ^k  ] = \sum_{k=0}^n [ \left ( a_k \mod  7  \right ) 3^k ]}

    Como en una suma (o en un producto) los sumandos (o los factores) pueden ser sustituidos por sus restos, vamos a calcular los  3^k mod  7 para 0 le k le 6:

      egin{array}{ccc}           k &  3^k & (3^k) mod 7           0 &  1 & 1           1 &  3 & 3           2 &  9 & 2           3 & 27 & 6           4 & 81 & 4           5 & 243 & 5           6 & 729 & 1           7 & 2181 & 3           vdots & vdots & vdots  end{array}

    la secuencia obtenida es 1,3,2,6,4,5,1… que COINCIDE con los saltos de las flechas blancas: si empezamos por la cifra 1, su fecha blanca nos lleva al 3, y de ahí al 2, y de ahí al 6 y de ahí al 4 y de ahí al 5 y de éste al 1 otra vez.

    Pero el factor 3^k está multiplicando (no sumando), así que, aunque veo la coincidencia con las flechas blancas no sé explicarlo.

    ¿me podéis ayudar?

    Publica una respuesta
  4. 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 ( 3^k  ) por 7:

    Sea N el número y { a_k } las n cifras decimales que lo componen:

    N = \sum_{k=0}^n a_k 10^k

    Entonces el resto al dividirlo por 7 es:

    N mod \ 7 = \left ( \sum_{k=0}^n a_k 10^k \right ) mod \ 7 =  \sum_{k=0}^n \big [ \left ( a_k 10^k \right ) mod \ 7 \big ] =  \sum_{k=0}^n \big [ \left ( a_k mod \ 7 \right ) \left ( 10^k mod \ 7 \right ) \big ] =  \sum_{k=0}^n \big [ \left ( a_k mod \ 7 \right ) \left ( 10  mod \ 7 \right ) ^k \big ] =  \sum_{k=0}^n \big [ \left ( a_k mod \ 7 \right ) 3^k \big ]

    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 (3^k mod \ 7 para 0 \le k \le 6):

    \begin{array}{ccc}           k &  3^k & (3^k) mod \ 7 \\           0 &  1 & 1 \\           1 &  3 & 3 \\           2 &  9 & 2 \\           3 & 27 & 6 \\           4 & 81 & 4 \\           5 & 243 & 5 \\           6 & 729 & 1 \\           7 & 2181 & 3 \\           \vdots & \vdots & \vdots  \end{array}

    la secuencia obtenida es 1,3,2,6,4,5… que COINCIDE con los saltos de las flechas blancas: si empezamos por la cifra 1, su flecha blanca nos lleva al 3, y de ahí al 2, y de ahí al 6 y de ahí al 4 y de ahí al 5 y de éste al 1 otra vez.

    Pero el factor 3^k está multiplicando (no sumando), así que, aunque veo la coincidencia con las flechas blancas no sé explicarlo.

    ¿me podéis ayudar?

    Publica una respuesta
  5. 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 \leq 11 cifras, de manera que podemos escribir a = r_{11}r_{10}\ldots r_1 r_0 , permitiendo que la primera cifra no-nula empezando por la izquierda no sea necesariamente r_{11} . Entonces a es divisible por 7 si, y sólo si,
    (r_0 + r_6 - r_3 - r_9) + 2(r_1 + r_7 - r_4 - r_{10}) + 3(r_2 + r_8 - r_5 - r_{11}) es múltiplo de 7.

    Publica una respuesta
  6. 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 n el número del círculo.

    Creo que no precisa más explicaciones ¿no?

    Saludos.

    Publica una respuesta
  7. @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?

    Publica una respuesta
  8. 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.

    Publica una respuesta
  9. @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.

    Publica una respuesta
  10. 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 por @avm (en http://gaussianos.com/sigue-el-camino-modulo-7/#comment-37028)?.

    Pues yo lo veo muy útil…

    Publica una respuesta
  11. 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.

    Publica una respuesta
  12. 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, especialmente si el que tiene el objeto contudente es el interlocutor.

    😉

    Publica una respuesta
  13. 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?

    Publica una respuesta
  14. No es mas rápido y sencillo hacerlo con una calculadora? que ganas de complicarse la vida…

    Publica una respuesta
  15. 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 que el número sea de tamaño monstruoso, no hará falta hacerlo más de una vez, y muy probablemente ni eso). El número resultante será congruente con el original, módulo 7, así que aplicamos el truquito éste de restar (aunque siendo números de 3 cifras, tampoco nos vamos a herniar por dividir) y listo.

    Lo de partir el número en cachitos también funciona para 11 y 13 (bueno, y para 77, 91 y 143), ya que 1001 es igual a 7·11·13. Aunque para el 11 hay técnicas mucho más sencillas, claro.

    Esto del grafo me suena a chino, la verdad. Me gusta demasiado usar la cabeza para cálculos numéricos como para dedicarme a esta variante (y mi método me gusta más :P).

    Publica una respuesta
  16. @Ñbrevu,

    el método que expones es al que hago referencia en http://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 http://gaussianos.com/sigue-el-camino-modulo-7/#comment-37026

    Publica una respuesta
  17. 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.

    Publica una respuesta
  18. 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.

    Publica una respuesta
  19. 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 353786. Entonces 2×1 + 3×2 + 1×7 + 5×3 + 4×5 + 6×3 + 2×7 + 3×8 + 1×6 = 112 que es múltiplo de 7. 112 : 2×1 + 3×1 + 1×2 = 7. No soy matemático sino ingeniero y esto lo hallé en un momento de aburrimiento en mi trabajo.

    Publica una respuesta
  20. Ah. Y los felicito por su blog, es muy interesante y gracias por todo lo que publican

    Publica una respuesta
  21. 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.

    Publica una respuesta

Trackbacks/Pingbacks

  1. Sigue el camino…módulo 7 (criterio de divisibilidad para el 7) - [...] Sigue el camino…módulo 7 (criterio de divisibilidad para el 7) gaussianos.com/sigue-el-camino-modulo-7/  por Borquez hace 2 segundos…
  2. Bitacoras.com - Información Bitacoras.com... Valora en Bitacoras.com: Existe una sencilla regla para comprobar si un número natural es divisible entre 7,…
  3. Sigue el camino…módulo 7 (criterio de divisibilidad para el 7) | Noticias - d2.com.es - [...] » noticia original [...]
  4. Tweets that mention Sigue el camino…módulo 7 | Gaussianos -- Topsy.com - [...] This post was mentioned on Twitter by gaussianos, redes sociales web. redes sociales web said: #hispaciencia Sigue el camino…módulo…
  5. Gaussianos cumple 5 años de vida - Gaussianos | Gaussianos - […] colaboración con Amazings), hablamos sobre un intento de demostración de P ? NP, os enseñé un grafo sobre la…

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *