Discussion :

[Nemerle]

B'jour,

tout est presque dans le titre: en se fixant un nombre de décimales n, il n'existe qu'un couple de solution de x^2+y^2=1 (à échange près).

Par exemple,
pour n=1, 0.6 et 0.8 sont les seules solutions de x^2+y^2=1
pour n=2, 0.28 et 0.96 sont les seules solutions de x^2+y^2=1
...

Quelqu'un connait un méthode pour le démontrer, ou un algo pour trouver la solution à l'ordre n ??

[pseudocode]

Quelqu'un connait un méthode pour le démontrer, ou un algo pour trouver la solution à l'ordre n ??

La brute force.


changement de variable:
a=X/10^n avec X entier
b=Y/10^n avec Y entier

a^2+b^2=1
(X/10^n)^2+(Y/10^n)^2=1
Y=Racine( 10^2n - X^2 )

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
FOR X=1 TO 10^2n
  Y = racine( 10^2n - X^2 )
  IF  isInteger( Y ) THEN
    RETURN (X,Y)
  END IF
NEXT

[Nemerle]

Ca c'est déjà fait... faudrait un truc un peu moins "force brute"

[Zavonen]

Peut être appeler Google avec "Triplet pythagoricien" ?
On cherche donc les triplets pythagoriciens
de la forme:
x,y,10^n
On peut en fait se limiter aux seuls triplets 'primitifs' (premiers entre eux)
Un thèorème nous dit qu'il n'existe pas de t.p.p. (x,y,z) avec z pair
Il faut donc chercher des triplets primitifs
x',y',5^n et multiplier tout par une puissance de 2 convenable
le problème est résolu pour n=1 et 2 l'auteur le rappelle d'ailleurs,
On obtiendra des triplets solutions pour les n supérieurs en multipliant par une puissance de 5 convenable, mais les triplets obtenus ne seront évidemment pas primitifs, on en est là pour l'instant.
Il existe beaucoup de résultats sur les triplets primitifs, en particulier:
Soit x soit y est un multiple de 3.
Soit x soit y est un multiple de 4.
Soit x soit y, soit x+y , soit x-y est un multiple de 7.
Cela doit permettre d'améliorer un peu la méthode proposée par Pseudocode, le test du carré parfait étant un peu coûteux.

[Zavonen]

Ce programme donne en moins de 3 secondes les
triplets pythagoriciens primitifs (à une puissance de 5 près...) correspondant aux 7 premières puissances de 5
Il est facile à partir de là de reconstruire les points du cercle unité à coordonnées décimales exactes, d'ordre <=7.
Après on dépasse la capacité du type utilisé:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
unsigned int pow_k_of_5(int k)
{
    unsigned int r=1;
    int i;
    for (i=1;i<=k;i++)
        r*=5;
    return r;
}
 
void find (unsigned int n)
{
    unsigned int x,y,maxy;
    for (x=1;x<n/sqrt(2);x++)
    {   maxy=sqrt(n*n-x*x);
        for (y=x;y<=maxy;y++)
        {
            if (x*x+y*y==n*n)
                printf("%u-%u-%u\n",x,y,n);
        }
    }
}
 
 
int main()
{
    find(pow_k_of_5(1));
    printf("-------------------------\n");
    find(pow_k_of_5(2));
    printf("-------------------------\n");
    find(pow_k_of_5(3));
    printf("-------------------------\n");
    find(pow_k_of_5(4));
    printf("-------------------------\n");
    find(pow_k_of_5(5));
    printf("-------------------------\n");
    find(pow_k_of_5(6));
    printf("-------------------------\n");
    find(pow_k_of_5(7));
    return 0;
}

Sortie:

3-4-5
-------------------------
7-24-25
15-20-25
-------------------------
35-120-125
44-117-125
75-100-125
-------------------------
175-600-625
220-585-625
336-527-625
375-500-625
-------------------------
237-3116-3125
875-3000-3125
1100-2925-3125
1680-2635-3125
1875-2500-3125
-------------------------
1185-15580-15625
4375-15000-15625
5500-14625-15625
8400-13175-15625
9375-12500-15625
10296-11753-15625
-------------------------
46875-62500-78125
51480-58765-78125

Process returned 0 (0x0) execution time : 2.906 s
Press any key to continue.

[Nemerle]

Merci pour ces retours, mais j'aimerais un algo rapide sur ce problème.

De façon générale, on peut montrer que x^2+y^2=z^2 primitif ou non a pour solutions les (x,y,z) vérifiant obligatoirement z=d(a^2+b^2) avec a et b premiers entre eux, et x et y s'écrivent aussi simplement à partir de a,b et d.

On peut donc partir de cette idée en testant les candidats d,a et b pour z=10^n, mais l'algo n'est non plus pas très performant...

[Zavonen]

Jusqu'à quelle valeur de n, veux tu aller ?

[Nemerle]

En pratique: 50

Mathématiquement: la question est bien sûr sur l'existence d'une formule donnant la suite des couples solutions par précision de décimales...

Et c'est bien sûr la question mathématique qui m'intéresse

[Zavonen]

Je m'en doutais, et j'ai essayé d'y réfléchir.
Au début ça a l'air croissant monotone, mais après ça se complique.
On peut trouver des trucs et les additionner, mais atteindre 10^50 ....
J'y réfléchirai à nouveau ce soir.

[pseudocode]

c'est un boulot pour Haskell et sa lazy evaluation...

chercher tous les triplets 2^n*(x,y,5^n) avec:

(3,4,5)
(x,y,z) --> ( x-2y+2z, 2x-y+2z, 2x-2y+3z)
(x,y,z) --> ( x+2y+2z, 2x+y+2z, 2x+2y+3z)
(x,y,z) --> (-x+2y+2z,-2x+y+2z,-2x+2y+3z)

[Nemerle]

Un truc trouvé: soit les deux suites a(n) et b(n) définies par

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
a0=6, b0=8
a(n+1)=2*a(n)*b(n)
b(n+1)=abs(a(n)^2-b(n)^2)

alors a(n) et b(n) sont des solutions de x^2+y^2= z^2 avec z=10^(2^n).

Je n'ai pas réussi encore à montrer qu'elles sont uniques, mais ça devrait être faisable.

C'est un début, mais il reste pas mal de soluces non trouvées pour le cas général z=10^n...

[briqueabrac]

Si on prend le quaternion (w,i,j,k) avec w= 0, i=0, j=0.6, k=0.8 et que l'on cherche sa matrice de rotation correspondante on obtient :
-1 0 0 0
0 -0.28 0.96 0
0 0.96 0.28 0
0 0 0 1
La formule de passage quaternion->matrice utilise exactement ce que tu as écrit.

[pseudocode]

Si on prend le quaternion (w,i,j,k) avec w= 0, i=0, j=0.6, k=0.8 et que l'on cherche sa matrice de rotation correspondante on obtient :
-1 0 0 0
0 -0.28 0.96 0
0 0.96 0.28 0
0 0 0 1
La formule de passage quaternion->matrice utilise exactement ce que tu as écrit.

oui, c'est normal vu que c'est la meme formule.

(a,b,*) -> (b²-a²,2ab,a²+b²)

Mais comme le dit Nemerle ca ne marche pas pour tous les TP. En fait ca ne marche que pour les triplets (a,b,10^2n)

(a,b,*) -> (b²-a²,2ab,a²+b²)

(6,8,10) -> (28,96,10^2) -> (5376,8432,10^4) -> ...

[Nemerle]

J'ai encore mieux, la relation de bi-récurrence est effectivement trouvée partout:

définissons les suites A et B à partir d'un couple de paramètre (r,s):

A(r,s,0)= r
B(r,s,0)=s
A(r,s,n+1)=2A(r,s,n)B(r,s,n)
B(r,s,n+&)=abs(A(r,s,n)^2-B(r,s,n)^2)

Pour tout a,b posons C(a,b)=10^(a*2^(b-1))

Alors Pour tout n>0, on a les triplets pytagoriciens

[ A(1,3,n) , B(1,3,n) , C(1,n) ]
[ A(18,26,n) , B(18,26,n) , C(3,n) ]
[ A(12,316,n) , B(12,316,n) , C(5,n) ]
[ A(1992,2456,n) , B(1992,2456,n) , C(7,n) ]
....

Conclusions: il me semble que les solutions recherchées se font via une infinité de bi-générateurs qui génère des sous-couples de solutions à croissance d'ordre 2^n... Ce qu'il faut deviner, c'est la bi suite des générateurs

1 , 3
18, 26
12, 316
1992, 2456
....

et ça me semble infaisable...

[pseudocode]

trouver les TP primitif de la forme (a,b,5^n)

3²+4²=5²
(3/5)² + (4/5)² = 1

soit "t" tel que cos(t)=3/5 et sin(t)=4/5

calculons:
cos(2t) = 2.cos(t)²-1 = 2.(3/5)²-1 = 7/25
sin(2t) = 2.sin(t).cos(t) = 2.(3/5).(4/5) = 24/25
=> (7/25)² + (24/25)² = 1
=> 7² + 24² = 25²

calculons:
cos(3t) = +cos(t)^3-3.cos(t).sin(t)² = -117/125
sin(3t) = -sin(t)^3+3.cos(t)².sin(t) = 44/125
=> (44/125)² + (117/125)² = 1
=> 44² + 117² = 125²

Et de maniere generale, on conjecture que
cos(n.t) = a/5^n
sin(n.t) = b/5^n
=> cos(n.t)² + sin(n.t)² = 1
=> (cos(n.t).5^n)² + (sin(n.t).5^n)² = (5^n)²

et que les TP sont de la forme (cos(n.t).5^n , sin(n.t).5^n , 5^n)

Reste a multiplier par 2^n pour solutioner le probleme de Nemerle:
(cos(n.t).10^n , sin(n.t).10^n , 10^n) avec t=arcos(3/5)

Exemple pour n=4, on trouve:
cos(4t)=0.8432 et sin(4t)=0.5376
-> (8432,5376,10000)

[Zavonen]

Pseudocode, comment es-tu sûr que les pp que tu trouves sont 'primitifs' ?
Pour ce qui me concerne, j'ai (essayé) de traiter le problème avec les pp (primitifs ou non) de la forme (a,b,c) où c est une puissance de 5(cf mon premier post).
J'ai constaté que quand on passe d'une puissance à la suivante, on mutiplie par 5 tous les pp trouvés à l'étape précédente et il s'ajoute un pp 'primitif' (un nouveau en quelque sorte).
J'ai été fureter sur le site :
http://forum.java.sun.com/thread.jsp...532&tstart=360
où l'auteur fait la remarque que les ppp sont exactement les carrés parfaits des complexes entiers (remarque non faite avant lui).
Tout le problème revenait donc à trouver à chaque fois ce nouveau ppp.
J'ai remarqué que quand une puissance de 5 est le carré d'une autre
par exemple 25 et 5 25 et 625, le ppp de rang le plus élevé découle de l'autre par simple élévation au carré, par contre le ppp pour 125 ne peut pas à ma connaissance être déduit simplement de ceux trouvés pour 5 et 25.
Les nombres que tu trouves corespondent aux miens et il y a de fortes chances pour que ta méthode soit la bonne, si tu peux établir que ton calcul conduit forcément à un ppp.
Par contre, pour une solution complète, les choses sont un peu plus complexes. Il faut d'abord avoir tous les pp et non seulement un ppp avant de multiplier par les puissances de 2.
Donc en fait pour avoir à l'ordre n
tu doit trouver ton ppp à l'ordre 1
le multiplier par 5 et ajouter ton ppp à l'ordre 2
multiplier les 2 par 5 et ajouter ton ppp ordre 3
et ainsi de suite jusqu'à l'ordre n.
Alors seulement tu peux multiplier par 2^n.
En admettant que nous ayons raison tous les deux, on peut accélerer l'algo
Calcul du ppp par ma méthode pour n=1,2,4, et toutes les puissances de 2 (simples élévations au carré)
Calcul du ppp par ta méthode pour n=3
Calcul du ppp par ma méthode pour 6,12,24, etc
Calcul du ppp par ta méthode pour n=5
et ainsi de suite en alternant jusqu'à ce qu'il n'y ait plus de trous jusqu'à la valeur fixée par exemple n=50 comme le suggère Nemerle.
Ensuite appliquer la méthode précédente.
Félicitations pour tes souvenirs de trigo.

[Nemerle]

Pseudocode: bravo!!!! la relation est produite, et j'avoue une frustation, je voulais regarder la piste trigonométrique demain matin....n'ayant plus les formules de trigo de base en tête... grrh!

Comme l'a mentionné zavonen, la "preuve" de l'unicité des solutions reste plus hardue... mais quoi? on est dans la vraie vie, on s'en fou

Il est intéressant de noter ici la variétés des tentatives:

- Zavonen en algèbre "pur" en se réduisant aux fondamentaux des primitifs, conduisant à la piste des 5^n, et amenant à mon avis vers le bon chemin pour une preuve complête;
- Nemerle en algèbre "récursive", en reprenant la détermination d'Euclide sous la forme x^2+y^2=z^2 <=> z=d(a^2+b^2),x=...,y=... et (a,b) 1iers entre eux, pour rechercher une bi-suite récurrente, en se prenant le mur exponentiel de face
- Pseudocode, pragmatique une fois de plus, faisant intervenir les fondamentaux du cercle unité, via la trigo

On a même vu un immision des quaternions

CA, c'est des maths!! Bravo encore à tous!

[pseudocode]

Les nombres que tu trouves corespondent aux miens et il y a de fortes chances pour que ta méthode soit la bonne, si tu peux établir que ton calcul conduit forcément à un ppp.

A mon avis, tout ca doit se démontrer en partant de la formule de Moivre:

cos(n.t) + i.sin(n.t) = (cos t + i.sin t)^n

Deja ca permet de montrer que:
cos(n.t) = X / (5^n) ou X est un entier
sin(n.t) = Y / (5^n) ou Y est un entier

Ensuite il faut démontrer que X ou Y est premier avec 5^n.

Il faudrait calculer la valeur de X a partir des coefficients du triangle de pascal. Avec des nombres comme 3 et 5, ont doit pouvoir montrer que soit X, soit Y et premier avec 5.

[Nemerle]

hummm... pas si facile que ça à mon avis, c'est jamais très bon de travailler avec des sommes pour un test de primalité...

Et il reste par ailleurs l'unicité des solutions trouvées...

2 remarques de détail:

- il faut prendre les valeurs absolues des cos(nt) et sin(nt)
- il faut un algo qui calcule avec une précision arbitraire les cos, sin et arcos, style Cordic.

[briqueabrac]

Je donne la suite géométrique que j'avais trouvé avec les quaternions, j'ai pas trouvé comment obtenir les solutions pour n=1

On a n = 0, x=1 ,y=0
On a n = 1, x=0.6 ,y=0.8
On construit le quaternion représentant la rotation selon l'axe <x,y,0> et d'angle pi : q= (0, 0.6, 0.8, 0)

Pour n = 2 on fait tourner le point n = 0 par le quaternion trouvé en n= 1
Pour n = 3 on fait tourner le point n = 1 par le quaternion trouvé en n = 2
ect...

ce qui plus simplement s'ecrit pour n>=2 :

xn+1 = 2*xn*yn*yn-1+(xn^2-yn^2)*xn-1
yn+1 = 2*xn*yn*xn-1+(yn^2-xn^2)*yn-1