MPO79 bis - Carrés à chiffres croissants
Modérateur : Politburo
- gege
- Fonctionne à 14400 bauds
- Messages : 7141
- Enregistré le : 31 janv. 2008 14:24
- Localisation : Banlieue Paârisienne
- Contact :
MPO79 bis - Carrés à chiffres croissants
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.
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.
- zpalm
- 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
Rapidement sur HP Prime :
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
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;
Bon maintenant il faut faire la même chose en RPN
- C.Ret
- 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
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 :
Soit en condensé:
Et voici un listing des carrés à chiffres croissants trouvés en-dessous du million:
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 :
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.
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.
└─────────┘
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:
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]
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.
- gege
- Fonctionne à 14400 bauds
- Messages : 7141
- Enregistré le : 31 janv. 2008 14:24
- Localisation : Banlieue Paârisienne
- Contact :
Re: Carrés à chiffres croissants
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.
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.
- zpalm
- Fonctionne à 9600 bauds
- Messages : 2919
- Enregistré le : 03 mai 2008 15:33
- Localisation : Grenoble
Re: Carrés à chiffres croissants
En regardant les résultats on voit que l'on peut grouper certains nombres en pyramides :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.
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
Voir la suite OEIS A028820.
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3404
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: Carrés à chiffres croissants
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 ?
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.
- zpalm
- Fonctionne à 9600 bauds
- Messages : 2919
- Enregistré le : 03 mai 2008 15:33
- Localisation : Grenoble
Re: Carrés à chiffres croissants
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.
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.
Re: Carrés à chiffres croissants
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.
Une version plus élégante, enfin, je trouve:
Ben
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;
}
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;
}
Re: Carrés à chiffres croissants
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.
Ben
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
Re: Carrés à chiffres croissants
Une version NewRPL copiée sur l'algo de Zpalm :
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
Code : Tout sélectionner
<<
1 SWAP FOR 'n'
IF n SQ ->STR "9" + UTF8-> ΔLIST 0 ≥ THEN n SQ END
NEXT
>>
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
- ledudu
- Fonctionne à 14400 bauds
- Messages : 5631
- Enregistré le : 26 mars 2009 13:07
- Localisation : Ile de France
- Contact :
Re: Carrés à chiffres croissants
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,
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,
- gege
- Fonctionne à 14400 bauds
- Messages : 7141
- Enregistré le : 31 janv. 2008 14:24
- Localisation : Banlieue Paârisienne
- Contact :
Re: MPO79 bis - Carrés à chiffres croissants
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.
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.
- Hobiecat
- Fonctionne à 9600 bauds
- Messages : 3626
- Enregistré le : 06 sept. 2011 14:57
- Localisation : Normandie
Re: MPO79 bis - Carrés à chiffres croissants
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é.
- zpalm
- Fonctionne à 9600 bauds
- Messages : 2919
- Enregistré le : 03 mai 2008 15:33
- Localisation : Grenoble
Re: Carrés à chiffres croissants
Jolie la version NewRPL, pour le test sur les listes c'est documenté quelque part ?
Re: Carrés à chiffres croissants
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