Un conjunto de números en donde nada puede ser hecho por la multiplicación de los demás en el conjunto.

Question

(Yo soy un programador, por favor, disculpe mi abuso o la falta de un adecuado lenguaje matemático)

El otro día necesitaba encontrar un número natural que es limpiamente divisible por todos los números enteros en el rango [1,10]

Para empezar, me di cuenta de que acababa de varios de ellos a todos:

1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 (a.k.a. 10!) = 3628800
3628800 mod 1 = 0
3628800 mod 2 = 0
3628800 mod 3 = 0
3628800 mod 4 = 0
3628800 mod 5 = 0
3628800 mod 6 = 0
3628800 mod 7 = 0
3628800 mod 8 = 0
3628800 mod 9 = 0
3628800 mod 10 = 0

Bueno, eso funciona, pero pensé que probablemente podría encontrar un número menor. Pensé que podía quitar por ejemplo, el factor de 6, debido a que puede ser hecho por la multiplicación de los factores 2 y 3, en el que también están en la lista.

Lo he intentado con solo incluir los números primos:

1 * 2 * 3 * 5 * 7 * 9 = 1890
1890 mod 1 = 0
1890 mod 2 = 0
1890 mod 3 = 0
1890 mod 4 = 2     uh-oh

Así, que no funciona. Es porque mientras que 4 puede ser hecha por la multiplicación de 2 y 2, sólo hay un 2 en la lista.

Lo que finalmente termina con:

1 * 2 * 4 * 5 * 7 * 9 = 2520

O: Un conjunto de números en un intervalo [1, N] que sólo incluye a los números que no pueden ser fabricados por la multiplicación de otros números en el conjunto, donde cada uno de esos números pueden ser usados sólo una vez.

Ahora, la pregunta (que es por pura curiosidad): este Es un común, conocido, llamado concepto matemático?

Answer 1

Dada una lista finita $(N_i)_{1\leq i\leq n}$ de los números naturales $\geq1$ uno se puede preguntar por el número más pequeño $N$ que es un múltiplo de todos los $N_i$. Esta $N$ se llama mínimo común múltiplo (MCM) de la $N_i$ y puede ser obtenido de la siguiente manera: Cada una de las $N_i$ tiene una única factorización en primos de la forma $$N_i=p_1^{\alpha_{i1}}\ p_2^{\alpha_{i2}}\ p_3^{\alpha_{i3}}\cdot\ldots=\prod_{k\geq1} p_k^{\alpha_{ik}}\ ,$$ donde $(p_1,p_2,p_3,\ldots)$ es la secuencia de los números primos, el $\alpha_{ik}$ son números naturales $\geq0$, y para cada una de las $i$ sólo un número finito de $\alpha_{ik}$$\ne0$.

Considere la posibilidad de una prima fija $p_k$. Este primer aparece en la $N_i$ con varios exponentes $\alpha_{ik}$, y no será una más grande entre ellos: Vamos a $$\rho_k:=\max\{\alpha_{ik}\>|\>1\leq i\leq n\}\ .$$ Esto significa: Entre el $N_i$ hay al menos uno que ha $p_k^{\rho_k}$ como un factor, pero ninguno contiene un mayor poder de $p_k$. Tomando de nuevo el teorema fundamental de la aritmética por sentado que se deduce que la LCM $N$ de la $N_i$ está dado por $$N=\prod_{k\geq1} p_k^{\rho_k}\ .\tag{1}$$

La fórmula (1) es más de naturaleza teórica. En la práctica, el LCM se determina utilizando el llamado algoritmo de euclides; y los primos no incluso hacer una aparición a continuación.

Answer 2

Estás buscando el mínimo común múltiplo de {1, 2, ..., 10}. Si generalizamos a lcm({1, 2, ..., n}) este es A003418, que tiene una gran cantidad de información sobre este problema. (Usted puede encontrar el OEIS un recurso útil en este tipo de problema.)

Aquí hay una manera de calcular estos números. Para todos los números primos del 2 al número de destino $n$, tome la potencia más grande de la prime que es menor o igual a $n$, y tomar el producto de todos estos primos poderes.