Nombre pair

Un nombre pair par rapport à une borne est un nombre naturel dont la factorisation premier ne contient pas de nombres premiers plus grands que la borne. Un tel nombre est également appelé -smooth. ${\ displaystyle S}$${\ displaystyle S}$

Un entier naturel est appelé puissance lisse par rapport à une borne si sa factorisation première ne contient que des puissances premières inférieures ou égales . Cela signifie que pour chaque facteur premier qui se produit, ce qui suit s'applique: ${\ displaystyle S}$${\ displaystyle S}$${\ displaystyle q}$${\ displaystyle a_ {q}}$

${\ displaystyle q ^ {a_ {q}} \ leq S}$.

Exemples

Par exemple, examinons le nombre 720 (factorisation première: 720 = 2 ⁴ 3 ² 5):

• c'est 5-lisse, 6-lisse ...
• mais pas 3-lisse ou 4-lisse (à cause du 5 comme facteur premier, puisque 5 est supérieur à 3 et 4)
• c'est aussi 16 puissances en douceur, 17 puissances en douceur ...,
• mais pas en douceur à 15 puissances (puisque dans la factorisation première, le 2 arrive à la 4ème puissance (= 16), ce qui signifie que la limite 15 est dépassée)

Dans ce qui suit, nous considérons le nombre 8 comme une limite .

8-lisse

• sont z. B. 3, 4, 5, 12, 14 ou 120
• mais pas 11 ou 26

8 puissances en douceur

• sont z. B.3, 4, 5, 12, 56 ou 840 (= 2 ³ 3 5 7)
• mais pas 9 (= 3 ² ) ou 16 (= 2 ⁴ )

Astuces:

• Si un nombre premier est le prochain plus grand nombre premier et , l'ensemble de -even nombres est égal à l'ensemble de -even nombres.${\ displaystyle p}$${\ displaystyle p_ {2}}$${\ Displaystyle p \ leq n <p_ {2}}$${\ displaystyle n}$${\ displaystyle p}$
• Les nombres à 2 paires correspondent aux puissances de deux .
• Formellement, le nombre 1 peut être considéré comme "1-lisse".

caractéristiques

Il existe une factorisation première unique pour chaque nombre naturel. Autrement dit, pour chacun il existe et nombres premiers , ainsi que des multiples tels qu'il ${\ displaystyle a \ in \ mathbb {N}}$${\ displaystyle n \ in \ mathbb {N}}$${\ displaystyle q_ {1}, \ dots, q_ {n} \ in \ mathbb {P}}$${\ displaystyle a_ {1}, \ dots, a_ {n} \ in \ mathbb {N}}$

${\ displaystyle a = \ prod _ {i = 1} ^ {n} q_ {i} ^ {a_ {i}}}$

Maintenant définissons

${\ displaystyle g (a): = \ max \ {q_ {i}; i = 1, \ dots, n \}}$

${\ displaystyle z (a): = \ max \ {q_ {i} ^ {a_ {i}}; i = 1, \ dots, n \}}$

Pour tout et le nombre est - lisse et - potentiellement lisse, pour tous et le nombre n'est ni - lisse ni - potentiellement lisse. ${\ Displaystyle g \ geq g (a)}$${\ Displaystyle z \ geq z (a)}$${\ displaystyle a}$ ${\ displaystyle g}$${\ displaystyle z}$${\ Displaystyle g <g (a)}$${\ Displaystyle z <z (a)}$${\ displaystyle a}$${\ displaystyle g}$${\ displaystyle z}$

7 nombres pairs

Les nombres pairs 7 (ou 7 pairs ) sont ceux qui consistent exclusivement en puissances des facteurs premiers 2, 3, 5 et 7, par exemple 1372 = 2 ² · 7 ³ .

Un terme souvent utilisé comme synonyme est celui des nombres hautement composés , avec des nombres à 7 paires différant du concept mathématique réel du nombre hautement composé , ce qui autorise tous les facteurs premiers et leur impose des conditions supplémentaires.

Puisque les nombres premiers 2, 3, 5 et 7 apparaissent dans les anciennes mesures et poids pré-métriques, qui sont orientés vers la divisibilité facile (par exemple 1 Nuremberg Apothekergran = 19600 Nürnberger Grän = 980 scrupules de Nuremberg = 3 livres Karl), cette séquence se joue également un rôle dans la recherche sur la métrologie historique . (voir aussi Nippur-Elle , Karlspfund , poids du pharmacien )

La séquence des 7 nombres pairs: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, 28, 30, 32, 35, 36, 40, 42 ... se trouvent sous la séquence A002473 dans OEIS avec la désignation "nombres hautement composés (2)" ( Nombres hautement composés (2): nombres dont les diviseurs premiers sont tous <= 7. )

Procédure

Le tamis quadratique , une technique de factorisation , est basé sur la factorisation première des résidus quadratiques . Cette décomposition peut facilement être effectuée pour des nombres pairs. Il est également intéressant de déterminer le plus grand facteur de lissage pour de nombreux nombres à la fois (et éventuellement d'analyser leurs facteurs résiduels plus en détail). À cette fin,
Daniel Bernstein a développé une méthode efficace qui détermine chaque facteur premier lisse de chaque nombre unique pour un ensemble de nombres naturels non décomposés au moyen de multiplications par groupe et de l'organisation la plus économique, sans effectuer de divisions de test avec les nombres premiers en question. La méthode utilise uniquement des algorithmes rapides connus pour la multiplication, la division sans reste et le calcul du plus grand diviseur commun de deux nombres naturels.

Séquences de nombres pairs

Pour chaque borne, les -even nombres correspondants forment une séquence . L' Encyclopédie en ligne des séquences d'entiers (OEIS) fournit ces séquences pour les petites barrières: ${\ displaystyle S}$${\ displaystyle S}$

• 02- nombres pairs: séquence A000079 dans OEIS - toutes les puissances de deux ${\ displaystyle 2 ^ {x}}$
• 03 nombres pairs: séquence A003586 dans OEIS - numéros de la forme${\ displaystyle 2 ^ {x} \ cdot 3 ^ {y}}$
• 05 nombres pairs: séquence A051037 dans OEIS - numéros de la forme${\ displaystyle 2 ^ {x} \ cdot 3 ^ {y} \ cdot 5 ^ {z}}$
• 07- nombres pairs: séquence A002473 dans OEIS - ...
• 11- nombres pairs: suivez A51038 dans OEIS
• Nombres pairs 13: séquence A80197 dans OEIS
• 17- nombres pairs: séquence A80681 dans OEIS
• 19- nombres pairs: séquence A80682 dans OEIS
• 23 nombres pairs: séquence A80683 dans OEIS

Littérature

• Carl Pomerance : Le rôle des nombres lisses dans les algorithmes théoriques des nombres. (PDF; 8,3 Mo) Proc. Int. Congr. Mathématiciens, Zurich 1994, Birkhauser Verlag, Bâle, 1995, pp.411-422
• Andrew Granville : Nombres lisses: théorie des nombres computationnelle et au-delà. (PDF; 403 ko) Dans: Théorie algorithmique des nombres. Publications MSRI 44 (2008) pp. 267-323

liens web

• Eric W. Weisstein : nombre lisse . Dans: MathWorld (anglais).

Preuve individuelle

1. ↑ D. Bernstein: Comment trouver des parties lisses d'entiers. Draft for Math. Comput., Fichier PDF