|
Apprendre Maple Site dédié au logiciel de calcul formel Maple
|
Voir le sujet précédent :: Voir le sujet suivant |
Auteur |
Message |
michel
Inscrit le: 23 Juin 2006 Messages: 72
|
Posté le: 03 Fév 2013 9:14 Sujet du message: décomposition d'entiers en sommes de carrés |
|
|
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 |
|
|
ALS
Inscrit le: 11 Sep 2006 Messages: 647
|
Posté le: 03 Fév 2013 11:44 Sujet du message: |
|
|
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 |
|
|
ALS
Inscrit le: 11 Sep 2006 Messages: 647
|
Posté le: 04 Fév 2013 8:23 Sujet du message: |
|
|
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 |
|
|
michel
Inscrit le: 23 Juin 2006 Messages: 72
|
Posté le: 04 Fév 2013 11:03 Sujet du message: décomposition de nombres en sommes de carrées |
|
|
> 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 |
|
|
ALS
Inscrit le: 11 Sep 2006 Messages: 647
|
Posté le: 05 Fév 2013 8:45 Sujet du message: |
|
|
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 |
|
|
michel
Inscrit le: 23 Juin 2006 Messages: 72
|
Posté le: 05 Fév 2013 9:18 Sujet du message: extraire des éléments d'un ensemble |
|
|
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 |
|
|
ALS
Inscrit le: 11 Sep 2006 Messages: 647
|
Posté le: 05 Fév 2013 12:43 Sujet du message: |
|
|
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 |
|
|
michel
Inscrit le: 23 Juin 2006 Messages: 72
|
Posté le: 06 Fév 2013 11:35 Sujet du message: choisir des éléments dans un ensemble |
|
|
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 |
|
|
ALS
Inscrit le: 11 Sep 2006 Messages: 647
|
Posté le: 06 Fév 2013 14:52 Sujet du message: |
|
|
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 |
|
|
michel
Inscrit le: 23 Juin 2006 Messages: 72
|
Posté le: 06 Fév 2013 20:40 Sujet du message: décomposition en sommes de carrés |
|
|
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 |
|
|
michel
Inscrit le: 23 Juin 2006 Messages: 72
|
Posté le: 09 Fév 2013 14:52 Sujet du message: décomposition (suite) |
|
|
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 |
|
|
ALS
Inscrit le: 11 Sep 2006 Messages: 647
|
Posté le: 10 Fév 2013 10:38 Sujet du message: |
|
|
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 |
|
|
|
|
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
|
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.
|