Misez p'tit, optimisez n°61: Produit de chiffres en séquence

[zpalm]

Voici un petit MPO en attendant la prochaine gazette.

Considérons la suite Un+1 = Un + (produit des chiffres non nuls de Un)

Si on commençe avec U1=1 on obtient : 1, 2, 4, 8, 16, 22, 26, 38, 62, 74 ….

Si on commence avec U1=3 on obtient : 3, 6, 12, 14, 18, 26, 38, 62, 74 …

On s’apercoit alors qu'à partir de 26 les deux suites vont être identiques. On peut définir LU(n), la Longueur de U pour U1=n, par le nombre de termes que l’on ne retrouve pas dans la suite commençant par 1. On a donc LU(3)=5.

Touver la valeur de n <=1000 pour laquelle LU(n) est maximale. On optimisera en particulier la rapidité d’obtention de la solution.

( Sommaire des MPO )

[C.Ret]

Voici, après une mûre réflexion dans les bouchons sur l'autoroute, mon algorithme pour HP-28S.

Il faut dans un premier temps créer la fonction NxtU qui permet de passer de u(n) à u(n+1).

Par exemple, en plaçant 607 au niveau 1: dela pile, la fonction NxtU renvoie 649.

Ensuite, LU(n) peut être calculé à partir du programme LUNE :

Code : Tout sélectionner

NxtU:                                          
« 1 OVER                                      @@  Fait une copie de n et prépare le produit de ses chiffres
  DO
     10 /				
     LAST MOD                                 @@  Extrait le dernier chiffre de n
     1 MAX                                    @@  Evite de prendre en compte les éventuels zéros
     ROT * SWAP IP                            @@  Effectue le produit des chiffres et arrondi n
  UNTIL DUP END                               @@  Boucle jusqu'à épuisement de n
  DROP + »                                    @@  Ajoute n et le produit de ses chiffres
					
	
LUNE:                                         
« 0 1 ROT                                     @@  0 est le compteur et 1 l'initial de la série issue de 1
  WHILE					
     WHILE DUP2 < REPEAT SWAP NxtU SWAP END   @@  Calcule les éventuels termes de la série issue de 1
     DUP2 >				
  REPEAT                                      @@  Si nécessaire le terme suivant de la série issue de n
     NxtU ROT 1 + ROT ROT                     @@   tout en incrémentant le compteur
  END					
  DROP2 »                                     @@  Efface les termes égaux en laissant le compteur LU(n)	

L'idée dans la LUNE est de calculer conjointement les suites issues de 1 et de n de telle sorte que l'on sache quel est le terme de la suite issue de 1 immédiatement au-dessus du terme actuel de la suite issue de n. La séquence ROT 1 + ROT ROT permet de compter le nombre de terme de la suite issuée de n.

P.S.: Bien évidemment, il y a moyen de faire plus court et d'optimiser. (Par exemple en inversant l'ordre des suites dans la pile). Je laisse aux lecteurs pratiquant le RPL le soin de découvrir l'astuce.

Par contre, le calcul n'est pas des plus rapide (il faut calculer conjointement deux suites. Peut-être une astuce permet d'accélérer les choses ??

[doum-doum]

Je dois être bouché, mais je ne vois pas la forme de ta suite, je n'arrive pas à savoir ce que tu veux calculer .

[badaze]

Je dois être bouché, mais je ne vois pas la forme de ta suite, je n'arrive pas à savoir ce que tu veux calculer .

+1

[C.Ret]

Je dois être bouché, mais je ne vois pas la forme de ta suite, je n'arrive pas à savoir ce que tu veux calculer .

Eh! Oui pardon , j'ai mal expliqué la suite.

La fonction NxtU calcule l'élement U(n+1) à partir de U(n).

Ainsi, par pressions sucessives sur la touche [NxtU] j'obtiens les termes de la suite.

Par exemple: 1 [NxtU] affiche 2 puis une pression sur [NxtU] affiche 4 et ainsi de suite ...


La fonction [LUNE] permet d'avoir directement LU(n).

par exemple 3 [LUNE] affiche 5 car 3 -> 6 -> 12 -> 14 -> 18 -> 26 qui est un des termes de la suite issue de 1.
Ce qui fait donc LU(3)=5 termes avant de rejoindre la suite issue de 1.

Désolé, la journée fut longue et les bouchons énervants !!

[babaorhum]

Désolé, la journée fut longue et les bouchons énervants !!

Belle proposition C.Ret sur 28s, j'aime bien ta LUNE ! ... de mon côté je suis parti dans les Listes (sur 28s aussi) pour aller un peu plus vite ... mais côté octets c'est pas économe (33 termes dans la suite U1 jusqu'à 1000) ... mais j'ai peut être moins de bouchons, c'est une excuse qui convient ? ...

[gege]

Bonjour,
Marrant, je ne vois pas pourquoi il n'y aurait pas de n pour lequel LU(n) est infini, en fait même il suffit de prendre un des U(n) et changer l'ordre de ses chiffres, non (exemple 38 -> 83) ?
Vite une machine !!!
G.E.

[zpalm]

Voici, après une mûre réflexion dans les bouchons sur l'autoroute, mon algorithme pour HP-28S.

Très bon début ! On ne dira jamais assez l'importance des bouchons dans l'évolution de la science moderne

Marrant, je ne vois pas pourquoi il n'y aurait pas de n pour lequel LU(n) est infini,

... et pourtant... la suite LU(n) est surprenante, il semblerait qu'elle soit liée aux fractales....

[C.Ret]

[ ...] de mon côté je suis parti dans les Listes (sur 28s aussi) pour aller un peu plus vite ...[...]

Je suis actuellemet moi aussi sur des listes pré-calculée en BASIC dans des tableaux de 1000 entiers.


En attendant que cela donne quelque chose de signifiatif, voici une seconde version de LUNE qui économise quelques octets en intervertisssant l'ordre des suites dans la pile. c'est strictement le même algorithme.

Code : Tout sélectionner

LUNE:                                         
« 0 SWAP 1                                    @@  0 est le compteur et 1 l'initial de la série issue de 1
  WHILE					
     WHILE DUP2 > REPEAT NxtU END             @@  Calcule les éventuels termes de la série issue de 1
     DUP2 <				
  REPEAT                                      @@  Si nécessaire le terme suivant de la série issue de n
     ROT 1 + ROT NxtU ROT                     @@   tout en incrémentant le compteur
  END					
  DROP2 »                                     @@  Efface les termes égaux en laissant le compteur LU(n)

Notons que cette façon de faire fonctionne car, quelque soit l'initiale n, les suites U(n) sont strictement croissantes.
Ce qui me laisse supposer qu'il doit y avoir un moyen de déterminer l'intiale n qui produit le plus grand LU(n) sans avoir à faire des milles et des cents de calculs ou manipuler des listes ou des tableaux kilométriques.

[dprtl]

Entre deux tentatives d'optimisation du "Compte est bon" (défi Gazette 4, affreusement difficile), j'ai testé ma première proposition naïve à ce MPO sur PB-1000 :

Code : Tout sélectionner

10 CLEAR:DIM A(1000):M=1000
20 U=1:FOR I=0 TO M-1:PRINT U;:A(I)=U:GOSUB 110:NEXT
30 X=0:FOR K=2 TO M:U=K
40 FOR I=0 TO M-1:L=0
50 IF A(L)<U THEN L=L+1:GOTO 50
60 IF A(L)>U THEN 90
70 IF X<I THEN X=I
80 PRINT "LU(";K;") =";I;" MAX =";X:GOTO 100
90 GOSUB 110:NEXT I
100 NEXT K:END
110 P=1:V$=STR$(U):FOR J=2 TO LEN(V$)
120 C=ASC(MID$(V$,J,1))-48:IF C>0 THEN P=P*C
130 NEXT J:U=U+P:RETURN

Pour fonctionner, ce programme aura besoin de l'extension mémoire RP-32, et de la partition mémoire suivante (par exemple) :

Code : Tout sélectionner

CLEAR 8000,0,25000

Un résultat sera affiché... au bout d'un certain temps... long long long :

Code : Tout sélectionner

[...]
LU( 62 ) = 0  MAX = 17
LU( 63 ) = 322  MAX = 322
LU( 64 ) = 3  MAX = 322
[...]
LU( 999 ) = 15  MAX = 322
LU( 1000 ) = 30  MAX = 322

... pour arriver jusqu'à 1000, prévoir des piles neuves.

Edit : un peu moins de 35h de calcul !

[zpalm]

Pas mal ! Pour aller plus vite essaye d'optimiser le sous-programme en 110.

Sur ma hp Prime j'ai le résultat en 1mn.

[C.Ret]

Dans le style qui met du temps à fournr un résultat j'ai aussi progressé.
Un peu moins que dans le style qui prend des kilo d'octets pour gagner un peut de temps.

Une fois les programmes NxtU et LUNE saisis, le programe SCRUN scrute les nombres jusqu'à 1000 pour trouver les plus grands LU().

Code : Tout sélectionner

CRUN:                             3:  2:  1:   @@ Commentaires:

« 3 5                                  r  lr    @@  Initialise record connu
  4 1000 FOR u                                  @@  Recherche les autres
     u LUNE                         r  lr  lu   @@  Calcule lu=LU(n)
     IF DUP2 <= THEN                            @@  Si lr<=lu alors échange r et lr avec n et lu 
         ROT DROP u                lr  lu   u   
         SWAP ROT                   u  lu  lr
     END                                        
     DROP                              r' lr'   @@  efface lu ou lr
  NEXT                                         
  R->C »                              		@@ Returne résultat sous forme (r,lr)                                        
 

Inconvénient, ce programme recalcule sans cesse la suite issue de 1. Avantage, il est suffisament court pour être présenté dans un MPO.

[zpalm]

Inconvénient, ce programme recalcle sans cesse la suite issue de 1. Avantage, il est suffisament court pour être présenté dans un MPO.

Il doit être possible de faire plus court que la suite LUNE et SCRUN et aussi plus rapide

[C.Ret]

Eh! Oui il doit y avoir un moyen d'aller vers la plus longue suite sans faire tous ces calculs...

Mais laissons le temps à chacun de trouver une voie...

En attendant, un petit graphe pour observer ce qui se passe :

Code : Tout sélectionner

0.:°1-2-4-8-16-22---26-----38-62-74-----102---104-108-116----122-----126-----------138--162-174-----202-206-218---234-----258---338-
..:         |  |    |      |  |  |     /   \   |     / | \    |     /   \           |    |   |      / \      |    / \      |    / \
1.:         13 20   18     32 52 54   66   101 59  68 84 113 120   77    118       132  152 154   166 200   176 178 186   242 266 317
..:         °  |   / \     |  °  |   / \    |  °   |  °   °  / \   |    / | \       |    |   |    / \   \    °  /   / \    |   °   °
2.:            15 9  14    24    36 39  60 100     53       93 115 70 76 109 114   124   88 136 139 160 191   171 156 172 179 
..:             ° ° / \    |     °  °   |   |      °        °   °  |  °  /   / \    |   / \  °   °  / \  °     °   |   °   °
3.:                7   12  17           44  91                     46   67 107 112 117 64  80      97 144         151
..:                °  / \  °           / \  °                      |   /   /   / \  °  °  / \      °  / \          °
4.:                  6   11           28  40                       34 61  83 106 111     48  55     128 140
..:                  |   |            |   °                        |  °   °  /    |      °  / \      |   |
5.:                  3   10           19                           31      103   110       43  50   119  95          
..:                  °   |            °                            °        °   / | \      °  / \    °   |
6.:                      5                                                     75 92 105     35  42      65
..:                      °                                                     |  |   °      |   |       | 
7.:                                                                            47 57         25  33      45
..:                                                                            |  °          °   |       |  
8.:                                                                            29                30      41
..:                                                                            |                 °       |
9.:                                                                            23                        27
..:                                                                            |                         °
10:                                                                            21
..:                                                                            °

[Gilles59]

HP50G + GoferList Mode exact

Code : Tout sélectionner

« DUP ->STR Chars « "0" ≠ » Filter STR-> Product + »  'Unext' STO    @ Calcul de Un+1

«
 0 0 -> m Lu
 « 
  {1}     @ La liste Un pour 1 est calculée au fur et à mesure des besoins
  2 1000 FOR n n 2. DISP
   0 SWAP n
   WHILE DUP2 POS NOT REPEAT 
    IF OVER Last OVER < THEN SWAP DUP Last Unext + SWAP ELSE Unext ROT 1 + UNROT END
   END
   DROP SWAP IF DUP m > THEN 'm' STO  n DUP 1. DISP 'Lu' STO ELSE DROP END
  NEXT
  m Lu
 »
»

[/size]

Même résultats que dprtl mais lent même avec l'émulateur ...

La liste pour la suite Un commençant par 1 est calculée 1 seule fois, sa "profondeur" augmente au fur et à mesure des besoins (mais la totalité de la liste est en mémoire à partir du calcul de la suite commençant par 63)..