The arithmetic complexity 
of a positive integer 
is the minimum 
for which there is a sequence 
with 
, 
, and
 |
for every 
.
Thus 
is the length of a shortest straight-line computation of 
using only addition, subtraction,
and multiplication. For 
, 2, ..., its values begin 0, 1, 2, 2, 3, 3, 4, 3, 3, 4,
4, 4, 5, 4, 4, 3, ... (OEIS A173419).
The conjecture that 
for every prime
number 
was disproved by Patanè (2026), who proved that the primes below 5000 satisfying
are exactly
 |
The scripts used for the exhaustive enumeration were produced with help from Claude. Patanè (2026) reports that he found the results through the scripts and verified the computations.
