M.P.O. n°67 : Les nombres de Hamming

[C.Ret]

Comme vous l’aurez compris en observant ce magnifique diagramme de Hass, le thème de ce nouvel M.P.O. vous propose de s'attarder sur l’étude des nombres de Hamming. Les nombres de Hamming ont plusieurs dénominations ; en fonction de leur champ d’application se sont des nombres moches , des nombres cinq-mous ou des glyphes babyloniens.


Les mathèmatiques les définissent comme étant les entiers de la forme , c'est-à-dire les entiers dont les seuls diviseurs premiers sont 2, 3 ou 5.

Les 20 premiers Nombre de Hamming sont : 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36


Comme Dijkstra, Edsger W. l’avait fait en 1976 dans son ouvrage A Discipline of Programming au chapitre n°17 intitulé "An exercise attributed to R. W. Hamming" ( Prentice-Hall, pp. 129–134, ISBN 978-0132158718 ), je vous propose quelque exercice pour vos Pockets et Micros préférés.

Evidemment, ce M.P.O. est en relation directe avec le M.R.A. n°2 qui partage le même thème mais pas le même objectif.


L’objectif de ce M.P.O. est d’écrire un code pour votre calculette ou micro qui permet de vérifier qu’un entier donné N est effectivement un nombre de Hamming.

Vous pourrez pour cela mettre en œuvre tout algorithme de votre choix et de votre convenance qui utilisera ou non les multiples propriétés des Nombre de Hamming.

Vous pourriez utiliser, par exemple, l’une ou l’autre des méthodes suivantes:

• décomposer le nombre N en facteur premiers et vérfier qu’il n’en a pas d’autres que 2,3 et 5 ;
• rechercher par récurrence l’entier N dans l’ensemble H des nombre de Hamming, sachant que si H est un ensemble composé uniquement de nombres de Hamming, alors 2.H, 3.H et 5.H sont également des ensembles de nombres de Hamming
• trouver les intonations justes de votre instrument de musique préféré et vérifier que N fait bien partie d’une harmonique de la gamme diatonique,
• retrouver les plaquettes d’argile que votre grand-père archéologue a remmenées d’Asie sumérienne et retrouver N parmi les glyphes mésopotamiens,
• tirer au sort le résultat du programme,… ou utiliser les résultats du MRA n°2
• utiliser un algorithme personnel, mais fort sympathique...

Le programme n’a pas d’autre contrainte que d’indiquer si le nombre saisi est un Nombre de Hamming ou Non et cela par tout moyen que vous jugerez opportun en fonction des capacités d’affichage, d’impression, la présence d’un signal sonore, d’un clignotement, de drapeaux, d'une couleur, de vibrations, explosions, ou la désintégration … de votre calculateur.


Quelques exemples de nombres à tester :

Code : Tout sélectionner

 Ne sont pas des nombres de Hamming:

       123 =  1 × 3 × 41 

      5040 =  1 × 2⁴ × 3² × 5 × 7

 337689200 =  1 × 2⁴ × 5² × 31 × 113 × 241

Sont des Nombres de Hamming:

       720 =  1 × 2⁴ × 3² × 5 

 559872000 =  1 × 2¹¹ × 3⁷ × 5³  

 777600000 =  1 × 2¹⁰ × 3⁵ × 5⁵  

Quelque soit l’algorithme que vous déciderez d’implémenter dans votre calculette ou micro, n’oublier pas de Miser Petit et d’Optimiser.

[bernouilli92]

Voici ma version pour hp 28 et hp 48 :

Code : Tout sélectionner

« 5
  WHILE DUP 1 >
  REPEAT
    WHILE DUP2 MOD NOT
    REPEAT 
      SWAP OVER / 
      SWAP
    END 
    .7 * IP
  END 
  DROP 1 ==
»

Taille: 85,5 octets


Et une version pour hp 42 basée sur le même principe :

Code : Tout sélectionner

01 LBL "Hamming"
02 STO 00
03 5
04 STO 01
05 LBL 01
06 RCL 00
07 RCL 01
08 MOD
09 x≠0?
10 GTO 02
11 RCL 01
12 STO÷ 00
13 GTO 01
14 LBL 02
15 RCL 01
16 0.7
17 *
18 IP
19 STO 01
20 1
21 X<>Y?
22 GTO 01
23 RCL 00
24 1
25 X≠Y?
26 0
27 END

Je ne suis toujours pas familier avec le langage de programmation des hp41/42.

Et une autre légèrement plus courte en utilisant un sous-programme et en remplaçant le test final par 1/X IP:

Code : Tout sélectionner

01 LBL "Hamming"
02 STO 00
03 5
04 XEQ 03
05 3 
06 XEQ 03
07 2
08 XEQ 03
09 RCL 00
10 1/X
11 IP
12 RTN
13 LBL 03
14 STO 01
15 LBL 01
16 RCL 00
17 RCL 01
18 MOD
19 x≠0?
20 RTN
21 RCL 01
22 STO÷ 00
23 GTO 01
24 END

Edit :
On peut gagner 8 octets sur la version RPL en remplaçant 0.7 * IP par 2 / CEIL

Code : Tout sélectionner

« 5
  WHILE DUP 1 >
  REPEAT
    WHILE DUP2 MOD NOT
    REPEAT 
      SWAP OVER / 
      SWAP
    END 
    2 / CEIL
  END 
  DROP 1 ==
»

Taille : 77,5 octets

[babaorhum]

Bonjour,
En mode "boeuf" (sans réfléchir), 5 lignes sur mon sharp pc-1350 :

Code : Tout sélectionner

10 "H" AREAD N : D=5 : GOSUB 40 : D=3 :GOSUB 40 : D=2 : GOSUB 40
20 IF N=1 THEN PRINT "YES" : END 
30 PRINT "NO" : END 
40 M=N/D : IF M=INT M THEN LET N=M : GOTO  40
50 RETURN 

33768900 def H donne "NO"
559872000 def H donne "YES"

... Pas calculé le nombre d'octets (il y a d'autres trucs en mémoire. .)

[alain1261]

Bonjour,
En mode "boeuf" (sans réfléchir), 5 lignes sur mon sharp pc-1350 :

Code : Tout sélectionner

10 "H" AREAD N : D=5 : GOSUB 40 : D=3 :GOSUB 40 : D=2 : GOSUB 40
20 IF N=1 THEN PRINT "YES" : END 
30 PRINT "NO" : END 
40 M=N/D : IF M=INT M THEN LET N=M : GOTO  40
50 RETURN 

33768900 def H donne "NO"
559872000 def H donne "YES"

... Pas calculé le nombre d'octets (il y a d'autres trucs en mémoire. .)

Simple mais efficace.

Bien vu pour le INT sans les parenthèses.

Sur mon PC1261, ton programme consomme 90 octets.

[C.Ret]

Ah! Je vois avec satisfaction que les premiers codes apparaissent.

A priori, vous utilisez surtout l'approche par la décomposition en facteur.
C'est effectivement une voie possible.

J'ai moi aussi quelques trucs dans ce genre de détermination :

Code : Tout sélectionner

dload"hamming test"

searching for 0:hamming test
loading
ready.
list

10 input "[dwn][dwn]N=";n  : print "[up]"chr$(27)"q"n; : s$="="
20 if n>1 then f%=2:gosub 1000:f%=3:gosub 1000:f%=5:gosub 1000
30 if n=1 then print " is hamming" : else print s$;n
40 end
1000 p%=0
1010 q=n/f%:if q=int(q) then p%=p%+1:n=q:goto 1010
1020 if p% then print s$;f%;:s$=".":if p%>1 then print "[up][lft][lft]";p%;"[lft][dwn]";
1030 return

ready.
RUN


 123 = 3 . 41

         4   2
 5040 = 2 . 3 . 5 . 7

              4   2
 337689200 = 2 . 5 . 844223

        4   2
 720 = 2 . 3 . 5  is hamming

              11   7   3
 559872000 = 2  . 3 . 5  is hamming

              10   5   5
 777600000 = 2  . 3 . 5  is hamming


N=? _

Tant qu'à décomposer, autant en profiter pour afficher la décomposition.

En RPL, j'avais pensé à une astuce récurrente.
N est un entier de Hamming ayant pour base (2,3,5) si l'un au moins des nombres H/2, H/3 ou H/5 est aussi un entier de hamming issue de la base(2,3,5).

Ce qui revient à décomposé jusqu'à arriver à 1 :

Code : Tout sélectionner

21600   
   /2 /2 /2 /2 /2 --> 675
                    /5 /5 ---> 27
                          /3 /3  /3  --->1  donc 21600 est hamming 21600 = 2^5.3^3.5^2

ISHAM?:
« IF DUP 1 == THEN DROP "is Hamming" KILL
  ELSE IF  DUP  2  MOD  NOT  THEN 2  /  ISHAM?
     ELSE IF  DUP 3  MOD  NOT  THEN  3 / ISHAM?
       ELSE IF DUP 5 MOD NOT THEN 5 / ISHAM? 
            END
       END
     END
  END »

Mais c'est pas rapide et rempli la pile de nombres... sans compter que la récurrence consomme un max de mémoire à cause des centaines d'appels de la fonction ISHAM?

Donc, j'ai ensuite trouvé plus facile de décomposer comme le fait bernouilli92
Mais pour fair court, j'utilise une structure FOR / NEXT, quitte à tester la multiplicité avec 4, ce qui est inutile (et toujours négatif car on vient d'épuiser celle de 2).
C'est un M.P.O., seul le nombre de pas compte, pas l'efficacité ou la vitesse !

Code : Tout sélectionner

HAM?:
« 2 5 FOR f
     WHILE DUP f MOD NOT 
        REPEAT f / END
  NEXT 1 == »

ce qui en BASIC revient à faire :

Code : Tout sélectionner

10:"H" AREAD N : FOR F=2 TO 5 
20 IF (N MOD F) = 0  THEN N=N/F : GOTO 20
30 NEXT F: PRINT N=1 : END

Mais pour mon HP41C et mon très lent SHARP PC-1211, j'ai trouvé bien mieux en recherchant du côté de la Mésopotamie antique.

[ledudu]

Machine : Casio Pro FX-1
Langage : Fortran Casio

Ce petit problème correspond tout juste aux capacités de cette machine.

Soit N=(2^a) x (3^b) x (5^c) x reste

Les registres 4, 5 et 6 contiennent les diviseurs 2, 3 et 5.
Les registres 7, 8 et 9 conservent le nombre de facteurs : a,b et c.

Le registre I sert de référence indirecte.
Si I=4 alors IM pointe sur le registre 4 et vaut donc 2.
Pour I=4, on cumule a dans le registre 7, puis pour I=5, b dans le registre 8 et enfin pour I=6, c dans le registre 9.

On START et on entre le nombre cible sur ENT 1.

A la fin des calculs, la machine affiche d'abord le reste, puis le nombre de puissances de 2, de 3 puis de 5. Il faut appuyer sur ANS pour afficher le nombre suivant.

Remarque : 3=2+0-0 : calcul de la partie entière du registre 2 dans le registre 3 grâce au registre 0 qui vaut 10^10 et à l'arrondi fait par la machine.

Code : Tout sélectionner

ENT 1:0=K10 10^x:4=K2:5=K3:6=K5:I=K4:
ST #1:2=1/IM:3=2+0-0:IF 3=2:3:2:3:
ST #2:1=2:I=I+5:IM=IM+K1:I=I-5:GOTO 1:
ST #3:IF I=K6:4:5:4:
ST #4:I=I+K1:GOTO 1:
ST #5:ANS 1:7:8:9:
127 pas / 127

D'autres programmes pour PRO Fx-1.

[Gilles59]

Bonjour à tous.

Sur 50G c'est un peu de la triche, en plus avec l'indispensable Library GOFERLIST

Code : Tout sélectionner

<< FACTORS  << TYPE >> Filter  { 5 3 2 } SAME >>

Instantané sur la vraie calc.