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 : 168
Inscription : 23 mars 2014 14:11

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

Message par Céline » 26 mars 2014 08:57

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.
Dernière édition par Céline le 26 mars 2014 18:14, édité 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 de l’utilisateur
Marge
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 4938
Inscription : 01 oct. 2008 14:39
Localisation : En bas, tout au fond à gauche.

Re: Misez p'tit : la suite de Syracuse

Message par Marge » 26 mars 2014 13:15

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 !

« Boris », c'est juste Maurice enrhumé.

Avatar de l’utilisateur
bernouilli92
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3741
Inscription : 21 nov. 2012 14:03
Localisation : Ile de France

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

Message par bernouilli92 » 26 mars 2014 18:01

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 : 168
Inscription : 23 mars 2014 14:11

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

Message par Céline » 26 mars 2014 18:14

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 : 168
Inscription : 23 mars 2014 14:11

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

Message par Céline » 26 mars 2014 19:38

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;
Dernière édition par Céline le 27 mars 2014 14:29, édité 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 de l’utilisateur
bernouilli92
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3741
Inscription : 21 nov. 2012 14:03
Localisation : Ile de France

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

Message par bernouilli92 » 26 mars 2014 19:54

@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 de l’utilisateur
C.Ret
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 2119
Inscription : 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 » 26 mars 2014 20:03

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 + CE-121 + CE-122. | VIC 20 Commodore 128D + Printer P-803 + SD2iec. | TI-57 LCD | TI-74 BasiCalc | TI-92 II | HP-28S + HP82240A | HP-41C + (2 memory + stat + IR) modules. | HP Prime Wireless Graphing Calculator | HP-15C | CASIO fx-602p + FA-1. .Sommaire des M.P.O.. . Sommaire du P.C.T.M. .

Céline
Fonctionne à 300 bauds
Fonctionne à 300 bauds
Messages : 168
Inscription : 23 mars 2014 14:11

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

Message par Céline » 26 mars 2014 20:03

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 de l’utilisateur
C.Ret
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 2119
Inscription : 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 » 26 mars 2014 20:51

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 + CE-121 + CE-122. | VIC 20 Commodore 128D + Printer P-803 + SD2iec. | TI-57 LCD | TI-74 BasiCalc | TI-92 II | HP-28S + HP82240A | HP-41C + (2 memory + stat + IR) modules. | HP Prime Wireless Graphing Calculator | HP-15C | CASIO fx-602p + FA-1. .Sommaire des M.P.O.. . Sommaire du P.C.T.M. .

Céline
Fonctionne à 300 bauds
Fonctionne à 300 bauds
Messages : 168
Inscription : 23 mars 2014 14:11

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

Message par Céline » 26 mars 2014 20:59

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 de l’utilisateur
bernouilli92
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3741
Inscription : 21 nov. 2012 14:03
Localisation : Ile de France

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

Message par bernouilli92 » 26 mars 2014 21:55

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 de l’utilisateur
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2499
Inscription : 03 mai 2008 15:33
Localisation : Grenoble

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

Message par zpalm » 27 mars 2014 01:20

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 de l’utilisateur
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2499
Inscription : 03 mai 2008 15:33
Localisation : Grenoble

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

Message par zpalm » 27 mars 2014 01:53

...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 de l’utilisateur
Marge
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 4938
Inscription : 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 » 28 mars 2014 03:48

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 !

« Boris », c'est juste Maurice enrhumé.

Céline
Fonctionne à 300 bauds
Fonctionne à 300 bauds
Messages : 168
Inscription : 23 mars 2014 14:11

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

Message par Céline » 28 mars 2014 19:46

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
Dernière édition par Céline le 28 mars 2014 22:34, édité 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

Revenir vers « Tous les Pockets »