Research · Number theory · integer complexity

Integer complexity of 2⁶¹ − 1: an expression with 127 occurrences of 1

This page presents a piece of research in number theory: an expression using only the digit 1, addition and multiplication, that equals exactly 2⁶¹ − 1, the Mersenne prime M61, with only 127 occurrences of 1. It shows the exact statement, the landscape of public values, then the whole expression, with an outside judge, a second path and a short program that anyone runs to recheck it.

1. The problem

The integer complexity of an integer n, written ‖n‖, is the fewest 1’s needed to write it using only addition, multiplication and parentheses. So ‖6‖ = 5, because 6 = (1+1)×(1+1+1) and nothing shorter works. No efficient algorithm for it is known: values are computed by exhaustive dynamic programming, which runs out long before the numbers at stake here.

The board’s target, verbatim: “Find an expression for N using fewer than 150 1’s”, with N = 2^61 - 1 = 2,305,843,009,213,693,951, the Mersenne prime M61. Being prime, N has no factorisation to exploit: any expression must build it additively, which is what makes it hard. The board’s checker (check.py) parses the expression with a small dedicated parser (no eval), checks that it contains only the characters 1, +, *, parentheses and spaces, that it evaluates exactly to N, and counts its occurrences of 1; that count, if under 150, is the score. Source: github.com/math-market/integer-complexity-m61, file TASK.md, read on 13 Oct 2026; the board and its checker are published under the Apache-2.0 licence.

The problem’s two numbers have different origins. 150 is the cost of a Horner expansion in base 32767: the board publishes it so you know exactly what to beat, and states explicitly that it is not a record. 115.5 is a floor nobody can go below: any expression using k ones has value at most 3^k/3, hence ‖N‖ ≥ 3 log₃ N ≈ 115.51, that is at least 116 occurrences of 1 (Selfridge’s bound, recalled by R. K. Guy, Unsolved Problems in Number Theory, section F26). The gap between 116 and 150 is the board’s territory.

2. The public landscape

The table gathers the problem’s two public landmarks: a theoretical bound that no result can go below, and a practical baseline published by the board. These are the bounds within which the research territory lies.

Readings of 13 Oct 2026: board math-market/integer-complexity-m61 (README, TASK.md, check.py, baseline.txt, LICENSE, pull request no. 4, list of pull requests), OEIS A005245, arXiv:1207.4841, arXiv:1404.2183.

Integer complexity is listed in OEIS A005245 (“the (Mahler-Popken) complexity of n”), with its first 20 values (1, 2, 3, 4, 5, 5, 6, 6, 6, 7, 8, 7, 8, 8, 8, 8, 9, 8, 9, 9…), computed by exhaustive dynamic programming for small integers. For N = 2⁶¹ − 1, that direct approach is out of reach: the best known algorithms compute every complexity up to a threshold M in time of order M^1.23 (Arias de Reyna and van de Lune, arXiv:1404.2183, section 4), far beyond what any machine can cover for M = 2⁶¹ − 1. Altman and Zelinsky (arXiv:1207.4841) study integers whose complexity is close to Selfridge’s bound and prove, for numbers of the form 2^m3^k, an exact equality ‖2^m3^k‖ = 2m + 3k for m ≤ 21; N = 2⁶¹ − 1 is not of this form (it is prime), and these methods do not apply to it directly.

At the readings of 13 Oct 2026, none of the sources cited gives the exact value of ‖2⁶¹ − 1‖: it is only known to lie between 116 and 150. 127 is neither a published bound nor an established exact value; it is the result of this page, inside that interval.

3. The result

The expression below uses only the digit 1, the operators + and *, and parentheses; it has 127 occurrences of 1 and equals exactly N, hence ‖N‖ ≤ 127.

The expression is published in full. The file in the board’s format is intcomplexity_m61_expression.json (689 bytes, 671 characters in the 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)

The checks

Four checks, replayed on 13 Oct 2026 on the expression file:

Output of the board judge on the expression:

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

Output of the judge on the expression with ‘+1’ appended:

REJECTED: expression evaluates to 2305843009213693952, not 2305843009213693951

Recheck it yourself

The program below contains the expression. Save it in a file verifier_intcomplexity.py and run python verifier_intcomplexity.py: Python 3 is enough, with no library to install. The program runs a stack-based evaluator (no recursion, written independently of the previous two checks), counts the occurrences of 1 and replays the canary (the expression with ‘+1’ appended must equal N + 1, hence no longer match N). Saveable version: verifier_intcomplexity_en.py.

# verifier_intcomplexity.py: standard library only; python verifier_intcomplexity.py
N = 2 ** 61 - 1
BASELINE = 150
ALPHABET = set("1+*() ")

# the expression of section 3, as is (characters 1, +, *, parentheses, spaces)
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

# check 1: a stack-based evaluator (no recursion), written independently of the page's second path
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]

# check 2, unrelated to check 1: count of 1's in the string, and validation of the character set
def compte_un(s):
    return s.count("1")

v1 = evalue_pile(EXPR)
print("N = 2^61 - 1 = %d" % N)
print("value == N: %s" % (v1 == N))
print("count of 1's: %d" % compte_un(EXPR))

# canary: the expression with '+1' appended must evaluate to N + 1, hence no longer match N
EXPR2 = EXPR + "+1"
v2 = evalue_pile(EXPR2)
print("canary: expression + '+1' -> value == N + 1: %s; value == N: %s" % (v2 == N + 1, v2 == N))

bon = v1 == N and compte_un(EXPR) < BASELINE and v2 == N + 1 and v2 != N
print(("VERIFIED: the expression evaluates exactly to N with %d occurrences of 1 (< %d); the canary loses equality to N" % (compte_un(EXPR), BASELINE)) if bon else "FAILURE")
raise SystemExit(0 if bon else 1)

This program was run on 13 Oct 2026 (Python 3.11.0rc2, python -I) on the published expression. Output obtained:

N = 2^61 - 1 = 2305843009213693951
value == N: True
count of 1's: 127
canary: expression + '+1' -> value == N + 1: True; value == N: False
VERIFIED: the expression evaluates exactly to N with 127 occurrences of 1 (< 150); the canary loses equality to N

The program agrees with the board judge and with the second path; the canary loses equality to N, as expected.

sha256 fingerprints

Public repository

The expression is filed on the board’s public repository: proposal no. 4 (pull request) of math-market/integer-complexity-m61, opened on 2 Oct 2026. Its file has the same sha256 fingerprint as the file of this page. State read on 13 Oct 2026: open, not merged, no comment and no review; the repository’s three other pull requests, all closed, concern the board’s infrastructure (guarding the verification harness), not expression proposals. The expression is published under the Apache-2.0 licence, as the board requires for submissions; the board, its statement and its checker are also under the Apache-2.0 licence (LICENSE of the repository). No third-party data enters the expression.

4. What this question models

This question belongs to combinatorial number theory: what is the fewest number of 1’s needed to write a given integer using only addition, multiplication and parentheses? The sequence of integer complexities has been listed in OEIS A005245 since the work of Mahler and Popken (1953); Richard Guy made it one of his “suspiciously simple sequences” (American Mathematical Monthly, 1986). The general problem of computing ‖n‖ for an arbitrary n has no known efficient algorithm; the best exact algorithms compute every value up to a threshold M in time M^α with α ≈ 1.23 (Arias de Reyna and van de Lune, arXiv:1404.2183), which puts an integer the size of 2⁶¹ − 1 out of reach of an exact computation.

The bracket 3 log₃ n ≤ ‖n‖ ≤ 3 log₂ n is due to Selfridge and Coppersmith (as recalled by Guy); Joshua Zelinsky improved the general upper bound (arXiv:2211.02995, cited by OEIS A005245). The board math-market/integer-complexity-m61 sets a practical threshold, 150, so the challenge is approachable without an exhaustive search, and publishes the theoretical floor, 116, as an unpassable baseline.

Sources: github.com/math-market/integer-complexity-m61 (README, TASK.md, check.py, baseline.txt, LICENSE, pull request no. 4, list of pull requests), OEIS A005245, arXiv:1207.4841, arXiv:1404.2183, read on 13 Oct 2026.

A research programme, an outside test

These results cover domains with nothing to do with each other: the geometry of packings (Packomania, Friedman Packing Center), space mechanics (ESA SpOC 4), number theory (IBM Ponder This) and graphs (FlyWire Codex). In each, the result is entered on a third party’s page, a table, a ranking or a list, and can be rechecked by computation: ESA evaluates each solution with its simulator, Packomania publishes the entries it accepts, IBM publishes a list of names, Friedman keeps a page that credits authors. These results belong to a single research programme: keep only what a certificate proves.

This page applies the same principle to a problem in number theory: an expression whose full text is published, an outside judge that checks it, and a second path then a short program that anyone runs to recheck it. Here, the reader rechecks it personally.

The principle is public: every hypothesis is tested by computation and kept only if a certificate proves it. Generative AIs serve me as assistants, interchangeable ones: they propose, my AI decides, the certificate settles. The internal workings remain confidential. The results are public.

The certificate changes the nature of proof. A result can be checked without trusting whoever produced it, as a proof can be checked without knowing its author. That is what makes this page possible: you do not have to believe me, you recheck. The submitted result is fixed and its fingerprint is published.

All the work runs on accessible hardware: a desktop PC, a Raspberry Pi 5 and a Raspberry Pi Pico, which also serve to check that the computation stays identical from one machine to another; occasionally, a 32-vCPU instance. The programme aims at a certifiable embedded AI, down to modest machines.

A result that is verifiable without trust, fixed and rechecked: these properties open onto the intended uses:

• certifiable embedded AI, down to modest machines;
• steering generative AIs, keeping only what is proven;
• verifiable identity for AI agents;
• audit after an incident: replaying a past decision exactly;
• reproducible science;
• an open map of certified computations: each result with its certificate, so that what is proven is not recomputed.

The research programme sets out this framework. All the results, with their sources and dates, are gathered on the Results page.