Note this version of the table is outdated and not maintained; the most up-to-date version of the information here can be found in the OEIS Integer Complexity Table.
See the associated post for an introductory discussion of the information presented in this table; all notation used is briefly explained below the table.
| Numbers and operators $A$ | Operand complexity $c_A(n)$ | Operator complexity $d_A(n)$ | Expression complexity $e_A(n)$ | Smallest number with complexity $n$, $m_A(n)$ | Largest number with complexity $n$, $M_A(n)$ | Number of numbers with complexity $n$, $n_A(n)$ |
| $\{0,S,+,\cdot\}$ | Constant 1 (A000012) | A263283 | ||||
| $\{1,S,\cdot\}$ | Constant 1 (A000012) | A319975 [expression] | ||||
| $\{1,+,\cdot\}$ | A005245 | – | – A213923 | A005520 | A000792 | A005421; cumulative sum is A048249 |
| $\{1,+,-,\cdot\}$ | A091333; $n$ for which this differs from $c_{\{1,+,\cdot\}}$ is A253177 | – | – | A255641 | A348083 | |
| $\{1,+,\cdot,/\}$ | Cumulative sum is A069765 | |||||
| $\{1,+,-,\cdot,/\}$ | $n$ for which this differs from $c_{\{1,+,-,\cdot\}}$ is A348069 | – | – | No known differences from A255641 | ||
| $\{1,$ $2,$ $3,$ $4,$ $5,$ $6,$ $7,$ $8,$ $9,$ $+,$ $-,$ $\cdot,$ $/\}$ | A181898(n-2) | |||||
| $\{1,+,-,\cdot,//\}$ | $n$ for which this differs from $c_{\{1,+,-,\cdot\}}$ is A346742 | – | – | No known differences from A255641 | ||
| $\{1,+,\cdot,{}^\wedge\}$ | A025280 | – A005208 | – | A003037 | ||
| $\{1,+,-,\cdot,{}^\wedge\}$ | A091334 | – | – | A347983 | ||
| $\{1,2,+,-,\cdot,{}^\wedge\}$ | A099053 | – | – | A060274 | ||
| $\{1,+,-,\cdot,/,{}^\wedge\}$ | A348089 | – | – | |||
| $\{1,+,-,\cdot,{}^\wedge,!\}$ | A329526 | undefined | undefined | |||
| $\{1,+,\cdot,{}^\wedge,\uparrow\uparrow\}$ | A306560 | – | – | |||
| $\{1,+,-,\cdot,{}^\wedge,\uparrow\uparrow\}$ | A323727 | – | – | |||
| $\{1,+,!^m\}$ (for all $m$) | A117607 | undefined | undefined | |||
| $\{1,+,T\}$ | A117632 | undefined | undefined | |||
| $\{0,1,+,\cdot,{}^\wedge,C_{10}\}$ | A259466 | |||||
| $\{1,+,\cdot,{}^\wedge,\#\}$ | A133344 | – | – | |||
| $\{1,+,\cdot,B\}$ | A274061 | – | – | |||
| $\{1,+,V\}$ | A293771 * | |||||
| $\{1,\mathbf{V},+\}$ | – | A003313 | – | A003064 [operator] | A003065 [operator] | |
| $\{1,\mathbf{V},+,-\}$ | – | A128998 | – | |||
| $\{1,\mathbf{V},+,\cdot\}$ | – | A230697 | – | |||
| $\{1,\mathbf{V},+,-,\cdot\}$ | – | A173419 | – | A141414(n+1) | ||
| $\{1,2,\mathbf{V},+,-,\cdot\}$ | – | A140361 = A173419 – 1 | – | A141414 |
$A$ is an “alphabet” of numbers together with some unary and/or binary operators. For any such alphabet, there is a collection of finite sequences of $A$, the RPN expressions (see the post), each of which determines a value. Then given a number $n,$ we can define the $A$-operand complexity $c_A(n)$ as the minimum number of numbers appearing in any RPN expression with value $n,$ and similarly the $A$-operator complexity $d_A(n)$ as the minimum number of operators, and the $A$-expression complexity $e_A(n)$ as the minimum total length of an RPN expression with value $n$.
Since it’s most commonly used in the OEIS, just “complexity” of $n$ is taken to mean the operand complexity. So for example except where otherwise noted, the sequence in the column for smallest number with complexity $n$ is $m_A(n) = \min\{k: c_A(k)=n\}$.
Similarly, the largest number with complexity $n$ is $M_A(n) = \max \{k: c_A(k)=n\}$ and the number of numbers of a given complexity is $n_A(n) = |\{k:c_A(k)=n\}|$. Note that the number of numbers of complexity at most $n$ is the cumulative sum of this, i.e. $\sum_{i=1}^n n_A(i)$.
A dash (-) in entry in the first three columns means that all of the operators in the alphabet of that row are binary, and hence the value for that entry can be trivially derived from the relations $e_A(n)$ $= 2c_A(n)-1$ $= 2d_A(n)+1$ that hold in such a case. A star (*) in a table entry indicates that the complexity formulation of the sequence is conjectural.
The division operator $/$ above denotes strict integer division: $j/k$ is defined only if $k|j$. On the other hand, $//$ is “floor division”, $j//k = \lfloor j/k \rfloor$, defined for all pairs of numbers. (The latter notation is borrowed from the Python programming language; note the C language uses just $/$ for floor division.)
Additional symbols that appear in the table: the unary operator $S$ is successor, i.e., it adds one to its argument; ${}^\wedge$ is the binary operation of ordinary exponentiation $a^b$; $\uparrow\uparrow$ is tetration, i.e., $a\uparrow\uparrow b$ is the value of an exponential tower of `$a$’s that is $b$ high; $!^m$ is the multiple factorial of order $m$, i.e., $a!^m = \prod_{k=0}^{\lfloor(a-1)/m\rfloor} (a-km)$; $T$ is the unary operator that gives the $i$th triangular number; $C_b$ is unary “$b$-bit complementation,” i.e., $C_b\,a = 2^b-1-a$; $\#$ is concatenation of decimal representations, i.e., $a\#b = a10^{\lceil\log_{10}b\rceil}+b$; $B$ is binary concatenation of ones, i.e., the left operand must be $2^k-1$ and the right operand must be 1 and the result is $2^{k+1}-1$; and $V$ is a (unary) operator that enlarges the alphabet with the top of the stack, whereas $\mathbf{V}$ means that any number which has already appeared in the stack may be used as an operand (i.e., the $V$ operation is executed “for free” whenever a number is added to the stack).
Note that the presence of $\mathbf{V}$ is conceptually related to the duplication operator $D$ that adds a copy of the top of the stack on top of the stack. It may be of interest to investigate the relationship of $e_{\{1,\mathbf{V},\ldots\}}$ and $e_{\{1,D,\ldots\}}$ for various sets of operators. Of course $V$ and $\mathbf{V}$ are related as well, so we might also expect a connection between $d_{\{1,+,V\}}$ and $d_{\{1,\mathbf{V},+\}}$ above, for example.
Additional sequences related to $c_{\{1,+,\cdot\}}(n)$
In this section we drop the subscript for $A=\{1,+,\cdot\}$.
The “span” of complexity $n$: $s(n) = M(n) – m(n)$ is A133374.
The second smallest number of complexity $n$: $m_2(n) = \min\{k:k\neq m(n), c(k)=n\}$ is A265360.
The complexity “height” of $n$: $h(n) = \min_i c^i(A) = c^{i+1}(A)$ is A117618.
The “depth complexity” of $n$: there is a canonical way to generate a tree from an RPN expression, and the depth complexity of $n$ is the minimum height of the tree of an RPN expression with minimal ones and value $n$. This is defined in more detail, and the depth complexity values given, in A210659. The smallest number with depth complexity equal to $n$ is given by A210660.
Variant operand complexity if every instance of + must have one operand equal to 1 and must produce a prime result is $\tilde{c}(n) =$ A061373 (of interest because for small $n$, we frequently have $\tilde{c}(n) = c(n)$, and the former is much easier to compute). Presumably, though, as $n$ grows the fraction of $n$ for which $\tilde{c}(n) = c(n)$ goes to zero, although that bears checking. The smallest $k$ such that $\tilde{c}(k)=n$ is A182061.