Non diviseur le moins courant

Fondamentalement, le problème est le suivant: pour un ensemble de nombres positifs, trouvez un nombre minimal qui n'est pas un diviseur d'un élément de , c'est-à-dire .$S$$d$$S$$\forall x \in S,\ d \nmid x$

Notons $n = |S|$et $C = \max(S)$ . Considérons la fonction $F(x) =$ le plus petit nombre premier ne divisant pas $x$ . Il est facile de voir que $F(x) \leq \log x$ . Et pour un ensemble $S$ , que $F(S) =$ le moins premier qui ne divise pas tout élément de $S$ . Nous avons une limite supérieure

Par conséquent, un simple algorithme de force brute, qui énumère tous les nombres de $1$ à $n \log C$ et vérifie s'il ne divise aucun élément de $S$ , est polynomial et a une complexité temporelle $O(n^2 \log C)$ .

L'autre façon de résoudre le problème est de calculer tous les facteurs pour chaque élément de $S$ et de les utiliser dans un algorithme de force brute pour vérifier si $x$ est une réponse en temps $O(1)$ . Cet algorithme a une complexité temporelle $O(n \cdot \min (\sqrt{C}, n \log C) + n \log C)$ et utilise la mémoire $O(n \log C)$ , car nous n'avons pas besoin de calculer et facteurs de stocker plus de $n \log C$ . Pour les petits $n$ et $C$ il fonctionne mieux.

En détail, l'algorithme se compose de deux parties:

1. Construire un ensemble $\hat{S}$ composé de tous les facteurs de tous les éléments de $S$ , c'est-à-dire

   $$\forall x \in S\ \forall f \le n \cdot \log C, \ (f \mid x \rightarrow f \in \hat{S})$$ Cela peut être fait en $O(n \cdot \min (\sqrt{C}, n \log C))$ temps et $O(n \log C)$ mémoire. (D'où cela vient-il? Pour tout élément de $S$ , nous pouvons le factoriser en utilisant soit la factorisation d'essai avec tous les nombres jusqu'à $\sqrt{C}$ ou tous les nombres premiers jusqu'à $n \log C$ , selon le plus petit; ainsi, chaque élément de $S$ peut être factorisé dans le temps $O(\min (\sqrt{C}, n \log C))$ .)

2. Trouver un nombre minimal . Cette étape nécessite , si l'on vérifie si peut être fait en .$d \notin \hat{S}$$O(|\hat{S}|) = O(n \log C)$$x \in \hat{S}$$O(1)$

J'ai deux questions qui m'intéressent:

1. Existe-t-il un algorithme plus rapide pour résoudre le problème?
2. Pour et donnés , comment pouvons-nous construire un ensemble avec le plus grand diviseur commun le moins commun?$n$$C$$S$

Il est possible d'améliorer votre deuxième algorithme en utilisant de meilleurs algorithmes pour la factorisation entière.

Il existe deux algorithmes de factorisation entière qui sont pertinents ici:

• GNFS peut factoriser un entier avec le temps d'exécution .$\le C$$O(L_C[0.33,1.92])$

• ECM peut trouver un facteur (le cas échéant) avec le temps d'exécution ; la recherche de tous les facteurs prendra fois plus longtemps (ce qui est relativement petit par rapport au temps d'exécution d'ECM).$\le n \log C$$O(L_{n \log C}[0.5,1.41])$$O(\log C / \log(n \log C))$

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

C'est une expression assez horrible pour le temps d'exécution, mais le fait important est que c'est plus rapide que les méthodes que vous avez mentionnées. En particulier, est asymptotiquement beaucoup plus petit que , c'est-à-dire que GNFS est beaucoup plus rapide que d'essayer tous les facteurs possibles . Aussi est asymptotiquement beaucoup plus petit que , par exemple, l' ECM est beaucoup plus rapide que d' essayer tous les facteurs possibles .$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$

Ainsi, le temps total d'exécution de cette méthode est à peu près , et c'est asymptotiquement meilleur que votre première méthode et asymptotiquement mieux que votre deuxième méthode. Je ne sais pas s'il est possible de faire encore mieux.$\tilde{O}(n \min(L_C[0.33,1.92], L_{n \log C}[0.5,1.41]))$

Le non-diviseur le moins commun peut être aussi grand que N log C, mais si les nombres N sont distribués aléatoirement, alors le non-diviseur le moins commun est probablement beaucoup plus petit, probablement beaucoup moins que N. Je construirais des tables dont les nombres premiers sont des diviseurs dont les nombres.

Pour chaque nombre premier p, nous avons un indice qui signifie que tous les nombres jusqu'à cet indice ont été examinés pour la divisibilité par p, et nous avons une liste de tous ces nombres qui étaient divisibles par.$k_p$

Alors pour d = 2, 3, 4, ... nous essayons de trouver un nombre divisible par d, ou de montrer qu'il n'y en a pas. Nous prenons le plus grand facteur premier p de d. Ensuite, nous vérifions tous les nombres qui étaient divisibles par p s'ils sont également divisibles par d. Si aucun n'est trouvé, alors nous vérifions d'autres nombres avec des indices> pour la divisibilité par p, en mettant à jour et la liste des nombres divisibles par p, et en vérifiant si chaque nombre est divisible par d.$k_p$$k_p$

Pour vérifier s'il existe un nombre divisible par p, on vérifie la moyenne des nombres p. Plus tard, si nous vérifions s'il existe un nombre divisible par 2p, il y a 50% de chances que nous ne devions vérifier qu'un seul nombre (celui qui est divisible par p), et 50% de chances de vérifier en moyenne 2p plus de nombres. Trouver un nombre divisible par 3p est très probablement rapide et ainsi de suite, et nous ne vérifions jamais plus de N nombres pour divisibilité par p, car il n'y a que N nombres.

J'espère que cela fonctionne avec environ vérifications de divisibilité.$N^2 / log N$

PS. Quelle serait la taille du résultat pour des nombres aléatoires?

Supposons que j'ai N nombres aléatoires. La probabilité que l'un des N nombres soit divisible par d est 1 - (1 - 1 / d) ^ N. Je suppose que la probabilité que chacun des nombres 1 ≤ d ≤ k soit un facteur de l'un des nombres aléatoires est calculée en multipliant ces probabilités (Ok, c'est un peu douteux, car ces probabilités ne sont probablement pas tout à fait indépendantes).

Avec cette hypothèse, avec N = 1000, il y a 50% de chances qu'un des nombres 1..244 ne divise aucun nombre, et un sur un milliard que chaque nombre jusqu'à 507 divise l'un des nombres. Avec N = 10 000, il y a 50% de chances qu'un des nombres 1..1726 ne divise aucun nombre, et un sur un milliard que chaque nombre jusqu'à 2979 divise l'un des nombres.

Je proposerais que pour N entrées aléatoires, la taille du résultat soit un peu plus grande que N / ln N; peut-être quelque chose comme N / ln N * (ln ln N) ^ 2. Voici pourquoi:

La probabilité qu'au moins un des N nombres aléatoires est divisible par un d aléatoire est . Si d est autour de N, alors est d'environ 1 - exp (-1) ≈ 0,6321. C'est pour un seul diviseur; les chances que chacun de plusieurs nombres d ≈ N soit un diviseur d'au moins un des N nombres sont assez minces, donc le maximum d sera significativement plus petit que N.$1 - (1 - 1/d)^N$$1 - (1 - 1/d)^N$

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

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

Nous ajouterions ces probabilités pour environ N / ln N valeurs d, mais pour la plupart d le résultat sera significativement plus grand, donc le plus grand d sera en quelque sorte plus grand que N / ln N mais significativement plus petit que N.

PS. Trouver un nombre divisible par d:

Nous choisissons le plus grand facteur premier p de d, puis nous examinons d'abord les nombres qui étaient déjà connus pour être divisibles par p. Disons d = kp. Ensuite, en moyenne, nous vérifions seulement k nombres qui sont divisibles par p tout en vérifiant ce d particulier, et nous vérifions au plus toutes les valeurs N pour la divisibilité par p dans l'ensemble, pour tout d divisible par p. En fait, nous vérifions très probablement moins de N valeurs pour la plupart des nombres premiers p, car après avoir vérifié toutes les N valeurs, l'algorithme se termine très probablement. Donc, si le résultat est R, alors je m'attends à ce que moins de N valeurs soient divisées par chaque nombre premier inférieur à R. En supposant que R ≤ N, cela représente environ N ^ 2 / log N vérifications.

PS. Exécution de certains tests

J'ai exécuté cet algorithme à quelques reprises avec N = 1 000 000 de nombres aléatoires> 0. Le non-diviseur le moins courant se situait entre 68 000 et 128 000 avec la grande majorité des exécutions entre 100 000 et 120 000. Le nombre de divisions était compris entre 520 millions et 1800 millions, ce qui est beaucoup moins que (N / ln N) ^ 2; la majorité des cas utilisaient entre 1 000 et 1 500 millions de divisions.