Mínimo común no divisor

Básicamente, el problema es: para un conjunto de números positivos, encuentre un número mínimo que no sea un divisor de ningún elemento de , es decir, .d S ∀ x ∈ S , d ∤ $S$$d$$S$$\forall x \in S,\ d \nmid x$

Denote $n = |S|$y $C = \max(S)$ . Considere la función $F(x) =$ el número primo mínimo que no divide $x$ . Es fácil ver que $F(x) \leq \log x$ . Y para un conjunto $S$ , dejó $F(S) =$ menos privilegiada que no divide ningún elemento de $S$ . Tenemos un límite superior

Por lo tanto, un algoritmo simple de fuerza bruta, que enumera todos los números del $1$ al $n \log C$ y comprueba si no divide ningún elemento de $S$ , es polinomial y tiene una complejidad de tiempo $O(n^2 \log C)$ .

La otra forma de resolver el problema es calcular todos los factores para cada elemento de $S$ y usarlos en un algoritmo de fuerza bruta para verificar si $x$ es una respuesta en el tiempo $O(1)$ . Este algoritmo tiene una complejidad de tiempo $O(n \cdot \min (\sqrt{C}, n \log C) + n \log C)$ y usa memoria $O(n \log C)$ , porque no necesitamos calcular y factores almacenar mayor que $n \log C$ . Para los pequeños $n$ y $C$ que tiene un mejor rendimiento.

En detalle, el algoritmo consta de dos partes:

1. Construya un conjunto $\hat{S}$ compuesto por todos los factores de todos los elementos de $S$ , es decir,

   $$\forall x \in S\ \forall f \le n \cdot \log C, \ (f \mid x \rightarrow f \in \hat{S})$$ Esto se puede hacer en $O(n \cdot \min (\sqrt{C}, n \log C))$ time y $O(n \log C)$ memory. (¿De dónde viene esto? Para cualquier elemento de $S$ , podemos factorizarlo usando la factorización de prueba con todos los números hasta $\sqrt{C}$ o todos los primos hasta $n \log C$ , lo que sea menor; por lo tanto, cada elemento de $S$ se puede factorizar en tiempo $O(\min (\sqrt{C}, n \log C))$ tiempo).

2. Encuentra el número mínimo . Este paso requiere tiempo, si se comprueba si se puede hacer en tiempo.$d \notin \hat{S}$$O(|\hat{S}|) = O(n \log C)$$x \in \hat{S}$$O(1)$

Tengo dos preguntas que me interesan:

1. ¿Existe un algoritmo más rápido para resolver el problema?
2. Para y dados , ¿cómo podemos construir un conjunto con máximo no común divisor?$n$$C$$S$

Es posible mejorar su segundo algoritmo utilizando mejores algoritmos para la factorización de enteros.

Hay dos algoritmos para la factorización de enteros que son relevantes aquí:

• GNFS puede factorizar un entero con tiempo de ejecución .O ( L C [ 0.33 , 1.92 ] $\le C$$O(L_C[0.33,1.92])$

• El ECM puede encontrar factores (si existe) con el tiempo de ejecución ; encontrar todos los factores tomará veces más tiempo (que es relativamente pequeño en comparación con el tiempo de ejecución de ECM).O ( L n log C [ 0.5 , 1.41 ] ) O ( log C / log ( n log C ) $\le n \log C$$O(L_{n \log C}[0.5,1.41])$$O(\log C / \log(n \log C))$

Aquí .$L_n[\alpha,c] = \exp\{c (\log n)^\alpha (\log \log n)^{1-\alpha}\}$

Esa es una expresión de aspecto bastante horrible para el tiempo de ejecución, pero el hecho importante es que es más rápido que los métodos que mencionó. En particular, es asintóticamente mucho más pequeño que , es decir, GNFS es mucho más rápido que probar todos los factores posibles . También es asintóticamente mucho más pequeño que , es decir, ECM es mucho más rápido que tratar todos los posibles factores .$L_C[0.33,1.92]$ ≤$\sqrt{C}$ L n log C [0.5,1.41]nlogC≤nlog$\le \sqrt{C}$$L_{n \log C}[0.5,1.41]$$n \log C$$\le n \log C$

Entonces, el tiempo de ejecución total para este método es aproximadamente , y esto es asintóticamente mejor que su primer método y asintóticamente mejor que su segundo método. No sé si es posible hacerlo aún mejor.$\tilde{O}(n \min(L_C[0.33,1.92], L_{n \log C}[0.5,1.41]))$

El no divisor menos común puede ser tan grande como N log C, pero si los números N se distribuyen al azar, entonces el no divisor menos común es probablemente mucho más pequeño, probablemente mucho menos que N. Construiría tablas de las cuales los primos son divisores de los cuales números.

Para cada número primo p tenemos un índice que significa que todos los números hasta ese índice han sido examinados por divisibilidad por p, y tenemos una lista de todos esos números que fueron divisibles por.$k_p$

Entonces para d = 2, 3, 4, ... tratamos de encontrar un número divisible por d, o mostramos que no hay ninguno. Tomamos el mayor factor primo p de d. Luego verificamos todos los números que fueron divisibles por p si también son divisibles por d. Si no se encuentra ninguno, verificamos más números con índices> para la divisibilidad por p, actualizando y la lista de números divisibles por p, y verificando si cada número es divisible por d.k $k_p$$k_p$

Para verificar si hay un número divisible por p, verificamos en promedio los números p. Más adelante, si verificamos si hay un número divisible por 2p, hay un 50% de posibilidades de que necesitemos verificar solo un número (el que es divisible por p), y un 50% de posibilidades de verificar en promedio 2p más números. Encontrar un número divisible por 3p es bastante rápido y así sucesivamente, y nunca verificamos la divisibilidad por más de N números por p, porque solo hay N números.

Espero que esto funcione con aproximadamente comprobaciones de divisibilidad.$N^2 / log N$

PD. ¿Qué tan grande sería el resultado para números aleatorios?

Supongamos que tengo N números aleatorios. La probabilidad de que uno de los N números sea divisible por d es 1 - (1 - 1 / d) ^ N. Supongo que la probabilidad de que cada uno de los números 1 ≤ d ≤ k sea un factor de uno de los números aleatorios se calcula multiplicando estas probabilidades (Ok, eso es un poco dudoso, porque estas probabilidades probablemente no sean del todo independientes).

Con esa suposición, con N = 1000, hay un 50% de posibilidades de que uno de los números 1..244 no divida ningún número, y uno entre mil millones de que cada número hasta 507 divida uno de los números. Con N = 10,000 hay un 50% de posibilidades de que uno de los números 1..1726 no divida ningún número, y uno entre mil millones de que cada número hasta 2979 divida uno de los números.

Yo propondría que para N entradas aleatorias, el tamaño del resultado es un poco mayor que N / ln N; tal vez algo como N / ln N * (ln ln N) ^ 2. Este es el por qué:

La probabilidad de que al menos uno de los números aleatorios n es divisible por un azar d es . Si d está alrededor de N, entonces es aproximadamente 1 - exp (-1) ≈ 0.6321. Eso es para un solo divisor; las posibilidades de que cada uno de varios números d ≈ N sea un divisor de al menos uno de los N números son bastante delgados, por lo que el máximo d será significativamente menor que N. 1 - ( 1 - 1 / d ) $1 - (1 - 1/d)^N$$1 - (1 - 1/d)^N$

Si d << N, entonces .$1 - (1 - 1/d)^N ≈ 1 - exp (-N / d)$

Si d ≈ N / ln N entonces .$1 - exp (-N / d) ≈ 1 - exp (- ln N) = 1 - 1/N$

Agregaríamos estas probabilidades para aproximadamente N / ln N valores d, pero para la mayoría de d el resultado será significativamente mayor, por lo que la mayor d será de alguna manera mayor que N / ln N pero significativamente menor que N.

PD. Encontrar un número divisible por d:

Elegimos el factor primo más grande p de d, y luego examinamos primero los números que ya eran divisibles por p. Di d = kp. Luego, en promedio, solo verificamos k números que son divisibles por p mientras verificamos esta d particular, y verificamos como máximo todos los valores de N para la divisibilidad por p en general, para todos los d divisibles por p. En realidad, lo más probable es que verifiquemos menos de N valores para la mayoría de los primos p, porque después de verificar todos los valores de N, el algoritmo probablemente termina. Entonces, si el resultado es R, entonces espero que se dividan menos de N valores por cada primo menos que R. Suponiendo que R ≤ N, se trata de N ^ 2 / log N verificaciones.

PD. Ejecutando algunas pruebas

Ejecuté este algoritmo varias veces con N = 1,000,000 números aleatorios> 0. El no divisor menos común estaba entre 68,000 y 128,000 con la gran mayoría de corridas entre 100,000 y 120,000. El número de divisiones fue entre 520 millones y 1800 millones, que es mucho menor que (N / ln N) ^ 2; La mayoría de los casos utilizan entre 1000 y 1500 millones de divisiones.