This post is authored by Stefan Steinerberger.
The Ulam sequence
is defined by starting with 1,2 and then repeatedly adding the smallest integer that is (1) larger than the last element and (2) can be written as the sum of two distinct earlier terms in a unique way. It was introduced by Stanislaw Ulam in a 1962 paper (`On some mathematical problems connected with patterns of growth of figures’) where he vaguely describes this as a one-dimensional object related to the growth of patterns. He also remarks (in a later 1964 paper) that `simple questions that come to mind about the properties of a sequence of integers thus obtained are notoriously hard to answer.’ The main question seems to have been whether the sequence has asymptotic density 0 (numerical experiments suggests it to be roughly 0.07) but no rigorous results of any kind have been proven so far.
A much stranger phenomenon seems to be hiding underneath (and one is tempted to speculate whether Ulam knew about it). A standard approach in additive cominatorics is to associate to the first elements of a sequence a
and work with properties of . If we do this with the elements of the Ulam sequence and plot the real part of the function, we get a most curious picture with a peak around
Such spikes are generally not too mysterious: if we take the squares we can observe a comparable peak at for the simple reason that squares are (mod 4). However, here things seem to be very different: numerically, the Ulam sequence does seem to be equidistributed in every residue class. Due to periodicity, the function only sees the set of numbers
and it makes sense to look at the distribution of that sequence on the torus for that special value . A plot of the first 10 million terms reveals a very strange distribution function.
The distribution function seems to be compactly supported (among the first 10 million terms only the four elements give rise to elements on the torus that lie outside .) The same phenomenon seems to happen for some other initial conditions (for example, 2,3 instead of 1,2) as well and the arising distribution functions seem to vary greatly.
Question 1: What is causing this?
Question 2: Are there other `natural’ sequences of integers with that property?
See also Stefan’s paper A Hidden Signal in the Ulam sequence .
Update: See also Daniel Ross’ subsequent study of Ulam’s sequence, presented in Daniel’s sort of public ongoing “research log”. (“It includes a summary at the top of the most interesting observations to date, which usually lags a couple weeks behind the most current stuff.”)