Recherche · Théorie des nombres · complexité entière

Complexité entière de 2⁶¹ − 1 : une expression à 127 occurrences de 1

Cette page présente un travail de recherche en théorie des nombres : une expression qui n’utilise que le chiffre 1, l’addition et la multiplication, et qui vaut exactement 2⁶¹ − 1, le nombre premier de Mersenne M61, avec seulement 127 occurrences de 1. Elle montre l’énoncé exact, le paysage des valeurs publiques, puis l’expression en entier, avec un juge extérieur, un second chemin et un programme court que chacun exécute pour la revérifier.

1. Le problème

La complexité entière d’un entier n, notée ‖n‖, est le plus petit nombre de 1 nécessaires pour l’écrire à l’aide des seules additions, multiplications et parenthèses. Ainsi ‖6‖ = 5, car 6 = (1+1)×(1+1+1) et rien de plus court ne convient. Aucun algorithme efficace n’en est connu : les valeurs se calculent par programmation dynamique exhaustive, qui devient impraticable bien avant les nombres en jeu ici.

La cible du tableau, en anglais : « Find an expression for N using fewer than 150 1’s », avec N = 2^61 - 1 = 2 305 843 009 213 693 951, le nombre premier de Mersenne M61. Étant premier, N n’a aucune factorisation à exploiter : toute expression doit le construire par additions, ce qui fait la difficulté du problème. Le contrôle du tableau (check.py) analyse l’expression avec un petit analyseur syntaxique dédié (pas de eval), vérifie qu’elle ne contient que les caractères 1, +, *, des parenthèses et des espaces, qu’elle vaut exactement N, et compte ses occurrences de 1 ; ce nombre, s’il est inférieur à 150, est le score. Source : github.com/math-market/integer-complexity-m61, fichier TASK.md, lu le 13/10/2026 ; le tableau et son contrôle sont publiés sous licence Apache-2.0.

Les deux nombres du problème ont des origines différentes. 150 est le coût d’une expansion de Horner en base 32767 : le tableau le publie pour qu’on sache exactement quoi battre, et précise explicitement que ce n’est pas un record. 115,5 est une borne que nul ne peut franchir par en dessous : toute expression à k occurrences de 1 vaut au plus 3^k/3, donc ‖N‖ ≥ 3 log₃ N ≈ 115,51, soit au moins 116 occurrences de 1 (borne de Selfridge, rappelée par R. K. Guy, Unsolved Problems in Number Theory, section F26). L’écart entre 116 et 150 est le terrain du tableau.

2. Le paysage public

Le tableau réunit les deux repères publics du problème : une borne théorique que nul résultat ne peut franchir, et un repère pratique publié par le tableau. Ce sont les bornes entre lesquelles se situe le terrain de recherche.

Lectures du 13/10/2026 : tableau math-market/integer-complexity-m61 (README, TASK.md, check.py, baseline.txt, LICENSE, pull request n° 4, liste des pull requests), OEIS A005245, arXiv:1207.4841, arXiv:1404.2183.

La complexité entière est répertoriée dans OEIS A005245 (« the (Mahler-Popken) complexity of n »), avec les 20 premières valeurs (1, 2, 3, 4, 5, 5, 6, 6, 6, 7, 8, 7, 8, 8, 8, 8, 9, 8, 9, 9…), calculées par programmation dynamique exhaustive pour les petits entiers. Pour N = 2⁶¹ − 1, cette approche directe est hors d’atteinte : les meilleurs algorithmes connus calculent toutes les complexités jusqu’à un seuil M en un temps de l’ordre de M^1,23 (Arias de Reyna et van de Lune, arXiv:1404.2183, section 4), bien au-delà de ce qu’aucune machine ne peut parcourir pour M = 2⁶¹ − 1. Altman et Zelinsky (arXiv:1207.4841) étudient les entiers dont la complexité est proche de la borne de Selfridge et montrent, pour des nombres de la forme 2^m3^k, une égalité exacte ‖2^m3^k‖ = 2m + 3k pour m ≤ 21 ; N = 2⁶¹ − 1 n’est pas de cette forme (c’est un nombre premier), et ces méthodes ne s’y appliquent pas directement.

Aux lectures du 13/10/2026, aucune des sources citées ne donne la valeur exacte de ‖2⁶¹ − 1‖ : elle est seulement connue à être comprise entre 116 et 150. 127 n’est ni une borne publiée ni une valeur exacte établie ; c’est le résultat de cette page, à l’intérieur de cet intervalle.

3. Le résultat

L’expression ci-dessous n’utilise que le chiffre 1, les opérateurs + et *, et des parenthèses ; elle compte 127 occurrences de 1 et vaut exactement N, donc ‖N‖ ≤ 127.

L’expression est publiée en entier. Le fichier au format du tableau est intcomplexity_m61_expression.json (689 octets, 671 caractères dans l’expression).

(((((1+1)+1))*(((((1+1)+1))*((((1+1))*((((((1+1))*(((1+1)+1))+1))*((((((1+1)+1))*((((1+1))*((((1+1))*((((1+1))*((((1+1))*((((1+1))*((((1+1))*((((((1+1))*(((1+1))*(((1+1))*((((1+1)+1))*(((1+1)+1)))))+1))*((((((1+1))*((((1+1)+1))*(((1+1)+1)))+1))*(((((1+1))*((((1+1))*((((1+1))*((((1+1))*((((1+1))*((((1+1))*((((1+1))*((((1+1))*((((1+1))*((((1+1))*((((1+1))*((((1+1))*((((1+1))*((((1+1))*((((1+1))*(((1+1))*(((1+1))*(((1+1))*((((1+1))*(((1+1))*(((1+1))*(((1+1))*(((1+1))*(((1+1))*(((1+1))*(((1+1))*(((1+1))*(((1+1))*(((1+1))*(((1+1))*(((1+1))*(((1+1))*(((1+1))*(((1+1))*(((1+1))*((1+1))))))))))))))))))+1))))))))))))))))))))))))))))))))))+1)))))))))))))))))))+1)))))))))+1)

Les vérifications

Quatre contrôles, rejoués le 13/10/2026 sur le fichier de l’expression :

Sortie du juge du tableau sur l’expression :

valid: evaluates to 2305843009213693951 using 127 ones
ACCEPTED: 127 < 150 — this improves on the published baseline

Sortie du juge sur l’expression à laquelle « +1 » est ajouté :

REJECTED: expression evaluates to 2305843009213693952, not 2305843009213693951

Revérifier soi-même

Le programme ci-dessous contient l’expression. Il suffit de l’enregistrer dans un fichier verifier_intcomplexity.py et de lancer python verifier_intcomplexity.py : Python 3 suffit, sans aucune bibliothèque à installer. Le programme applique un évaluateur par pile (sans récursion, écrit indépendamment des deux contrôles précédents), compte les occurrences de 1 et rejoue le canari (l’expression à laquelle « +1 » est ajouté doit valoir N + 1, donc ne plus correspondre à N). Version enregistrable : verifier_intcomplexity_fr.py.

# verifier_intcomplexity.py : bibliothèque standard seule ; python verifier_intcomplexity.py
N = 2 ** 61 - 1
BASELINE = 150
ALPHABET = set("1+*() ")

# l'expression de la section 3, telle quelle (caractères 1, +, *, parenthèses, espaces)
EXPR = "(((((1+1)+1))*(((((1+1)+1))*((((1+1))*((((((1+1))*(((1+1)+1))+1))*((((((1+1)+1))*((((1+1))*((((1+1))*((((1+1))*((((1+1))*((((1+1))*((((1+1))*((((((1+1))*(((1+1))*(((1+1))*((((1+1)+1))*(((1+1)+1)))))+1))*((((((1+1))*((((1+1)+1))*(((1+1)+1)))+1))*(((((1+1))*((((1+1))*((((1+1))*((((1+1))*((((1+1))*((((1+1))*((((1+1))*((((1+1))*((((1+1))*((((1+1))*((((1+1))*((((1+1))*((((1+1))*((((1+1))*((((1+1))*(((1+1))*(((1+1))*(((1+1))*((((1+1))*(((1+1))*(((1+1))*(((1+1))*(((1+1))*(((1+1))*(((1+1))*(((1+1))*(((1+1))*(((1+1))*(((1+1))*(((1+1))*(((1+1))*(((1+1))*(((1+1))*(((1+1))*(((1+1))*((1+1))))))))))))))))))+1))))))))))))))))))))))))))))))))))+1)))))))))))))))))))+1)))))))))+1)"
assert set(EXPR) <= ALPHABET

# contrôle 1 : évaluateur par pile (sans récursion), écrit indépendamment du second chemin de la page
def evalue_pile(s):
    nums, ops = [], []

    def appliquer():
        b, a = nums.pop(), nums.pop()
        op = ops.pop()
        nums.append(a + b if op == "+" else a * b)

    i = 0
    while i < len(s):
        c = s[i]
        if c == " ":
            i += 1
        elif c == "1":
            nums.append(1); i += 1
        elif c == "(":
            ops.append("("); i += 1
        elif c == ")":
            while ops[-1] != "(":
                appliquer()
            ops.pop(); i += 1
        elif c in "+*":
            while ops and ops[-1] == "*" and c == "+":
                appliquer()
            ops.append(c); i += 1
        else:
            raise ValueError("caractere hors grammaire : %r" % c)
    while ops:
        appliquer()
    assert len(nums) == 1
    return nums[0]

# contrôle 2, sans rapport avec le contrôle 1 : nombre de 1 dans la chaîne, et validation du jeu de caractères
def compte_un(s):
    return s.count("1")

v1 = evalue_pile(EXPR)
print("N = 2^61 - 1 = %d" % N)
print("valeur == N : %s" % (v1 == N))
print("nombre de 1 : %d" % compte_un(EXPR))

# canari : l'expression à laquelle on ajoute « +1 » doit évaluer à N + 1, donc ne plus correspondre à N
EXPR2 = EXPR + "+1"
v2 = evalue_pile(EXPR2)
print("canari : expression + « +1 » -> valeur == N + 1 : %s ; valeur == N : %s" % (v2 == N + 1, v2 == N))

bon = v1 == N and compte_un(EXPR) < BASELINE and v2 == N + 1 and v2 != N
print(("VÉRIFIÉ : l'expression évalue exactement à N avec %d occurrences de 1 (< %d) ; le canari perd l'égalité à N" % (compte_un(EXPR), BASELINE)) if bon else "ÉCHEC")
raise SystemExit(0 if bon else 1)

Ce programme a été exécuté le 13/10/2026 (Python 3.11.0rc2, python -I) sur l’expression publiée. Sortie obtenue :

N = 2^61 - 1 = 2305843009213693951
valeur == N : True
nombre de 1 : 127
canari : expression + « +1 » -> valeur == N + 1 : True ; valeur == N : False
VÉRIFIÉ : l'expression évalue exactement à N avec 127 occurrences de 1 (< 150) ; le canari perd l'égalité à N

Le programme s’accorde avec le juge du tableau et avec le second chemin ; le canari perd l’égalité à N, comme prévu.

Empreintes sha256

Dépôt public

L’expression est déposée sur le dépôt public du tableau : proposition n° 4 (pull request) de math-market/integer-complexity-m61, ouverte le 02/10/2026. Son fichier a la même empreinte sha256 que le fichier de cette page. État lu le 13/10/2026 : ouverte, non fusionnée, sans commentaire ni relecture ; les trois autres pull requests du dépôt, toutes fermées, portent sur l’infrastructure du tableau (garde du harnais de vérification), non sur des propositions d’expression. L’expression est publiée sous licence Apache-2.0, comme l’exige le tableau pour les soumissions ; le tableau, son énoncé et son contrôle sont eux aussi sous licence Apache-2.0 (LICENSE du dépôt). Aucune donnée tierce n’entre dans l’expression.

4. Ce que modélise cette question

Cette question relève de la théorie des nombres combinatoire : quel est le plus petit nombre de 1 nécessaires pour écrire un entier donné avec seulement l’addition, la multiplication et des parenthèses ? La suite des complexités entières est répertoriée dans OEIS A005245 depuis les travaux de Mahler et Popken (1953) ; Richard Guy en a fait l’une des « suspiciously simple sequences » (American Mathematical Monthly, 1986). Le problème général de calculer ‖n‖ pour un n arbitraire ne dispose d’aucun algorithme efficace connu ; les meilleurs algorithmes exacts calculent toutes les valeurs jusqu’à un seuil M en temps M^α avec α ≈ 1,23 (Arias de Reyna et van de Lune, arXiv:1404.2183), ce qui place un entier de la taille de 2⁶¹ − 1 hors d’atteinte d’un calcul exact.

L’encadrement 3 log₃ n ≤ ‖n‖ ≤ 3 log₂ n est dû à Selfridge et à Coppersmith (rappelé par Guy) ; Joshua Zelinsky a amélioré la borne supérieure générale (arXiv:2211.02995, cité par OEIS A005245). Le tableau math-market/integer-complexity-m61 retient un seuil pratique, 150, pour que le défi soit accessible sans recherche exhaustive, et publie la borne théorique, 116, comme plancher indépassable.

Sources : github.com/math-market/integer-complexity-m61 (README, TASK.md, check.py, baseline.txt, LICENSE, pull request n° 4, liste des pull requests), OEIS A005245, arXiv:1207.4841, arXiv:1404.2183, lus le 13/10/2026.

Un programme de recherche, une épreuve extérieure

Ces résultats couvrent des domaines sans rapport entre eux : la géométrie des empilements (Packomania, Friedman Packing Center), la mécanique spatiale (ESA SpOC 4), la théorie des nombres (IBM Ponder This) et les graphes (FlyWire Codex). Dans chacun, le résultat est inscrit sur la page d’un tiers, table, classement ou liste, et se revérifie par calcul : l’ESA évalue chaque solution avec son simulateur, Packomania publie les entrées qu’il retient, IBM publie une liste de noms, Friedman tient une page qui crédite les auteurs. Ces résultats relèvent d’un même programme de recherche : ne retenir que ce qu’un certificat prouve.

Cette page applique le même principe à un problème de théorie des nombres : une expression dont le texte complet est publié, un juge extérieur qui la vérifie, et un second chemin puis un programme court que chacun exécute pour la revérifier. Ici, le lecteur revérifie lui-même.

Le principe est public : chaque hypothèse est testée par le calcul et n’est retenue que si un certificat la prouve. Des IA génératives me servent d’assistants, interchangeables : elles proposent, mon IA décide, le certificat tranche. Le fonctionnement interne reste confidentiel. Les résultats, eux, sont publics.

Le certificat change la nature de la preuve. Un résultat se vérifie sans faire confiance à celui qui l’a produit, comme une démonstration se vérifie sans connaître son auteur. C’est ce qui rend cette page possible : vous n’avez pas à me croire, vous revérifiez. Le résultat déposé est figé et son empreinte est publiée.

Tout le travail tourne sur du matériel accessible : un PC de bureau, un Raspberry Pi 5 et un Raspberry Pi Pico, qui servent aussi à vérifier que le calcul reste identique d’une machine à l’autre ; ponctuellement, une instance de 32 processeurs virtuels. Le programme vise une IA embarquée certifiable, jusque sur des machines modestes.

Un résultat vérifiable sans confiance, figé, revérifiable : ces propriétés ouvrent sur les usages visés :

• l’IA embarquée certifiable, jusque sur des machines modestes ;
• le pilotage des IA génératives, dont on ne retient que ce qui est prouvé ;
• l’identité vérifiable des agents d’IA ;
• l’audit après incident : rejouer exactement une décision passée ;
• la science reproductible ;
• la carte ouverte des calculs certifiés : chaque résultat avec son certificat, pour ne pas recalculer ce qui est prouvé.

Le programme de recherche détaille ce cadre. Tous les résultats, avec leurs sources et leurs dates, sont réunis sur la page Résultats.