Chapter 4: Systems Based on Numbers

Section 5: Mathematical Constants

Operator representations

Instead of repeatedly applying an operation to a sequence of digits one can consider forming integers (or other numbers) by performing trees of operations on a single constant. Thus, for example, any integer m can be obtained by a tree of m-1 additions of 1's such as (1+ (1 + 1))+1. Another operator that can be used to generate any integer is a · b=2 a + b - 1. In this case 6 is (1 · (1 · 1)) · 1, and an integer m can be obtained by Tr[1+IntegerDigits[m, 2]]-2 or at most Log[2,m] applications of ·. The operator k a+ b - k + 1 can be used for any k. It also turns out that BitXor[2a, b] + 1 works, though in this case even for 2 the smallest representation is (1 · 1) · (1 · ((1 · 1) · 1)). (For BitOr[2a, b]-1 the number of applications needed is With[{i = IntegerDigits[m, 2]}, Tr[i + 1] + i[[2]](1 + i[[3]]) - 1].) The pictures below show the smallest number of operator applications required for successive integers. With the pair of operators a+b and a×b (a case considered in recreational mathematics for n-ary operators) numbers of the form 3^s have particularly small representations. Note that in all cases the size of the smallest representation must at some level increase like Log[m] (compare pages 1067 and 1070), but there may be some "algorithmically simple" integers that have shorter representations.

From Stephen Wolfram: A New Kind of Science [citation]