Nombres de Hamming (généralisés)
Posté le 16/10/2016 à 10:58
La factorisation en nombre premier consiste à décomposer un nombre entier naturel en produit de nombres premiers. Le nombre $n_{1}=36$ peut se décomposer, par exemple, de la manière suivante : $n_{1}=2^{2}*3^{3}$.
Un nombre de Hamming, ou nombre dit régulier (1), est un nombre entier naturel pour lequel la factorisation en nombre premier ne fait apparaitre aucun nombre premier supérieur à 5. Par example : $n_{2}=14$ n'est pas un nombre de Hamming. En effet, il peut se décomposer sous la forme $n_{2}=2^{1}*7^{1}$. Un nombre de Hamming généralisé est un nombre entier naturel pour lequel la factorisation en nombre premier ne fait apparaitre aucun nombre premier supérieur à N. Le problème d'aujourd'hui consiste à générer la séquence des nombre de Hamming généralisé pour tout entier N.
Je pense à deux méthodes possibles : une méthode génératrice et une méthode destructrice.
Le premier type de méthode génère les nombres d'un ensemble donné. Par exemple, pour trouver l'ensemble des nombres puissance de deux, on peut partir de $P_{0}=1$ et, $\forall n\in\mathbb{N}$, définir $P_{n+1}=P_{n}*2$. On construit petit à petit les puissances de deux en multipliant le précédent nombre par deux, un jeu d'enfant !
Une méthode destructrice, quant à elle, part d'un ensemble donné et retire peu à peu les éléments ne satisfaisant pas un critère donné. Par exemple, une méthode destructrice connue serait la méthode du crible d'Eratosthène (2). Ce permet de trouver tout les nombre premiers inférieur à une limite maximum. On part d'une table contenant tout les nombres entiers naturels de $2$ à la limite prescrite. Pour chaque entier, on peut soit être dans un état premier $\text{P}$, soit dans un état non premier $\text{NP}$, soit dans un état non déterminé $\text{ND}$. Tant qu'il reste un ou plus élément $\text{ND}$, on sélectionne le plus petit et on le marque comme étant un nombre premier $\text{P}$ et on marque $\text{NP}$ tout ses multiples. On "détruit" petit à petit tout les nombres qui ne sont pas premiers.
Commençons par la construction de l'ensemble des nombres de Hamming plus petits que $N$ par méthode génératrice. On sait qu'un nombre de Hamming se décompose sous la forme $n = 2^{i}\cdot 3^{j}\cdot 5^{k}$ avec $i\ge 0$, $j \ge 0$ et $k \ge 0$. Il s'agit donc d'énumérer toute les combinaisons de $i$, $j$ et $k$ tel que $n < N$. De plus, on se rends vite compte qu'il est possible de restreindre $i$, $j$, et $k$. Choisissons pour le moment $j=0$ et $k=0$, $n=2^{i}\cdot 3^0\cdot 5^0$. $i$ ne peut dépasser $\log_{2}(N)$, auquel cas $n$ dépasserait $N$. On peut restreindre $j$ et $k$ de la même manière. Pour construire l'ensemble des nombres de Hanning, on énumère donc toute les combinaisons de $i$, $j$ et $k$ avec $\lfloor \log_{2}(N) \rfloor \ge i \ge 0$, $\lfloor \log_{3}(N) \rfloor \ge j \ge 0$ et $\lfloor \log_{5}(N) \rfloor \ge k \ge 0$ et on construit le nombre $n = 2^i*2^j*2^k$.
La méthode destructrice est inspirée du crible d'Eratosthène décrite plus haut (2). On va partir de l'ensemble des nombres entiers. En partant du premier nombre premier différent de $2$, $3$ ou $5$, on va retirer de la liste le nombre lui-même ainsi que tout ses multiples.
Si l'on regarde plus en détail ces deux méthodes, la méthode génératrice est très avare en mémoire. On génère chaque nombre de hamming directement. La complexité est en $O( \lfloor \log_{2}(N) \rfloor * \lfloor \log_{3}(N) \rfloor * \lfloor \log_{5}(N) \rfloor)$. A l'inverse, la méthode destructrice nécessite que l'on garde en mémoire tout les nombres jusqu'à $N$ !
Un nombre de Hamming, ou nombre dit régulier (1), est un nombre entier naturel pour lequel la factorisation en nombre premier ne fait apparaitre aucun nombre premier supérieur à 5. Par example : $n_{2}=14$ n'est pas un nombre de Hamming. En effet, il peut se décomposer sous la forme $n_{2}=2^{1}*7^{1}$. Un nombre de Hamming généralisé est un nombre entier naturel pour lequel la factorisation en nombre premier ne fait apparaitre aucun nombre premier supérieur à N. Le problème d'aujourd'hui consiste à générer la séquence des nombre de Hamming généralisé pour tout entier N.
Je pense à deux méthodes possibles : une méthode génératrice et une méthode destructrice.
Le premier type de méthode génère les nombres d'un ensemble donné. Par exemple, pour trouver l'ensemble des nombres puissance de deux, on peut partir de $P_{0}=1$ et, $\forall n\in\mathbb{N}$, définir $P_{n+1}=P_{n}*2$. On construit petit à petit les puissances de deux en multipliant le précédent nombre par deux, un jeu d'enfant !
Une méthode destructrice, quant à elle, part d'un ensemble donné et retire peu à peu les éléments ne satisfaisant pas un critère donné. Par exemple, une méthode destructrice connue serait la méthode du crible d'Eratosthène (2). Ce permet de trouver tout les nombre premiers inférieur à une limite maximum. On part d'une table contenant tout les nombres entiers naturels de $2$ à la limite prescrite. Pour chaque entier, on peut soit être dans un état premier $\text{P}$, soit dans un état non premier $\text{NP}$, soit dans un état non déterminé $\text{ND}$. Tant qu'il reste un ou plus élément $\text{ND}$, on sélectionne le plus petit et on le marque comme étant un nombre premier $\text{P}$ et on marque $\text{NP}$ tout ses multiples. On "détruit" petit à petit tout les nombres qui ne sont pas premiers.
Commençons par la construction de l'ensemble des nombres de Hamming plus petits que $N$ par méthode génératrice. On sait qu'un nombre de Hamming se décompose sous la forme $n = 2^{i}\cdot 3^{j}\cdot 5^{k}$ avec $i\ge 0$, $j \ge 0$ et $k \ge 0$. Il s'agit donc d'énumérer toute les combinaisons de $i$, $j$ et $k$ tel que $n < N$. De plus, on se rends vite compte qu'il est possible de restreindre $i$, $j$, et $k$. Choisissons pour le moment $j=0$ et $k=0$, $n=2^{i}\cdot 3^0\cdot 5^0$. $i$ ne peut dépasser $\log_{2}(N)$, auquel cas $n$ dépasserait $N$. On peut restreindre $j$ et $k$ de la même manière. Pour construire l'ensemble des nombres de Hanning, on énumère donc toute les combinaisons de $i$, $j$ et $k$ avec $\lfloor \log_{2}(N) \rfloor \ge i \ge 0$, $\lfloor \log_{3}(N) \rfloor \ge j \ge 0$ et $\lfloor \log_{5}(N) \rfloor \ge k \ge 0$ et on construit le nombre $n = 2^i*2^j*2^k$.
La méthode destructrice est inspirée du crible d'Eratosthène décrite plus haut (2). On va partir de l'ensemble des nombres entiers. En partant du premier nombre premier différent de $2$, $3$ ou $5$, on va retirer de la liste le nombre lui-même ainsi que tout ses multiples.
Si l'on regarde plus en détail ces deux méthodes, la méthode génératrice est très avare en mémoire. On génère chaque nombre de hamming directement. La complexité est en $O( \lfloor \log_{2}(N) \rfloor * \lfloor \log_{3}(N) \rfloor * \lfloor \log_{5}(N) \rfloor)$. A l'inverse, la méthode destructrice nécessite que l'on garde en mémoire tout les nombres jusqu'à $N$ !