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

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.

Article lu   fois.

L'auteur

Liens sociaux

Viadeo Twitter Facebook Share on Google+   

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 2 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 2 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 tout 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 colonne s 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
Sélectionnez

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
Sélectionnez

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()
Sélectionnez

<?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
Sélectionnez

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
Sélectionnez

<?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 3 277 lignes dans la table `couplesab` et 300 lignes, tout rond, dans la table `premiers`

VI. Liste des sommes possibles selon Madame S (de 3 277 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 tout 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
Sélectionnez

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
Sélectionnez

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 colonne s 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
Sélectionnez

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 colonne s 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 toutes façons, 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.

Vous avez aimé ce tutoriel ? Alors partagez-le en cliquant sur les boutons suivants : Viadeo Twitter Facebook Share on Google+   

  

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.