Des carrés magiques : un problème vieux de plus de 200 ans

par **fatal_error** » 18 Sep 2012, 15:11

Du concret oui : indique une méthode convergeant plus rapidement que quelques minutes vers un carré !
De façon moins immédiate mais systématique, les articles cités précédemment en lien offrent des indices.

ouais le concret c'est que tu dis du vent, et que t'es incapable de faire un truc toi meme. Et sinon c'est quand que tu cites bourbaki et pourquoi pas le figaro?? :ptdr:

par **chan79** » 18 Sep 2012, 15:20

Dlzlogic a écrit:Je vais être "hors sujet", puisqu'il ne s'agit pas de "carré", mais j' en cliquant sur le bouton en bas à gaucheai eu un problème très intéressant concernant les nombres. Voila, en gros et de mémoire de quoi il s'agissait.
On cherche à représenter un graphisme zonal. La contrainte est le suivante : toutes les lignes sont des segments de hachures parallèles. Par exemple, pour représenter des triangles il y aura 3 réseaux de hachures. La difficulté réside naturellement dans le fait que les extrémités des segments doivent être confondus pour chacun des triangles dessinés. Le triangle n'est cité qu'à titre d'exemple simple.

Si ça intéresse quelqu'un, je peux ressortir mes archives.

intéressant et geogebra est bien adapté pour ça
un lien vers un dessin à animer en cliquant sur le bouton en bas à gauche
le triangle est déformable

par **chan79** » 18 Sep 2012, 15:24

Dlzlogic a écrit:Je vais être "hors sujet", puisqu'il ne s'agit pas de "carré", mais j'ai eu un problème très intéressant concernant les nombres. Voila, en gros et de mémoire de quoi il s'agissait.
On cherche à représenter un graphisme zonal. La contrainte est le suivante : toutes les lignes sont des segments de hachures parallèles. Par exemple, pour représenter des triangles il y aura 3 réseaux de hachures. La difficulté réside naturellement dans le fait que les extrémités des segments doivent être confondus pour chacun des triangles dessinés. Le triangle n'est cité qu'à titre d'exemple simple.

Si ça intéresse quelqu'un, je peux ressortir mes archives.

Dlzlogic a écrit:Je vais être "hors sujet", puisqu'il ne s'agit pas de "carré", mais j' en cliquant sur le bouton en bas à gaucheai eu un problème très intéressant concernant les nombres. Voila, en gros et de mémoire de quoi il s'agissait.
On cherche à représenter un graphisme zonal. La contrainte est le suivante : toutes les lignes sont des segments de hachures parallèles. Par exemple, pour représenter des triangles il y aura 3 réseaux de hachures. La difficulté réside naturellement dans le fait que les extrémités des segments doivent être confondus pour chacun des triangles dessinés. Le triangle n'est cité qu'à titre d'exemple simple.

Si ça intéresse quelqu'un, je peux ressortir mes archives.

intéressant et geogebra est bien adapté pour ça
un lien vers un dessin à animer en cliquant sur le bouton en bas à gauche
le triangle est déformable

par **chan79** » 18 Sep 2012, 15:30

Dlzlogic a écrit:Je vais être "hors sujet", puisqu'il ne s'agit pas de "carré", mais j'ai eu un problème très intéressant concernant les nombres. Voila, en gros et de mémoire de quoi il s'agissait.
On cherche à représenter un graphisme zonal. La contrainte est le suivante : toutes les lignes sont des segments de hachures parallèles. Par exemple, pour représenter des triangles il y aura 3 réseaux de hachures. La difficulté réside naturellement dans le fait que les extrémités des segments doivent être confondus pour chacun des triangles dessinés. Le triangle n'est cité qu'à titre d'exemple simple.

Si ça intéresse quelqu'un, je peux ressortir mes archives.

Intéressant
Geogebra est bien adapté pour représenter ce genre de dessin.
Un lien vers un triangle hachuré, à animer en cliquant sur le bouton en bas à gauche. Le triangle est déformable.
Tu peux mettre ta doc, Dlzlogic :zen:

par **Deliantha** » 18 Sep 2012, 15:37

fatal_error a écrit:ouais le concret c'est que tu dis du vent, et que t'es incapable de faire un truc toi meme. Et sinon c'est quand que tu cites bourbaki et pourquoi pas le figaro?? :ptdr:

J'ai mis en cuvée mes carrés alors n'abuse pas trop du cubi. Hypergeo fait la figuration cartographique.
Quant aux logiciels traceurs de courbe, il y en a pléthore en ligne par n'importe quel moteur (à charger)...

par **beagle** » 18 Sep 2012, 15:55

Sur du 3x3 avec 200 premiers nombres,
on scinde le problème en deux matrices:
celle des unités
celle des dizaines

attention, pour les dizaines dans l'exemple de Deliantha, une diago est en 3x7 qui donnera +1 par rapports aux autres rangées colonnes et l'autre diago

matrice des unités,
à mon avis elles sont peu nombreuses

matrice des dizaines,
soit les matrices les plus petites existantes (on peut répéter 3 fois le mème nombre),
alors ne peut-on en déduire l'expression des suivantes?

then réunion de deux matrices unités+dizaines,
then on enlève quand ce ne sont pas des nombres premiers.

C'est pas du boulot pour du matlab ou apparenté?

par **beagle** » 18 Sep 2012, 16:01

Pas eu le temps de faire mes commentaires sur le carré de 4x4 avec 1à8x2.

Bravo à Chan, pour le nombre , et pour le détail de la classification des 1-trucs, 2-machins,...
Bravo à Le Jeu qui est bien revanu.
Bravo à Fatal-errror parti un peu tard, mais tant mieux, cela nous a obligé à réfléchir.
bravo à Dlzlogic, bien essayé, dommage d'échouer sur la partie géométrique vu les compétences dans ce domaine, trop de concentrations sur la partie informatique?
Bravo à Doraki, toutjours partisan du moindre effort, un vrai mathématicien quoi,
sa division non par 8 mais par 32, chapeau!
Bravo à Delanthia, on a bien squatté son fil...

je n'ai pas eu le temps de répondre sur structure.
Je suis encore à bosser à mon rythme dessus, donc je mets juste la structure régulière dans message suivant.

par **Dlzlogic** » 18 Sep 2012, 16:05

chan79 a écrit:Intéressant
Geogebra est bien adapté pour représenter ce genre de dessin.
Un lien vers un triangle hachuré, à animer en cliquant sur le bouton en bas à gauche. Le triangle est déformable.
Tu peux mettre ta doc, Dlzlogic :zen:

Je joins un pdf qui montre 3 états de la même image.
L'outil en question n'est qu'un éditeur, la partie gauche représente le dessin élémentaire, la partie droite, une visualisation du résultat réel. Dans cette fenêtre, les 2 vecteurs servent à orienter les axes de référence.
Le dessin élémentaire et la façon de le représentés sont stockée dans un petit fichier texte

*MotifEss05, Motif de hachure samedi 10 juin 2006 17:55:30
53.594184424,0.0925,0.4683,24.758145445,0.186019848,0.35957,-114.160879844
305.062877190,0.5000,0.8758,213.411489539,0.136751097,0.39694,-232.875821108
227.524584756,0.7174,0.5634,62.627366392,0.111929709,0.50321,-284.499817651
137.876482121,0.3868,0.2057,20.470614377,0.907635835,0.39751,-28.470631786
269.383430148,0.9664,0.9664,11.363278251,0.134976495,0.91020,-137.882072876
358.522753263,0.0291,0.9664,69.518795155,0.129344854,0.93737,-245.692511215
180.000000000,0.9574,0.0698,87.741907074,0.154135981,0.90113,-206.030870462

Ce type de fichier est "normalisé" et utilisé par des logiciels.
http://www.dlzlogic.com/EditePat.pdf

Le dessin lui-même n'a aucun intérêt, il s'agit d'un dessin utilisé pour mise au point.
Je n'ai plus tout dans ma mémoire, mais j'ai tout dans celle de ma machine.

par **beagle** » 18 Sep 2012, 16:11

Pour le 4x4
une matrice avec du 0 et 1, on place le 1 en vertical:
1010
1010
0101
0101
une matrice est en deux fois du 0-1 sur du horizontal
0011
1100
0011
1100
cela donne en x2
0022
2200
0022
2200

somme des deux matrices
1032
3210
0123
2301

si on fait du +1 pour repasser sans les zéros
2143
4321
1234
3412

il nous reste à dédoubler ce truc.

par **beagle** » 18 Sep 2012, 16:18

troisième matrice qui sera avec les 1 en direction diagonale
0110
1001
0110
1001
cette matrice est fois 4
0440
4004
0440
4004

on ajoute à la matrice réunion des deux premières
2583
8325
1674
7416

par **C.Ret** » 18 Sep 2012, 17:08

Dlzlogic a écrit:Concernant le nombre 1 (l'unité), autrefois, il me semble que c'était un nombre premier. Aurait-il perdu ce statut ? Quelle en est la raison ?

Ben oui, on m'avais expliqué qu'un nombre premier n'avait pas d'autre facteur que 1 et lui-même.
C'est bien le cas avec 1, qui n'a pas d'autre facteur que lui-même et 1.
Mais, bon à chaque époque ses définitions.

Voici les carrés magiques constitués de nombre premiers (donc sans le 1), inférieurs à 200, sans répétition:

Code: Tout sélectionner: Idt Sd Sv ShSa SaSh Sh Sa SvSh S= 177 17 89 71 17 113 47 71 89 17 71 5 101 47 113 17 47 29 101 101 5 71 101 29 47 113 59 5 89 59 29 5 59 113 89 59 29 29 59 89 113 59 5 29 59 89 5 59 113 47 29 101 71 5 101 101 29 47 17 113 47 101 5 71 17 89 71 47 113 17 71 89 17 S= 267 29 131 107 29 167 71 107 131 29 107 11 149 71 167 29 71 47 149 149 11 107 149 47 71 167 89 11 131 89 47 11 89 167 131 89 47 47 89 131 167 89 11 47 89 131 11 89 167 71 47 149 107 11 149 149 47 71 29 167 71 149 11 107 29 131 107 71 167 29 107 131 29 S= 219 37 79 103 37 139 43 103 79 37 103 7 109 43 139 37 43 67 109 109 7 103 109 67 43 139 73 7 79 73 67 7 73 139 79 73 67 67 73 79 139 73 7 67 73 79 7 73 139 43 67 109 103 7 109 109 67 43 37 139 43 109 7 103 37 79 103 43 139 37 103 79 37 S= 213 41 89 83 41 113 59 83 89 41 83 29 101 59 113 41 59 53 101 101 29 83 101 53 59 113 71 29 89 71 53 29 71 113 89 71 53 53 71 89 113 71 29 53 71 89 29 71 113 59 53 101 83 29 101 101 53 59 41 113 59 101 29 83 41 89 83 59 113 41 83 89 41 S= 309 43 127 139 43 199 67 139 127 43 139 7 163 67 199 43 67 79 163 163 7 139 163 79 67 199 103 7 127 103 79 7 103 199 127 103 79 79 103 127 199 103 7 79 103 127 7 103 199 67 79 163 139 7 163 163 79 67 43 199 67 163 7 139 43 127 139 67 199 43 139 127 43 Matrice non première: S= 111 7 61 43 7 73 31 43 61 7 43 1 67 31 73 7 31 13 67 67 1 43 67 13 31 73 37 1 61 37 13 1 37 73 61 37 13 13 37 61 73 37 1 13 37 61 1 37 73 31 13 67 43 1 67 67 13 31 7 73 31 67 1 43 7 61 43 31 73 7 43 61 7

La méthode est simple, elle consiste dans un premier temps à dresser la liste des nombres premiers inférieurs à 200.

Ensuite, c'est une recherche un peu bête à partir de trois de ces nombres premiers, sans le 2 tout de même.

En effet, tous les nombres premiers, sauf 2, sont impairs. Comme on fait une somme à trois nombres dans les carrés 3x3, la somme magique est nécessairement impaire (impair+impair = pair et impair + pair = impair).

Donc, si l'on incorpore 2, on a un problème de parité, il n'y aura aucun carré magique 3x3 contenant le nombre premier 2.

Ensuite, il y a donc 45 premiers à "tester", je le fais par ordre croissant.
Pour éviter de compter deux fois les mêmes carrés, j'impose c>a.

Le carré est donc de la forme :
[ a b c ]
[ d e f ]
[ g h i ]
avec S = a+b+c

Comme je ne dispose que d'un Commodore C128D ( 128ko - 2 MHz - 8bits ) pour faire le travail j'utilise un minimum de boucles (trois en fait).

Au début de l'analyse, je pensais en faire une quatrième sur e. Mais c'est inutile.

Considérons que les varaible sont a,b,c et e.

A chaque itération de ma recherche de solution, je peux calculer à partir de a,b,c et e les autres "cases du carré" :

On a : S= a+e+i
Donc on peut exprimer i en fonction de S,a et e
i = S - a - e

De même pour les autres case de la ligne inférieure :
g = S - c - e
h = S - b - e
i = S - a - e

Ma première idée était donc de calculer ainsi g h i pour chaque quadruplet { a b c e }

Mais, on sait que
S = g + h + i
S = S - c - e + S - b - e + S - a - e
S = S - (a+b+c) + 3.e

Or a+b+c=S, on a donc :
S = S - S + 3.e

On retrouve bien la relation utilisée par Chan79: S=3.e

En fait, il ne sert à rien de chercher les valeurs de e, il faut juste prendre a b et c de telle façon que S=a+b+c soit un multiple par trois d'un des nombres premiers (qui sera donc e).

C'est donc ce que fait mon modeste programme en BASIC qui tourne sur une machine qui a déjà fêté ses 30 ans de loyaux services.

Deux boucles sur a et b sélectionnent séquentiellement les nombres premiers de la liste.
Une boucle supplèmentaire permet de retenir les c tel que e = S/3 = (a+b+c)/3 soit un nombre premier de la liste.

On a alors les quatres variables a b c et e

Le programme calcule (à l'aide de relation utilisant S et les 4 variables) alors successivement i h g d et f dans cet ordre et en passant au c suivant dès que l'un des calculs donne un nombre :
- qui n'est pas un des nombres premier de la liste,
- qui est déjà utilisé dans le carré,
- qui produit un carré symétrique.
- qui ne vérifie pas une relation de somme (la seule a tester est en en fait d+e+f=S)
En particulier, par construction je prends toujours c>a. Il faut aussi surveiller que i>a, g<c et g<a

L'astuce du programme consite à effectuer ces test dans l'ordre et sans perdre de temps. Dès qu'un des nombre est impssible, on teste le c suivant.

Et si l'on arrive au dernier c possible, on boucle sur b puis sur a.

Avec un tel algorithme, sans compiler le programme, un ordinosaure 8bits à 2 MHz de 1982 met environ 1h30 pour imprimer les carrés.

Par contre j'ai une question qui concerne les répétition. En autorisant (une fois) la répérition des nombre premier, pourquoi je n'obtient pas plus de carré magique. Alors que le même programme, en autorisant deux fois chaque répétition produit une quasi infinité de carré magique contenant trois fois chaque nombre premier ?

Question un peu bête. Mais je n'en trouve pas la raison ? Alors qu'avec d'autre nombre (que les nombres premiers), on peut trouver bien plus de solutions en autorisant (même une seule fois) les répétitions!?!

par **chan79** » 18 Sep 2012, 18:25

C.Ret a écrit:Ben oui, on m'avais expliqué qu'un nombre premier n'avait pas d'autre facteur que 1 et lui-même.
C'est bien le cas avec 1, qui n'a pas d'autre facteur que lui-même et 1.
Mais, bon à chaque époque ses modes.

Voici les carrés magiques constitués de nombre premiers (donc sans le 1), inférieurs à 200, sans répétition:

Code: Tout sélectionner
Idt Sd Sv ShSa SaSh Sh Sa SvSh S= 177 17 89 71 17 113 47 71 89 17 71 5 101 47 113 17 47 29 101 101 5 71 101 29 47 113 59 5 89 59 29 5 59 113 89 59 29 29 59 89 113 59 5 29 59 89 5 59 113 47 29 101 71 5 101 101 29 47 17 113 47 101 5 71 17 89 71 47 113 17 71 89 17 S= 267 29 131 107 29 167 71 107 131 29 107 11 149 71 167 29 71 47 149 149 11 107 149 47 71 167 89 11 131 89 47 11 89 167 131 89 47 47 89 131 167 89 11 47 89 131 11 89 167 71 47 149 107 11 149 149 47 71 29 167 71 149 11 107 29 131 107 71 167 29 107 131 29 S= 219 37 79 103 37 139 43 103 79 37 103 7 109 43 139 37 43 67 109 109 7 103 109 67 43 139 73 7 79 73 67 7 73 139 79 73 67 67 73 79 139 73 7 67 73 79 7 73 139 43 67 109 103 7 109 109 67 43 37 139 43 109 7 103 37 79 103 43 139 37 103 79 37 S= 213 41 89 83 41 113 59 83 89 41 83 29 101 59 113 41 59 53 101 101 29 83 101 53 59 113 71 29 89 71 53 29 71 113 89 71 53 53 71 89 113 71 29 53 71 89 29 71 113 59 53 101 83 29 101 101 53 59 41 113 59 101 29 83 41 89 83 59 113 41 83 89 41 S= 309 43 127 139 43 199 67 139 127 43 139 7 163 67 199 43 67 79 163 163 7 139 163 79 67 199 103 7 127 103 79 7 103 199 127 103 79 79 103 127 199 103 7 79 103 127 7 103 199 67 79 163 139 7 163 163 79 67 43 199 67 163 7 139 43 127 139 67 199 43 139 127 43 Matrice non première: S= 111 7 61 43 7 73 31 43 61 7 43 1 67 31 73 7 31 13 67 67 1 43 67 13 31 73 37 1 61 37 13 1 37 73 61 37 13 13 37 61 73 37 1 13 37 61 1 37 73 31 13 67 43 1 67 67 13 31 7 73 31 67 1 43 7 61 43 31 73 7 43 61 7

La méthode est simple, elle consiste dans un premier temps à dresser la liste des nombres premiers inférieur à 200.

Ensuite, c'est une recherche un peu bête à partir de trois de ces nombres premiers, sans le 2 tout de même.

En effet, tous les nombres premiers, sauf 2, sont impairs. Comme on fait une somme à trois nombre dans les carré 3x3, la somme magique est nécessairement impaire (impair+impair = pair et impair + pair = impair).

Donc, si l'on incorpore 2, on a un problème de parité, il n'y aura aucun carré magique 3x3 contenant le nombre premier 2.

Ensuite, il y a donc 45 premiers à "tester", je le fais par ordre croissant.
Pour éviter de compter deux fois les mêmes carrés, j'impose c>a.

Le carré est donc de la forme :
[ a b c ]
[ d e f ]
[ g h i ]
avec S = a+b+c

Comme je ne dispose que d'un Commodore C128D ( 128ko - 2 MHz - 8bits ) pour faire le travail je vais utiliser un minimum de boucles (trois en fait).

AU début de l'analyse, je penser en faire une quatrième sur e. Mais c'est inutile.

COnsidérons que les varaible sont a,b,c et e.

A chaque itération de ma recherche de solution, je peux calculer à partir de a,b,c et e les autres "cases du carré" :

On a : S= a+e+i
Donc on peut exprimer i en fonction de S,a et e
i = S - a - e

De même pour les autres case de la ligne inférieure :
g = S - c - e
h = S - b - e
i = S - a - e

Ma première idée était donc de calculer ainsi g h i pour chaque quadruplet { a b c e }

Mais, on sait que
S = g + h + i
S = S - c - e + S - b - e + S - a - e
S = S - (a+b+c) + 3.e

Or a+b+c=S, on a donc :
S = S - S + 3.e

En fait, il ne sert à rien de chercher les valeur de e, il faut juste prendre a b et c de telle façon que S=a+b+c soit un multiple de trois d'un des nombre premiers e.

C'est donc c que fait mon modeste programme, en BASIC qui tourne sur une machine qui a déjà fêté ses 31 ans de loyaux services.

Deux boucles sur a et b sélectionne séquentiellement les nombre premiers.
Un boucle supplèmentaire permet de retenir les c tel que e = S/3 = (a+b+c)/3 soit des nombre premier.

On a alors les quatres varaibles a b c et e

Le programme calcule alors successivement i h g d et f dans cet ordre et en passant au c suivant dès que l'un des calculs donne un nombre :
- qui n'est pas un des nombre premier possible
- qui est déjà utilisé dans le carré
- qui produit un carré symétrique. En particulier, par construction je prends toujours c>a. Il faut aussi surveiller que i>a, g<c et g<a

L'astuce du programme consite à effectuer ces test dans l'ordre et sans perdre de temps. Dès qu'un des nombre est impssible, on teste le c suivant.
Et si l'on arrive au dernier c possible, on boucle sur b puis sur a.

Avec un tel algorithme, sans compiler le programme, un ordinosaure 8bits à 2 MHz met environ 1h30 pour imprimer les carrés.

oui, j'ai fait comme ça, grosso modo.
Ca n'en fait donc que 5 vraiment différents ( fameuse division par 8)
En prenant les inférieurs à 300, j'arrive à 15.

par **Deliantha** » 18 Sep 2012, 18:31

C.Ret a écrit:Avec un tel algorithme, sans compiler le programme, un ordinosaure 8bits à 2 MHz met environ 1h30 pour imprimer les carrés.

C.Ret, la démonstration vaut son pesant et valide l'usage de l'informatique calculatoire en tant qu'aide.

Revenons à la théorie, devant nous permettre de converger vers la résolution de carrés de carrés 3X3.

M3 est un sous ev. des matrices réelles 3X3, sous la forme : H=aU+bV+cW où {U,V,W} est une base.

Les formules génériques de Lucas en définissent l'ensemble des valeurs possibles avec leurs équations.

par **LeJeu** » 18 Sep 2012, 19:29

Deliantha a écrit:C.Ret, la démonstration vaut son pesant et valide l'usage de l'informatique calculatoire en tant qu'aide.

Revenons à la théorie, devant nous permettre de converger vers la résolution de carrés de carrés 3X3.

M3 est un sous ev. des matrices réelles 3X3, sous la forme : H=aU+bV+cW où {U,V,W} est une base.

Les formules génériques de Lucas en définissent l'ensemble des valeurs possibles avec leurs équations.

Très cher Deliantha,

Je pense qu tu as mal lu C.ret, il pose comme dans Lucas
A = a+b
B = a-b-c
C = a+c
pour arriver à la casez centrale a = (A+B+C )/3

Mais pour le cas qui nous concerne, c'est mieux car il peut attaquer en choisissant A B C premiers, c'est un départ particulièrement adapté au problème

Donc l'informatique avait bien embarqué la théorie ... .

Sinon en plus C-Ret donne le résultat, je veux dire le bon :-)

par **Deliantha** » 19 Sep 2012, 09:24

LeJeu a écrit:
Donc l'informatique avait bien embarqué la théorie ... .

Sinon en plus C-Ret donne le résultat, je veux dire le bon

Enterrons la solution avant l'heure si on y tient, mais le problème vieux de 200 ans demeure ouvert..-:)

par **beagle** » 19 Sep 2012, 09:53

Le Jeu dit c'est bon pour C.Ret sur Chan's problem.
Et Deliantha à l'origine du fil, reviens à la charge sur:
"Revenons à la théorie, devant nous permettre de converger vers la résolution de carrés de carrés 3X3."

Je suis hors jeu sur un tel problème,
j'ai pas les notions de maths pour bidouiller à la main,
j'ai pas les notions d'informatique pour bidouiller un programme,
et je n'ai pas non plus les deux ensemble.
Mais Deliantha met la barre un peu haut, c'est pas les problèmes pour s'initier.M'enfin!

par **Alannaria** » 19 Oct 2012, 01:46

Quelqu'un s'est-il amusé à dénicher ou dériver ses carrés de carrés (non) magiques d'ordre n=3 (et plus) ?

Des carrés magiques : un problème vieux de plus de 200 ans

Des modèles de carrés

Mes carrés de carrés au cube et à l'hypercube étendus...

Aux carrés d'as censeurs...

Qui est en ligne