Não Divisor Menos Comum

Basicamente, o problema é: Para um conjunto de números positivos, encontre um número mínimo que não seja um divisor de nenhum elemento de , ou seja, .$S$$d$$S$$\forall x \in S,\ d \nmid x$

Denotar $n = |S|$e $C = \max(S)$ . Considere a função $F(x) =$ o menor número primo que não divide $x$ . É fácil ver que $F(x) \leq \log x$ . E para um conjunto $S$ , deixe- $F(S) =$ a menos nobre que não divide qualquer elemento de $S$ . Temos um limite superior

Portanto, um algoritmo simples de força bruta, que enumera todos os números de $1$ a $n \log C$ e verifica se não divide nenhum elemento de $S$ , é polinomial e possui complexidade de tempo $O(n^2 \log C)$ .

A outra maneira de resolver o problema é calcular todos os fatores para cada elemento de $S$ e usá-los no algoritmo de força bruta para verificar se $x$ é uma resposta no tempo $O(1)$ . Esse algoritmo possui complexidade de tempo $O(n \cdot \min (\sqrt{C}, n \log C) + n \log C)$ e usa memória $O(n \log C)$ , porque não precisamos calcular e armazenar factores superior a $n \log C$ . Para pequenos $n$ e $C$ ele apresenta melhor desempenho.

Em detalhes, o algoritmo consiste em duas partes:

1. Construa um conjunto $\hat{S}$ composto por todos os fatores de todos os elementos de $S$ , ou seja,

   $$\forall x \in S\ \forall f \le n \cdot \log C, \ (f \mid x \rightarrow f \in \hat{S})$$ Isso pode ser feito no tempo $O(n \cdot \min (\sqrt{C}, n \log C))$ e na memória $O(n \log C)$ . (De onde isso vem? Para qualquer elemento de $S$ , podemos fatorá-lo usando a fatoração de teste com todos os números até $\sqrt{C}$ ou todos os números primos até $n \log C$ , o que for menor; portanto, cada elemento de $S$ pode ser fatorado no tempo $O(\min (\sqrt{C}, n \log C))$ .)

2. Encontre o número mínimo . Esta etapa requer tempo , se verificar se pode ser feito no tempo .$d \notin \hat{S}$$O(|\hat{S}|) = O(n \log C)$$x \in \hat{S}$$O(1)$

Tenho duas perguntas nas quais estou interessado:

1. Existe um algoritmo mais rápido para resolver o problema?
2. Para dados e , como podemos construir um conjunto com o máximo não divisor comum menos?$n$$C$$S$

É possível melhorar seu segundo algoritmo usando algoritmos melhores para fatoração de número inteiro.

Existem dois algoritmos para fatoração inteira que são relevantes aqui:

• O GNFS pode fatorar um número inteiro com o tempo de execução .$\le C$$O(L_C[0.33,1.92])$

• O ECM pode encontrar fatores (se houver algum) com o tempo de execução ; encontrar todos os fatores levará vezes mais (o que é relativamente pequeno comparado ao tempo de execução do ECM).$\le n \log C$$O(L_{n \log C}[0.5,1.41])$$O(\log C / \log(n \log C))$

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

Essa é uma expressão de aparência horrenda para o tempo de execução, mas o fato importante é que isso é mais rápido do que os métodos mencionados. Em particular, é assintoticamente muito menor que , ou seja, o GNFS é muito mais rápido do que tentar todos os possíveis fatores . Também é assintoticamente muito menor do que , ou seja, de ECM é muito mais rápida do que tentar todos os factores possíveis .$L_C[0.33,1.92]$$\sqrt{C}$$\le \sqrt{C}$$L_{n \log C}[0.5,1.41]$$n \log C$$\le n \log C$

Portanto, o tempo total de execução desse método é aproximadamente , e isso é assintoticamente melhor que o seu primeiro método e assintoticamente melhor que o seu segundo método. Não sei se é possível fazer ainda melhor.$\tilde{O}(n \min(L_C[0.33,1.92], L_{n \log C}[0.5,1.41]))$

O não divisor menos comum pode ser tão grande quanto N log C, mas se os números N forem distribuídos aleatoriamente, o não-divisor menos comum provavelmente será muito menor, provavelmente muito menor que N. Eu criaria tabelas das quais primos são divisores cujos números são

Para cada número primo p, temos um índice que significa que todos os números até esse índice foram examinados quanto à divisibilidade por p, e temos uma lista de todos os números que foram divisíveis por.$k_p$

Então, para d = 2, 3, 4, ... tentamos encontrar um número divisível por d ou mostrar que não há nenhum. Tomamos o maior fator primo p de d. Em seguida, verificamos todos os números que foram divisíveis por p se eles também são divisíveis por d. Se nenhum for encontrado, verificamos outros números com índices> para divisibilidade por p, atualizando e a lista de números divisíveis por p e verificando se cada número é divisível por d.$k_p$$k_p$

Para verificar se existe um número divisível por p, verificamos em média os números de p. Mais tarde, se verificarmos se há um número divisível por 2p, há 50% de chance de precisarmos verificar apenas um número (aquele que é divisível por p) e 50% de chance de verificar em média 2p mais números. Encontrar um número divisível por 3p provavelmente é rápido e assim por diante, e nunca verificamos mais de N números quanto à divisibilidade por p, porque existem apenas N números.

Espero que isso funcione com verificações de divisibilidade de$N^2 / log N$

PS. Qual o tamanho do resultado para números aleatórios?

Suponha que eu tenho N números aleatórios. A probabilidade de um de N números ser divisível por d é 1 - (1 - 1 / d) ^ N. Suponho que a probabilidade de que cada um dos números 1 ≤ d ≤ k seja um fator de um dos números aleatórios seja calculada multiplicando essas probabilidades (Ok, isso é um pouco complicado, porque essas probabilidades provavelmente não são totalmente independentes).

Com essa suposição, com N = 1000, há uma chance de 50% de que um dos números 1..244 não divida nenhum número e um em um bilhão que todo número até 507 divide um dos números. Com N = 10.000, há 50% de chance de um dos números 1..1726 não dividir nenhum número e um em um bilhão que todo número até 2979 divide um dos números.

Eu proporia que, para N entradas aleatórias, o tamanho do resultado seja um pouco maior que N / ln N; talvez algo como N / ln N * (ln ln N) ^ 2. Aqui está o porquê:

A probabilidade de que pelo menos um de N números aleatórios é divisível por um d aleatório é . Se d estiver em torno de N, então é cerca de 1 - exp (-1) ≈ 0,6321. Isso é para um único divisor; as chances de que cada um dos vários números d ≈ N seja um divisor de pelo menos um dos números N são muito pequenas, portanto o máximo d será significativamente menor que N.$1 - (1 - 1/d)^N$$1 - (1 - 1/d)^N$

Se d << N, então .$1 - (1 - 1/d)^N ≈ 1 - exp (-N / d)$

Se d ≈ N / N Em seguida, .$1 - exp (-N / d) ≈ 1 - exp (- ln N) = 1 - 1/N$

Nós adicionaríamos essas probabilidades para cerca de N / ln N valores d, mas para a maioria d o resultado será significativamente maior, portanto o maior d será de alguma forma maior que N / ln N, mas significativamente menor que N.

PS. Encontrando um número divisível por d:

Escolhemos o maior fator primo p de d e, em seguida, examinamos primeiro os números que já se sabia serem divisíveis por p. Diga d = kp. Então, em média, verificamos apenas k números que são divisíveis por p enquanto verificamos este d em particular, e verificamos no máximo todos os valores de N para divisibilidade por p em geral, para todos os d divisíveis por p. Na verdade, provavelmente verificamos menos de N valores para a maioria dos números primos p, porque, depois de verificar todos os N valores, o algoritmo provavelmente termina. Portanto, se o resultado for R, espero que valores menores que N sejam divididos por cada primo menor que R. Supondo que R ≤ N, trata-se de verificações de N ^ 2 / log N.

PS. Executando alguns testes

Eu executei esse algoritmo algumas vezes com N = 1.000.000 de números aleatórios> 0. O não-divisor menos comum estava entre 68.000 e 128.000, com a grande maioria das execuções entre 100.000 e 120.000. O número de divisões estava entre 520 milhões e 1800 milhões, muito abaixo de (N / ln N) ^ 2; a maioria dos casos usou entre 1000 e 1500 milhões de divisões.