Hay un número divisible por todos los números enteros del 1 al 200, a excepción de dos números consecutivos. ¿Cuáles son los dos?

Question

Reitero la pregunta, básicamente hay algún número, $n$ que existe que es múltiplo de todos los números enteros $1, \dots, 200$, a excepción de dos números consecutivos en ese rango. El objetivo es encontrar cuáles son esos dos números enteros consecutivos son. La respuesta no es trivial, ya que $n$ debe ser divisible por todos los números, es difícil encontrar dos números al lado de cada uno de los otros los múltiplos de los números no son menos de $200$ e tal que aquellos que no pueden ser el primer factorizados en los números que están en la factorización prima de $n$.

He tratado de hacer este cálculo, pero el MCM de los números en el rango (menos dos de ellos) es descomunal y la comprobación de la condición de divisibilidad parece que no funciona en mi equipo. El problema sería sencilla si los dos números no tienen que ser consecutivos, ya que sólo podríamos seleccionar dos números primos, pero ya que uno debe ser, esto no es posible.

Estoy tratando de pensar en las propiedades de divisibilidad que podría ayudar, pero no he encontrado nada que trabajaron aún. Por ejemplo, yo estaba buscando los números que un primer ejemplo de que un número antes o después de que es el cuadrado de un número primo. De esta manera, podríamos decir que el primer número se omite de $n$ y que no es sólo un factor de la raíz cuadrada del número en $n$. No estoy seguro de si eso sería definitivamente el trabajo, pero a pesar de que no podía encontrar esos números. Traté de otro cuadrado perfecto y un número primo, $196$ e $197$, pero debe haber factores suficientes para hacer dos $14$s en $n$, por lo que no funciona bien.

Yo no soy de experiencia en todo en la teoría de los números o de la matemática discreta, esto es sólo un rompecabezas que he escuchado. (También, como referencia, no sé la respuesta a la ingeniería inversa algo de). Cualquier ayuda se agradece!

Gracias!

Answer 1

Excelente pregunta! La respuesta es $127$ e $128$... pero, ¿por qué? Si quieres encontrar un número divisible por $1,2,3,4$ usted podría multiplicar estos números y decir $24$. Sin embargo, pronto te das cuenta de $4$ ya es un múltiplo de $2$; se puede utilizar sólo $3\times4$ conseguir $12$. Por lo tanto, sólo es necesario multiplicar las mayores potencias de los números primos que el factor de que todos los dígitos de $2$ a $200$ para obtener un número que sea divisible por todos los números enteros de $1$ a $200$.

Si usted hace esto, usted encontrará el número de es $2^7\cdot3^4\cdot5^3\cdot7^2\cdot11^2\cdot13^2\cdot17\cdot19\cdot23\cdot29\cdot\ldots$(el resto de los números primos hasta $199$) = un número muy grande.

Lo siguiente que necesitamos es encontrar una restricción para eliminar dos números consecutivos. Uno de los dos números debe ser par. La única manera de eliminar un número desde el cálculo anterior sin modificar cualquiera de los otros números primos es reducir el poder de $2^7$ a $2^6$; esto elimina el número de $128$ de la lista. Desde $127$ es también un número primo, también puede ser removido de la lista sin que afecte a cualquiera de los otros números primos en la lista...

Espero que esto ayude.

Answer 2

Sugerencia: Piense acerca de cómo muchos de los factores de $2$ el número va a tener y encontrar un primer cercanos.

Answer 3

El proceso de pensamiento (probablemente parcialmente orden inverso):

• $m<200<2m\implies m>100$
• si $m$ no dividen por una mayor potencia principal de otros números, por lo menos un número primo, entonces su factorización, puede estar compuesto por otros números.
• 243 es la siguiente potencia de 3 después de 81, que es demasiado grande (y que pasa por todos los otros poderes más grandes de los números primos), y 162 falla en escapar de 81.
• mayor potencia de 2, en el intervalo de una factorización de la es $2^7=128$, que es demasiado grande para otros números primos (incluyendo 2) para ser añadido.
• $129=3×43\implies (127,128)$

Editar

Segundo punto fue este:

• Si $$m=p^x\cdot q^y$$ then its factorization, can be made up for by the product of a number that has $p^x$ in its factorization, and another that has $p^y$ in its factorization. It follows that, if at least one of $x,y$ aren't unique to $m$, then $m$ is a divisor of $$n

Answer 4

Desde que usted mencionó específicamente tratando de resolver este problema computacionalmente, espero que sea de acuerdo a publicar algunas código de Python aunque no estamos en StackOverflow.

Mientras que usted está trabajando con la norma acotada enteros, Python no debería tener ningún problema calculando lcm para números grandes o comprobación de la divisibilidad. No trabajo con flotadores (por ejemplo 1.3279275150902608e+87) o numpy de tamaño fijo enteros.

from functools import reduce
from math import gcd


def lcm(x, y):
    return x * y // gcd(x, y)


N = 200
for i in range(1, N+1):
    # Testing i and i + 1
    all_except_two = list(range(1, i)) + list(range(i + 2, N + 1))
    lcm_all_except_two = reduce(lcm, all_except_two)
    divisible_by_i = (lcm_all_except_two % i == 0)
    divisible_by_i_plus_one = (lcm_all_except_two % (i + 1) == 0)
    if not divisible_by_i and not divisible_by_i_plus_one:
        print(f"{lcm_all_except_two}\nisn't divisible by either {i} or {i+1}.")

Se emite:

1327927515090260884407345538562367745796828278681721394601759928808007945120777126248000 no es divisible por cualquiera de las 127 o 128.

en unos pocos milisegundos. También funciona para N=500.

Answer 5

Uno de los dos números consecutivos es incluso vamos a llamarlo $m$ si $m\neq 128$ entonces ambos $m/2$ e $128$ dividir el número por lo tanto $lcm(m/2,128)$ divide el número y $m$ divide $lcm(m/2,128)$ así que por transitividad $m$ divide el número; contradicción a fin de $m=128$ y te deja con dos opciones para el otro.