# Problème des quatre quatre

Le problème des quatre quatre, parfois appelé « puzzle des quatre quatre », est un problème récréatif arithmétique : « Quels sont les entiers naturels que l'on peut écrire en utilisant quatre fois le chiffre quatre et les opérations usuelles ? »

## Genèse

Le jeu est mentionné pour la première fois dans l'ouvrage Knowledge: An Illustrated Magazine of Science édité en 1881 par Richard A. Proctor, un astronome anglais réputé pour avoir dressé une des premières cartes de la planète Mars.
Dans son livre Mathematical Recreations and Essays, W. W. Rouse Ball en donne en 1892 une description précise et le présente comme un « amusement mathématique, qui aurait été proposé pour la première fois en 1881 ».

## Règles

Plusieurs variantes du jeu existent, selon les symboles mathématiques qu’on s’autorise, sachant que toutes acceptent bien sûr l’addition (« + »), la soustraction (« − »), la multiplication (« × »), la division (« ÷ ») et les parenthèses :
* avec quatre fois le nombre 4 et les quatre opérations élémentaires, il est possible d'obtenir tous les entiers naturels de 0 à 9, mais il n'est pas possible d'obtenir 10 ni 11 ;
* avec quatre chiffres quatre et concaténation possibles (possibilité d'écrire des nombres formés de chiffres 4 comme « 44 ») le nombre de solutions augmente ;
* avec le recours aux factorielles (« n! »), à la racine carrée (« √ »), aux puissances (comme dans 44$^4$), on peut aller jusqu'à 74 (= 4! + 4! + 4! + √4) ;
* avec la virgule en tête de nombre (,4 = 0,4 = 4/10) et la fonction gamma (Γ, où Γ(n) = (n − 1)!, ainsi Γ(4) = 6), on peut aller bien au-delà.
On accepte parfois la fonction inverse (« 1/n »), la sous-factorielle (notée !n = n!·(1 - 1/1! + 1/2! - 1/3! + 1/4! - ... ±1/n!), la sommation (exemple : $\sum _{i=-{\sqrt {4}}}^{4!}{\frac {4i}{4}}=297$), voire des opérations originales telles que le produit des nombres inférieurs de même parité ("n!!", par exemple 9!! = 9x7x5x3x1) ou la somme des nombres inférieurs ("n?", par exemple 4? = 4+3+2+1). La répétition à l'infini de la décimale 4 peut être acceptée ou non : ",${\overline {4}}$" (pour 0,4444… = 4/9).
En revanche l’opérateur logarithme n’est pas autorisé, car on peut systématiquement exprimer n'importe quel entier par la formule suivante :
    $n=-{\sqrt {4}}{\frac {\ln \left[\left(\ln \underbrace {\sqrt {\sqrt {\cdots {\sqrt {4}}}}} _{n}\right)/\ln 4\right]}{\ln {4}}}$

## Solutions

Voici des exemples de solutions pour les 23 premiers entiers naturels, en utilisant des règles classiques. Pour chacun, il existe de nombreuses solutions correctes. Les expressions en bleu s'obligent à ne faire appel qu’à quatre entiers 4 (plutôt que quatre chiffres 4) et aux opérations arithmétiques élémentaires. Celles en italique recourent plusieurs fois au même opérateur.
Il est particulièrement difficile de résoudre certains nombres. Ainsi, pour 113, David A. Wheeler a suggéré :
    $\Gamma (\Gamma (4))-{\frac {4!+4}{4}}$
Autre exemple d'utilisation de la fonction gamma : 157 = ((Γ(4)!+4) ÷ 4) - 4!.
Accepter d’utiliser le pourcentage ("%") dans les formules — notamment au dénominateur — permet d’accéder à un ensemble bien plus vaste de nombres. Par exemple : 113 = (√4 + (√4 + 4!)%) ÷ (√4)%.

## Résolution algorithmique

Le problème et ses généralisations (cinq 5, six 6, etc.) peuvent être résolus par un algorithme simple, qui fait appel à des tables reliant entiers naturels et expressions à base du chiffre choisi. Une telle table existe pour chaque nombre n d’occurrences de d. Par exemple, si d=4, la table pour deux occurrences de d contiendra notamment la paire (8 ; 4+4) ; celle pour trois occurrences de d contiendra la paire (2 ; (4+4)/4), etc. Les tables pour n=1 et n=2 contiennent les formules élémentaires, qui ne sont pas la combinaison de formules plus petites. Ainsi, pour n=1 :
et pour n=2 :
La tâche consiste alors à se référer par récurrence à ces tables, en partant de n=1 jusqu’à dans notre exemple n=4. Pour un n donné, on construit la table en recensant les combinaisons pertinentes de formules plus petites.

## Variantes
### Extrait de la table des solutions au problème des six 6

La notation ,6... représente ici le nombre 2/3, avec 6 en décimale récurrente.

### Autres puzzles similaires

On peut concevoir d’autres variantes du jeu en remplaçant le quatuor de 4 par tout autre ensemble de chiffres, par exemple ceux qui composent une année de naissance : 1, 9, 6 et 5 pour 1965.