MPO79 bis - Carrés à chiffres croissants

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
Avatar du membre
gege
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 7141
Enregistré le : 31 janv. 2008 14:24
Localisation : Banlieue Paârisienne
Contact :

MPO79 bis - Carrés à chiffres croissants

Message par gege »

Bonjour,
Dans la lignée des bidouilles de nombres entiers, voici une question qui s'énonce simplement mais que seules nos petites machines peuvent résoudre :
Trouver les nombres qui sont des carrés et dont les chiffres sont en ordre croissant.
Exemple : 23357889 = 4833²
A vos claviers !
G.E.
Modifié en dernier par gege le 22 oct. 2017 07:37, modifié 2 fois.
Avatar du membre
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2919
Enregistré le : 03 mai 2008 15:33
Localisation : Grenoble

Re: Misez p'tit, Optimisez - N°79 - carrés à chiffres croiss

Message par zpalm »

Rapidement sur HP Prime :

Code : Tout sélectionner

EXPORT MPO79(N)
BEGIN
 LOCAL r:={};
 FOR I FROM 1 TO N DO
  IF ΠLIST(ΔLIST(ASC(STRING(I^2)+"99"))≥0) THEN r(0):=I^2 END;
 END;
 RETURN r;
END;
MPO79(100000) retourne en 23s la liste des 49 nombres compris entre 1 et 100000² qui sont des carrés et dont les chiffres sont en ordre croissant, le dernier étant 4444488889=66667²

Bon maintenant il faut faire la même chose en RPN :)
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°79 - carrés à chiffres croiss

Message par C.Ret »

J'ai installé un bouton dans la barre menu de mon explorateur internet, comme cela je peut repasser les posts de zpalm au ralenti, image par image.

En réalité, j'ai commencé en BASIC sur Pocket.

Mais come le RPN est suggéré, je le présente en premier :

Code : Tout sélectionner

PC PRGRM                 t:    z:    y:    x:     Alpha:  00:    // Comments
                                          ┌─────────┐
001 LBL "MPO79"           .     .     .   │ max     │            // SAISIR n maximum et EXECUTER MPO79
                                          └─────────┘
001 LBL "MPO79"           .     .     .     max        .    .                                  
002 STO 00                .     .     .     .          .    n    // n maximum mémorisé dans registre 00:
003 LBL 01                .     .     .     .          .    n    // *** BOUCLE sur n ***       
004   RCl 00  X^2  STO Y  .     .     n²    n²         .    n    //    pour chaque n on calcule son carré n²
006   CLA ARCL X          .     .     n²    n²    " n² "    n    //    n² est prédisposé dans registre alpha:
009   LBL 02              .     .     a     i     " n² "    n    //   *** BOUCLE décomposition du carré n² ***
010     STO Z             .     i     a     i     " n² "    n    //      i=décomposition de n²;  a=unité précèdante
011     10                i     a     i     10    " n² "    n    //      i ← divisions successives de n² par 10
012     ST/ T             i/10  a     i     10    " n² "    n    //      précalcul i suivant en z:
013     MOD               .     i/10  a     r     " n² "    n    //      r unité actuelle ← i MOD 10
014     x>y?   GTO 03     .     i/10  a     r     " n² "    n    // r>a ?  chiffres non croissants; EXIT
016     RCL Z             .     .     r     i/10  " n² "    n    //
017     INT               .     .     r     i     " n² "    n    //      i valeur entière du quotien 
018   x>0?  GTO 02        .     .     a     i     " n² "    n    //   * boucle sur tous les chiffre du carré n² (i>0)
                                                ┌─────────┐
020   AVIEW               .     .     .     0   │ " n² "  │ n    //   AFFICHE/IMPRIME le carré à chiffres croisants n² 
                                                └─────────┘
021   LBL 03              .     .     .     0          .    n    // 
022  DSE 00  GTO 01       .     .     .     0          .    n-1  // * boucle jusqu'à revenir à n = 0
024  AOFF                 .     .     .     0          .    0    // restaure affichage normal
                                          ┌─────────┐
025 END                   .     .     .   │ 0       │  .    0    // fin du programme.
                                          └─────────┘
Soit en condensé:

Code : Tout sélectionner

01 LBL "MPO79"  STO 00                            // Mémorise n maximal dans 00: 
03  LBL 01  RCl 00  X^2  STO Y  CLA ARCL X        // Boucle sur n décroissant - prédispose n² dans registre Alpha:
09  LBL 02                                        // Décompose le carré n² à l'aide de  division successives par 10
      STO Z  10  ST/ T  MOD  x>y?  GTO 03            // Sort de la décomposition si chiffres croissants
      RCL Z  INT  x>0?  GTO 02                       // Boucle sur tous les chiffres de n²
      AVIEW                                          // Affiche carré n² aux chiffres décroissants
21  LBL 03  DSE 00  GTO 01                        // Décrémente n et boucle
24  AOFF                                          // Restaure affichage numérique.
25 END 

Et voici un listing des carrés à chiffres croissants trouvés en-dessous du million:
Image Image

L'impression se fait par l'instruction AVIEW. Avantage, la valeur reste affichée pendant la recherche de la suivante; D'où d'ailleurs le AOFF pour revenir à l'affichage normal de la pile en fin de programme.
Comme le montre le listing, la séquence 06 CLA ARCL X et remplacée par une séquence plus longue qui affiche les résultats sous la forme " 134689 = 367 ^ 2 "

Et le programme pour SHARp PC-1211 équivalent :

Code : Tout sélectionner

1 N=N+1,I=NN,R=I
2 A=R,R=I,I=INT .1I,R=R-10I:IF A<R GOTO 1
3 IF I GOTO 2
4 PRINT N*N,N : GOTO 1

Utilisation:
CLEAR [ENTER]  (pour la première utilisation, sinon continue avec les entiers suivant N) 
RUN [ENTER]
Evidemment, je n'aurais pas avec ces matériels les 50 premiers carrés aux chiffres croissants en 23 secondes !!!
Mais bon...ça marche encore.
Modifié en dernier par C.Ret le 09 mai 2017 19:12, modifié 3 fois.
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.
Avatar du membre
gege
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 7141
Enregistré le : 31 janv. 2008 14:24
Localisation : Banlieue Paârisienne
Contact :

Re: Carrés à chiffres croissants

Message par gege »

Bonjour,
Bravo !!! Vous êtes trop forts !
Du coup j'ai changé le titre, vu que la recherche de solutions est déjà terminée, inutile d'en faire un "défi".
Ce qui m'a intéressé est la forme particulière des quelques familles de nombres qui se dégagent, exemple 166...667² (avec autant de 6 que l'on veut).
Y a-t-il quelque chose derrière tout ça ? A voir.
Super les solutions.
A+
G.E.
Avatar du membre
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2919
Enregistré le : 03 mai 2008 15:33
Localisation : Grenoble

Re: Carrés à chiffres croissants

Message par zpalm »

gege a écrit :Ce qui m'a intéressé est la forme particulière des quelques familles de nombres qui se dégagent, exemple 166...667² (avec autant de 6 que l'on veut).
Y a-t-il quelque chose derrière tout ça ? A voir.
En regardant les résultats on voit que l'on peut grouper certains nombres en pyramides :

Code : Tout sélectionner

          4x4=16
        34x34=1156
      334x334=111556
    3334x3334=11115556
  33334x33334=1111155556
333334x333334=111111555556

          5x5=25
        35x35=1225
      335x335=112225
    3335x3335=11122225
  33335x33335=1111222225
333335x333335=111112222225

          7x7=49
        67x67=4489
      667x667=444889
    6667x6667=44448889
  66667x66667=4444488889
666667x666667=444444888889

        17x17=289
      167x167=27889
    1667x1667=2778889
  16667x16667=277788889
166667x166667=27777888889

        37x37=1369
      367x367=134689
    3667x3667=13446889
  36667x36667=1344468889
366667x366667=134444688889
Si l'on regarde la liste des 428 premiers nombres il est clair qu'il y a un motif qui se dégage, de là à trouver une formule pour déterminer tous les carrés à chiffres croissants....

Voir la suite OEIS A028820.
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: Carrés à chiffres croissants

Message par C.Ret »

Effectivement, trouver une formule pour tous ces nombres, n'est pas évident.
Par contre, ces "structures" pourraient éventuellement justifier un algorithme de recherche plus efficace (tout au moins pour les grands nombres) qu'elle simple recherche séquentielle ?
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.
Avatar du membre
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2919
Enregistré le : 03 mai 2008 15:33
Localisation : Grenoble

Re: Carrés à chiffres croissants

Message par zpalm »

Les racines des carrés à chiffres croissants constituent la suite OEIS A028819.

Cette suite a la propriété (non démontrée) suivante:

"It appears that from a(53) onwards all terms have nondecreasing digits and has one of the following forms: 16..67, 3..34, 3..35, 3..37, 3..367, 3..36..67, 36..67 and 6..67 and all number of such forms are terms. - Chai Wah Wu, Dec 07 2015".

Ce que l'on peut vérifier avec la liste des 422 premiers nombres.
Ben
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1549
Enregistré le : 21 août 2016 19:04

Re: Carrés à chiffres croissants

Message par Ben »

A défaut de pouvoir montrer le code basique qui n'apporterait rien de nouveau, voici le code en C

Une version pas trop élégante, mais qui colle plus avec la version BASIC d'un pocket.

Code : Tout sélectionner

#include <stdio.h>
#include <math.h>

int main(int argc, char *argv[], char *env[])
{
	double a=0,e=0,b=0,d=0,r;

l10:
	a++;
	e=pow(a,2);
	b=e;
	r=99;
l30:
	b=floor(b*.1);
	d=e-b*10;
	if (d>r) goto l10;
	r=d;
	e=b;
	if (b>0) goto l30;
	
	printf("%f ^2= %f\n",a,pow(a,2));
	goto l10;

	return 0;
}
Une version plus élégante, enfin, je trouve:

Code : Tout sélectionner

#include <stdio.h>
#include <math.h>
#include <stdbool.h>

int main(int argc, char *argv[], char *env[])
{
   double a=0,e=0,b=0,d=0,r;
   bool trouv;

   while (1)
   {
      a++;
      e=pow(a,2);
      b=e;
      r=99;
      trouv=true;
      while (b>0)
      {
         b=floor(b*.1);
         d=e-b*10;
         if (d>r)
         {
            b=0;
            trouv=false;
         }
         r=d;
         e=b;
      }
      if (trouv) printf("%f ^2= %f\n",a,pow(a,2));
   }
   return 0;
}
Ben
Ben
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1549
Enregistré le : 21 août 2016 19:04

Re: Carrés à chiffres croissants

Message par Ben »

Salut,

Une petite après-midi sur la terrasse, sous le parasol avec un PC-1211. Le code permet de dépasser le 99999^2

Bon, vu la vitesse de la bête, je ne l'ai pas fait calculer de 1 à 9999999999 ;-) J'ai juste fait quelques coups de sondes, tout à l'air de bien fonctionner.

Code : Tout sélectionner

5 CLEAR
10 A=A+1:GOSUB 100:I=C+1:F=99:B=A(I):D=0
20 E=INT(B*.1):E=B-E*10:B=INT(B/10):D=D+1
30 IF E>F THEN 80
40 IF B=0 THEN 60
50 F=E:GOTO 20
60 IF I=H-1 BEEP 1:PRINT A;"=";A(I):GOTO 80
70 I=I+1:B=A(I):IF D<5 LET F=0
75 GOTO 20
80 FOR i=10 TO H-1:A(I)=0:NEXT i:GOTO 10
100 B=A:C=10
110 A(C)=INT(B/1E5)
120 A(C)=B-A(C)*1E5
130 B=INT(B/1E5)
140 IF B<>0 LET C=C+1:GOTO 110
150 FOR D=10 TO C
155 H=C+D-9
160 FOR E=10 TO C
170 F=A(D)*A(E)+G:G=0
180 IF F>99999 LET G=INT(F/1E5):F=F-G*1E5:A(H)=A(H)+F:GOTO 195
190 A(H)=A(H)+F
195 H=H+1
200 NEXT F
210 IF G<>0 LET A(H)=A(H)+G:H=H+1
220 NEXT D
230 RETURN
Ben
Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1602
Enregistré le : 27 oct. 2010 20:46

Re: Carrés à chiffres croissants

Message par Gilles59 »

Une version NewRPL copiée sur l'algo de Zpalm :

Code : Tout sélectionner

<<
 1 SWAP FOR 'n'
  IF n SQ ->STR "9" + UTF8-> ΔLIST 0 ≥ THEN n SQ END
 NEXT
>>
100000 MPO79 renvoie les 49 solutions sur la pile en 66 secondes

A noter qu'un test sur une liste réagit différemment en NewRPL qu'en UserRPL. La vitesse du NewRPL est du même ordre de grandeur que la PRIME (~ 3 fois moins rapide) bien que probablement pénalisé par sa multiprécision (ici 32 chiffres significatifs) et le processeur de la 50g est sauf erreur ~4 fois mois rapide. C'est vraiment pas mal ;D J'ose même pas lancer cela en UserRPL lol
Modifié en dernier par Gilles59 le 22 oct. 2017 00:44, modifié 2 fois.
Casio FX-502P /602P / 603P / FX180P+ / FX4000P / TI57 / TI66 / TI74 Basicalc / TI95 Procalc / HP12C / HP15C LE / DM41L / HP 30B / HP39GII / HP 48SX USA / 49G / 49g+ / 50G / 50G NewRPL / HP Prime / Oric 1 / Amstrad CPC 6128+ CM14 et MM12 / Alice 32
Avatar du membre
ledudu
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5631
Enregistré le : 26 mars 2009 13:07
Localisation : Ile de France
Contact :

Re: Carrés à chiffres croissants

Message par ledudu »

Salut
Ce fil ayant échappé à la numérotation des MPO avait été proposé par zPalm dans le deuxième message comme MPO79 mais celui-ci est à présent attribué.
Je propose donc MPO79 Bis pour le retrouver dans le sommaire des MPO.

Gégé (ou un admin), tu peux changer le premier titre ?
Misez p'tit, Optimisez - N°79 BIS - carrés à chiffres croissant

Merci,
Avatar du membre
gege
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 7141
Enregistré le : 31 janv. 2008 14:24
Localisation : Banlieue Paârisienne
Contact :

Re: MPO79 bis - Carrés à chiffres croissants

Message par gege »

Bonjour,
Voilà qui est fait.
Le fil avait commencé comme MPO79 mais vu la simplicité de lalgorithme, je l'avais débaptisé.
Le voilà promu à nouveau.
G.E.
Modifié en dernier par gege le 22 oct. 2017 13:43, modifié 1 fois.
Avatar du membre
Hobiecat
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3626
Enregistré le : 06 sept. 2011 14:57
Localisation : Normandie

Re: MPO79 bis - Carrés à chiffres croissants

Message par Hobiecat »

Même sur la base d'algorithmes simples, on peut faire des MPO à mon avis : n'oublions pas que les MPOs originels de l'Op étaient plus basés sur l'optimisation que sur la complexité. ;)
Avatar du membre
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2919
Enregistré le : 03 mai 2008 15:33
Localisation : Grenoble

Re: Carrés à chiffres croissants

Message par zpalm »

Gilles59 a écrit : 22 oct. 2017 00:17 Une version NewRPL copiée sur l'algo de Zpalm :
[...]
A noter qu'un test sur une liste réagit différemment en NewRPL qu'en UserRPL.
Jolie la version NewRPL, pour le test sur les listes c'est documenté quelque part ?
Gilles59
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1602
Enregistré le : 27 oct. 2010 20:46

Re: Carrés à chiffres croissants

Message par Gilles59 »

zpalm a écrit : 22 oct. 2017 09:55
Gilles59 a écrit : 22 oct. 2017 00:17 Une version NewRPL copiée sur l'algo de Zpalm :
[...]
A noter qu'un test sur une liste réagit différemment en NewRPL qu'en UserRPL.
Jolie la version NewRPL, pour le test sur les listes c'est documenté quelque part ?
Je vais demander sur le forum HPCALC. Je me demande si c'est voulu ou si c'est une anomalie lol. UserRPL fonctionne comme la Prime et donc imposerait le PILIST ou un truc équivalent
Casio FX-502P /602P / 603P / FX180P+ / FX4000P / TI57 / TI66 / TI74 Basicalc / TI95 Procalc / HP12C / HP15C LE / DM41L / HP 30B / HP39GII / HP 48SX USA / 49G / 49g+ / 50G / 50G NewRPL / HP Prime / Oric 1 / Amstrad CPC 6128+ CM14 et MM12 / Alice 32
Répondre

Retourner vers « Tous les Pockets »