Programmation des solutions de l'équation dans $\mathbb N$; x²-y²=a

gebrane

Bonjour, pourriez-vous partager vos connaissances et compétences afin de partager  un programme en Python, C, ... permettant de trouver toutes les solutions de l'équation dans $\mathbb N$; x²-y²=a sans en manquer une ? ( elles sont en nombre fini)

Voici ce que j'ai su faire, on a évidement $y\leq x$ et $x\geq \sqrt a$, j'ai cherché les solutions avec x petit qu'un million faute de faire mieux

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

int main() {
int a, x, y;
printf("Entrez un entier a : ");
scanf("%d", &a);
for(x = floor(sqrt(a)); x <=1000000; x++) {
    for(y = 1; y <= x; y++) {
        if((x*x - y*y) == a) {
            printf("Solution : x = %d, y = %d\n", x, y);
        }
    }
}
return 0;
}

Après exécution le programme me sort ceci pour a=39

Solution : x = 8, y = 5

Solution : x = 20, y = 19
rapidement et après un moment il continu à sortir d'autres" solutions "

Solution : x = 133568, y = 25701

Solution : x = 195696, y = 62747

Solution : x = 220332, y = 36077

Solution : x = 225828, y = 61267

Solution : x = 227920, y = 20197

Solution : x = 252624, y = 128741

Solution : x = 270180, y = 92589

Solution : x = 272628, y = 119149

Solution : x = 278216, y = 9733

Solution : x = 322012, y = 24749

Solution : x = 326848, y = 205925

Solution : x = 334488, y = 14597

Solution : x = 336424, y = 329979

Solution : x = 338280, y = 304891

Solution : x = 340540, y = 1837

Solution : x = 341616, y = 70939

Solution : x = 347844, y = 271571

Solution : x = 375052, y = 276115

Solution : x = 402536, y = 291077

Solution : x = 406796, y = 337555

Solution : x = 415956, y = 176877

Solution : x = 434648, y = 207099

Solution : x = 440112, y = 382693

Solution : x = 449740, y = 94829

Solution : x = 450716, y = 354733

Solution : x = 456696, y = 311291

Je ne comprends pas !

Math Coss

Les entiers en C, c'est borné (par $32\,767$ semble-t-il). Tes solutions dépassent les bornes, manifestement. De là à savoir ce qui est calculé quand c'est aberrant... Ce qui se passe, c'est que c'est « légitimement » aberrant. Essaie de remplacer "int a, x, y" par "long a, x, y".

Sinon, pour la borne supérieure de $x$, on peut tout de même faire mieux : vu que $x+y$ et $x-y$ sont des diviseurs de $a$, leur somme $2x$ ne peut pas dépasser $a$.

Erratum : leur somme $2x$ ne peut pas dépasser $2a$, et pas $a$ ! Autrement dit $y\le x\le a$.

gebrane

Merci @Math Coss  En remplaçant la boucle

for(x = floor(sqrt(a)); x <= 1000000 par 

for(x = floor(sqrt(a)); x <= a/2  je reçois une solution mais avec

for(x = floor(sqrt(a)); x <= 1+a/2, je reçois les deux solutions

bizarre la programmation

dp

Ce n'est qu'une supposition mais à mon avis tu overflow… lorsque x*x et y*y atteignent 2^32, ceux-ci passent à -2^32+1 et ainsi de suite jusqu'à 2^32 pour recommencer.

gebrane

@dp même si le programme reboucle, il ne doit pas sortir comme solution par exemple  x = 133568, y = 25701

Car elle ne l'est pas sauf si le C a du mal à calculer 133568²-25701²

dp

Et pourquoi ça ne serait pas le cas ? Regarde :

Solution : x = 133568, x*x=660541440, y = 25701, y*y=660541401, 39

bisam

C'est ce qu'on vient de te dire : ton $x$ est plus grand que $2^{17}=131072$ donc $x^2 > 2^{32}$ et par conséquent, les calculs faits dans ton programme ne donnent pas les bons résultats.

Tu peux gagner un petit peu en faisant calculer $(x-y)*(x+y)$ à la place de $x^2-y^2$ car les nombres intermédiaires seront moins grands.

dp

Après ce que moi je trouve aberrant (sans aucune offense bien sûr) c'est surtout que tu n’aies pas daigné ouvrir le moindre livre de programmation en C… parce que bon, les limites des différents types numériques, c'est genre à la deuxième page de n'importe quel chapitre s'y rapportant (généralement dans les tous premiers) quel que soit le livre.

gebrane

@Math Coss  Il y a une erreur dans cette assertion "vu que x+y et x−y sont des diviseurs de a, leur somme 2x ne peut pas dépasser a."

Ce que je vois si x|a et y|a alors x+y\leq 2a et non pas x+y\leq a ' On a le contre a=4, x=4 et y=2)

Le programme rectifié marche bien

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

int main() {
long a, x, y;
printf("Entrez un entier a : ");
scanf("%d", &a);
for(x = floor(sqrt(a)); x <=2a

; x++) {
    for(y = 1; y <= x; y++) {
        if((x*x - y*y) == a) {
            printf("Solution : x = %d, y = %d\n", x, y);
        }
    }
}
return 0;

}

gebrane

Je préfère ne pas répondre à "tu n’aies pas daigné ouvrir le moindre livre de programmation en C"

@dp pourquoi te sens-tu obliger d'intervenir dans mes fils ?, si tu n'as rien d’intéressant à proposer garde ces commentaires pour toi.

dp

Pourtant tu y réponds. Mais soit. Je n'interviendrai plus dans aucun de tes fils, si tel est ton souhait.

gebrane

Soit, marché conclu.

Lorsqu'on lit un livre, on ne comprend vraiment ce qu'on lit que lorsque le besoin s'en fait sentir.

Je te souhaite patience avec tes élèves

Math Coss

Je me suis en effet planté d'un facteur $2$ (mais pas $4$) : de $x+y\le a$ et $x-y\le a$ on tire $2x\le 2a$ puis $x\le a$.

gebrane

Bonjour @Math Coss  si tu as à programmer ce petit problème ( utile pour les prof au Lycée) comment ferais-tu ?

Médiat_Suprème

On peut faire un peu mieux en prenant $x \leq \frac{a+1}{2}$

Math Coss

En C, rien. En Python il faudrait réfléchir. Avec Sage :

sage: def S(a=39):
....:     return [(x,sqrt(x^2-a)) for x in range(1,a+1) if is_square(x^2-a)]
....: 
sage: S()
[(8, 5), (20, 19)]

gai requin

On a aussi $x-y\leq\sqrt a$.
Donc $S=\left\{((d+a/d)/2,(a/d-d)/2)\mid d\text{ divise }a,d\leq\sqrt a\text{ et }d=a/d\bmod 2\right\}$.

gebrane

IL parait que sage est très bien . Une traduction en Python

import math

a = int(input("Entrez un entier a : "))

for x in range(math.floor(math.sqrt(a)), 2*a):
    for y in range(1, x+1):
        if (x*x - y*y) == a:
            print("Solution : x =", x, ", y =", y)

Math Coss

Il faudrait tout de même éviter la double boucle, typiquement en calculant $u=\sqrt{x^2-a}$ et en testant si c'est à peu près égal à l'entier le plus proche, $y=\lfloor u+1/2\rfloor$ ; par exemple, si $|y-u|<10^{-6}$, on calcule pour de bon $x^2-y^2-a$.

gebrane

La première étape était de donner un programme qui marche. Les améliorations viennent après. Mais je réfléchis comment programmer les solutions dans \N  de ax²-by²=c  pour atteindre le cas général des equations  ax²+by²=c dans Z. Ce n'est pas évident sauf pour les habitués

gebrane

Un programme en C qui marche pour résoudre  dans $\N$, ax²-by²=c où a,b et c des entiers naturels non nuls

edit  programme faux

Math Coss

L'équation est paire en $x$ et $y$, ça ne change vraiment pas grand-chose !

gebrane

Il  y a deux à  discuter: a,b de signes opposés et a,b de même  signes 

Math Coss

Ah pardon, je n'avais pas compris que c'était $a$ et $b$ qui comptaient. Apparemment je ne comprends pas grand-chose ces jours-ci.

C'est beaucoup plus compliqué que ça. Si $a=1=-b$, on peut factoriser et les solutions sont bornées a priori. En général, ce n'est pas le cas et il peut y avoir une infinité de solutions. C'est le cas par exemple des équations de Pell-Fermat, dont par exemple $x^2-2y^2=1$ : pour tout $n$, si $u$ et $v$ sont les entiers tels que $u+v\sqrt2=\bigl(1+\sqrt2\bigr)^{2n}$, alors $(u,v)$ est solution.