Stephen Wolfram's: A New Kind of Science | Online
Jump to Page
Look Up in Index
Search

Chapter 4 Notes > Section 5 > Page 916 > Note (c) Previous note-----Next note
Notes for: Systems Based on Numbers | 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.






PAGE IMAGE

Page image

RELATED LINKS

Pages related to this note:

*

All notes on this page:

* Nested radicals
* Digital slope representation
* Representations for integers
* Operator representations
* Number classification
* All notes for this section
* Downloadable programs for this page
* Downloadable images
* Search Forum for this page
* Post a comment
* NKS | Online FAQs
From Stephen Wolfram: A New Kind of Science [citation] Previous note-----Next note