Encontrar $n$ tal que $n$ no dividir cualquier número entero en el conjunto de

Question

Se le da un conjunto de números enteros $\{a, b, c, d, e, f, g, \ldots\}$. Encontrar el mínimo $n$ que no divida a cualquier número de la serie.

Este es un problema de programación, pero estoy en busca de una solución matemática.

Answer 1

Deje que el conjunto se $A = \{ n_1, \ldots, n_N \}$, donde los elementos $n_i$ están ordenados en orden ascendente. Deje $P(n)$ ser verdadera, si y sólo si $n \in \mathbb{N}$ no dividir cualquier elemento de $A$. Por lo $n>1$. La tarea es encontrar un mínimo de $n$ con que propiedad $P$ cierto para $A$.

Cada número $n_i$ únicamente factorizes en $$ n_i = p_1^{e_1} p_2^{e_2} \cdots $$ donde $p_k$ $k$- ésimo número primo y el exponente es un número entero no negativo.

Sus divisores aparte de $1$ son producto de sus factores primos (los números primos con los no-cero exponentes) con exponentes de tal manera que no exceda el $e_i$.

Un candidato para una solución de $n$ no debe ser un divisor de cualquier $n_i$. Por lo que no puede ser cualquiera de los que ocurren los factores primos.

El más pequeño de los números primos $p$ no ocurre no es un divisor de cualquier $n_i$.

Como Rubén señaló, otro límite superior es $n_N+1$. El conjunto $\{ 2,4\}$ prefiere $p=3<4+1=5$, la $\{ 2,3\}$ prefiere $n_2+1=4<5$.

Hasta este punto podemos limitar la solución a $$ B = \{ 2, \ldots, \min(p, n_N+1) \} $$

Si hay un número $n$ menor que $p$, lo que quiere hacer el trabajo, él mismo debe ser un producto de números primos, cada uno de estos pequeños que $p$.

Entonces, ¿cómo podemos combinar los factores primos tales mantener $P$ verdad?

Uno podría tratar de un primer factor con exponente uno de los más grandes de lo que mostró en el $n_i$. Para $\{ 2,3,6 \}$ daría $2^{1+1}=4$ $3^{1+1}=9$ donde $4$ beats $p=5$ $6+1=7$ como límites superior.

Un problema práctico es decidir cuándo invertir el esfuerzo en la determinación de los factores primos.

Answer 2

Yo no veo ninguna solución. Sólo se necesita comprobar los números primos y el primer poderes como posibles respuestas, pero que no es un gran ahorro. Si $6$ fueron para que no sea un divisor de un número, $2$ o $3$ es ya no un divisor.

Answer 3

Un trivial algoritmo sería la prueba para cada número natural $k \geq 2$ si se divide a alguno de los números en la lista. Este algoritmo se ejecuta en ($O(m^2)$donde $m$ es el mayor número de la serie), suponiendo que la comprobación de la divisibilidad toma tiempo constante (lo cual no es cierto por lo suficientemente grande como enteros). Tenga en cuenta que $m + 1$ es siempre una solución, ya que es un divisor $d$ $n$ siempre cumple $d \leq n$. $m + 1$ es la solución cuando el conjunto se $\{ 2, 3, 4, ..., m - 1, m \}$. No es cierto que la solución tiene que ser un prime (a menos que se requieran $\gcd(s, n) = 1$ para la solución de $s$ y todos los $n$ en el conjunto).

function answer(set S)
    for each 1 < k < m + 2
        isdivisor = false
        for each n in set S
            if k divides n
                isdivisor = true
                break (exit from inner for loop)
        if not(isdivisor) return k

En la práctica, parece que el tiempo de ejecución dependerá fundamentalmente de la respuesta, y será de aproximadamente lineal.

Más abstracto, si escribimos el conjunto como $\{ n_1, ..., n_m \}$ y escribir $n_j = \prod^\infty_{k = 1} p_{k}^{q_{j,k}} $ donde $p_k$ es el k-ésimo número primo, la solución que buscamos es una secuencia $l_1, l_2, ...$ con $\forall j \in [1, ..., m]$ $\exists t$ $l_t > q_{j, k}$ que minimiza $ s = \prod^\infty_{k = 1} p_k^{l_k} $.

Aún estoy pensando en un algoritmo más eficiente basado en esta descripción y Eratóstenes criba, pero creo que no es particularmente bueno. No es difícil dar límites en la solución. Tenemos $2 \leq s \leq m + 1$ $s \leq p_k^w$ donde $w = 1 + \max_{j \in \mathbb{N}} q_{j, k}$ para cada uno de los prime $p_k$.