C'est mieux comme ça

Tu ne vois pas que (ac+bd)²+(ad-bc)² est de la forme C² + D² ?
Tu y es presque.

donc :   (ac+bd)²+(ad-bc)² =  C^2 + D^2  =c'^2+d'^2 ??    

J'ai utilisé les lettres C et D pour t'ouvrir les yeux.
Mais elles ne sont plus utiles pour rédiger.

Tu veux démontrer que c' et d' existent et sont entiers.
Dans ce but, tu as le droit d'écrire des choses comme :
Soit c' = ... et d' = ...
Alors N^p+1 = (ac+bd)²+(ad-bc)² = c'² + d'²

D'accord merci beaucoup pour votre aide !!
Bonne journée et à bientôt !

N'oublie pas de dire pourquoi c' et d' sont des entiers naturels.

Si tu veux voir comment faire avec les complexes, n'hésite pas à demander.
On peut aussi faire une récurrence contrairement à ce que j'ai plus ou moins écrit auparavant.
Sinon, bonne journée à toi aussi

bonjour,

au fait ... et la question 1 (l'algorithme) ?
parce que il n'a aucun rapport avec la question 2 ni avec Brahmagupta ni les complexes.

C'est vrai, je l'avais complétement oubliée !
A toi l'honneur mathafou

bonjour à tous

juste une petite remarque sur la question 2)
on a N = a²+b² ----> symétrie de a et de b
N^p = c²+d²  ----> idem

N^p+1 = (ac+bd)²+(ad-bc)² ---- on pressent qu'il peut y avoir 2 couples(c';d')

Aïe, je n'avais pas vu que ad-bc ne convient pas toujours, car on veut des entiers naturels.
Heureusement qu'on a un peu le choix

il me semble qu'étant donné que comme ce sont les carrés de c ' et d ' qui interviennent,
le signe n'a pas d'importance, me trompe-je ?

je me suis amusée à programmer (algobox) les questions 1 et 2, et en effet, selon le N choisi, on retrouve bien les 2 couples.

je pense aussi, que lorsque l'exo sera entièrement terminé, il pourrait être intéressant de le programmer en python,
plus adapté qu'algobox ici, mais je ne maitrise pas dans sa syntaxe.
avis aux amateurs

...mais christophe13 a gardé le meilleur pour la fin ^^.
attendons de voir sa réponse à mes questions sur le sujet...

Bonjour à vous tou(te)s,

@ carita
Pourrais tu, sinon donner ta version Algobox ( mais pourquoi pas ? ), du moins donner quelques indications sur l'algorithme que tu as utilisé. A ma grande honte (), je ne suis pas parvenu à traiter cette question 1... je suis parti dans des doubles boucles infernales. Merci.

bonjour ZEDMAT
oui, pas de souci, mais pas sur cette page, on ne va pas embrouiller le posteur.
d'autant plus que d'autres peuvent trouver plus simple ou plus élégant...

ce que je te propose, c'est de le transmettre à Malou, qui te le transmettra.
il y aura mon adresse mail, si besoin d'échange.
bonne programmation

Merci carita.

je pense que à ce niveau de l'exo , le plus simple est de rechercher par "force brute"
une seule boucle for ou while, au choix, suffit
(au pire du pire une boucle imbriquée mais beurk)

par contre avant même de commencer à écrire la moindre ligne de code il faut se poser quelques questions sur ce qu'on souhaite faire:
- cherche-t-on toutes les décompositions possibles de n ?
ou une seule suffira ?

- 36 = 6² + 0² est il accepté ou rejeté
(dans ou dans ^*, privé de 0)

- on ne cherchera pas spécialement à faire un algorithme hyper optimisé, permettant de décomposer de très grands nombres

@carita et ZEDMAT,
Pourquoi ne pas créer un nouveau sujet pour la question qui vous intéresse ?
En mettant le lien ici.
D'autres pourront ainsi en profiter

Re bonjour !
J'ai essayé de faire un programme en langage naturel mais je ne sais pas si cela est juste

a et b deux entiers naturels
pour b allant de 1 à k
           Pour a allant de 1 à k
                          Si N=a^2+b^2 alors
                                      Afficher a et b
                          Sinon N != a^2+b^2
                           Fin de si
             Fin de pour
Fin de pour

un très bon début

reste à creuser un peu :

"de 1 à k "
k va dépendre de N en fait
à la main quand s'arrêterait-on de chercher ?

"sinon" : bein sinon ... on ne fait rien du tout en fait , donc pas besoin de sinon.
inutile de dire chacun des essais qui ont "raté" au cours du balayage des valeurs !

on pourra discuter aussi de quelque améliorations :
- une seule boucle suffit : on sait extraire une racine carrée, tout de même !

- il se peut que aucune des valeurs essayée ne marche, que N ne soit pas la somme de deux carrés du tout (par exemple 3 ne peut pas être somme de deux carrés )
et ça on ne s'en aperçoit que à la fin quand toutes les boucles sont terminées
comment le savoir dans l'algorithme pour dire "N n'est pas somme de deux carrés" ?
au lieu de rester muet sans rien dire du tout.

a et b deux entiers naturels
pour a et b allant de (1,k,N)
                          Si N=a^2+b^2 alors
                                      Afficher a et b
                           Fin de si
             Fin de pour
Fin de pour
Afficher "N n'est pas somme de deux carrés"

Est-ce mieux ainsi ??

pas vraiment

ta boucle "pour" sur deux variables est en fait deux boucles imbriquées
et quand tu devras traduire cet algorithme en Python , Algobox ou quoi , tu devras bien les écrire ces deux boucles imbriquées
quand je parlais de une seule boucle je ne voulais pas du tout dire cela
mais une seule boucle sur une seule variable
et dans la boucle calculer l'autre variable.

et puis ne pas confondre :
amélioration (pour rendre l'algorithme plus rapide, plus convivial etc)
et une modification nécessaire au fonctionnement

cette histoire de une boucle au lieu de deux c'est de l'amélioration pour accélérer l'exécution
pas du tout pour que ça fonctionne ou pas.
si ça te chante reste avec deux boucles

par contre ce qui est indispensable c'est de dire dans quelle(s) gamme(s) de valeur(s) vont varier les variables de boucles

dans le précédent tu disais "de 1 à k"
ce n'était pas bon parce qu'on ne sait pas ce que vaut ce "k"

maintenant tu dis
"allant de (1,k,N)"
c'est pire
c'est quoi ce "k" qui traine là dedans et qui n'a plus rien à y faire ?? ça ne veut plus rien dire du tout
tu veux dire que ça va essayer les valeurs de x et de y edit : de a et de b depuis 1 jusqu'à N ?
bein tu dit "de 1 à N" point barre !
(c'est pas très malin, mais ça marchera)

entrée N
a et b deux entiers naturels
pour b allant de 1 à N
    Pour a allant de 1 à N
        Si N=a^2+b^2 alors
            Afficher a et b
        Fin de si
    Fin de pour
Fin de pour

Vous m'avez complétement perdu, de ce que j'ai compris:

Entrée N
a et b deux entiers naturels
pour b allant de 1 à b^2
    Pour a allant de 1 à a^2
        Si N=a^2+b^2 alors
            Afficher a et b
        Fin de si
    Fin de pour
Fin de pour

C'est un peu mieux ??

je t'ai donné le truc qui marche

" pour b de 1 à b² " ça ne peut pas marcher parce que b ne pourra jamais dépasser la valeur b² forcément b !
cette boucle ne se terminerait jamais !

forcément dans une boucle "pour" saine, la valeur finale ne doit pas dépendre de la valeur de la variable de boucle !
"pour b de 1 à une valeur qui ne dépend pas de b" !!
à une valeur qui ne dépend que de N, constante pour un N donné

valeur finale = N est OK mais pas très malin car aussi bien a que b seront forcément inférieurs à la racine carrée de N

donc OK serait :
pour b de 1 (ou de 0) à racine de N

plus malin encore est de ne dire que une seule fois 5 = 1² + 2²
et pas 1² +2² et 2² + 1²
en imposant a b

mais on va en rester là pour l'instant déja.
ça répond à la question : un algorithme.

passer à la traduction en un vrai langage de programmation, Algobox ou Python ou autres, pour pouvoir le tester en tant que programme est intéressant..

Lorsque je mets cet algorithme sur python ça me dit que sqrt(N) est une erreur.
Voici l'algorithme :

N=int(input("N="))
for b in range (1,sqrt(N)):
    for a in range(1,sqrt(N)):
        N=a**2+b**2
print("a=")
print("b=")
Puis-je laisser cet algorithme en langage naturel ?

sqrt n'existe que dans le module "math"
donc il faut faire précéder le tout de
from math import *

en plus où donc est disparu le test "si N = a² + b² " ??
il doit être traduit explicitement par un if
et une condition "égal" se traduit par "= ="
un seul = veut dire une affectation : "mettre la valeur de ce qui est à droite dans la variable qui est à gauche"
et pas un test

tes "print" sont mal placés car ils ne s'exécutent que une fois les boucles terminées et quoi qu'il arrive

ce n'est pas ce que tu avais écrit :

      Si N=a^2+b^2 alors
        Afficher a et b
      Fin de si

Même en mettant from math import* cela m'affiche:
    for b in range (1,sqrt(N)):
TypeError: 'float' object cannot be interpreted as an integer
Voila le programme:

from math import*
N=int(input("N="))
for b in range (1,sqrt(N)):
    for a in range(1,sqrt(N)):
        if N==a**2+b**2:
            print(a,b)

PS :
en fait ça ne fonctionne toujours pas car "range" travaille sur des nombres entiers or sqrt est un nombre réel (float)
il faut floor(sqrt(N)) (la partie entière de la racine de N)

range (m, n) fait varier de m à n-1 inclus
pour aller jusqu'à cette racine carré incluse, on doit mettre floor(sqrt(N))+1

malgré ces corrections c'est pas terrible
si N = 25, ça donne :

>>>
a= 4 b= 3
a= 3 b= 4
>>>

bof
et il "oublie" 0² + 5², c'est bien une somme de deux carrés , non ?
il n'a jamais été dit de deux carrés non nuls !

mieux serait de partir de 0
... in range(0, floor(sqrt(N))+1)

et de n'afficher que si a > b :

... if N == a**2+b**2 and a >= b

from math import *

N=int(input("N="))
for b in range (0,floor(sqrt(N))+1):
    for a in range(0,floor(sqrt(N))+1):
        if N==a**2+b**2 and a>=b :
            print("a=",a," b=",b)

Merci beaucoup !!
Bonne soirée et à bientôt !

Bonne soirée à toi aussi et pour la question 2) :

nota sur l'algo :
on peut faire fi des complications du floor(sqrt(N))
et mettre directement N, soit "au plus simple" :

N=int(input("N="))
for b in range (0,N+1):
    for a in range(b,N+1):
        if N==a**2+b**2 :
            print("a=",a," b=",b)

# décomposition en somme de deux carrés 
# par force brute, optimisé, b >= a
def somcar(n) :
    xm = floor(sqrt(n/2)) # valeur maximale de a
    nc = 0 # nombre de décompositions
    nb = 0 # nombre de boucles effectuées
    # de a = 0 : on accepte 0² + b² si n est un carré parfait
    for a in range(0,xm+1) :
        b = sqrt(n-a*a)
        if b == floor(b) : # si b est un entier
            print(n," = ",a,"² + ",int(b),"²",sep='')
            nc = nc+1 # compte les solutions trouvées
        nb = nb+1 # compte les boucles effectuées (pour info)
    # fin de la boucle
    if nc == 0 :
        print(n,"n'est pas somme de deux carrés")
    else :
        print(nc,"décompositions")
    print(nb,"boucles effectuées, pour a de ",0,"à",xm)

@mathafou
bravo ! et merci pour toutes ces informations.

à la lecture de tes explications, j'ai essayé avec une seule boucle, ça marche très bien.

au départ, j'étais partie sur 2 boucles imbriquées,
mais justement en faisant partir la seconde boucle à partir du compteur de la 1ère,
et avec les 2 racines carrées, bien sûr.

mais quand j'ai lu "2 boucles imbriquées, beurk"... j'ai revu ma copie.
et en effet, c'est plus mieux bien

@Sylvieg
Si tu veux voir comment faire avec les complexes, n'hésite pas à demander.
si le posteur ne le demande pas... perso ça m'intéresse

bonne soirée à tous !

avec les complexes on a deja deux méthodes comme indiquées précédemment :

soit en utilisant directement le développement du binome (x+iy)^p
soit par récurrence pour dire la même chose.
mais ... il y a plus puissant encore !

et comme je le disais aussi : cela peut être simplement équivalent à la méthode utilisant Brahmagupta

en effet
(a+ib)(c+id) = (ac -bd) +i(ad+bc)

ce qui donne directement la relation de Brahmagupta en passant aux normes
(a² + b²)(c²+d²) = (ac -bd) ² + (ad+bc)²
ou en échangeant les signes, c'est à, dire en remplaçant b par -b, comme déja remarqué

autre remarque sur une propriété générale des nombres de la forme a+ib, a et b dans
ce que l'on nomme l'ensemble , aussi appelé "entiers de Gauss"

la somme et le produit de deux entiers de Gauss sont des entiers de Gauss
(assez évident car la somme et le produit de nombres entiers de sont des entiers de , et il n'y a qu'à développer)
et par extension (soit avec la formule du binome, soit par récurrence) qu'une puissance d'un entier de Gauss est un entier de Gauss.

on part donc d'un nombre n somme de deux carrés n = a²+b² = (a+ib)(a-ib)
et on veut montrer que n^p est aussi somme de deux carrés


les remarques précédente impliquent que cela est (c+id)(c-id) = c² + d²
avec c et d dans
terminé.

et même plus :
si deux nombres quelconques n et m sont tous deux sommes de deux carrés , leur produit aussi
et pas seulement les puissances d'un même nombre.
on ne va pas discuter d'avantage non plus de tout ce qui se sait sur les décompositions d'un nombre en somme de carrés...
il y une grosse littérature là dessus.

salut,
petite modif du code pour avoir une fonction renvoyant la liste des couples [a,b] (sous edupython)

from lycee import *
def somme2carres(n):
  """decomposition d'un entier en somme de deux carres"""
  L=[]
  m=floor(sqrt(n/2))
  for a in range(1,m+1):
    b=sqrt(n-a*a)
    if b==floor(b):
        L.append([a,b])
  return L

@mathafou merci ! tout est parfaitement clair