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

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 ?

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 ?

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.

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.

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.

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.

<?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.

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 :

INSERT INTO Nom_de_table VALUES (a,b),(a¹,b¹),(a²,b²),....(an,bn)

pour ne soumettre que deux requêtes 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`

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.

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;

Et l'on obtient les 11 lignes qui suivent :

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

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.

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;

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

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

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 :

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.