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 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.