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.