Misez p'tit Optimisez n°53 : la suite de Syracuse
Modérateur : Politburo
Misez p'tit Optimisez n°53 : la suite de Syracuse
Sommaire des MPO
Bonjour,
la suite de Syracuse est une suite de premier terme entier et strictement positif telle que u(n+1)=u(n)/2 si u(n) est pair et u(n+1)=3u(n)+1 sinon.
La conjecture de Syracuse affirme que cette suite finit toujours par atteindre 1.
Je vous propose d'écrire un programme qui prend u(0) et renvoie
- le temps de vol : plus petit indice n tel que u(n)=1
- l'altitude maximale : valeur maximale de la suite.
Saurez-vous trouver un u(0) qui permette un temps de vol très long, pareil pour l'altitude ? Et les deux ?
Bonne journée à tous.
Bonjour,
la suite de Syracuse est une suite de premier terme entier et strictement positif telle que u(n+1)=u(n)/2 si u(n) est pair et u(n+1)=3u(n)+1 sinon.
La conjecture de Syracuse affirme que cette suite finit toujours par atteindre 1.
Je vous propose d'écrire un programme qui prend u(0) et renvoie
- le temps de vol : plus petit indice n tel que u(n)=1
- l'altitude maximale : valeur maximale de la suite.
Saurez-vous trouver un u(0) qui permette un temps de vol très long, pareil pour l'altitude ? Et les deux ?
Bonne journée à tous.
Modifié en dernier par Céline le 26 mars 2014 17:14, modifié 3 fois.
TI-30 Galaxy
fx-180P, fx-4000P
HP 11c, 12c, 12c le, 15c, 15c le
HP 32s, 32s ii, 42s, 17b ii, 30b, 35s
HP 28s, 48s, 48sx, 48g, 50g, prime
fx-180P, fx-4000P
HP 11c, 12c, 12c le, 15c, 15c le
HP 32s, 32s ii, 42s, 17b ii, 30b, 35s
HP 28s, 48s, 48sx, 48g, 50g, prime
- Marge
- Fonctionne à 14400 bauds
- Messages : 6186
- Enregistré le : 01 oct. 2008 14:39
- Localisation : En bas, tout au fond à gauche.
Re: Misez p'tit : la suite de Syracuse
Eh bien ça démarre fort !
(ce sera donc le Misez p'tit, Optimisez - N°53)
(ce sera donc le Misez p'tit, Optimisez - N°53)
3 hommes, 3 demis, un 3a... Magnéto, Serge !
Quelques-uns de mes petits programmes pour machines Hewlett-Packard :
15C : Knight's Tour ;
29C : (k-)Permutations, Combinations, Linear Regression and Pseudo-random number ;
34C : Hanoi Towers - Automatic & Manual resolutions ;
67__: A L I E N .
♣ ♦ « Boris », c'était juste Maurice enrhumé. ♥ ♠
Quelques-uns de mes petits programmes pour machines Hewlett-Packard :
15C : Knight's Tour ;
29C : (k-)Permutations, Combinations, Linear Regression and Pseudo-random number ;
34C : Hanoi Towers - Automatic & Manual resolutions ;
67__: A L I E N .
♣ ♦ « Boris », c'était juste Maurice enrhumé. ♥ ♠
- bernouilli92
- Fonctionne à 14400 bauds
- Messages : 5259
- Enregistré le : 21 nov. 2012 13:03
- Localisation : Ile de France
Re: Misez p'tit Optimisez n°53 : la suite de Syracuse
Voici ma contribution pour hp48g, il est possible que cela fonctionne également sur hp28s et hp48s (si la fonction MAX existe).
Taille en octets : 105
u(0)=27 donne un temps de vol de 111 et une altitude de 9232.
Sinon intuitivement, je pense que les nombres de la forme 2^n-1 donnent une grande altitude, ce qui assez vrai, par contre je n'ai pas d'idée pour les u(0) qui donnent un long temps de vol.
Il faudrait légèrement corriger l'énoncé : ... de premier terme entier strictement positif telle que ...
Code : Tout sélectionner
<<
0 0 ROT
WHILE
SWAP OVER MAX SWAP
DUP 1 =/
REPEAT
ROT 1 + ROT ROT
IF DUP 2 MOD
THEN
3 * 1 +
ELSE
2 /
END
END
DROP
>>
u(0)=27 donne un temps de vol de 111 et une altitude de 9232.
Sinon intuitivement, je pense que les nombres de la forme 2^n-1 donnent une grande altitude, ce qui assez vrai, par contre je n'ai pas d'idée pour les u(0) qui donnent un long temps de vol.
Il faudrait légèrement corriger l'énoncé : ... de premier terme entier strictement positif telle que ...
HP, Casio, Sharp, Psion, quelques TI et divers autres
Re: Misez p'tit Optimisez n°53 : la suite de Syracuse
Corrigé
Oui la fonction max existe aussi sur hp 28S.
Oui la fonction max existe aussi sur hp 28S.
TI-30 Galaxy
fx-180P, fx-4000P
HP 11c, 12c, 12c le, 15c, 15c le
HP 32s, 32s ii, 42s, 17b ii, 30b, 35s
HP 28s, 48s, 48sx, 48g, 50g, prime
fx-180P, fx-4000P
HP 11c, 12c, 12c le, 15c, 15c le
HP 32s, 32s ii, 42s, 17b ii, 30b, 35s
HP 28s, 48s, 48sx, 48g, 50g, prime
Re: Misez p'tit Optimisez n°53 : la suite de Syracuse
Une proposition non optimisée pour la hp-prime, histoire de l'utiliser un peu cette machine…
Code : Tout sélectionner
export syracuse(n)
begin
local c=0, m=0;
repeat
c:=c+1;
m:=max(m,n);
if fp(n/2)==0
then n:=n/2
else n:=3*n+1
end;
until n==1;
{c+1,m};
end;
Modifié en dernier par Céline le 27 mars 2014 13:29, modifié 1 fois.
TI-30 Galaxy
fx-180P, fx-4000P
HP 11c, 12c, 12c le, 15c, 15c le
HP 32s, 32s ii, 42s, 17b ii, 30b, 35s
HP 28s, 48s, 48sx, 48g, 50g, prime
fx-180P, fx-4000P
HP 11c, 12c, 12c le, 15c, 15c le
HP 32s, 32s ii, 42s, 17b ii, 30b, 35s
HP 28s, 48s, 48sx, 48g, 50g, prime
- bernouilli92
- Fonctionne à 14400 bauds
- Messages : 5259
- Enregistré le : 21 nov. 2012 13:03
- Localisation : Ile de France
Re: Misez p'tit Optimisez n°53 : la suite de Syracuse
@celine : il y a une petite erreur dans ton programme, il ne donne pas les bons résultats pour n=1.
Voici une nouvelle version permettant de gagner 2,5 octets :
Taille : 102,5 octets
Voici une nouvelle version permettant de gagner 2,5 octets :
Code : Tout sélectionner
<<
0 1 ROT
WHILE
DUP 1 =/
REPEAT
ROT 1 + OVER 4 ROLL MAX ROT
IF DUP 2 MOD
THEN
3 * 1 +
ELSE
2 /
END
END
DROP
>>
HP, Casio, Sharp, Psion, quelques TI et divers autres
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3419
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: Misez p'tit Optimisez n°53 : la suite de Syracuse
Ah! Chouette un MPO. Et cette fois je le vois le jour même !
Bien.
Mais c'est pas pour autant que j'ai une solution efficace...
Me reste plus qu'à en chercher une...
Bien.
Mais c'est pas pour autant que j'ai une solution efficace...
Me reste plus qu'à en chercher une...
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Re: Misez p'tit Optimisez n°53 : la suite de Syracuse
oui j'avais corrigé en supprimant le print pour un affichage plus rapide.bernouilli92 a écrit :il y a une petite erreur dans ton programme, le print de la fin devrait afficher c et non c+1
Il semble que 9232 soit une altitude difficile à dépasser avec des départs à altitude "raisonnable".bernouilli92 a écrit :u(0)=27 donne un temps de vol de 111 et une altitude de 9232
Pour 737, j'obtiens un temps de vol de 140 et une altitude de 9232.
TI-30 Galaxy
fx-180P, fx-4000P
HP 11c, 12c, 12c le, 15c, 15c le
HP 32s, 32s ii, 42s, 17b ii, 30b, 35s
HP 28s, 48s, 48sx, 48g, 50g, prime
fx-180P, fx-4000P
HP 11c, 12c, 12c le, 15c, 15c le
HP 32s, 32s ii, 42s, 17b ii, 30b, 35s
HP 28s, 48s, 48sx, 48g, 50g, prime
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3419
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: Misez p'tit Optimisez n°53 : la suite de Syracuse
Avec 1023, je monte à 118096 en un temps de vol ne dépassant pas 63 :
run
n=? 1023
1023 ->3070->1535->4606->2303->6910->3455->10366->5183->15550->7775->23326->
11663->34990->17495->52486->26243->78730->39365->118096->59048->29524->14762->7381
->22144->11072->5536->2768->1384->692->346->173->520->260->130->65->196->98->49->148
->74->37->112->56->28->14->7->22->11->34->17->52->26->13->40->20->10->5->16->8->4->2->1
Max:118096 ToF:63
ready.
run
n=? 1023
1023 ->3070->1535->4606->2303->6910->3455->10366->5183->15550->7775->23326->
11663->34990->17495->52486->26243->78730->39365->118096->59048->29524->14762->7381
->22144->11072->5536->2768->1384->692->346->173->520->260->130->65->196->98->49->148
->74->37->112->56->28->14->7->22->11->34->17->52->26->13->40->20->10->5->16->8->4->2->1
Max:118096 ToF:63
ready.
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Re: Misez p'tit Optimisez n°53 : la suite de Syracuse
C'est de la voltige aérienne làC.Ret a écrit :Avec 1023, je monte à 118096 en un temps de vol ne dépassant pas 63
TI-30 Galaxy
fx-180P, fx-4000P
HP 11c, 12c, 12c le, 15c, 15c le
HP 32s, 32s ii, 42s, 17b ii, 30b, 35s
HP 28s, 48s, 48sx, 48g, 50g, prime
fx-180P, fx-4000P
HP 11c, 12c, 12c le, 15c, 15c le
HP 32s, 32s ii, 42s, 17b ii, 30b, 35s
HP 28s, 48s, 48sx, 48g, 50g, prime
- bernouilli92
- Fonctionne à 14400 bauds
- Messages : 5259
- Enregistré le : 21 nov. 2012 13:03
- Localisation : Ile de France
Re: Misez p'tit Optimisez n°53 : la suite de Syracuse
Voici la liste des plus petits u(0) donnant une suite croissante d'altitudes. Je me suis arrêté à 1231.
1 -> 1
2 -> 2
3 -> 16
7 -> 52
15 -> 160
27 -> 9232
255 -> 13120
447 -> 39364
639 -> 41524
703 -> 250504
Et voici la même chose pour le temps de vol :
1 -> 0
2 -> 1
3 -> 7
6 - > 8
7 -> 16
9 -> 19
18 -> 20
25 -> 23
27 -> 111
54 -> 112
73 -> 115
97 -> 118
129 -> 121
171 -> 124
231 -> 127
313 -> 130
327 -> 143
649 -> 144
703 -> 170
871 -> 178
On voit que la progression est plus lente, les grands sauts sont rares.
Les plus gros sauts sont avec u(0)=27 et u(0)=703, un peu comme pour l'altitude.
EDIT : Le nombre suivant 703 qui donne une altitude plus grande est 1819 qui donne une altitude de 1276936.
1 -> 1
2 -> 2
3 -> 16
7 -> 52
15 -> 160
27 -> 9232
255 -> 13120
447 -> 39364
639 -> 41524
703 -> 250504
Et voici la même chose pour le temps de vol :
1 -> 0
2 -> 1
3 -> 7
6 - > 8
7 -> 16
9 -> 19
18 -> 20
25 -> 23
27 -> 111
54 -> 112
73 -> 115
97 -> 118
129 -> 121
171 -> 124
231 -> 127
313 -> 130
327 -> 143
649 -> 144
703 -> 170
871 -> 178
On voit que la progression est plus lente, les grands sauts sont rares.
Les plus gros sauts sont avec u(0)=27 et u(0)=703, un peu comme pour l'altitude.
EDIT : Le nombre suivant 703 qui donne une altitude plus grande est 1819 qui donne une altitude de 1276936.
HP, Casio, Sharp, Psion, quelques TI et divers autres
- zpalm
- Fonctionne à 9600 bauds
- Messages : 2930
- Enregistré le : 03 mai 2008 15:33
- Localisation : Grenoble
Re: Misez p'tit Optimisez n°53 : la suite de Syracuse
Sympa ce MPO! Sur WP 34S en 19 pas (38 octets):
On entre u(0) puis [A], le programme retourne le temps de vol dans X et l'altitude maximale dans Y.
Code : Tout sélectionner
001 LBL A
002 FILL
003 STO- Y
004 x#1?
005 SKIP 002
006 DROP
007 RTN
008 INC Y
009 EVEN?
010 SKIP 006
011 3
012 *
013 INC X
014 x>?Z
015 STO Z
016 BACK 008
017 2
018 /
019 BACK 015
- zpalm
- Fonctionne à 9600 bauds
- Messages : 2930
- Enregistré le : 03 mai 2008 15:33
- Localisation : Grenoble
Re: Misez p'tit Optimisez n°53 : la suite de Syracuse
...et ma version pour HP Prime:
Code : Tout sélectionner
EXPORT SYRACUSE(N)
BEGIN
LOCAL C,M=N;
WHILE N>1 DO
C:=C+1;
IF even(N) THEN
N:=N/2;
ELSE
N:=3*N+1;
M:=MAX(N,M);
END;
END;
RETURN {C,M};
END;
- Marge
- Fonctionne à 14400 bauds
- Messages : 6186
- Enregistré le : 01 oct. 2008 14:39
- Localisation : En bas, tout au fond à gauche.
Re: Misez p'tit Optimisez n°53 : la suite de Syracuse
Mon humble contribution : une version améliorable pour HP-19/29c :
Résultats en X et Y pour la 29, imprimés pour la 19.
30 pas + 3 registres (*7octets) = 51 octets pour la 29c.
34 pas + 3 registres (*7octets) = 55 octets pour la 19c. La sagesse de Coubertin.
Code : Tout sélectionner
LBL 9
1
STO +1
RCL 1
STO 2
LBL 7
ISZ
2
/
FRAC
X # 0 ?
GTO 0
1
LAST X
X # Y ?
GTO 7
RCL 2
RCL 0
R/S (29) ou (RCL 1 PRINT RCL 2 PRINT RCL 0 PRINT ADV : 19)
0
STO 0
GTO 9
LBL 0
LAST X
6
*
1
+
STO 2
GTO 7
30 pas + 3 registres (*7octets) = 51 octets pour la 29c.
34 pas + 3 registres (*7octets) = 55 octets pour la 19c. La sagesse de Coubertin.
3 hommes, 3 demis, un 3a... Magnéto, Serge !
Quelques-uns de mes petits programmes pour machines Hewlett-Packard :
15C : Knight's Tour ;
29C : (k-)Permutations, Combinations, Linear Regression and Pseudo-random number ;
34C : Hanoi Towers - Automatic & Manual resolutions ;
67__: A L I E N .
♣ ♦ « Boris », c'était juste Maurice enrhumé. ♥ ♠
Quelques-uns de mes petits programmes pour machines Hewlett-Packard :
15C : Knight's Tour ;
29C : (k-)Permutations, Combinations, Linear Regression and Pseudo-random number ;
34C : Hanoi Towers - Automatic & Manual resolutions ;
67__: A L I E N .
♣ ♦ « Boris », c'était juste Maurice enrhumé. ♥ ♠
Re: Misez p'tit Optimisez n°53 : la suite de Syracuse
Je n'ai pas encore de pocket mais j'ai étudié le manuel du sharp pc-1500, et j'ai essayé de programmer la suite de Syracuse en Basic. Quelqu'un pourrait-il le vérifier et me dire si il tourne correctement ? Bien sûr, aucune optimisation, je n'en suis pas là. Mais je me rends bien compte que même s'il tourne, mon programme est vraiment lourdingue !
Code : Tout sélectionner
10 : INPUT "ENTRER U(0) ";A
20 : C=1 : M=A
30 : IF A=1 THEN GOTO 100
40 : IF INT(A/2)-A/2=0 THEN GOTO 70
50 : A=3*A+1 : IF M<A THEN LET M=A
60 : GOTO 80
70 : A=A/2
80 : C=C+1
90 : GOTO 30
100 : PRINT "ALTITUDE : ";M;"VOL : ";C
Modifié en dernier par Céline le 28 mars 2014 21:34, modifié 1 fois.
TI-30 Galaxy
fx-180P, fx-4000P
HP 11c, 12c, 12c le, 15c, 15c le
HP 32s, 32s ii, 42s, 17b ii, 30b, 35s
HP 28s, 48s, 48sx, 48g, 50g, prime
fx-180P, fx-4000P
HP 11c, 12c, 12c le, 15c, 15c le
HP 32s, 32s ii, 42s, 17b ii, 30b, 35s
HP 28s, 48s, 48sx, 48g, 50g, prime