# P2608: Shortest addition chain for the 127th Mersenne number

- ID: `P2608`
- Reference: `mersenne-127-addition-chain`
- Page: https://theoremdb.org/statements/P2608
- Record maturity: Reviewed problem with recorded work

## Problem

An addition chain starts at \(1\) and appends sums of two earlier terms. What is the minimum length \(\ell(2^{127}-1)\) of an addition chain ending at \(2^{127}-1\)?

### Problem setup

- **Definition.** The length is the number of appended terms, so the initial 1 has length zero.
- **Remark.** Repeated summands are allowed.

### What counts as a solution

- Give a shortest chain and a certificate excluding every shorter length.

## Status

A reported exhaustive Hamming-weight result gives the lower endpoint, while an explicit 136-step addition chain gives the upper endpoint. [4](#reference-4)

## Work

### Evidence for the current status

**Proposition 1 (The strongest located interval is 133 through 136).** A reported exhaustive Hamming-weight result gives the lower endpoint, while an explicit 136-step addition chain gives the upper endpoint.

Put
\[
N=2^{127}-1=170141183460469231731687303715884105727.
\]
The strongest bound located in the literature and database audit is
\[
133\leq \ell(N)\leq136.
\]

The upper endpoint is independently replayed in this dataset. The lower endpoint uses Neill Clift's exhaustive verification of the Knuth-Stolarsky inequality for every integer of binary Hamming weight at most 128, as reported in Achim Flammenkamp's addition-chain database. Since
\[
\lambda(N)=\lfloor\log_2N\rfloor=126,
\qquad \nu(N)=127,
\]
that result gives
\[
\ell(N)\geq126+\lceil\log_2 127\rceil=133.
\]
The public report states the scope and completion date, November 2023, but the audit did not locate a compact certificate that can be replayed inside this fixture. For comparison, the published analytic theorem of Schönhage independently gives \(\ell(N)\geq132\).

No source found in the audit proves that 136 is optimal or supplies a chain of length at most 135. The four possible values 133, 134, 135, and 136 therefore remain open on the evidence recorded here.

### Background and intake notes

Current rigorous bounds are 127 <= ell(2^127-1) <= 136. The gap is small enough for defect-based enumeration while the endpoint is far beyond direct integer-state BFS.

- Original intake status: Status unknown. Addition-chain tables and work on the Scholz-Brauer problem must be checked for this exact Mersenne exponent.
- The exponent chain 1,2,3,5,7,14,28,56,63,126,127 is a star chain. Applying M_(a+b)=2^b M_a+M_b constructs the 136-step incumbent, where M_k=2^k-1.
- Lower-bound search should combine doubling bounds, small-step theory, and admissible addition-chain defect tables. Any pruned defect pattern is useful saved state.

- Recorded example: The lower bound 127 follows because a chain of length 126 reaches at most 2^126.

### Other known results

- **Computation 1** (reproduced): Brauer's star-chain construction expands a ten-step chain for 127 into a checked 136-step chain for 2^127-1. [3](#reference-3)
- **Proposition 2** (supported): Settling the target requires either a chain of length at most 135 or a certificate excluding all three shorter lengths. [1](#reference-1)

### Prior approaches

- **Route 1** (supported): Schönhage's theorem is an independently checkable floor, while Clift's reported Hamming-weight sweep raises it by one. [2](#reference-2) [4](#reference-4) [3](#reference-3) [5](#reference-5) [1](#reference-1)

### Runnable artifacts

- **Artifact 1** (reproduced): A standard-library verifier reconstructs the displayed chain, checks all 136 sums, and fixes its canonical digest.

### Computational notes

- The displayed 10-step star chain for exponent 127 was checked term by term. Expanding each star step with M_(a+b)=2^b M_a+M_b gives a recoverable addition chain of length (127-1)+10=136 for the target.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `mersenne-127-addition-chain`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>Gap obtained by combining the current lower-bound audit with the replayed upper-bound certificate. additionchains.com checked 2026-08-01. Gap obtained by combining the current lower-bound audit with the replayed upper-bound certificate https://additionchains.com/
   - Also cited at Current computational project and source-code index, checked 2026-07-25
   - website; reference source; web version checked 2026-08-01; checked 2026-07-25
   - Source use: citation_only
   - Provides the current independent addition-chain tables checked for the exact Mersenne target and nearby incumbents.
2. <a id="reference-2"></a>Arnold Schönhage, A lower bound for the length of addition chains, Theoretical Computer Science 1(1), 1975, pages 1-12; Achim Flammenkamp, Shortest Addition Chains, current Conjectures section; Neill M. Clift, Calculating optimal addition chains, Computing 91, 2011, pages 265-284 https://doi.org/10.1016/0304-3975(75)90008-0
   - Also cited at Theoretical Computer Science 1(1), 1975, pages 1-12
   - scholarly_publication; reference source; version of record; checked 2026-08-01
   - Source use: citation_only
   - Gives the general addition-chain lower bound used to constrain the exact Mersenne target.
3. <a id="reference-3"></a>Alfred Brauer, “On addition chains”. Bulletin of the American Mathematical Society 45(10) (1939), 736-739. DOI 10.1090/S0002-9904-1939-07068-7. Alfred Brauer, On addition chains, Bulletin of the American Mathematical Society 45(10), 1939, pages 736-739; explicit specialization and replay in this dataset https://doi.org/10.1090/S0002-9904-1939-07068-7
   - Also cited at Bulletin of the American Mathematical Society 45(10), 1939, pages 736-739
   - scholarly_publication; reference source; version of record; checked 2026-08-01
   - Source use: citation_only
   - Provides the classical star-chain construction specialized to the packet's 136-step certificate.
4. <a id="reference-4"></a>Achim Flammenkamp, Shortest Addition Chains, Conjectures section, report that Neill Clift verified the Knuth-Stolarsky inequality for every n with v(n)<=128 by November 2023; upper endpoint replayed by m127ac-artifact-chain-replay. Achim Flammenkamp, Shortest Addition Chains, Conjectures section, report that Neill Clift verified the Knuth-Stolarsky inequality for every n with v(n)<=128 by November 2023; upper endpoint replayed by m127ac-artifact-chain-replay https://wwwhomes.uni-bielefeld.de/achim/addition_chain.html
   - Also cited at Conjectures section, November 2023 Hamming-weight verification report
   - website; reference source; web version checked 2026-08-01; checked 2026-07-25
   - Source use: citation_only
   - Reports the current lower-bound verification used for the interval 133 through 136 at the 127th Mersenne number.
   - Source named by the research packet.
5. <a id="reference-5"></a>Computing 91, 2011, pages 265-284 https://doi.org/10.1007/s00607-010-0118-8
   - scholarly_publication; reference source; version of record; checked 2026-08-01
   - Source use: citation_only
   - Develops the optimal addition-chain computation used by the current lower-bound tables.