Não Divisor Menos Comum

11

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, .SdSxS, dx

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)logx . E para um conjunto S , deixe- F(S)= a menos nobre que não divide qualquer elemento de S . Temos um limite superior

F(S)F(lcm(S))F(Cn)nlogC.

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

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(nmin(C,nlogC)+nlogC) e usa memória O(nlogC) , porque não precisamos calcular e armazenar factores superior a nlogC . Para pequenos n e C ele apresenta melhor desempenho.

Em detalhes, o algoritmo consiste em duas partes:

  1. Construa um conjunto S^ composto por todos os fatores de todos os elementos de S , ou seja,

    xS fnlogC, (fxfS^)
    Isso pode ser feito no tempo O(nmin(C,nlogC)) e na memória O(nlogC) . (De onde isso vem? Para qualquer elemento de S , podemos fatorá-lo usando a fatoração de teste com todos os números até C ou todos os números primos até nlogC , o que for menor; portanto, cada elemento de S pode ser fatorado no tempo O(min(C,nlogC)) .)
  2. Encontre o número mínimo . Esta etapa requer tempo , se verificar se pode ser feito no tempo .dS^O(|S^|)=O(nlogC)xS^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?nCS
SkyterX
fonte
1. Por "pré-cálculo", eu quis dizer antes de iniciar o algoritmo de força bruta. 2. A complexidade da factoring é de facto subexponencial, ver o definiton de . C
SkyterX
@DW no ponto 2, a complexidade do fatoramento é subexponencial no comprimento da cadeia de bits que representa o número, mas o SkyterX diz corretamente que é , ou seja, proporcional à raiz quadrada do tamanho de o número. O(C)
Lieuwe Vinkhuijzen
@LieuweVinkhuijzen, isso não parece certo para mim. A complexidade de fatorar usando o GNFS será algo como , que é significativamente menor que . Veja en.wikipedia.org/wiki/… . O(exp{1.9(logC)1/3(loglogC)2/3})O(C)
DW
A afirmação de que o segundo método tem um desempenho melhor "para pequenos e " não está correta. Ele funciona melhor apenas se . Portanto, precisa ser grande para o segundo método ter um desempenho melhor (não pequeno). nCnC/log(C)n
DW
@DW Você está certo, eu não estava ciente da complexidade do GNFS.
Lieuwe Vinkhuijzen

Respostas:

6

É 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 .CO(LC[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).nlogCO(LnlogC[0.5,1.41])O(logC/log(nlogC))

Aqui .Ln[α,c]=exp{c(logn)α(loglogn)1α}

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 .LC[0.33,1.92]CCLnlogC[0.5,1.41]nlogCnlogC

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.O~(nmin(LC[0.33,1.92],LnlogC[0.5,1.41]))

DW
fonte
Eu acho que qualquer algoritmo rápido para este problema deve incluir algum tipo de fatoração de conjunto de entrada . Vou verificar esses algoritmos de fatoração, mas ainda há um problema de testá-los adequadamente, o que suscita um segundo problema que eu mencionei na construção do conjunto com resposta máxima. SS
SkyterX
O ECM encontra um fator no tempo que você dá. Se todos os fatores de um número forem ≤ n log C, será necessário repetir o algoritmo, até o log C / log (n log C).
gnasher729
3

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.kp

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.kpkp

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 deN2/logN

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(11/d)N1(11/d)N

Se d << N, então .1(11/d)N1exp(N/d)

Se d ≈ N / N Em seguida, .1exp(N/d)1exp(lnN)=11/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.

gnasher729
fonte