Misez p'tit Optimisez n°87 : solution entière à une équation diophantienne

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

Avatar du membre
dprtl
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 463
Enregistré le : 27 janv. 2013 00:26
Localisation : Strasbourg
Contact :

Misez p'tit Optimisez n°87 : solution entière à une équation diophantienne

Message par dprtl »

Voici un petit problème difficile à résoudre à la main, difficile également pour les moteurs de calcul formel les plus puissants. Mais on devrait pouvoir en venir à bout rapidement par calcul numérique, même avec une machine de la génération des Casio FX-602P ou HP-15C.

Il s'agit de trouver au moins une solution entière à l'équation diophantienne suivante :

Code : Tout sélectionner

60912 + y^2 = 2^x
La même équation sous une forme plus jolie :

Image

Comme c'est un MPO, l'idée est de fournir le programme le plus court possible, en utilisant les meilleures fonctionnalités de votre calculette (les nombres complexes par exemple). Le temps de calcul ne devrait pas être un problème ici.

Sommaire des MPO.
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°87 : solution entière à une équation diophantienne

Message par C.Ret »

OH! Le bel MPO !

Avec la pluie et les vents qui battent mes fenêtres, je sais ce que je vais faire cet après-midi :)


Ce qui est bien c'est que j'ai déjà un peu d'avance, j'ai trouvé la boite qui correspond :

Image
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 : 2918
Enregistré le : 03 mai 2008 15:33
Localisation : Grenoble

Re: Misez p'tit Optimisez n°87 : solution entière à une équation diophantienne

Message par zpalm »

Image

2^x doit être supérieur à 60912, donc x est supérieur ou égal à 16.

Pour x=16 on a 65236-60912 = 4624 = 68^2
(EDIT: il faut lire 65536 et non 65236 pour 2^16)

Pas besoin de programme pour trouver x=16 et y=68 :wink:
Modifié en dernier par zpalm le 09 déc. 2018 12:03, modifié 1 fois.
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°87 : solution entière à une équation diophantienne

Message par C.Ret »

Euh! Avec mes lego, je n'arrive pas à remonter l'équation avec les coordonnées ( 16 , 68 ) Il me manque 720 pièces !

Il me semble que cela vient de l'assemblage sur l'axe de puissance secondaire. Avec 16 chevaux, je monte au couple prodigieux de 65536 hp

Je ne sais pas quel engin utilise zpalm, se doit être l'humidité, son moteur n'indique que 65236 sur ce même axe secondaire avec portant autant de cheveaux.

J'espère que pour vous l'apéro est aussi bon que celui que consomme zpalm.
D'ailleurs je vais faire comme lui et me resservir un verre.
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 : 2918
Enregistré le : 03 mai 2008 15:33
Localisation : Grenoble

Re: Misez p'tit Optimisez n°87 : solution entière à une équation diophantienne

Message par zpalm »

Effectivement, il y eu une erreur de typo dans mon message, un 5 a été malencontreusement remplacé par un 2, mais le résultat est le même...

60912+68^2 = 65536 = 2^16
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: Misez p'tit Optimisez n°87 : solution entière à une équation diophantienne

Message par ledudu »

Oui, (16,68) est la première solution à sortir.
Un petit programme rapide montre qu'on dépasse allègrement la précision de nos machines si on reste sur un calcul de y=f(x).
Est-ce l'objectif de ce MPO, de trouver la suivante ?
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°87 : solution entière à une équation diophantienne

Message par C.Ret »

Bon sang ! la bouteille est vide et je viens de me rendre compte de mon erreur !

Voilà maintenant que mon programme s'arrête, et je m'aperçois qu'il cherchait les solutions pour 60912+x^2 = 2^x !

Je passe à table et m'y remets sérieusement après une bonne sieste !
mpo 87 sieste.png
mpo 87 sieste.png (153.59 Kio) Vu 11383 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
dprtl
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 463
Enregistré le : 27 janv. 2013 00:26
Localisation : Strasbourg
Contact :

Re: Misez p'tit Optimisez n°87 : solution entière à une équation diophantienne

Message par dprtl »

ledudu a écrit : 09 déc. 2018 12:01 Oui, (16,68) est la première solution à sortir.
Un petit programme rapide montre qu'on dépasse allègrement la précision de nos machines si on reste sur un calcul de y=f(x).
Est-ce l'objectif de ce MPO, de trouver la suivante ?
L'objectif du MPO était de trouver une solution par programmation, et non par raisonnement mathématique ! Nos calculatrices sont en effet bien incapables de sortir une phrase du style "2^x doit être supérieur à 60912, donc x est supérieur ou égal à 16.".

Sinon, il existe une deuxième solution dans l'ensemble Z, triviale.
Avatar du membre
phm
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1361
Enregistré le : 08 avr. 2016 18:36
Localisation : Est Parisien

Re: Misez p'tit Optimisez n°87 : solution entière à une équation diophantienne

Message par phm »

dprtl a écrit : 09 déc. 2018 13:32
ledudu a écrit : 09 déc. 2018 12:01 Oui, (16,68) est la première solution à sortir.
Un petit programme rapide montre qu'on dépasse allègrement la précision de nos machines si on reste sur un calcul de y=f(x).
Est-ce l'objectif de ce MPO, de trouver la suivante ?
L'objectif du MPO était de trouver une solution par programmation, et non par raisonnement mathématique ! Nos calculatrices sont en effet bien incapables de sortir une phrase du style "2^x doit être supérieur à 60912, donc x est supérieur ou égal à 16.".

Sinon, il existe une deuxième solution dans l'ensemble Z, triviale.
Si on ne raisonne pas mathématiquement, cela doit inclure un test pour les racines négative je pense
HEWLETT-PACKARD : The best
CANON
X-07 X-730 X-711 XR-100 XM-101 XP-110F XP-120F XP-130F XP-140

AMSTRAD CPC-464 CPC-6128 ATARI STF DAI Indata
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°87 : solution entière à une équation diophantienne

Message par C.Ret »

Effectivement, une analyse du terme de droite de l'équation montre que les solutions pour y sont aussi valable pour -y.


Ce que confirme ce petit code pour SHARP PC-1211 à optimiser bien sûr :

Code : Tout sélectionner

1 L=LN 2,E=€5:FOR X=1TO 33:R=EXP XL-60912:IF R>0 LET Y=INT √ERE/E,Z=-Y:IF Y=INT YPRINT X;Z;" OR ";X;Y
2 NEXT X:END
78 bytes( Il reste 1346 STEPS et 168MEMORIES au-delà des 24 registres alphabétiques dont seuls 7 sont utilisés)
Les seules solutions entières découvertes par mon pauvre SHARP sont les couples (16,-68) et (16,68) .
Modifié en dernier par C.Ret le 09 déc. 2018 16:37, modifié 2 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
dprtl
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 463
Enregistré le : 27 janv. 2013 00:26
Localisation : Strasbourg
Contact :

Re: Misez p'tit Optimisez n°87 : solution entière à une équation diophantienne

Message par dprtl »

C.Ret a écrit : 09 déc. 2018 14:06 [...]

Code : Tout sélectionner

78 bytes( Il reste 1346 STEPS et 168MEMORIES au-delà des 24 registres alphabétiques dont seuls 7 sont utilisés)
Les seules solutions découvertes par mon pauvre SHARP sont les couples (16,-68) et (16,68) .
Ce n'est pas évident d'écrire un énoncé de MPO original qui ne soit pas résolu en moins d'une heure par Zpalm et C.Ret. J'essaierai de faire mieux la prochaine fois :D
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°87 : solution entière à une équation diophantienne

Message par C.Ret »

C'est que ma petite sieste m'a fait le plus grand bien :)

Ce n'est qu'un premier jet. Les versions HP-15C, Fx-602p ou TI-57 LCD restent encore à élaborer.


Voici un code plus abouti qui permet de résoudre tout type d'équation diophantienne en X,Y :

Le code est en quatre parties :

-ligne 1 et 2 - PARAMETRES
On y code l'équation sous la forme 1:E= «expression en X» - «membre en Y» [ENTER]
En ligne 2:, on peut modifier la précision de résultats, plus P est grand, plus la précision est grande et les temps de recherche longs.

-Ligne 6 à 9 - sous programmes pour recherche par dichotomie

-Ligne 10 à 12 - Recherche de Y pour X donné par l'utilisateur
L'appel se fait par DEF+X après avoir saisi la valeur donnée pour X

-Ligne 20 à 22 - Recherche de X pour Y donné par l'utilisateur
L'appel se fait par DEF+C (la touche Y ne peut pas servir en mode DEF) après avoir saisi la valeur donnée pour Y.
Cette dernière partie est identique à la précèdente.

Il y a donc de quoi optimiser ici aussi (j'ai une petite idée, X et Y sont respactivement A(24) et A(25) - héhéhé

Code : Tout sélectionner

1:E=60912+YY-2^X                   
2:P=€4               
3:E=INT ABS PE/P*SGN E:RETURN

Code : Tout sélectionner

6:A=Y,C=X,F=E:RETURN              
7:BEEP 1:PRINT X,Y:RETURN      
8:B=Y,D=X,G=E:RETURN

Code : Tout sélectionner

10 "X" AREAD X : Y=0    :GOSUB 1:A=Y,F=E,Y= €6 : GOSUB 1:B=Y,G=E
11 IF SGN FG>0 BEEP 3:PRINT "NO SOL. AT X=";X:END
12 Y=(A+B)/2: IF PB-PA>1 GOSUB 1:GOSUB 7+SGN E:GOTO 11
13 BEEP 2:PRINT "APPROX.",Y:END

Code : Tout sélectionner

20 "C" AREAD Y: X= 1 :GOSUB 1:C=X,F=E,X=31:GOSUB 1:D=X,G=E
21 IF SGN FG>0 BEEP 3:PRINT "NO SOL. AT Y=";Y:END
22  X=(C+D)/2:IF PD-PC>1GOSUB 1:GOSUB 7-SGN E:GOTO 21
23 BEEP 2:PRINT "APPROX.",X:END
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
dprtl
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 463
Enregistré le : 27 janv. 2013 00:26
Localisation : Strasbourg
Contact :

Re: Misez p'tit Optimisez n°87 : solution entière à une équation diophantienne

Message par dprtl »

Avec un peu de recul, je reconnais que le sujet de ce MPO 87 était un peu facile, et donc, pas très passionnant. Mais comme ma calculette de la semaine est la FX-602P je vous propose ici mon programme. Elle sera le sujet de mon prochain article de blog perso ; dont l'audience est limitée, et ça se comprend :)

L'algorithme (naïf) est le suivant :
- calcul de l'expression1 (à droite de l'équation), on stocke le résultat dans la mémoire F (utilisée pour les branchements conditionnels sur FX-602P)
- calcul de l'expression2 (à gauche)
- si expression1 = expression2 alors on affiche Y (MR01) puis X (MR00). C'est terminé.
- si expression2 > expression1 alors on incrémente X
- sinon on incrémente Y
- on recommence au début

Voici le code pour FX-602P :

Code : Tout sélectionner

LBL0 2 x^y MR00 = MinF 60912 + MR01 x^2 = x=F GOTO2 x>=F GOTO1 1 M+01 GOTO0 
LBL1 1 M+00 GOTO0
LBL2 MR01 HLT MR00
Cela nous fait 30 pas. Difficile de faire mieux non ? Un MPO peut aussi se concevoir comme un programme simple à travers lequel on optimise le temps du programmeur mauvais en math...

Utilisation :
1) choisir la valeur de départ du calcul pour X puis taper Min00, et pour Y, taper Min01
2) lancer le programme
3) affichage de Y
4) [EXE] pour afficher X
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°87 : solution entière à une équation diophantienne

Message par Marge »

Bonsoir,
Ne t'en fais pas : j'ai proposé de bons sujets de MPO et de très nuls, si nuls qu'ils ne valent aucune mention ici ; personne ne m'en a porté grief.

Tu dis :
"Cela nous fait 30 pas. Difficile de faire mieux non ? Un MPO peut aussi se concevoir comme un programme simple à travers lequel on optimise le temps du programmeur mauvais en math..."

Je dis que si on évaluait la qualité des programmeurs à leur seules rapidité et "masthlicité", bah... le monde serait encore plus pauvre qu'il n'est.
Je comprends néanmoins ta réserve.

L'important selon moi : la création.
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
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°87 : solution entière à une équation diophantienne

Message par C.Ret »

dprtl a écrit : 14 déc. 2018 22:59 […] Difficile de faire mieux non ?
Oui, difficile, mais pas impossible :

Utilisation :
1) saisir la valeur maximale pour X { typiquement inférieur à 47 }
2) lancer le programme par la touche PO { ce qui va tester les valeurs de X dans l'ordre décroissant }
3) affichage de X : Y { le programme s'arrête s'il trouve une solution entière, l'avantage d'une fx-602p est de pouvoir combiner l'affichage grâce au registre ALPHA }
4) [EXE] pour continuer à rechercher d'éventuel autre couple d'entiers (x,y) solution
5) Arrêt sur une erreur { P0 Error 013 } lors du calcul de la racine pour x<16 et donc arrêt de la recherche

Registres :
Mn0 valeur x
Mn1 valeur y

Programs/Sous-program:
P0 Mémorise une estimation de Y, si valeur entière affiche X : Y à l'aide de P1 puis décrémente X et boucle
P1 Affiche le couple X :Y en mode Alpha à partir des registres Mn0 et Mn1, puis attend action de l'utilisateur pour continuer

Code:

Code : Tout sélectionner

PO  Min00 LBL0  2 x^y MR00 - 60912 =  inv √ Min01 inv FRAC inv x=0? GSBP5 inv DSZ Goto0
P5  inv "AL inv AR00 inv : inv AR01 inv "AL HLT


Si j'estime bien cela doit faire aussi environ 27 steps. Merci de le confirmer.


Et je suis du même avis que Marge, il n'y a pas de M.P.O. facile ou difficile, ni de code mieux qu'un autre. Ce qui compte réellement est que l'on puisse échanger nos idées, participer chacun à sa façon et à son rythme en s'inspirant des idées ou suggestions des uns et des autres.
Modifié en dernier par C.Ret le 15 déc. 2018 15:17, modifié 4 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.
Répondre

Retourner vers « Tous les Pockets »