Selfridge's powers-of-two integer-complexity problem

Exact statement

Selfridge asked whether $\lVert 2^n\rVert=2n$ for every $n$ , where $\lVert m\rVert$ is the least number of ones needed to build $m$ using addition, multiplication, and parentheses.

StatusOpen; the FPRD track proves only restricted expression-family results

External reviewNo documented external or specialist review of these FPRD results is recorded.

Context

The direct construction of 2^n as a product of n copies of (1+1) uses 2n ones. The problem is whether any formula using addition and multiplication can do better.

Definitions

$\lVert m\rVert$ is the minimum number of occurrences of 1 in an expression for $m$ using only $+$ , $\times$ , and parentheses.

Proof or evidence

The public track states the external question and separates it from every grammar-restricted theorem below.

Problem, scope, and current frontier →

Verification notes

The open status and current literature context were checked against the cited 2026 integer-complexity paper.

Limitations

None of the current FPRD claims quantifies over all integer-complexity expressions.
No improvement to the unrestricted verification frontier is claimed.

Open work

Keep the restricted track paused pending a new normal-form or effective-height theorem; more residue tables are not the current frontier, and unrestricted Selfridge remains open.