User:Glen Whitney/IntegerComplexityTable

See the introduction to integer complexity for a discussion of the information presented in this table. All notation used here is briefly summarized below the table. Please post any comments or suggested updates to the table on the discussion page.

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]
$\{0,S,\cdot 2\}$	Constant 1 (A000012)	A056792	– A056791	A052955 [operator]	A131577 [operator]	A000045
$\{1,S,\cdot 2\}$	Constant 1 (A000012)	– A014701 = A056792 - 1	A056792	A052955 [expression]	$2^{n}$ = A000079 [operator]	A000045
$\{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
${\begin{array}{c}\{1,2,3,4,5,6,7,8,9,\\+,-,\cdot ,/\}\end{array}}$				A181898(n-2)
$\{1,+,-,\cdot ,//\}$	$n$ for which this differs from $c_{\{1,+,-,\cdot \}}$ is A346742	–	–	No known differences from A255641
$\{1,+,{}^{\wedge }\}$	– A348262	–	A213924
$\{1,+,\cdot ,{}^{\wedge }\}$	A025280	– A005208	– A217250	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 },p\}$		A062537 [unary]		A062860 [unary operator]		A061396 [unary operator]
$\{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

Summary of notations (see the introduction for more detail)

$A$ is an “alphabet” of numbers together with some unary and/or binary operators. For any such alphabet, there is a collection of certain finite sequences from $A$ , the RPN expressions, 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$ . As a variant of $d_{A}$ , the $A$ -unary operator complexity of $n$ is the minimum number of unary operator symbols in an RPN expression with value $n$ ; sequences relating to in are labeled with "[unary]" in the table above.

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 quantity, i.e. $\sum _{i=1}^{n}n_{A}(i)$ .

A dash (–) in an entry in the first three columns means that the value can be computed trivially from another one of the first three columns: either all of the operators in the alphabet of that row are binary, and hence the relations $e_{A}(n)=2c_{A}(n)-1=2d_{A}(n)+1$ hold, or all of the operators are unary, in which case we have $c_{A}(n)=1$ and $e_{A}(n)=d_{A}(n)+1$ .

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 from the table

$S$

the unary successor operator, i.e., it adds one to its argument.

$\cdot m$

the unary operation of multiplying by

m

. Thanks to Kate Stange for pointing out the series with operators

S

and

\cdot 2

.

${}^{\wedge }$

the binary operation of ordinary exponentiation

a^{b}

.

$\uparrow \uparrow$

the binary operation of tetration, i.e.,

a\uparrow \uparrow b

is the value of an exponential tower of `

a

’s that is

b

high.

$p$

the unary operation that gives the

i

th prime on argument

i

. Thanks to Jon Awbrey for pointing out the series related to alphabet

\{1,\cdot ,{}^{\wedge },p\}

. Note that one could alternatively use the alphabet

\{2,\cdot ,{}^{\wedge },p\}

and count only the operands and unary operators, with the proviso that the value of the empty expression is 1. Note that for these alphabets, the operand-minimal, operator-minimal, and expression-minimal RPN expressions are unique modulo

22\cdot =22^{\wedge }

(thanks to unique factorization), and hence one can recover all of the operand complexity, operator complexity, unary operator complexity, and expression complexity from any two of them. However, it is unclear at the moment whether there is another sequence currently in the OEIS which together with the unary operator complexity A062537 allows a brief formula for the other complexity measures for

\{1,\cdot ,{}^{\wedge },p\}

.

$!^{m}$

the unary multiple factorial of order

m

, i.e.,

a!^{m}=\prod _{k=0}^{\lfloor (a-1)/m\rfloor }(a-km)

.

$T$

the unary operator that gives the

i

th triangular number on argument

i

.

$C_{b}$

unary “b-bit complementation,” i.e.,

C_{b}a=2^{b}-1-a

.

$\#$

binary concatenation of decimal representations, i.e.,

a\#b=a10^{\lceil \log _{10}(b+1)\rceil }+b

; for example,

16\#20=1620

.

$B$

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

.

$V$

a unary operator that enlarges the alphabet by adding as a new allowed numeric operand the number currently on 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 $V$ and $\mathbf {V}$ are conceptually related to the duplication operator $D$ that adds a copy of the top of the stack to the stack. For example, 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 to each other as well, so we might also expect for example a connection between $d_{\{1,+,V\}}$ and $d_{\{1,\mathbf {V} ,+\}}$ above, for example.

Additional sequences related to $c_{\{1,+,\cdot \}}(n)$

The alphabet $A=\{1,+,\cdot \}$ is by far the most studied within the OEIS in terms of the sequences included. We summarize other entries related to $A$ -complexity measures in this section, dropping the subscript $A$ for notational convenience.