This site is supported by donations to The OEIS Foundation.

User:Glen Whitney/IntegerComplexity

From OeisWiki
Jump to: navigation, search

Analyzing the "complexity" of an integer

There are many interrelated sequences in the OEIS that all have to do with one general approach to quantifying the “complexity” of an integer. This approach assumes that you have some basic “building blocks” for constructing integers: starting numbers you’re allowed to use, and operations that you may apply to them. The general idea, then: the number of these building blocks that you need to arrive at a particular integer is one way of characterizing how “complex” that integer is.

This approach to constructing integers may seem familiar from the “Four fours” puzzle: Given four instances of the number 4 to start with, and a variety of operations that you might use, how many different whole numbers can you construct? For some examples,

Here it seems quite reasonable that in terms of “expressing with fours,” the number eight is “simpler” than the number three.

The lowest-numbered sequence (that I’ve found) in the OEIS that has to do with integer complexity is A000792. In the case of this sequence, the only number you’re allowed to start with is one, and the only operations you’re allowed to use are plus and times. The th entry of sequence A000792 then tells you the largest number you can produce using at most ones.

Somewhat more formally, let be an “alphabet” of numbers and operators; for simplicity we’ll assume all operators are unary or binary. One can then form finite sequences of elements from ; such a sequence is a well-formed RPN expression if no initial subsequence has as many binary operators as numbers. Each well-formed RPN expression unambiguously determines its value: imagine you have an initially-empty stack of numbers, and go through the sequence from left to right. Any time you encounter a number, put it on top of the stack; when you encounter a unary operator, modify the top number on the stack by applying that operator; and when you encounter any binary operator , remove and (respectively) from the second-to-top and top positions of the stack, and then put on top of the stack (reducing the height of the stack by one). The value of the RPN expression is the top number on the stack when the entire expression has been scanned. The well-formed condition guarantees the stack never empties.

We can now define the -operand complexity of a number , which we’ll write as , as the minimum number of numbers in any well-formed RPN expression with value ; the -operator complexity as the minimum number of operators in any well-formed RPN expression with value , and similarly the -expression complexity as the minimum length of a well-formed RPN expression with value . There is no general relationship between , and , but if contains only binary operators, then

.

(Briefly, to see this, count the number of operators needed to reduce the operands to a single number; clearly the minimal expression in any case ends with a stack of just one number.) Similarly, if there are only unary operators in the alphabet, then there can only be one (useful) operand, so trivially and .

Since it’s the most common notion of complexity used in the OEIS, we take “complexity” without an adjective to refer to , the -operand complexity. Surprisingly many different phenomena may be cast in terms of this notion of integer complexity, even ones that may not appear so at first glance. For example, Jon Awbrey points out that the notions in Riffs and Rotes can be viewed as a sort of operator complexity of the natural numbers, for an appropriate alphabet , as long as only occurrences of unary operators are counted. Or the length of the Double-and-Add algorithm (see A232559) can be characterized as the operator complexity with respect to other alphabets.

The Integer Complexity Table organizes sequences in the OEIS related to these notions of integer complexity, according to the alphabet and the particular measure or property of the complexity.

One final note: there's no particular reason that (most occurrences) of "integer" above can't be replaced with other number systems, like rationals or reals. So far, though, to the best of my knowledge, there are no sequences in the OEIS dealing with this notion of the complexity of rationals, algebraic integers, reals, or other systems -- although there could of course be.

This article originally appeared on StudioInfinity and is reproduced and updated here by the author.