Résoudre une énigme arithmétique à l'aide de PHP et MySQL

Maljuna Kris, à Raf qui n'était point sotte

Ne dit-on pas d'une quête incertaine et harassante : «c'est comme chercher une aiguille dans une botte de foin» ? Si l'esprit humain sait se montrer performant pour déduire et extrapoler, il s'épuise en revanche assez rapidement dans les dénombrements et les appariements. Ce n'est pas le cas du SGBD lequel, en outre, bat l'humain à plates coutures dès qu'il s'agit de s'attaquer à des séries dépassant quelques dizaines d'unités. On voit ici comment, mises en synergie, une once d'ingéniosité du codeur et les extraordinaires capacités du SGBD viennent aisément à bout d'un casse-tête a priori abscons. ♪

- Titre : Résoudre une énigme arithmétique à l'aide de PHP et MySQL

- Auteur : Maljuna Kris, à Raf qui n'était point sotte

- Parution : 3 mai 2009

- Mise à jour : 11 mai 2009

- Licence : Copyright ® 2009 Maljuna Kris. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.

Sommaire

- I. Énoncé de l'énigme

- II. Reformulation de l'énoncé de l'énigme

- III. PHP et MySQL à la rescousse

- IV. Nombres premiers

- V. Alimentons les deux tables

- VI. Liste des sommes possibles selon Madame S (de 3277 lignes à 11 lignes)

- VII. Suppression des produits non UNIQUEs (de 11 lignes à 51 lignes)

- VIII. La solution (de 51 lignes à 1 seule ligne)

- IX. Conclusion

I - Énoncé de l'énigme

On donne à Monsieur P la valeur du produit de deux entiers positifs a,b compris dans l'intervalle 2 à 99, bornes incluses [2-99].
On donne à Madame S la valeur de la somme de ces deux mêmes entiers positifs.
On leur demande, sans se communiquer ces valeurs, de découvrir a et b.
Chacun sait la nature de l'information détenue par l'autre, et tous deux sont d'émérites logiciens.

- Monsieur P : - Je ne peux pas déterminer ces deux nombres avec ces seules informations.

- Madame S : - Je le savais.

- Monsieur P : - Alors, je connais a et b.

- Madame S : - Du coup, moi aussi.

Et vous, saurez-vous découvrir a et b avec ces seuls indices ?

II - Reformulation de l'énoncé de l'énigme

a et b ont donc, chacun, une valeur comprise dans l'intervalle 2 à 99, bornes incluses. Dans l'absolu, ils peuvent même être égaux.
Si la connaissance de leur produit P ne permet pas de déterminer ces deux entiers, on en déduit que P n'est pas le produit de deux nombres premiers.
Le fait que Madame S dise qu'elle avait déjà pu le déduire de la connaissance de leur somme S implique que l'on élimine toutes les sommes paires, et, partant, que a != b (a+a est toujours pair puisque a+a=a x 2).
Je vous sens dubitatifs. Connaissez-vous les termes de la conjecture de Goldbach ?
Tout nombre entier pair strictement supérieur à 2 peut être écrit comme la somme de deux nombres premiers (le même nombre premier pouvant être utilisé deux fois).
De ces premières déductions il apparaît qu'on doit pouvoir dresser la liste exhaustive des sommes S impaires que l'on peut obtenir en additionnant deux nombres, non tous deux premiers, de l'intervalle [2-99],et, pour chaque item de cette liste, la liste des produits que fournirait chaque couple {a,b} permettant de former la somme S.
En poussant la réflexion, on s'aperçoit que l'on doit aussi supprimer toutes les lignes qui retournent une somme supérieure à 57.
Pourquoi ?
Parce que si S est compris entre 57 et 153 (57 <= S <= 153) alors S peut s'écrire 53 + n, avec 4 <= n <= 100.
Et si S est compris entre 155 et 197 (155 <= S <= 197) alors S peut s'écrire 97 + n, avec 58 <= n <= 100.
97 et 53 étant des nombres premiers les produits 53 x n et 97 x n auraient une décomposition unique.
Vous souhaitez vous y atteler ?
Libre à vous. Elle commence comme suit :

- 11 : 18(2x9) 24(3x8) 28(4x7) 30(6x5)

- 17 : 30(2x15) 42(3x14) 52(4x13) 60(5x12) 66(6x11) 70(7x10) 72(8x9)

- 23 : 42(2x21) 60(3x20) 76(4x19)…….

Cela devient vite fastidieux, n'est-ce pas ?
D'autant qu'en suivant le raisonnement qui découle de l'échange de nos logiciens, puisque Monsieur P dit «alors, je connais a et b», on peut en déduire que le produit P n'apparaît qu'une seule fois dans la liste que nous venons de décrire.
Il nous faudrait donc expurger de cette liste les P : 30, 42, 60 … De nouveau bien fastidieux, n'est-il pas vrai ?
Alors la liste ne comporterait plus qu'une seule somme à laquelle ne correspondrait qu'un produit, ce qui permet à Madame S d'affirmer «du coup, moi aussi.»
Et si nous demandions de l'aide à l'informatique ?

III - PHP et MySQL à la rescousse

On se propose de créer, dans une base de données `ps` une table contenant deux colonnes a et b, afin d'y ranger la population des couples a,b de l'intervalle [2-99], sans doublons, et où a != b.

La table couplesab

CREATE TABLE `couplesab` (
`a` tinyint(2) NOT NULL,
`b` tinyint(2) NOT NULL,
PRIMARY KEY (`a`,`b`),
) ENGINE=MyISAM

Mais nous aurons aussi besoin d'une table contenant tous les couples premiers de l'intervalle [2-99], sans doublons, et où a != b.

La table premiers

CREATE TABLE IF NOT EXISTS `premiers` (
`pa` tinyint(2) NOT NULL,
`pb` tinyint(2) NOT NULL,
PRIMARY KEY (`pa`,`pb`)
) ENGINE=MyISAM;

Pour le remplissage des tables, on va se faire aider par PHP.
Hélas, on commence par découvrir que PHP ignore la notion de nombre premier. Au demeurant, à ma connaissance, les tableurs également.
Qu'à cela ne tienne, on va la lui enseigner.

IV - Nombres premiers

Un nombre premier peut se définir comme un nombre qui ne peut se décomposer en d'autres facteurs que lui-même et 1.
En d'autres termes, si l'on ne découvre pas de diviseur entier pour n dans l'intervalle [2 racine carré n], on peut en conclure que n est un nombre premier.
Admettez cela comme un postulat, si on atteint la racine carrée d'un nombre entier sans avoir trouvé de diviseur entier à ce nombre, on n'en trouvera plus jusqu'à ce nombre.

Fonction estpremier()

<?php
function estPremier($n){
$n +=0;
if($n < 4){return true;} // 2 et 3 sont premiers
elseif(($n % 2)==0){return false;} //nombre pair
else{
$div = 1;
while (($div+=2) <= sqrt($n)){// on saute les diviseurs pairs,
// parenthèses pour forcer la précédence des opérateurs
if (fmod($n,$div)==0){return false;}// on a trouvé un diviseur
}
return true;// on n'a pas trouvé de diviseur
}
}
?>

D'aucuns objecteront que ce code est optimisable, mais, dans le cadre qui nous occupe, il devrait suffire.

V - Alimentons les deux tables

On va profiter des possibilités de PHP pour se simplifier la vie en veillant à ne pas créer de doublons et à respecter la règle a != b
D'autre part on va utiliser la syntaxe MySQL :

Requête d'insertion

INSERT INTO Nom_de_table VALUES (a,b),(a&#185;,b&#185;),(a&#178;,b&#178;),....(an,bn)

pour ne soumettre que deux requêtes d'insertion.

Script d'insertion

<?php
$values=null;$prems=null; //initialisation des buffers pour les requêtes
$as=range(2,99);$bs=$as; //autant faire faire le travail par php
foreach($as as $a){
foreach($bs as $b){
if(($a%2==0)&&($b%2)==0){}// sauter les paires de pairs
elseif(estPremier($a)&& estPremier($b)){
if($a<$b){$prems .= "($a,$b)\n, ";}
}
elseif($a<$b){$values .= "($a,$b)\n, ";} // pour assurer a <> b
}
}
$values=substr($values,0,-2);
$prems=substr($prems,0,-2);//supprime les virgules finales

$connect=mysql_connect("localhost","root","");// on est sur un WAMPSERVER
$db=mysql_select_db('ps',$connect);/* juste un préalable,
avoir créé les tables décrites précédemment dans une base de données `ps`*/
$sql="INSERT IGNORE INTO `couplesab` VALUES\n $values";
$res=mysql_query($sql) or die(mysql_error()."<br />$sql");
$sql="INSERT IGNORE INTO `premiers` VALUES\n $prems";
$res=mysql_query($sql) or die(mysql_error()."<br />$sql");
?>

Nous nous retrouvons avec 3277 lignes dans la table `couplesab` et 300 lignes, tout rond, dans la table `premiers`

VI - Liste des sommes possibles selon Madame S (de 3277 lignes à 11 lignes)

Tâchons de demander à MySQL la liste exhaustive des sommes S impaires que l'on peut obtenir en additionnant deux nombres, non tous deux premiers, de l'intervalle [2-99], de somme S < 57 et, pour chaque item de cette liste, la liste des produits que fournirait chaque paire a,b permettant de former la somme S.

Liste exhaustive des sommes S

SELECT
DISTINCT a + b AS S,
GROUP_CONCAT(CONCAT(a*b,'(',a,'x',b,')') ORDER BY a*b) AS Ps
FROM `couplesab`
LEFT JOIN premiers ON pa+pb = a+b
WHERE pa IS NULL
AND MOD(a+b,2) <>0
AND a+b < 57
GROUP BY S
ORDER BY S;

On remarquera l'utilisation d'une jointure externe LEFT JOIN, couplée avec un filtre [ WHERE pa IS NULL ] qui permet d'éliminer les sommes qui pourraient s'obtenir avec deux nombres premiers.

On s'assure aussi de ne récupérer de sommes impaires en testant l'application de la fonction Modulo 2 à chaque a+b.

Et l'on obtient les 11 lignes qui suivent :

S

Ps

11

18(2x9),24(3x8),28(4x7),30(5x6)

17

30(2x15),42(3x14),52(4x13),60(5x12),66(6x11),70(7x10),72(8x9)

23

42(2x21),60(3x20),76(4x19),90(5x18),102(6x17),112(7x16),120(8x15),126(9x14),130(10x13),132(11x12)

27

50(2x25),72(3x24),92(4x23),110(5x22),126(6x21),140(7x20),152(8x19),162(9x18),170(10x17),176(11x16),180(12x15),182(13x14)

29

54(2x27),78(3x26),100(4x25),120(5x24),138(6x23),154(7x22),168(8x21),180(9x20),190(10x19),198(11x18),204(12x17),208(13x16),
210(14x15)

35

66(2x33),96(3x32),124(4x31),150(5x30),174(6x29),196(7x28),216(8x27),234(9x26),250(10x25),264(11x24),276(12x23),286(13x22),
294(14x21),300(15x20),304(16x19),306(17x18)

37

70(2x35),102(3x34),132(4x33),160(5x32),186(6x31),210(7x30),232(8x29),252(9x28),270(10x27),286(11x26),300(12x25),312(13x24),
322(14x23),330(15x22),336(16x21),340(17x20),342(18x19)

41

78(2x39),114(3x38),148(4x37),180(5x36),210(6x35),238(7x34),264(8x33),288(9x32),310(10x31),330(11x30),348(12x29),364(13x28),
378(14x27),390(15x26),400(16x25),408(17x24),414(18x23),418(19x22),420(20x21)

47

90(2x45),132(3x44),172(4x43),210(5x42),246(6x41),280(7x40),312(8x39),342(9x38),370(10x37),396(11x36),420(12x35),442(13x34),
462(14x33),480(15x32),496(16x31),510(17x30),522(18x29),532(19x28),540(20x27),546(21x26),550(22x25),552(23x24)

51

98(2x49),144(3x48),188(4x47),230(5x46),270(6x45),308(7x44),344(8x43),378(9x42),410(10x41),440(11x40),468(12x39),494(13x38),
518(14x37),540(15x36),560(16x35),578(17x34),594(18x33),608(19x32),620(20x31),630(21x30),638(22x29),644(23x28),648(24x27),
650(25x26)

53

102(2x51),150(3x50),196(4x49),240(5x48),282(6x47),322(7x46),360(8x45),396(9x44),430(10x43),462(11x42),492(12x41),520(13x40),
546(14x39),570(15x38),592(16x37),612(17x36),630(18x35),646(19x34),660(20x33),672(21x32),682(22x31),690(23x30),696(24x29),
700(25x28),702(26x27)

Ce qui est assez copieux et nécessite que l'on supprime les produits non UNIQUEs.

VII - Suppression des produits non UNIQUEs (de 11 lignes à 51 lignes)

Petite difficulté, les produits, a*b, ne peuvent être comptés avant d'avoir été calculés par la requête.
C'est là que la définition de l'acronyme SQL va prendre tout son sens.
The Structured Query Language, comme son nom ne l'indique pas forcément, permet l'imbrication des requêtes les unes dans les autres.
C'est la notion de sous-requête qui est sous-entendue dans cette structuration. Une requête peut s'appuyer sur le résultat d'une requête qu'elle inclut, et ce sur plusieurs niveaux éventuellement.

Suppression des produits non UNIQUEs

SELECT e1.P,e1.S,e1.a,e1.b
FROM (
SELECT DISTINCT a,b, a + b AS S, a*b AS P
FROM `couplesab`
LEFT JOIN premiers ON pa+pb = a+b
WHERE pa IS NULL
AND MOD(a+b,2) <> 0
AND (a+b) < 53) AS e1
)
GROUP BY e1.P
HAVING COUNT(e1.P)= 1;

L'absence des colonnes e1.a et e1.b dans la clause GROUP BY n'est pas problématique ici, HAVING COUNT(e1.P)= 1 assurant l'unicité des lignes récupérées.

Comme on n'a pas pu, simultanément, compter les produits et les regrouper par somme, le nombre de lignes repasse à 51.

P

S

a

b

18

11

2

9

24

11

3

8

28

11

4

7

50

27

2

25

52

17

4

13

54

29

2

27

76

23

4

19

92

27

4

23

96

35

3

32

98

51

2

49

100

29

4

25

112

23

7

16

124

35

4

31

140

27

7

20

144

51

3

48

148

41

4

37

152

27

8

19

160

37

5

32

172

47

4

43

176

27

11

16

188

51

4

47

208

29

13

16

216

35

8

27

230

51

5

46

232

37

8

29

234

35

9

26

238

41

7

34

246

47

6

41

250

35

10

25

280

47

7

40

288

41

9

32

304

35

16

19

308

51

7

44

336

37

16

21

344

51

8

43

348

41

12

29

400

41

16

25

414

41

18

23

418

41

19

22

442

47

13

34

468

51

12

39

494

51

13

38

496

47

16

31

510

47

17

30

518

51

14

37

578

51

17

34

608

51

19

32

620

51

20

31

638

51

22

29

644

51

23

28

650

51

25

26

Mais pourquoi se contenter d'un seul niveau d'imbrication ?

VIII - La solution (de 51 lignes à 1 seule ligne)

En effet, SQL permet de faire une requête qui s'appuie sur le résultat de la requête précédente.

La solution

SELECT e2.S,e2.P,e2.a,e2.b
FROM (
SELECT e1.P,e1.S,e1.a,e1.b
FROM (
SELECT DISTINCT a + b AS S, a*b AS P,a,b
FROM `couplesab`
LEFT JOIN premiers ON pa+pb = a+b
WHERE pa IS NULL
AND MOD(a+b,2) <>0
AND (a+b) < 53) AS e1)
GROUP BY e1.P
HAVING COUNT(e1.P)= 1) as e2)
GROUP BY e2.S
HAVING COUNT(e2.P)=1;

Et nous obtenons, comme par magie, la ligne suivante :

S

P

a

b

17

52

4

13

IX - Conclusion

On aura compris que cette énigme éculée ne constituait qu'un prétexte à une présentation de certaines pratiques, en PHP et en MySQL. Pratiques qui, pour être basiques, n'en constituent pas moins des repoussoirs pour certains débutants qui se tourneront plus volontiers vers les tableurs pour tenter de résoudre ce genre de problèmes.
On a ainsi vu comment générer automatiquement, en PHP, une plage de valeurs dans un tableau mémoire [array] avec la fonction range() et comment parcourir ces mêmes tableaux avec la structure foreach().
Nous avons utilisé la possibilité de créer un index UNIQUE sur deux colonnes en MySQL, la syntaxe d'INSERT multiple [INSERT IGNORE Nom_de_table VALUES (a,b),(a¹,b¹),(a²,b²),….(an,bn)], IGNORE rejetant les lignes qui enfreindraient les contraintes d'intégrité, d'unicité d'index par exemple, mais insérant les autres lignes.
L'utilisation de DISTINCT pour éviter de générer des doublons dans une requête. Rappelons que la notion de doublon, pour DISTINCT, concerne la totalité du n-uplet et non pas la seule colonne qu'il précède. SELECT DISTINCT nom, prenom FROM la_table ne retournera qu'un seul DUPONT Michel, mais retournera aussi DUPONT Henri. Alors que SELECT DISTINCT nom FROM la_table ne retournera qu'un seul DUPONT.
On a vu une utilisation de la fonction GROUP_CONCAT() qui est à CONCAT() ce que SUM() est à l'opérateur +, et l'on aura remarqué sa possibilité de classement interne avec son propre ORDER BY.
La réalisation de la différence relationnelle en couplant une jointure externe LEFT JOIN et un filtre de nullité sur la colonne de jointure LEFT JOIN premiers ON pa+pb = a+b WHERE pa IS NULL nous permettant d'éliminer tous les couples {a,b} dont la somme peut s'obtenir avec deux nombres premiers.
Enfin, l'imbrication des requêtes a permis de décomposer la problématique par niveaux, chaque couche utilisant les résultats de la couche précédente pour nous faire progresser vers la solution de l'énigme.
J'espère, abstraction faite des quelques notions mathématiques utilisées, auxquelles on aurait dû recourir de toute façon, que le côté ludique aura permis à quelques-uns de s'accrocher et de découvrir à quel point tout ceci est, avec MySQL, d'une simplicité enfantine et que cela aura pu susciter le goût de transposer ces techniques sur d'autres problématiques.