A Hidden Signal in the Ulam Sequence

ABSTRACT

The Ulam sequence is defined as a₁ = 1, a₂ = 2, and a_n being the smallest integer that can be written as the sum of two distinct earlier elements in a unique way. This gives Ulam remarked that understanding the sequence, which has been described as “quite erratic,” seems difficult and indeed nothing is known. We report the empirical discovery of a surprising global rigidity phenomenon: there seems to exist a real α ∼ 2.5714474995… such that supported on a subset of . Indeed, for the first 10⁷ elements of Ulam’s sequence, The same phenomenon arises for some other initial conditions a₁, a₂: the distribution functions look very different from each other and have curious shapes. A similar but more subtle phenomenon seems to arise in Lagarias’ variant of MacMahon’s “primes of measurement” sequence.

KEYWORDS:

• additive number theory
• combinatorial number theory
• Ulam sequence

2000 AMS SUBJECT CLASSIFICATION:

• 11B30
• 37P99

Acknowledgment

The result for the Ulam sequence was originally discovered using only the first 10,000 numbers for each set of initial conditions; the precision of the results presented here would not have been possible without the datasets compiled and generously provided by Daniel Strottman for all initial conditions that were discussed. Sinan Güntürk observed the arithmetic regularity of the location of the peaks which gave rise to Section 2.3. Bruce Reznick was very helpful in explaining the early history of the Stern sequence. Jud McCranie informed the author of additional data and performed additional tests on them providing a better estimate for α_{(1, 2)}. The computations involving the ζ −function were carried out using Oldyzko’s list [Odlyzko 15] of the first 100,000 roots. The author is indebted to Steven Finch for extensive discussions and his encouragement.