ChronoMath, une chronologie des MATHÉMATIQUES
à l'usage des professeurs de mathématiques, des étudiants et des élèves des lycées & collèges


Suite de Hamming         Programme JavaScript

 i  Richard W. Hamming (1915-1998) est un ingénieur informaticien américain qui s'intéressa aux problèmes du codage des caractères alphanumériques afin de traitement automatique par des machines (programme informatique). Le code Hamming est un système de codage possédant 3 bits de contrôles de parité croisés permettant de détecter et d'éliminer (ou du moins de très fortement diminuer) toute erreur de transmission de l'information à distance.

Ces travaux furent récompensés en particulier par le prix Alan Turing 1968 et une médaille Richard Hamming  fut créée en son honneur en 1988 (dont il fut le premier récipiendaire). On pourra consulter la page du prix Turing consacrée à sa biographie :

» http://amturing.acm.org/award_winners/hamming_1000652.cfm

Voici un problème d'arithmétique d'apparence simple mais dont la résolution informatique demande une certaine réflexion :

Rechercher, par ordre croissant, la suite des entiers naturels n'admettant comme diviseurs premiers que 2, 3 ou 5.
Ces nombres constituent la suite dite de Hamming.

 !   Attention (réponse à un lecteur) : Si n est un entier de la suite de Hamming, l'énoncé ne dit pas que n admet  2, 3 et 5 comme diviseurs premiers mais que les diviseurs premiers de n sont 2, 3 ou 5, ce "ou" n'étant pas exclusif. Par exemple 4 fait partie de la suite cherchée, tout comme 18 ou 30.

Indication : si n est un élément de la suite de Hamming, sa décomposition en produit de facteurs premiers est de la forme 2α3β5γ avec α, β et γ entiers non tous nuls. 2, 3 et 5 sont éléments de la suite. Si n > 5 est un candidat dans votre recherche, alors, n devant être de la forme 2α3β5γ, l'un au moins des trois nombres n/2, n/3 et n/5 doit figurer dans la suite déjà construite. Cette condition nécessaire est clairement suffisante.

Programmation de la méthode en JavaScript :

Pour tester ce programme vous devrez simplement entrer la valeur maximale nmax de n. L'expression x = a%b retourne dans x le reste de la division euclidienne de a par b.

Initialisation : 2, 3, 4 et 5 sont les premiers éléments de la suite cherchée. La variable nommée suite est une chaîne de caractères stockant la suite de Hamming sous la forme 2-3-4-5-6-8...

Boucle principale : Pour n variant de 6 à nmax : si n est divisible par 2, on cherche si sa moitié est dans la table, de même pour divisible par 3 ou 5. Si oui, le drapeau d est mis à 1. Le compteur nh augmente alors de 1 (nh++) ; on stocke h(nh), nh-ème terme de la suite.

Fonction (sous-programme) "cherche" : on recherche si n/2 (ou n/3 ou n/5) est dans la table (boucle j). Si oui, le drapeau d est mis à 1 : n est élément de la suite; on force la fin de la boucle (break) et on retourne la valeur du drapeau (return d) au programme principal.

» JavaScript : fonctions mathématiques usuelles , traitement des chaines de caractères
 


<SCRIPT LANGUAGE=JavaScript>
 var h=new Array();
function go()
{
n=prompt("Donnez n max : ",1000);
if (n==null) {return} else {nmax=eval(n)};

for (i=1;i<=4;i++) {h[i]=i+1}  // initialisation
suite="2-3-4-5";  // premiers termes de la suite
nh=4;  // nh est le compteur de la suite
for (n=6;n<=nmax;n++)  // boucle principale
{
x=0;
if (n%2==0) {x=n/2};
if (n%3==0) {x=n/3};
if (n%5==0) {x=n/5};
if (x>0)
{
d=cherche(x,nh)
if (d==1)
{
nh++;h[nh]=n;
suite=suite+"-"+n.toString();
}
}
}
alert(suite)
}

function cherche(x,nh)
{
d=0;
for (j=1;j<=nh;j++){if (h[j]==x) {d=1;break}}
return d
}
</SCRIPT>

 ➔  On remarquera que la réponse du programme est quasi immédiate. En termes de complexité, le programme est en O(n), autrement dit, le temps de calcul, fondé sur la boucle principale, est proportionnel à n (» Landau). Voici le résultat pour n = 1500 :

© Serge Mehl - www.chronomath.com