Le calcul de phi(k) pour 1<k<N
Donné un grand N, j'ai besoin de parcourir tous les phi(k) telle que 1 < k < N :
- temps-la complexité doit être
O(N logN)
- de la mémoire-la complexité doit être sous
O(N)
(puisque les valeurs de N sera d'environ 1012)
Est-il possible? Si oui, comment?
- Un Projet d'Euler?
- Voir "Combien de nombres inférieurs à N sont premiers entre eux N?": stackoverflow.com/questions/1019040/... à propos de la même question: comment calculer phi(k) rapidement.
- Ce n'est pas un Projet d'Euler, mais elle a été engendrée par l'un de leurs problèmes que j'ai maintenant résolu.
- Qu'est-ce que "rapidement"?
- ShreevatsaR: Cette question a été sur le calcul de Phi(k) dans l'isolement. Cette question est sur le calcul de tous les Phi(k) dans la séquence jusqu'à un certain N. C'est lié, mais encore significativement différente de la question.
- Au hasard: c'est l'ordre d'itération important?
- Jamais l'esprit; je n'ai pu avoir de la mémoire de la complexité en bas à O(x/ln(x)) ou alors...
- L'ordre n'est pas important; "rapidement" est un membre de O(n log n).
Vous devez vous connecter pour publier un commentaire.
Cela peut être fait avec de la Mémoire de complexité O(Sqrt(N)) et le PROCESSEUR de complexité O(N * Log(Log(N))) avec une optimisation du mode fenêtré au Crible d'Eratosthène, tel que mis en œuvre dans l'exemple de code ci-dessous.
Qu'aucune langue n'a été spécifié et que je ne connais pas Python, j'ai mis en œuvre dans VB.net cependant je peux le convertir en C# si vous avez besoin que.
Noter que en O(N * Log(Log(N))), cette routine est l'affacturage chaque nombre en O(Log(Log(N))) en moyenne, ce qui est beaucoup, beaucoup plus rapide que le plus rapide de la seule N de la factorisation des algorithmes implantés par certaines réponses ici. En fait, à N = 10^12, il est 2400 fois plus vite!
J'ai testé cette routine sur mon 2Ghz Intel Core 2 portable et il calcule plus de 3 000 000 Phi() les valeurs par seconde. À cette vitesse, il vous faudra environ 4 jours pour calculer 10^12 valeurs. J'ai aussi testé l'exactitude jusqu'à 100 000 000 sans erreurs. Il est basé dans les entiers 64 bits, de sorte que rien jusqu'à 2^63 (10^19) doivent être précis (bien trop lent pour n'importe qui).
J'ai aussi un Visual Studio WinForm (également VB.net) pour l'exécution de/tester, que je peux vous fournir si vous le souhaitez.
Laissez-moi savoir si vous avez des questions.
Comme demandé dans les commentaires, j'ai ajouté ci-dessous une version C# du code. Cependant, parce que je suis actuellement dans le milieu de certains autres projets, je n'ai pas eu le temps de convertir moi-même, j'ai donc utilisé un de la en ligne VB vers C# conversion des sites (http://www.carlosag.net/tools/codetranslator/). Alors, soyez conscient que ce n'était converti et je n'ai pas eu le temps de tester ou vérifier moi-même encore.
Personne n'a trouvé un moyen plus rapide pour calculer phi(k) (aka, Euler indicateur de fonction) que par d'abord de trouver les facteurs premiers de k. Les meilleurs mathématiciens ont jeté beaucoup de cycles de CPU sur le problème depuis 1977, puisque trouver un moyen plus rapide pour résoudre ce problème serait de créer une faiblesse dans la À clé publique RSA algorithme. (À la fois le public et la clé privée RSA sont calculées en fonction de phi(n), où n est le produit de deux grands nombres premiers.)
Le calcul de phi(k) doit être faite en utilisant la factorisation en nombres premiers de k, qui est la seule façon raisonnable de le faire. Si vous avez besoin d'un rappel sur les que, wikipédia porte la formule.
Maintenant, si vous avez de calculer tous les diviseurs premiers de chaque nombre entre 1 et d'un grand N, vous allez mourir de vieillesse avant de voir un résultat, alors j'aimerais aller dans l'autre sens, c'est à dire construire tous les nombres inférieurs à N, à l'aide de leurs éventuels facteurs premiers, c'est à dire tous les nombres premiers inférieurs ou égaux à N.
Votre problème va donc être similaire à l'informatique de tous les diviseurs d'un nombre, seulement vous ne savez pas quel est le nombre maximum de fois que vous pouvez trouver un certain nombre premier dans la factorisation à l'avance. Peaufiner un itérateur à l'origine écrit par Tim Peters sur la liste python (quelque chose J'ai blogué sur...) pour inclure l'indicateur de fonction, une mise en œuvre possible en python qui donne k, phi(k) paires pourraient être comme suit:
Si vous avez besoin d'aide sur le calcul de tous les facteurs premiers en dessous de N, j'ai aussi blogué à ce sujet... Gardez cependant à l'esprit que le calcul de tous les nombres premiers inférieurs à 1012 est en soi un exploit remarquable...
Est-ce à partir de Project Euler 245? Je me souviens de cette question, et j'ai renoncé à elle.
Le moyen le plus rapide que j'ai trouvé pour le calcul de l'indicateur est de multiplier les facteurs premiers (p-1) ensemble, étant donné que k n'a pas répété facteurs (qui n'a jamais été le cas si je me souviens correctement la problématique).
Donc, pour le calcul des facteurs, il serait probablement préférable d'utiliser gmpy.next_prime ou pyecm (courbe elliptique de la factorisation).
Vous pouvez également tamis facteurs premiers de Jaime suggère. Pour les nombres jusqu'à 1012, le maximum, le premier facteur est inférieur à 1 millions de dollars, qui devrait être raisonnable.
Si vous memoize factorisations, il peut accélérer votre fonction phi encore plus.
Pour ce genre de problèmes, je suis en utilisant un itérateur qui renvoie pour chaque entier m < N la liste des nombres premiers < sqrt(N) qui divisent m. Pour mettre en œuvre un itérateur je suis en utilisant un tableau Un de longueur R où R > sqrt(N). À chaque point de la matrice Un contient la liste des nombres premiers qui divisent les entiers m .. m+R-1. I. e. Un[m % R] contient des nombres premiers divisant m. Chaque premier p est exactement dans une liste, c'est à dire dans Un[m % R] pour le plus petit nombre entier dans la plage m .. m+R-1 est divisible par p. Lors de la génération de l'élément suivant de l'itérateur tout simplement la liste dans Un[m % R] est retournée. Ensuite, la liste des nombres premiers sont retirés de Un[m % R] et chaque nombre premier p est ajouté à Un[(m+p) % R].
Avec une liste de nombres premiers < sqrt(N) divisant m il est facile de trouver la factorisation de m, puisqu'il y a au plus une prime de plus de sqrt(N).
Cette méthode a une complexité O(N log(log(N))) sous l'hypothèse que toutes les opérations dont la liste des opérations en O(1). La mémoire requise est O(sqrt(N)).
Il y a malheureusement certains frais généraux constants ici, donc je cherchais un moyen plus élégant pour générer les valeurs de phi phi(n), mais je n'ai pas été couronnée de succès.
Voici un efficace python générateur. Le problème, c'est qu'il ne donne pas les résultats dans l'ordre. Il est basé sur https://stackoverflow.com/a/10110008/412529 .
De la mémoire de la complexité est O(log(N)) comme il n'a qu'à stocker une liste de facteurs premiers pour un seul numéro à la fois.
CPU complexité est à peine superlinear, quelque chose comme O(N log log N).
Je pense que vous pouvez aller dans l'autre sens. Au lieu de factoriser un entier k pour obtenir phi(k), vous pouvez tenter de générer tous les nombres entiers de 1 à N de nombres premiers et obtenir phi(k) rapidement. Par exemple, si Pn est le maximum de la prime est inférieure à N, vous pouvez générer tous les nombres entiers inférieurs à N par
P1 i 1 * P2 i 2 * ... * Pn i n où chaque ij exécuter de 0 à [log (N) /log (Pj)] ([] est la fonction floor).
De cette façon, vous pouvez obtenir phi(k) rapidement sans cher la factorisation en nombres premiers et encore parcourir tout k entre 1 et N (pas dans l'ordre mais je pense que vous n'avez pas de soins sur commande).
Tamis de la totients à n:
Ce factorise N = PQ, où P & Q sont premiers.
Fonctionne très bien, en Élixir ou Erlang.
Vous pouvez essayer différents générateurs de votre séquence pseudo-aléatoire.
x*x + 1
est couramment utilisé.Cette ligne:
defp f0(x, n), do: rem((x * x) + 1, n)
Les autres points d'amélioration: meilleure alternative, ou pgcd, rem et abs fonctions