Misez p'tit Optimisez n°53 : la suite de Syracuse

Ici, on fait dans le petit, le LCD qui déchire sa race, on y cause même calculatrices quand on est en manque !

Modérateur : Politburo

Répondre
Céline
Fonctionne à 300 bauds
Fonctionne à 300 bauds
Messages : 169
Enregistré le : 23 mars 2014 13:11

Misez p'tit Optimisez n°53 : la suite de Syracuse

Message par Céline »

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.
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
Avatar du membre
Marge
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 6172
Enregistré le : 01 oct. 2008 14:39
Localisation : En bas, tout au fond à gauche.

Re: Misez p'tit : la suite de Syracuse

Message par Marge »

Eh bien ça démarre fort !
(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é.
Avatar du membre
bernouilli92
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5226
Enregistré le : 21 nov. 2012 13:03
Localisation : Ile de France

Re: Misez p'tit Optimisez n°53 : la suite de Syracuse

Message par bernouilli92 »

Voici ma contribution pour hp48g, il est possible que cela fonctionne également sur hp28s et hp48s (si la fonction MAX existe).

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
>>
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 ...
HP, Casio, Sharp, Psion, quelques TI et divers autres
Céline
Fonctionne à 300 bauds
Fonctionne à 300 bauds
Messages : 169
Enregistré le : 23 mars 2014 13:11

Re: Misez p'tit Optimisez n°53 : la suite de Syracuse

Message par Céline »

Corrigé :wink:
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
Céline
Fonctionne à 300 bauds
Fonctionne à 300 bauds
Messages : 169
Enregistré le : 23 mars 2014 13:11

Re: Misez p'tit Optimisez n°53 : la suite de Syracuse

Message par Céline »

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
Avatar du membre
bernouilli92
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5226
Enregistré le : 21 nov. 2012 13:03
Localisation : Ile de France

Re: Misez p'tit Optimisez n°53 : la suite de Syracuse

Message par bernouilli92 »

@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 :

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
>>
Taille : 102,5 octets
HP, Casio, Sharp, Psion, quelques TI et divers autres
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3404
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

Message par C.Ret »

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...
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.
Céline
Fonctionne à 300 bauds
Fonctionne à 300 bauds
Messages : 169
Enregistré le : 23 mars 2014 13:11

Re: Misez p'tit Optimisez n°53 : la suite de Syracuse

Message par Céline »

bernouilli92 a écrit :il y a une petite erreur dans ton programme, le print de la fin devrait afficher c et non c+1
oui j'avais corrigé en supprimant le print pour un affichage plus rapide.
bernouilli92 a écrit :u(0)=27 donne un temps de vol de 111 et une altitude de 9232
Il semble que 9232 soit une altitude difficile à dépasser avec des départs à altitude "raisonnable".
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
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3404
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

Message par C.Ret »

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.
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.
Céline
Fonctionne à 300 bauds
Fonctionne à 300 bauds
Messages : 169
Enregistré le : 23 mars 2014 13:11

Re: Misez p'tit Optimisez n°53 : la suite de Syracuse

Message par Céline »

C.Ret a écrit :Avec 1023, je monte à 118096 en un temps de vol ne dépassant pas 63
C'est de la voltige aérienne là 8)
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
Avatar du membre
bernouilli92
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5226
Enregistré le : 21 nov. 2012 13:03
Localisation : Ile de France

Re: Misez p'tit Optimisez n°53 : la suite de Syracuse

Message par bernouilli92 »

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.
HP, Casio, Sharp, Psion, quelques TI et divers autres
Avatar du membre
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2918
Enregistré le : 03 mai 2008 15:33
Localisation : Grenoble

Re: Misez p'tit Optimisez n°53 : la suite de Syracuse

Message par zpalm »

Sympa ce MPO! Sur WP 34S en 19 pas (38 octets):

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 
On entre u(0) puis [A], le programme retourne le temps de vol dans X et l'altitude maximale dans Y.
Avatar du membre
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2918
Enregistré le : 03 mai 2008 15:33
Localisation : Grenoble

Re: Misez p'tit Optimisez n°53 : la suite de Syracuse

Message par zpalm »

...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;
Avatar du membre
Marge
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 6172
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

Message par Marge »

Mon humble contribution : une version améliorable pour HP-19/29c :

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
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.
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é.
Céline
Fonctionne à 300 bauds
Fonctionne à 300 bauds
Messages : 169
Enregistré le : 23 mars 2014 13:11

Re: Misez p'tit Optimisez n°53 : la suite de Syracuse

Message par Céline »

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
Répondre

Retourner vers « Tous les Pockets »