Apprendre Maple Index du Forum Apprendre Maple
Site dédié au logiciel de calcul formel Maple
 
  Page d'accueilPage d'accueil   FAQFAQ    RechercherRechercher    Liste des MembresListe des Membres    Groupes d'utilisateursGroupes d'utilisateurs 
S'enregistrerS'enregistrer    ProfilProfil   Se connecter pour vérifier ses messages privésSe connecter pour vérifier ses messages privés   ConnexionConnexion 

décomposition d'entiers en sommes de carrés

 
Poster un nouveau sujet   Répondre au sujet    Apprendre Maple Index du Forum -> Programmation
Voir le sujet précédent :: Voir le sujet suivant  
Auteur Message
michel



Inscrit le: 23 Juin 2006
Messages: 72

MessagePosté le: 03 Fév 2013 9:14    Sujet du message: décomposition d'entiers en sommes de carrés Répondre en citant

Bonjour,
Je souhaite vérifier par programmation la propriété suivante :
tout entier dans [129, 129+13²[ s'écrit comme une somme de carrés distincts et inférieurs ou égaux à 12.
Exemples : 133=9²+6²+4² ; 168=10²+8²+2² ; 272=11²+10²+5²+3²+1².
Quel algorithme suivre ? Quelle programme Maple envisager ? Merci
Revenir en haut de page
Voir le profil de l'utilisateur Envoyer un message privé
ALS



Inscrit le: 11 Sep 2006
Messages: 647

MessagePosté le: 03 Fév 2013 11:44    Sujet du message: Répondre en citant

Bonjour,

Pour qu'un entier naturel n soit somme de trois carrés, il faut et il suffit
qu'il ne soit pas de la forme 4^h(8k + 7) avec (h; k) dans N^2.

Voici une méthode naive pour obtenir les entiers se décomposant en somme de 3 carrés distincts:

Code:

> L:=NULL:
> for x from 0 to 12 do
>   for y from 0 to 12 do
>      for z from 0 to 12 do
>           n:=x^2+y^2+z^2:
>           if (x-y)*(y-z)*(z-x)<>0 and n>128 and n<129+13^2 then L:=L,[n,x,y,z] fi
>      od
>    od
> od:

> sort({L});
Revenir en haut de page
Voir le profil de l'utilisateur Envoyer un message privé
ALS



Inscrit le: 11 Sep 2006
Messages: 647

MessagePosté le: 04 Fév 2013 8:23    Sujet du message: Répondre en citant

Programme de décomposition en 5 carrés tous différents (carrés de nbs <=12)

Code:

> decomp:=proc(n)
>  local i,j,k,l,m,a,s;
>  a:={seq(k,k=0..12)}:
>  s:=NULL:
>  for i to nops(a) do
> for j to nops(a) do
>  for k to nops(a) do
>  for l to nops(a) do
>   for m to nops(a) do
> if (i-j)*(i-k)*(i-l)*(i-m)*(j-k)*(j-l)*(j-m)*(k-l)*(k-m)*(l-m)<>0 and n=a[i]^2+a[j]^2+a[k]^2+a[l]^2+a[m]^2
>  then s:=s,sort([a[i],a[j],a[k],a[l],a[m]]);
>  end if;
>  od;od;od;od;od;
>  (convert([s],set));
>  end proc:
>
> decomp(168);

                          {[2, 3, 5, 7, 9]}

> decomp(272);

                          {[3, 5, 6, 9, 11]}
 
Revenir en haut de page
Voir le profil de l'utilisateur Envoyer un message privé
michel



Inscrit le: 23 Juin 2006
Messages: 72

MessagePosté le: 04 Fév 2013 11:03    Sujet du message: décomposition de nombres en sommes de carrées Répondre en citant

> Carrés := proc (n) local x, y, z, t, u, v; for x from 12 by -1 to 1 do for y from x by -1 to 1 do for z from y by -1 to 1 do for t from z by -1 to 1 do for u from t by -1 to 1 do for v from u by -1 to 1 do if (x-y)*(y-z)*(z-t)*(t-u)*(u-v)*(v-x) <> 0 and n = x^2+y^2+z^2+t^2+u^2+v^2 then lprint([n, x, y, z, t, u, v]) end if end do end do end do end do end do end do end proc;
> for i from 129 to 150 do Carrés(i) end do;
[130, 8, 6, 4, 3, 2, 1]
[131, 7, 6, 5, 4, 2, 1]
[136, 9, 5, 4, 3, 2, 1]
[136, 7, 6, 5, 4, 3, 1]
[139, 8, 6, 5, 3, 2, 1]
[139, 7, 6, 5, 4, 3, 2]
[143, 8, 7, 4, 3, 2, 1]
[146, 8, 6, 5, 4, 2, 1]
[147, 9, 6, 4, 3, 2, 1]
Merci ALS ; voici ma dernière monture. je voudrais [130, 10, 5, 2] .
Revenir en haut de page
Voir le profil de l'utilisateur Envoyer un message privé
ALS



Inscrit le: 11 Sep 2006
Messages: 647

MessagePosté le: 05 Fév 2013 8:45    Sujet du message: Répondre en citant

Bonjour,
[130, 10, 5, 2] n'est pas possible car 10²+5²+2²=129.
D'autre part, si vous remplacez by -1 to 1 par by -1 to 0, vous aurez plus de possibilités.
Revenir en haut de page
Voir le profil de l'utilisateur Envoyer un message privé
michel



Inscrit le: 23 Juin 2006
Messages: 72

MessagePosté le: 05 Fév 2013 9:18    Sujet du message: extraire des éléments d'un ensemble Répondre en citant

Bonjour,
Le problème revient à :
trouver les éléments d'un ensemble formant une somme donnée.
E:={12²,11²,10²,..,1²,0²}
n élément de [129, 129+13²[
la somme n étant composée de 6 termes au plus de E et distincts ;
chaque n de E est décomposable en une somme au moins.
Exemples :
[129,10²,5²,2²],[130,11²,3²],[144,12²],[188,10²,7²,5²,3²,2²,1²],[265,12²,11²] sauf erreurs.
Pourquoi dans les programmes précédents certains n n'ont pas de décompositions ? Merci.
Revenir en haut de page
Voir le profil de l'utilisateur Envoyer un message privé
ALS



Inscrit le: 11 Sep 2006
Messages: 647

MessagePosté le: 05 Fév 2013 12:43    Sujet du message: Répondre en citant

Bonjour,
C'est normal, car je n'avais pas exploré toutes les k-places possibles parmi les 12 possibilités, avec k de 1 à 6.
C'est chose faite avec ce programme en utilisant la fonction choose.
Je trie à la fin (tri à bulle peu performant), donc soyez patient pour avoir toutes les possibilités.

Code:

> restart: with(combinat):

> a:=[1,2,3,4,5,6,7,8,9,10,11,12]:
> L:=NULL: for k to 6 do L:=L,op(choose(a,k)): od:

> r:=NULL:
> for k in L do
>   n:=nops(k):
>   s:=sum(a[k[i]]^2,i=1..n):
>   if s>=129 and s<129+13^2 then r:=r,[s,op(k)] fi;
> od:
> Z:=[r]: n:=nops(Z):
>    for j from n to 2 by -1 do
>         for i to j-1 do  if Z[i][1]>Z[i+1][1] then Z:=subsop(i=Z[i+1],i+1=Z[i],Z) fi
> od od:

>Z;

Revenir en haut de page
Voir le profil de l'utilisateur Envoyer un message privé
michel



Inscrit le: 23 Juin 2006
Messages: 72

MessagePosté le: 06 Fév 2013 11:35    Sujet du message: choisir des éléments dans un ensemble Répondre en citant

Bonjour ALS,
Ce dernier programme fonctionne parfaitement.
Si je n'abuse pas, encore quelques questions :
Comment rendre la procédure decomp exhaustive pour qu'elle convienne à tous les n ?
Comment aller chercher les éléments de Z qui correspondent à un n donné ?
ou encore comment adapter une procédure pour un n donné ? Merci beaucoup.
Revenir en haut de page
Voir le profil de l'utilisateur Envoyer un message privé
ALS



Inscrit le: 11 Sep 2006
Messages: 647

MessagePosté le: 06 Fév 2013 14:52    Sujet du message: Répondre en citant

Je vous laisse adapter au cas général, en suivant le même principe.
Je ferais une procédure decomp(n,nbmax) , en mettant en paramètres formels le nb n et le nb maximal de carrés nbmax en lequel vous voulez décomposer n.

Mais pourquoi prendre une somme de 5 ou 6 carrés? alors que:

Citation:

Tout entier positif peut s'exprimer comme la somme d'au plus quatre carrés.
Revenir en haut de page
Voir le profil de l'utilisateur Envoyer un message privé
michel



Inscrit le: 23 Juin 2006
Messages: 72

MessagePosté le: 06 Fév 2013 20:40    Sujet du message: décomposition en sommes de carrés Répondre en citant

Bonsoir,
Je pense qu'il ne s'agit pas de n'importe quel entier mais seulement de n € [129, 129+13²[ décomposé en somme de carrés distincts dont le plus grand est 12². cf proposition établie par R.L.Graham en 1964.
Revenir en haut de page
Voir le profil de l'utilisateur Envoyer un message privé
michel



Inscrit le: 23 Juin 2006
Messages: 72

MessagePosté le: 09 Fév 2013 14:52    Sujet du message: décomposition (suite) Répondre en citant

Bonjour,
J'ai repris votre programme qui fonctionne. Le tri n'est pas nécessaire pour ce que je veux.
> restart; with(combinat);
> a := [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12];
> L := NULL;
> for k to 6 do L := L, op(choose(a, k)) end do;
> r := NULL;
> for k in L do n := nops(k); s := sum(a[k[i]]^2, i = 1 .. n); if (s >= 129 and
s < 129+13^2) then r := r, [s, op(k)] end if end do;
> Z := [r]; n := nops(Z);
> for p from 129 to 297 do for m to n do if Z[m][1] = p then lprint(Z[m]) end if end do end do;
[129, 2, 5, 10]
[129, 4, 7, 8]
[129, 2, 3, 4, 10]
[129, 2, 5, 6, 8]
[129, 2, 3, 4, 6, 8]
[130, 3, 11]
[130, 7, 9]
etc...
Comment faire écrire la 1ière décomposition de chaque n seulement ?
Exemples [129,2,5,10],[130,3,11],[131,11,3,1]...[297,12,10,7,2]
Revenir en haut de page
Voir le profil de l'utilisateur Envoyer un message privé
ALS



Inscrit le: 11 Sep 2006
Messages: 647

MessagePosté le: 10 Fév 2013 10:38    Sujet du message: Répondre en citant

Bonjour,
Il suffit de rajouter un petit drapeau fait[p], initialisé à false, et mis à true dès que la première décomposition a été effectuée.

Code:

restart; with(combinat):
> a := [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]:
> L := NULL:
> for k to 6 do L := L, op(choose(a, k)) end do:
> r := NULL:
> for k in L do
>   n := nops(k); s := sum(a[k[i]]^2, i = 1 .. n);
>    if (s >= 129 and
>        s < 129+13^2) then r := r, [s, op(k)] end if end do:
>  Z := [r]: n := nops(Z):
>  for p from 129 to 297 do
>      fait[p]:=false:
>      for m to n do if not fait[p] and Z[m][1] = p then lprint(Z[m]): fait[p]:=true end if end do end do:
Revenir en haut de page
Voir le profil de l'utilisateur Envoyer un message privé
Montrer les messages depuis:   
Poster un nouveau sujet   Répondre au sujet    Apprendre Maple Index du Forum -> Programmation Toutes les heures sont au format GMT + 2 Heures
Page 1 sur 1

 
Sauter vers:  
Vous ne pouvez pas poster de nouveaux sujets dans ce forum
Vous ne pouvez pas répondre aux sujets dans ce forum
Vous ne pouvez pas éditer vos messages dans ce forum
Vous ne pouvez pas supprimer vos messages dans ce forum
Vous ne pouvez pas voter dans les sondages de ce forum


phpBB

Développé par phpBB © 2001, 2006 phpBB Group
Traduction par : phpBB-fr.com


Apprendre Maple - ©  - Alain Le Stang - Navigation optimisée pour une résolution 1024 x 768.