Défi Turing : du MPO à la pelle

[caloubugs]

Je suis inscrit dans une sympathique compétition de petits programmes à monter pour répondre à des énigmes mathématiques.
Défi Turing http://www.apprendre-en-ligne.net/turing/index.php.
Certains sont inaccessibles à nos vieilles compagnes (des milliards de calculs parfois) mais il y a matière à s'amuser un peu pour nos longues soirées d'hiver...
Par exemple le n°77 qui parait impossible mais avec une petite astuce ma HP71B la résout en 34 secondes...

Problème 77
Somme de deux carrés
Deux nombres de 4 chiffres ont la propriété suivante : abcd = ab^2 + cd^2.

1233 = 12^2 + 33^2
8833 = 88^2 + 33^2

Quel est le plus grand nombre de 8 chiffres de ce type : abcdefgh = abcd^2 + efgh^2 ?

Avis aux amateurs ! Il y a un problème nouveau chaque semaine et 100 actuellement en stock...

[Gilles59]

J
Quel est le plus grand nombre de 8 chiffres de ce type : abcdefgh = abcd^2 + efgh^2 ?[/i].

oublions déjà la méthode brutale,même sur une calculatrice rapide genre HP PRIME

Code : Tout sélectionner

EXPORT MPO()
BEGIN
 X:=1e8;
 REPEAT
  X:=X-1;Z:=X/1e4;
 UNTIL X==IP(Z)²+(FP(Z)*1E4)²;
 RETURN X;
END;

Bon j'attends encore (en espérant qu'il n'y a pas d'erreur, je n'ai rien testé avant ;D)

EDIT : OK je l'ai, pas d'erreur dans le programme mais beaucoup plus lent que la HP71

[bernouilli92]

@Gilles59 : ton programme utilise la méthode brute, il revient à tester toutes les combinaisons.
C'est équivalent à avoir deux boucles imbriquées, chacune de 1 à 9999.

J'ai une autre piste, elle donne une solution, il se trouve que c'est le plus grand nombre mais la méthode ne garantie pas que le nombre trouvé soit le plus grand.
Par contre elle est beaucoup plus lente que celle de la hp71b : 114s au lieu de 34s.
C'est l'algo ou est ce que la hp71b est beaucoup plus rapide que la hp48sx?

Code : Tout sélectionner

<< 2 -> I <<
    WHILE
      I I SQ - 25e6 + SQRT DUP FP
    REPEAT
       DROP
      'I' 1 STO+
    END
    5000 - 10000 * I +
  >>
>>

Il faut remplacer SQRT par le symbole racine carrée.


ÉDIT : j'ai testé le même programme sur hp71b et il trouve la solution en 3min26. C'est bien l'algo qu'il faut améliorer.

[C.Ret]

Tout cela est bien long, je trouve les deux solutions 1233 et 8833 en 5s avec mon HP28S, qui pourtant n'est pas un foudre de guerre.

L'algorithme suivit est le suivant,

Pour déterminer les entier abcd, je cherche à calculer la partie cd pour ab donné.

L'égalité abcd = ab² + cd² est transcrite à l'aide de deux variables, la donnée ab et le résultat cherché cd :

On doit donc trouver cd tel que 100*ab + cd = ab*ab + cd*cd
On résoud ainsi une équation du second degré en cd et les solution possible sont de la forme : 2*cd = (1 ± √(1+4*(100-ab)*ab)

Evidemment, en parcourant le domaine des valeur de ab, on ne retiendra que les solution entières, c'est à dire celle dont le terme sous le radical de la racine sont des carrés parfaits.
Par ailleurs, cd étant positif, seule la solution 2*cd = (1 + √(1+4*(1000-ab)*ab) est à retenir.

J'obtient donc le code suivant:

Code : Tout sélectionner

« 10 99 FOR ab                 
     1 100 ab - ab * 4 * + √
     IF DUP FP NOT THEN
      1 + 2 / ab 100 * +
     ELSE DROP END
  NEXT »

Il ne me reste plus qu'à étendre le principe pour des nombres à 6, 8, 10 ou 12 chiffres :

Code : Tout sélectionner

« {}                             @  Initialise la liste des nombres
  1 6 FOR p                      @  Recherche les nombre de 2, 4, ... et 12 chiffres
   p ALOG → b                    @  Ce qui revient à travailler en base 10, 100, 1000 .... 10000
   « p 1 - ALOG 1 + b 1 - FOR m  @  Pour m variant de 1…1 à 9…9
        m 4 DISP                 @  Affiche afin de faire patienter
        1 b m - m * 4 * + √      @  Evalue la solution
        IF DUP FP NOT THEN       @  Vérifie que le carré est parfait
            1 + 2 / m b * + +    @  Ajoute le nombre ab…fg à la liste des nombres
            DUP 1 DISP           @  Affiche afin de faire patienter
        ELSE DROP END            
     NEXT »
  NEXT »

Je trouve { 1233 8833 990100 ... } en environ 1 min (en évitant les affiches de m)

Evidemment cela va de moins en moins vite.
Reste à trouver un moyen de ne pas tester toutes les valeurs m, mais uniquement celles qui sont proches (de part et d'autre) d'un carré parfait.

[bernouilli92]

Tout cela est bien long, je trouve les deux solutions 1233 et 8833 en 5s avec mon HP28S, qui pourtant n'est pas un foudre de guerre.

Les durées données précédemment sont pour la solution à 8 chiffres.

[Gilles59]

@Gilles59 : ton programme utilise la méthode brute, il revient à tester toutes les combinaisons..

Hello Bernouilli, C'est bien ce que je voulais dire avec ma formulation ambigue :
Que ma méthode brute est à oublier sur nos machines même avec une HP PRIME (quoique ca marche en quelques dizaines de minutes)

[C.Ret]

Les durées données précédemment sont pour la solution à 8 chiffres.

A zut, il me faut presque 18 min pour tester tous les nombres de 2 à 8 chiffres ! (J'en trouve 5 d'ailleurs)

Que ma méthode brute est à oublier sur nos machines même avec une HP PRIME (quoique ca marche en quelques dizaines de minutes)

A zut, si en plus il faut faire en moins de 10 min, je ne suis plus dans le coup.

Mais, sur nos calculettes, 10 min c'est rapide ! Ce qui prouve bien que c'est parfaitement réalisable sur une HP prime !
J'ose pas sortir mon SHARP PC-1211 !

[bernouilli92]

Mais, sur nos calculettes, 10 min c'est rapide ! Ce qui prouve bien que c'est parfaitement réalisable sur une HP prime !
J'ose pas sortir mon SHARP PC-1211 !

Si cela met 10 min sur une Prime, ce qui reste acceptable, je me demande combien cela prendrait sur une hp 41, sûrement plus d'une journée.

ÉDIT : cela devrait prendre de l'ordre de 14h sur une hp48sx.

[Gilles59]

C'est bien plus de 10mn sur Prime en recherche exhaustive (et encore on a la chance que ... )

Si on commence à calculer par les chiffres de droite comme on le ferait à la main, les contraintes fortes apparaissent ...

Par exemple: abcd = ab^2 + cd^2.

si d=0 alors forcément b=0 alors c<>0 alors cd² finit par 00 => impossible (10% de recherche en moins)

si d=1 alors forcément b=0 alors etc ....

si d=2 alors b=? impossible puisque b²+4 doit finir par 2 (çà divise le temps de recherche par 2)
etc etc

je me demande même si quelque chose de tres proche (voir la même chose) n'est pas dans ce forum déjà.

[gege]

Bonjour,
Intéressant, les problèmes vont de 'semble simple' à 'oulà dur dur'...
De longues soirées d' "amusement" en vue, merci.
G.E.

[caloubugs]

Hello à tous,

La solution évidente est trop longue pour nos grands-mères, en Python je l'avais joué bourrin.
Par contre un participant a fait un algo qui rend ce pb accessible (15 s sur z1gr).
J'en suis à 60 problèmes de résolus (donc pas si mal classé que ça... C'est pour titiller certains ici )

Je vais suivre le classement avec intérêt

Et pour les sujets oulala, y'a le 75 :
Un dialogue de fous. Quoique...

X et Y sont deux nombres entiers différents, supérieurs à 1, avec X+Y < 100.
Simon et Paul sont deux mathématiciens. Simon connaît la somme S=X+Y. Paul connaît le produit P=X*Y. Simon sait que Paul connaît le produit et Paul sait que Simon connaît la somme.
Une conversation s'engage entre les deux mathématiciens :

Paul dit: "Je ne peux pas trouver ces nombres."
Simon dit: "J'étais sûr que vous ne pouviez pas les trouver. Je ne peux pas les trouver non plus."
Paul dit: "Alors, j'ai trouvé ces nombres."
Simon dit: "Si vous avez pu les trouver, alors je les ai aussi trouvés."

Quels sont ces nombres ? Donner comme réponse le produit X*Y*S*P

[bellamy]

Je me suis inscrit à ce site merci pour le tuyau !

Précision : le challenge c'est de trouver la réponse en moins d'une minute

[bernouilli92]

Je me suis inscrit à ce site merci pour le tuyau !

Précision : le challenge c'est de trouver la réponse en moins d'une minute

Oui, sur un PC.

[Gilles59]

12 résolus en RPL (pseudo nemo59)... j'ai mis les sources dans les solutions...

Sur une calculatrice la limite de la minute n'a pas grand sens comparé à des quadri-coeurs 4Ghz et autres bêtes de course ;D L'idée de la limite de temps est plutôt pour inciter à trouver des algo malins (ce que je n'ai pas beaucoup fait encore) ... d'ailleurs cette limite de temps a aboutit à des effets pervers sur Euler Project (çà ressemble beaucoup dans l'esprit, j'en ai résolu une centaine largement en RPL) : même en optimisant çà ne tient plus du tout sur calculatrice ou même sur l'émulateur....

[caloubugs]

12 résolus en RPL (pseudo nemo59)... j'ai mis les sources dans les solutions...

Sur une calculatrice la limite de la minute n'a pas grand sens comparé à des quadri-coeurs 4Ghz et autres bêtes de course ;D L'idée de la limite de temps est plutôt pour inciter à trouver des algo malins (ce que je n'ai pas beaucoup fait encore) ... d'ailleurs cette limite de temps a aboutit à des effets pervers sur Euler Project (çà ressemble beaucoup dans l'esprit, j'en ai résolu une centaine largement en RPL) : même en optimisant çà ne tient plus du tout sur calculatrice ou même sur l'émulateur....

Cool ! J'ai vu ton pseudo vite grimper
Et tu auras vu l'optimisation de jodyl sur le défi 77... Fallait quand même le trouver !

Par contre y parvenir en moins d'une minute, c'est pas toujours facile sur nos vieux tromblons. Sans compter quelques programmes qui nécessitent du récursif...

On va pouvoir partager nos expériences !

Je ne connaissais pas Euler Project excepté les références mises sur le défi Turing (qui pompe du coup largement sur eux). Avec ces 2 là, on en a jusqu'à Noël 2020...