# Lengths of the shortest "simple" equation, that use only the number '1', equal to a given natural numbers.

Is there a formula, for determining the length of the shortest formula, that uses only the number '1', parenthesis, and the hyperoperations $\{\{+, - \}, \{\times, / \}, \{\text{^}, \log_N,\text{nth root}\}, \{↑↑,\ldots\}, \ldots \}$ , that is equal to a given natural number?

The trend is simple at first, before gradually becoming very complex, below is a list of what I think should be the first few (first 400) elements, followed by a list of their lengths.

$$\small{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)\text{^}(1+1+1)\\(1+1+1)\text{^}(1+1)\\(1+1+1)\text{^}(1+1)+1\\(1+1+1)\text{^}(1+1)+1+1\\(1+1+1+1)\times(1+1+1)\\(1+1+1+1)\times(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+1\\(1+1)\text{^}(1+1+1+1+1)-1\\(1+1)\text{^}(1+1+1+1+1)\\\ldots\\(1+1+1)↑↑(1+1)\times(1+1)\\\ldots\\(1+1)\text{^}(1+1+1+1+1+1)\\\ldots\\(1+1+1)\text{^}(1+1+1+1)\\\ldots\\(1+1+1)↑↑(1+1)\times(1+1+1+1)\\\ldots\\(1+1+1+1+1)\text{^}(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)\\\ldots\\(1+1+1+1)↑↑(1+1)\\\ldots\\(1+1+1+1)↑↑(1+1)*(1+1+1)/(1+1)\\(1+1)↑↑(1+1+1)\times(1+1+1+1+1)\text{^}(1+1)\\\ \\1, 3, 5, 7, 9, 11, 13, 13, 13, 15, 17, 17, 19, 17, 15, 13\\15, 17, 19, 21, 23, 23, 21, 19, 17, 15, 13, 15, 17, 19, 19, 17\\\ldots}$$

In answer to, Elaqqad, if so restrict operations to the first few, perhaps with some info about why this is necessary.

Thanks to Ross Millikan for showing that with just '1', parenthesis, $+$ and $\times$, the answer is the sequence at oeis.org/A005245, and additionally with powers is oeis.org/A025280.

Thease sequences decelerate fantastically :)

Thease sequences take only the number of $1$s into account and ignore factors such as parenthesis complexity. From the $2$nd sequence, numbers that are more complicated to construct than any smaller number include:

$1, 2, 3, 4,\\5, 7, 11, 13, 21, 23, \ldots$

Of which are not prime:

$4, 21, \ldots$

From my sequences above:

Numbers that are more complicated to construct than any smaller number include:

$1, 2, 3, 4, 5, 6,\\7, 10, 11, 13, 20, 21, \ldots$

Of which are not prime:

$4, 6, 10, 20, 21\ldots$

The table below shows the first appearance of operations, although the larger values may yet prove inaccurate:

$+\ 2\\-\ 14\\\times\ 12\\/\ 384\\\text{^}\ 9\\↑↑\ 16$

• Do mean $N$ in $log_N$ to be arbitary, or does it also have to be constructed in terms of $1$'s?
– jxnh
Apr 8 '15 at 18:01
• $9=(1+1+1)\text{^}(1+1)$, 13 characters not 17. Obviously 10 can then be constructed with only 15. Apr 8 '15 at 18:12
• Also 8 = (1+1)^(1+1+1) Apr 8 '15 at 18:15
• But surely the answer is no, there is no closed-form formula for this. Apr 8 '15 at 18:18
• You might be interested in oeis.org/A005245, which is the minimum number of $1$'s to which you can add +*() and get each number. It is up the same alley. I didn't find your sequence in OEIS Apr 8 '15 at 18:18

Similar is OEIS A005245, which gives the number of $1$'s required to represent each number using just add, multiply, and parentheses. Subtraction, division, and powers are not allowed and the other characters are not counted. For example, $19=(1+1)\times (1+1+1)\times (1+1+1)+1$ uses nine $1$'s. Allowing powers gets A025280