In mathematics, the Ulam numbers comprise an integer sequence devised by and named after Stanisà Âaw Ulam, who introduced it in 1964. The standard Ulam sequence (the (1, 2)-Ulam sequence) starts with U<sub>1</sub> = 1 and U<sub>2</sub> = 2. Then for n > 2, U<sub>n</sub> is defined to be the smallest integer that is the sum of two distinct earlier terms in exactly one way and larger than all earlier terms.
As a consequence of the definition, 3 is an Ulam number (1 + 2); and 4 is an Ulam number (1 + 3). (Here 2 + 2 is not a second representation of 4, because the previous terms must be distinct.) The integer 5 is not an Ulam number, because 5 = 1 + 4 = 2 + 3. The first few terms are
There are infinitely many Ulam numbers. For, after the first n numbers in the sequence have already been determined, it is always possible to extend the sequence by one more element: is represented as a sum of two of the first n numbers, so either it is a term of the sequence or it can be expressed in a different way as a sum of two elements. But since all other sums of two elements among the first n are less than , there must be an element of the sequence between U<sub>n</sub> and . The next element is therefore the smallest of the uniquely representable numbers that exceed U<sub>n</sub>.
Ulam is said to have conjectured that the numbers have zero density, but they seem to have a density of approximately 0.07398.
Apart from 1 + 2 = 3 any subsequent Ulam number cannot be the sum of its two prior consecutive Ulam numbers.
For n > 2, any three consecutive Ulam numbers (U<sub>nâÂÂ1</sub>, U<sub>n</sub>, U<sub>n+1</sub>) as integer sides will form a triangle.
The sequence of Ulam numbers forms a complete sequence.
For every integer n > 1 there is always at least one Ulam number U<sub>j</sub> such that n ≤ U<sub>j</sub> < 2n.
In any sequence of 5 consecutive positive integers {i, i + 1,..., i + 4}, i > 4 there can be a maximum of 2 Ulam numbers.
Ulam numbers are pseudo-random and too irregular to have tight bounds. Nevertheless from the properties above, namely, at worst the next Ulam number U<sub>n+1</sub> ≤ U<sub>n</sub> + U<sub>nâÂÂ2</sub> and in any five consecutive positive integers at most two can be Ulam numbers, it can be stated that
where N<sub>n</sub> are the numbers in NarayanaâÂÂs cows sequence: 1,1,1,2,3,4,6,9,13,19,... with the recurrence relation N<sub>n</sub> = N<sub>nâÂÂ1</sub> +N<sub>nâÂÂ3</sub> that starts at N<sub>0</sub>.
It has been observed that the first 10 million Ulam numbers satisfy except for the four elements (this has now been verified for the first Ulam numbers). Inequalities of this type are usually true for sequences exhibiting some form of periodicity but the Ulam sequence does not seem to be periodic and the phenomenon is not understood. It can be exploited to do a fast computation of the Ulam sequence (see External links).
The idea can be generalized as (u, v)-Ulam numbers by selecting different starting values (u, v). A sequence of (u, v)-Ulam numbers is regular if the sequence of differences between consecutive numbers in the sequence is eventually periodic. When v is an odd number greater than three, the (2, v)-Ulam numbers are regular. When v is congruent to 1 (mod 4) and at least five, the (4, v)-Ulam numbers are again regular. However, the Ulam numbers themselves do not appear to be regular.
A sequence of numbers is said to be s-additive if each number in the sequence, after the initial 2s terms of the sequence, has exactly s representations as a sum of two previous numbers. Thus, the Ulam numbers and the (u, v)-Ulam numbers are 1-additive sequences.
If a sequence is formed by appending the largest number with a unique representation as a sum of two earlier numbers, instead of appending the smallest uniquely representable number, then the resulting sequence is the sequence of Fibonacci numbers.