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] + i2 (1 + i3) - 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 3s 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.

Image Source Notebooks:

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