Integer Complexity

Ed Pegg Jr
Wolfram Research

Using the set of symbols {1, ×, +} and parentheses, how many 1’s does it take to represent 23?  It turns out that eleven are needed. Surprisingly, the number 27 requires only nine.
23 = (1+1+1) * ((1+1) * (1+1+1)+1) + 1 + 1
27 = (1+1+1) * (1+1+1) * (1+1+1)

This topic was discussed on page 916 of A New Kind of Science.  Since publication of NKS, a long-standing conjecture for this problem was disproved via Mathematica code.  That code and other programming tricks will be shown, along with relevant online databases.  The whole problem will then be expanded into the realm of complex numbers, a topic that apparently hasn’t been researched.

Created by Mathematica  (April 20, 2004)