Misez Rapide–Accélérez n°2 : La suite des nombres de Hamming
Modérateur : Politburo
-
- Fonctionne à 1200 bauds
- Messages : 434
- Enregistré le : 05 juin 2014 22:23
- Localisation : Dans le Gâtinais avec les abeilles, près de Fontainebleau
Re: Misez Rapide–Accélérez n°2 : La suite des nombres de Ham
La difficulté est de le faire voir à la machine, qui peut bénéficier d'une aide Cotorep tellement elle est aveugle.
J'ai bien une idée en balayant progressivement les puissances de 2, 3 et 5, ça pourrait éviter le balayage brut.
Par contre l'algo va être un poil velu (lapalissade ! ), du moins pour moi, jamais fait ça.
HP : 15C, 41CV, 48GX, 71B, 75C Canon X-07 Sharp PC 1403H, PC1500A, PC1600, PC-G850V Texas : CC40, 66, 74, 95, 92 Casio : PB-700, PB-1000, Z-1GR Psion 5mx, mais pas que...
- bernouilli92
- Fonctionne à 14400 bauds
- Messages : 5259
- Enregistré le : 21 nov. 2012 13:03
- Localisation : Ile de France
Re: Misez Rapide–Accélérez n°2 : La suite des nombres de Ham
Cette méthode oblige à calculer beaucoup plus de nombres que nécessaire pour avoir une liste sans trous.
l'exemple de charognard calcule les nombres jusque environ 6900, ce qui correspond à environ le 159ème nombre de hamming. Et avec cette liste, le 100ème terme est bon, par contre la liste contient des trous vers la fin, ce qui fait que le 150ème n'est pas le bon.
Une manière d'optimiser cela est de choisir les limites des 3 boucles de manière cohérente, ce qui est le cas dans l'exemple de charognard (12, 8 et 5) :
2^12->4096
3^8->6561
5^5->3125
On a des valeur max comparables mais on voit déjà qu'il y aura des trous dans la liste quand on va dépasser le nombre 3125.
Idéalement, il faudrait, pour avoir tous les nombres de Hamming en dessous de exp(N), que les trois boucles aillent de 0 à A, B, C avec :
A=N/ln(2) arrondi à l'entier supérieur
B=N/ln(3) arrondi à l'entier supérieur
C=N/ln(5) arrondi à l'entier supérieur
Ce qui donne, par exemple, pour N=10, c'est à dire obtenir tous les nombres de hamming en dessous de 22026 :
boucle des puissances de 2 : de 0 à 15
boucle des puissances de 3 : de 0 à 9
boucle des puissances de 5 : de 0 à 7
Et même comme cela, je ne suis pas sûr qu'il n'y ait pas de trou vers la fin de la liste.
Dans cette exemple, j'obtiens une liste de 1280 termes.
Le 200 ème terme est bon : 16200
Le 250 ème terme est bon : 38880
Le 260 ème terme est bon : 46656
Le 270 ème terme est bon : 54000
Le 280 ème n'est pas bon : 62500 alors qu'il devrait être 62208
On voit que même avec 1280 termes, cela déconne déjà au 280 ème terme.
Je pense que la liste n'est plus bonne dès que les nombres sont supérieurs à 22026. Ici la liste est bonne jusqu'à un nombre supérieur à 22026, je pense que cela est dû au fait qu'on est allé un peu plus loin dans la boucle : jusqu'à l'entier supérieur à ce qui est nécessaire.
Voici le code pour HP 48g
Code : Tout sélectionner
« { }
0 7 FOR A
0 9 FOR B
0 15 FOR C
{ 2 3 5}
A B C 3 ->LIST ^
EVAL * * +
NEXT
NEXT
NEXT
SORT
»
Exemple :
Code : Tout sélectionner
«
11 5 LN 3 LN 2 LN -> N X Y Z
« { }
0 N X / FOR A
0 N Y / FOR B
0 N Z / FOR C
A X * B Y * C Z * + +
IF DUP N <
THEN EXP +
ELSE DROP
END
NEXT
NEXT
NEXT
0 RND SORT
»
»
Au niveau des performances: le programme précédent modifié avec 8 à la place de 11 comme premier nombre me donne une liste de 122 termes au bout de 37 secondes.
A titre de comparaison: si je construis la liste des 100 premiers termes par une boucle de 1 à 1536 et en testant à chaque fois le nombre courant pour savoir si c'est un nombre de hamming (avec le code pour hp48g publié dans le post MPO67), cela prend environ 150 secondes.
-
- Fonctionne à 1200 bauds
- Messages : 434
- Enregistré le : 05 juin 2014 22:23
- Localisation : Dans le Gâtinais avec les abeilles, près de Fontainebleau
Re: Misez Rapide–Accélérez n°2 : La suite des nombres de Ham
L'idéal, serait justement un algo qui construise progressivement les nombres dans l'ordre tout de suite sans être obligé de les stocker.
Et donc, de calculer les 100 premiers exactement pour avoir le 100e.
Ici, le problème est d'avoir une liste suffisamment grande pour obtenir le nième terme : or au départ, on ne sait absolument pas jusqu'où il faut monter...
Par exemple pour le 500e ? Je construit tous les hamming jusqu'à quelle valeur ?
Attention à ceux qui ont encore des cheveux...
HP : 15C, 41CV, 48GX, 71B, 75C Canon X-07 Sharp PC 1403H, PC1500A, PC1600, PC-G850V Texas : CC40, 66, 74, 95, 92 Casio : PB-700, PB-1000, Z-1GR Psion 5mx, mais pas que...
- charognard
- Fonctionne à 9600 bauds
- Messages : 4412
- Enregistré le : 06 juin 2007 19:28
- Localisation : Indre et loire
- Contact :
Re: Misez Rapide–Accélérez n°2 : La suite des nombres de Ham
Je ne vois pas pourquoi il y aurait des trous !Une manière d'optimiser cela est de choisir les limites des 3 boucles de manière cohérente, ce qui est le cas dans l'exemple de charognard (12, 8 et 5) :
2^12->4096
3^8->6561
5^5->3125
On a des valeur max comparables mais on voit déjà qu'il y aura des trous dans la liste quand on va dépasser le nombre 3125.
3125*5 = 15625
6561*3 = 19683
4096*2 = 8192
Si tu as un exemple concret ?
Car pour moi ma couverture (12,8,5) suffit largement pour du 144*48=6912 (pour moi la couverture garantie va jusqu'à 8191)
Pour vérifier vous avez le N(159) ?
Mon code trouve 6912
- bernouilli92
- Fonctionne à 14400 bauds
- Messages : 5259
- Enregistré le : 21 nov. 2012 13:03
- Localisation : Ile de France
Re: Misez Rapide–Accélérez n°2 : La suite des nombres de Ham
Tu as raison, ton programme se limite aux nombres inférieurs ou égaux à 6912 et avec cela tu obtiens bien une liste de 159 nombres qui sont bien les 159 premiers nombres de Hamming.charognard a écrit :Je ne vois pas pourquoi il y aurait des trous !Une manière d'optimiser cela est de choisir les limites des 3 boucles de manière cohérente, ce qui est le cas dans l'exemple de charognard (12, 8 et 5) :
2^12->4096
3^8->6561
5^5->3125
On a des valeur max comparables mais on voit déjà qu'il y aura des trous dans la liste quand on va dépasser le nombre 3125.
3125*2 = 6250
4096*2 = 8192
Si tu as un exemple concret ?
Car pour moi ma couverture (12,8,5) suffit largement pour du 144*48=6912
Ton programme parcours beaucoup plus que 159 nombres (480 en fait) et parmi tous les nombres produits, on est obligé de n'en garder qu'un petit nombre pour avoir un ensemble compact.
C'est mon premier exemple qui produit 1280 termes alors que seul environ 275 forment un ensemble sans trous.
Ma remarque était due à une intuition car 3125 est beaucoup plus petit que 6912, mais tu as raison : 3125 * 2 sera aussi calculé.
- bernouilli92
- Fonctionne à 14400 bauds
- Messages : 5259
- Enregistré le : 21 nov. 2012 13:03
- Localisation : Ile de France
Re: Misez Rapide–Accélérez n°2 : La suite des nombres de Ham
Je ne crois pas que ce soit possible autrement qu'en testant les nombres un à un de manière croissante.caloubugs a écrit :Ce qui est dommage, c'est de passer par la construction d'une liste de nombres qu'on trie ensuite.
L'idéal, serait justement un algo qui construise progressivement les nombres dans l'ordre tout de suite sans être obligé de les stocker.
Et donc, de calculer les 100 premiers exactement pour avoir le 100e.
Quand que tu regardes le graphe, il n'y a aucun lien entre un nombre de hamming et celui d'après.
Exemple : pour passer de 125 à 128, il faut faire un énorme chemin.
Pour trouver celui d'après, il faut parcourir des tas de combinaisons pour ne retenir que le nombres qui viens juste après. Et un algo comme cela est plus compliqué que de parcourir et tester les nombres croissants un à un.
-
- Fonctionne à 1200 bauds
- Messages : 434
- Enregistré le : 05 juin 2014 22:23
- Localisation : Dans le Gâtinais avec les abeilles, près de Fontainebleau
Re: Misez Rapide–Accélérez n°2 : La suite des nombres de Ham
donc si j'ai déterminé H(n) et que j'applique l'algo, je trouve H(n+1).
Par exemple, si on a H(100)=1536, comment trouver H(101) ?
Je pensais que justement en testant les puissances adéquates de 2, 3 et 5, on puisse déterminer la valeur la plus basse qui soit supérieure à 1536 et hop on a notre 101ème terme.
Disons que 1536 < 2^11, 3^7 et 5^5.
5^5=3125 c'est notre première valeur de référence.
On va progressivement faire diminuer la puissance de 5 et faire varier les puissances de 3 et de 2 (en fonction de ce qui reste)
Pour 5^4=625,
pour 3^1 : on multiplie 625 par 3 ce qui donne 1875 (c'est mieux) (on reste avec 2^0)
pour 3^0 : il faut prendre 2^2 pour dépasser 1536 ce qui fait 2500 (écarté)
Pour 5^3=125
Pour 3^3 : on obtient 125*27=3375 (écarté)
Pour 3^2 : il faut prendre 2^1 d'où 125*9*2=2250 (écarté)
Pour 3^1 : il faut prendre 2^3 d'où 125*3*8=3000 (écarté)
Pour 3^0 : il faut prendre 2^4 d'où 125*16=2000 (écarté)
Pour 5^2 on a les étapes suivantes :
3^4 : 25*81=2025 (écarté), 3^3 : 25*27*2^2=2700 (écarté), 3^2 : 25*9*2^3=1800 (c'est mieux !)
3^1 : 25*3*2^5=2400 (écarté), 3^0 : 25*2^6=1600 (c'est mieux !!)
Pour 5 on a les étapes suivantes :
5*3^6=3645, 5*3^5*2=2430, 5*3^4*2^2=1620, 5*3^3*2^4=2160, 5*3^2*2^6=2880, 5*3*2^7=1920,5*2^9=2560
Pour 3 et 2 tous seuls :
3^7=2187, 3^6*2^2=2916, 3^5*2^3=1944, 3^4*2^5=2592, 3^3*2^6=1728, 3^2*2^8=2304, 3*2^9=1536 (tiens c'est H(100) donc on écarte), 2^11=2048.
Donc si tout va bien H(101)=1600. Ouf.
Je suis d'accord que je calcule plein de nombres de Hamming qui seront recalculés ensuite mais cette méthode permet d'obtenir le premier nombre de Hamming supérieur à n'importe quel seuil.
Bon, j'espère que je ne me suis pas planté...
HP : 15C, 41CV, 48GX, 71B, 75C Canon X-07 Sharp PC 1403H, PC1500A, PC1600, PC-G850V Texas : CC40, 66, 74, 95, 92 Casio : PB-700, PB-1000, Z-1GR Psion 5mx, mais pas que...
- charognard
- Fonctionne à 9600 bauds
- Messages : 4412
- Enregistré le : 06 juin 2007 19:28
- Localisation : Indre et loire
- Contact :
Re: Misez Rapide–Accélérez n°2 : La suite des nombres de Ham
Code : Tout sélectionner
10 CLS
20 FOR A=0 TO 5
25 D=5^A
30 FOR B=0 TO 8
35 E=D*3^B
40 FOR C=0 TO 12
50 F=E*2^C-1
60 IF D<6912 THEN PSET (D MOD 144, D/144) ELSE C=13
70 NEXT C
80 NEXT B
90 NEXT A
100 DIM S(160)
140 I=1
150 FOR Y=0 TO 47
160 FOR X=0 TO 143
170 IF POINT (X,Y) LET S(I)=X+1+Y*144,I=I+1
180 NEXT X
190 NEXT Y
- bernouilli92
- Fonctionne à 14400 bauds
- Messages : 5259
- Enregistré le : 21 nov. 2012 13:03
- Localisation : Ile de France
Re: Misez Rapide–Accélérez n°2 : La suite des nombres de Ham
Ce que je te disais c'est qu'un algo de ce type là est beaucoup plus compliqué que de tester si les nombres suivants sont des nombre de hamming pas.caloubugs a écrit :En fait, l'algorithme que je pensais est de construire les hamming les uns après les autres.
donc si j'ai déterminé H(n) et que j'applique l'algo, je trouve H(n+1).
.....
Je suis d'accord que je calcule plein de nombres de Hamming qui seront recalculés ensuite mais cette méthode permet d'obtenir le premier nombre de Hamming supérieur à n'importe quel seuil.
Bon, j'espère que je ne me suis pas planté...
Si tu as H(100)=1536, ben c'est plus simple de tester si 1537 est un nombre de hamming ou pas, puis 1538 etc jusqu'à 1600 qui se trouve être un nombre de hamming. et voilà tu as ton H(101).
Après avec des valeurs élevées, il est possible que ton "algo" soit plus efficace, peut-être.
Entre le H(1000) et H(1001), il y a 51840000-51200000=640000 nombres à tester.
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3419
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: Misez Rapide–Accélérez n°2 : La suite des nombres de Ham
Et je vous remercie de l'intérêt que vous portez à cet exercice. C'est ce que j'aime avec les internautes qui fréquentent ce forum, ... vous estes géniaux...
Et là, l'air de rien, du génie, il va falloir en avoir. Car l'air de rien le sujet en a fait réfléchir des gens comme nous, mais aussi Dijska, Hamming et toute une génération du M.I.T. à l’époque, puis plus tard dans les instituts, école et bureau d’études informatiques…
J'ai évidement mon algorithme préféré qui m'a servi en son temps au défit Turing, mais je ne veux pas influencer la réflexion collégiale. En fait, le but secret de ce MRA n°2 est justement de vérifier si mon point de vue se vérifie dans la pratique.
Je serais donc un peu laconique dans ce premier post résumé.
L'idée d'une résolution géométrique utilisant le quadrillage 3D que forment les points en prenant pour coordonnées les puissances de 2,3 et 5 est une excellente idée. Le quadrillage étant très régulier, le seul souci est effectivement de tout remettre dans l’ordre.
Petite piste, l’ordre, c’est remettre les points selon une droite orientée de l’origine vers l’infini. Pour cela il faut trouver une projection. Mais comme les points sont dans un espace 3D, il faut avant de projeter sur une droite, trouver une projection dans un plan…
L’idée de parcourir un sur-ensemble de nombre et tester s’ils sont "hamming", est à mon avis la meilleur méthode pour trouver les premiers nombre. Comme l’a très brillamment démontré charo. En effet, les nombres de Hamming sont relativement denses au début.
Puis au fur et à mesure que l’on grimpe dans les nombres, il y a de plus en plus de nombres issus d’autres facteurs premiers (et leur multiples, y compris ceux multiple de 2,3 et 5 …) et donc ils deviennent de plus en plus rares, rendant un peu caduque la solution de parcourir tous les entiers.
A ce moment, il peut devenir plus facile et plus rapide de construire la liste en l'augmentant progressivement. Ce qui pour les grands nombre va vite nous faire gagner du temps par rapport au parcourt systématique de tous les entiers. Mais il nous reste à découvrir le moyen de ne pas faire de "Trous".
Bon, je crois que nous sommes en bonne voie…
Je suis juste un peu déçu que personne n’utilise les techniques musicales ou babyloniennes. C’est un peu dommage, … mais c’est surtout le souci du MPO. N°67 qui n’a pas encore découvert le Graal.
- gege
- Fonctionne à 14400 bauds
- Messages : 7147
- Enregistré le : 31 janv. 2008 14:24
- Localisation : Banlieue Paârisienne
- Contact :
Re: Misez Rapide–Accélérez n°2 : La suite des nombres de Ham
Un autre programme, ici sur PC-E500 :
Code : Tout sélectionner
10 N=100:DIM H(N):H(1)=1:FOR I=1 TO N-1
20 D=H(I):PRINT D;:J=1:A=INT(D/5)
30 IF H(J)<=A THEN J=J+1:GOTO 30
40 B=5*H(J):A=INT(D/3)
50 IF H(J)<=A THEN J=J+1:GOTO 50
60 C=3*H(J):A=INT(D/2):IF C<B THEN B=C
70 IF H(J)<=A THEN J=J+1:GOTO 70
80 A=2*H(J):IF A<B THEN B=A
90 H(I+1)=B:NEXT I:PRINT H(I)
Il trouve les 100 premiers nombres de Hamming en 47 secondes.
Il y a une optimisation simple, mais vous allez tellement vite que je le poste tout de suite !
Je continue à chercher...
G.E.
EDIT : h(500) = 937500...
- charognard
- Fonctionne à 9600 bauds
- Messages : 4412
- Enregistré le : 06 juin 2007 19:28
- Localisation : Indre et loire
- Contact :
Re: Misez Rapide–Accélérez n°2 : La suite des nombres de Ham
un nombre de haming est défini par 3 composantes X,Y,Z.
Bref pour faire imager ... la masse de blocs de ciment.
On les calcule un par un et on les balance dans une solution visqueuse.
Ensuite on part en plongée et on a les blocs triés suivant leur profondeur.
Problème :
Si pour les premiers blocs on trouve de suite. Plus on avance et moins c'est dense !
Il faudrait donc un liquide avec une densité évoluante et suffisamment discriminante.
Bref.
J'ai mon liquide visqueux (l'écran). Je me penche sur la densité maintenant.
- gege
- Fonctionne à 14400 bauds
- Messages : 7147
- Enregistré le : 31 janv. 2008 14:24
- Localisation : Banlieue Paârisienne
- Contact :
Re: Misez Rapide–Accélérez n°2 : La suite des nombres de Ham
Voici la version plus optimisée :
Code : Tout sélectionner
10 N=100:DIM H(N):H(1)=1:U=1:V=1:W=1:FOR I=1 TO N-1
20 D=H(I):PRINT D;:A=INT(D/5)
30 IF H(U)<=A THEN U=U+1:GOTO 30
40 B=5*H(U):A=INT(D/3)
50 IF H(V)<=A THEN V=V+1:GOTO 50
60 C=3*H(V):A=INT(D/2):IF C<B THEN B=C
70 IF H(W)<=A THEN W=W+1:GOTO 70
80 A=2*H(W):IF A<B THEN B=A
90 H(I+1)=B:NEXT I:PRINT H(I)
Il trouve les 100 premiers nombres de Hamming en 12 secondes...
Les 200 premiers en 25 secondes.
G.E.
EDIT : ben zut j'ai tué le MRA ??
Le principe est le suivant :
On est au Nième nombre de Hamming H(N) et on cherche le suivant.
Celui-ci est forcément 5 fois, 3 fois ou 2 fois un nombre dans la liste des nombres de Hamming qu'on a déjà.
On se débrouille pour avoir trois pointeurs U, V et W qui sont les indices vérifiant que U est le plus petit tel que 5*H(U) > H(N), pareil avec V et W pour 3 et 2.
Donc le prochain nombre de Hamming est le plus petit de 5*H(U), 3*H(V) et 2*H(W).
Et on recommence...
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3419
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: Misez Rapide–Accélérez n°2 : La suite des nombres de Ham
C'est juste que tout le monde est plongé dans la lecture de la nouvelle Gazette !
Ton algorithme est très proche du mien.
La seule différence est que j ne "recherche pas" les H(v), H(u) ou H(w) à chaque pas, mais je fait avancer un pointeur qui donne tout de suite la bonne position pour le coup suivant.
Prenons le temps d'expliquer :
Dans un premier temps observons les dix premiers Nombre de Hamming :
Code : Tout sélectionner
1 2 3 4 5 6 8 9 10 12
Code : Tout sélectionner
1 2 3 4 5 6 8 9 10 12
/|\ /|\ /|\ /|\ /|\ /|\ /|\ /|\ /|\ /|\
/ | \ / | \ / | \ / | \ / | \ / | \ / | \ / | \ / | \ / | \
2 3 5 4 6 10 6 9 15 8 12 20 10 15 25 12 18 30 16 24 40 18 27 45 20 30 50 24 36 60
Code : Tout sélectionner
1
┌──────────────────────────┼──────────────────────────┐
2 3 5
┌────────┼────────┐ ┌────────┼────────┐ ┌────────┼────────┐
4 6 10 6 9 15 10 15 25
┌──┼──┐ ┌──┼──┐ ┌──┼──┐ ┌──┼──┐ ┌──┼──┐ ┌──┼──┐ ┌──┼──┐ ┌──┼──┐ ┌──┼──┐
8 12 20 12 18 30 20 30 50 12 18 30 18 27 45 30 45 75 20 30 50 30 45 75 50 75 125
Cette redondance va créer générer beaucoup de nombres redondants, ce qui va passablement ralentir le mécanisme de remise dans l’ordre de tout cela. Sans compter qu’il va falloir mémoriser de millier de nombre.
Il est possible de présenter l’arbre en l’organisant dans l’ordre des nombre :
Code : Tout sélectionner
1 =1
┌──────────────────────────┼──────────────────────────┐
2 │ │ =2
┌────────┼────────┐ 3 │ =3
4 │ │ ┌────────┼────────┐ │ =4
│ │ │ │ │ │ 5 =5
┌──┼──┐ 6 │ 6 │ │ ┌────────┼────────┐ =6
8 │ : ┌──┼──┐ │ ┌──┼──┐ │ │ │ │ │ =8
° │ : │ : : │ │ : : 9 │ │ │ │ =9
│ : │ : : 10 │ : : ┌──┼──┐ │ 10 │ │ =10
12 : 12 : : ┌──┼──┐ 12 : : : : : │ ┌──┼──┐ │ │ =12
° : ° : : : : : ° : : : : : 15 : : : 15 │ =15
: : : : : : : : : : : ┌──┼──┐ : : : ┌──┼──┐ │
: : : : : : : : : : : : : : : : : : : : │
° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° °
20 18 30 20 30 50 18 30 18 27 45 30 45 75 20 30 50 30 45 75 25
Code : Tout sélectionner
1 =1
┌──────────────────────────┼──────────────────────────┐
2 │ │ =2
┌────────┼────────┐ 3 │ =3
4 │ │ ┌────────┼────────┐ │ =4
│ │ │ │ │ │ 5 =5
┌──┼──┐ 6 │ ° │ │ ┌────────┼────────┐ =6
8 │ : ┌──┼──┐ │ │ │ │ │ │ =8
+ │ : │ : : │ 9 │ │ │ │ =9
│ : │ : : 10 ┌──┼──┐ │ ° │ │ =10
12 : ° : : ┌──┼──┐ : : : │ │ │ =12
+ : : : : : : : : : 15 ° │ =15
: : : : : : : : : ┌──┼──┐ │
: : : : : : : : : : : : │
° ° ° ° ° ° : : : : : : :
+ + 20 18 30 20 30 50 18 27 45 30 45 75 25
On constate aussi qu’à chaque pas, il faut sélectionner la feuille de valeur la plus faible (qui se trouve être le plus souvent celle issue des 2-multiples, mais pas toujours). Une fois la feuille minimale sélectionnée de valeur h, cette sous-branche sera constituée des valeur 2h ,3h et 5h. Il y a de grandes chances que parmi ces trois racine, une ou deux sont communes avec une autre sous-branche car n’oublions pas que h est un nombre de Hamming.
Donc, tout revient comme s’il n’y avait , à chaque étape de la constituion de l’arbre que trois bourgeons possibles, l’un 2-multiple, l’autre 3-multiple et le dernier 5-multiple.
D’où l’idée de construire l’arbre à partir de trois pointeurs :
Comme pour le code de gégé, d’utiliser les 3 pointeurs que l’on déplace sur la liste des nombres de Hamming que l’on a déjà construite.
Au départ, on n’a que la racine 1 dans cette liste : les trois pointeurs a, b et c pointent donc tous sur cet unique élément, générant les prochains candidats a 3 et 5 (respectivement 2*H(a), 3*H(b) et 5*H(c).
Code : Tout sélectionner
{ 1 }
^abc
/ | \
/ | \
2 3 5
Code : Tout sélectionner
{ 1 2 }
^bc ^a
/ | |
3 5 4
Code : Tout sélectionner
{ 1 2 3}
^c ^a ^b
| | |
5 4 9
Code : Tout sélectionner
{ 1 2 3 4}
^c ^ab
| / \
5 6 9
Code : Tout sélectionner
{ 1 2 3 4 5}
^c ^ab
| / \
10 6 9
Code : Tout sélectionner
{ 1 2 3 4 5 6}
^c ^b ^a
| | |
10 9 8
Code : Tout sélectionner
{ 1 2 3 4 5 6 8}
^c ^b ^a
| | |
10 9 10
Cependant, le plus petit des candidats est 9 donné par ^b
Code : Tout sélectionner
{ 1 2 3 4 5 6 8 9}
^c ^b ^a
| | |
10 12 10
Code : Tout sélectionner
{ 1 2 3 4 5 6 8 9 10}
^c ^b ^a
| | |
15 12 12
Code : Tout sélectionner
{ 1 2 3 4 5 6 8 9 10 12}
^c ^b ^a
| | |
15 15 16
Voilà cela donne un code dont le principe est le même que celui proposé par gégé, à ceci prêt que l’on n’a pas à rechercher les H(u), H(v) ou H(w), car leur « position » est mise à jour « automatiquement » à chaque pas.
Code : Tout sélectionner
LIST
10 m%=511: DIM H(m%): N=1: A=2:B=3:C=5: INPUT r% : T0=TIMER
20 DO
30 : h%=n% AND m%: n%=n%+1: H(h%)=N: IF r%<92 THEN PRINT N,
40 : IF A=N THEN a%=(a%+1)AND m%: A=2*H(a%)
50 : IF B=N THEN b%=(b%+1)AND m%: B=3*H(b%)
60 : IF C=N THEN c%=(c%+1)AND m%: C=5*H(c%)
70 : N=MIN(A,B,C)
80 LOOP WHILE n%<r%
90 PRINT N:PRINT "H(";n%;"=";H(h%);tab(30);INT((TIMER-T0)/6)/10;"s"
ready.
run
? 10
1 2 3 4 5 6 8 9
10 12 15
h 10 = 12 .4s
ready.
run
? 50
1 2 3 4 5 6 8 9
10 12 15 16 18 20 24 25
27 30 32 36 40 45 48 50
54 60 64 72 75 80 81 90
96 100 108 120 125 128 135 144
150 160 162 180 192 200 216 225
240 243 250
h 50 = 243 2.3s
ready.
RUN
? 100
h 100 = 1536 3.8s
ready.
RUN
? 200
h 200 = 16200 7.9s
ready.
_
En effet, rien ne sert de garder en mémoire les valeur H() inférieur à la position du pointeur ^c (c'est-à-dire la variable c%)
Bon, mais cela ne revient qu’à utiliser un algorithme basé sur le fait que si H est un ensemble de nombres de Haming, alors 2.H, 3.H et 5.H le sont également et que donc on peut construire un arbre qui parcouru astucieusement donne la suite des nombres dans l’ordre.
Il doit exister d’autres moyens à partir d’autres approche.
Comme par exemeple les puissances [p q r] successives [2 3 5] ou l’approche géométique des tétrades des point (x,y,z) dans le repère géométrique (*2 *3 *5) .
Code : Tout sélectionner
H [ p q r ] H [ p q r ] H [ p q r ]
--- ---------- --- ---------- --- ----------
1 0 0 0 15 0 1 1 40 3 0 1
2 1 0 0 16 4 0 0 45 0 2 1
3 0 1 0 18 1 2 0 48 4 1 0
4 2 0 0 20 2 0 1 50 1 0 2
5 0 0 1 24 3 1 0 54 1 3 0
6 1 1 0 25 0 0 2 60 2 1 1
8 3 0 0 27 0 3 0 64 6 0 0
9 0 2 0 30 1 1 1 72 3 2 0
10 1 0 1 32 5 1 0 75 0 1 2
12 2 1 0 36 2 2 0 80 4 0 1
- gege
- Fonctionne à 14400 bauds
- Messages : 7147
- Enregistré le : 31 janv. 2008 14:24
- Localisation : Banlieue Paârisienne
- Contact :
Re: Misez Rapide–Accélérez n°2 : La suite des nombres de Ham
Excellent !
Je suppose que tu es sur Palm 5mx ? Je testerai sur Sharp.
On n'ira pas plus loin avec cette méthode.
Attention la taille limitée du buffer limite aussi les indices calculables.
Je cherche côté "géométrique".
G.E.