Notes

Chapter 4: Systems Based on Numbers

Section 3: Recursive Sequences


Ulam sequences

Slightly more complicated definitions in terms of numbers yield all sorts of sequences with very complicated forms. An example suggested by Stanislaw Ulam around 1960 (in a peculiar attempt to get a 1D analog of a 2D cellular automaton; see pages 877 and 928) starts with {1, 2}, then successively appends the smallest number that is the sum of two previous numbers in just one way, yielding

{1, 2, 3, 4, 6, 8, 11, 13, 16, 18, 26, 28, 36, 38, 47, 48, 53, 57, …}

With this initial condition, the sequence is known to go on forever. At least up to n=10^6 terms, it increases roughly like 13.5n, but as shown below the fluctuations seem random.


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