Let's say I give you a calculator with a stack-based memory: you can push a positive integer onto the stack, or clone the top element of the stack, or perform arithmetic operations on the top two elements of the stack—addition, subtraction, multiplication, integer division.

Suppose these operations each have a cost: the cost of pushing a number onto the stack is the number itself, and the cost of every other operation is 1. The game is to find, for each integer in the range 1…256, the lowest-cost program which terminates with that integer being the only item in the stack.

For example, a minimal-cost program for generating 7 is:

1,3,@,+,+

In detail, this program

• Starts with an empty stack, as always. [ ]
• Pushes 1 onto the stack. [ 1 ]
• Pushes 3 onto the stack. [1, 3]
• Clones (@) the top member of the stack [1, 3, 3]
• Adds the top two members of the stack [1, 6]
• Adds the top two members of the stack, yielding the desired result. [ 7 ]

Of course, there may be many equally-inexpensive programs for generating the same number.

In this article, I describe:

1. An algorithm for finding the lowest-cost program to generate a number.
2. An optimization strategy which speeds up the algorithm by cutting out unnecessarily repeated work.
3. A fantastic theoretical result about how complicated the lowest-cost program can be.
4. An interesting consequence about prime numbers.

At a high level, this article is about how hard numbers are to produce when using a specific calculation language. (This is the numbers' algorithmic complexity, i.e. their "Kolmogorov complexity"). Some numbers can be produced very cheaply, while others defy simple calculations—and large numbers are not always more costly to produce than smaller ones! Compare the cheapest programs for producing 177 and 256:

[2, @, @, 1, +, +, @, @, 2, +, *, *, +] # yields 177, costs 15
[2, @, *, @, *, @, *] # yields 256; costs 8

At a lower level, the work in this article was inspired by the Piet programming language, an esoteric programming language in which programs are bitmap images reminiscent of Piet Mondrian's paintings. It's advantageous to compute numbers using the fewest pixels possible, and this article describes how to do just that.

There are many different strategies for producing a number. For example, you might try to produce its prime factors and multiply them together. Or maybe it would be cheaper to produce a convenient nearby power of two, then subtract. Or maybe you could write out the number in a particular base by repeatedly multiplying by the base and adding numbers together.

There are many possibilities—how do we find the optimal strategy? My solution is to recast the problem of finding a cheap program as a problem of searching a graph for the shortest possible path between two nodes. By recasting the program-finding problem as a path-finding problem, we can apply an off-the-shelf optimal algorithm called branch and bound (a.k.a. uniform cost search) which is guaranteed to find the shortest path through any graph.

Here is the recasting strategy:

• The nodes of the graph are contents in the stack. For example, [1,5,7].
• The weighted directed edges between nodes are the operators such as addition, multiplication, pushing a number onto the stack, and cloning the top of the stack. The "source" node is the state of the stack before the operator is applied, and the "target" node is the state of the stack after the operator is applied. The length/weight of the edge is the cost of an operator.
• Paths between two nodes in the graph are therefore sequences of operators which, if you apply them, transform the start state into the goal state. The total "length" of the path is the total cost of the program.
• In our particular problem, we want to find the lowest-cost program which transforms the initial state [] into our desired number [N]. In other words, we want a minimal-length path between [] and N in the graph.

This conversion is all we need; the branch-and-bound algorithm is guaranteed to find the shortest path through this graph and consequently to find the shortest program for generating a particular number. (Python code)

We get results like these (each line consists of a number, followed by an optimally inexpensive program for generating that number). See first results for the complete list.

1 1
2 2
3 3
4 4
5 5
6 3,@,+
7 7
8 4,@,+
9 3,@,*
10 5,@,+
11 3,@,*,2,+
12 3,@,+,@,+
13 3,@,+,@,+,1,+
14 4,@,*,2,-
15 4,@,*,1,-
16 4,@,*
--- snip ---
248 5,@,@,*,*,1,-,@,+
249 3,@,@,*,@,*,2,+,*
250 5,@,@,*,*,@,+
251 5,@,@,*,*,@,+,1,+
252 3,@,+,@,@,1,+,*,*
253 4,@,*,@,*,3,-
254 4,@,*,@,*,2,-
255 4,@,*,@,*,1,-
256 4,@,*,@,*

The branch-and-bound algorithm, as implemented, is guaranteed to produce

We have found that all of the numbers between 1 and 256 can be generated using optimal-cost programs that only use constants between 1 and 5. We can ask for a particular number N, what the largest constant you need to include in order to generate the lowest-cost program?

For example, you might imagine that while the numbers between 1 … 256 cost less than 16 and require only constants as high as 5, larger numbers—at least the outputs of the Ackermann function, perhaps? — would cost more and require some greater constants in order to be written as cheaply as possible; if you attempt to compute the number with fewer constants, the program will cost more than is optimal.

On the other hand, you might imagine that all integers can be written as cheaply as possible using only a fixed handful of constants. This would suggest that number-generating programs are not especially penalized for computing large numbers by using small constants and a bunch of arithmetic, rather than employing larger constants and fewer arithmetic operations.

What do you think? (You should feel free to decide what you believe before continuing.) I puzzled over this for a long time, as both views seemed intuitively appealing and a proof seemed elusive. Eventually, however, I established the answer.

What I proved was the following theorem:

Theorem. Each positive integer N can be optimally computed with a program that uses only the constants 1…5. That program is absolutely as cheap as possible, meaning that all other programs for computing N, regardless of constants they use, cost at least as much.

Moreover, I proved that this bound is tight in the sense that the theorem works for constants in [1…5], but fails for shorter intervals like [1…4].

The theorem is actually a direct consequence of the following Lemma:

Lemma Each positive integer N can be optimally computed with a program that uses only the constants 1…5 and which costs no more than N.

The lemma provides a sort of diagonalization argument. First, I'll prove that the lemma implies the theorem, then I'll prove the lemma.

The lemma implies the theorem. Suppose the lemma is true and you have an optimally-costed program \(Q\) for generating an integer N. If \(Q\) only uses the constants 1…5, the theorem holds for \(N\). Otherwise, make a new program \(Q^\prime\) by replacing each constant greater than 5 in \(Q\) with an optimal subroutine that produces that constant instead and that uses only the constants 1…5. Because of the lemma, this substitution doesn't increase the cost of the program. Hence \(Q^\prime\) costs the same as the optimal program \(Q\) and only uses the constants 1…5, which establishes the theorem for N.