Ulam number

An Ulam number is a member of an integer sequence devised by and named after Stanislaw Ulam, who introduced it in 1964.^[1] The standard Ulam sequence (the (1, 2)-Ulam sequence) starts with U₁ = 1 and U₂ = 2. Then for n > 2, U_n 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.

Examples

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

1, 2, 3, 4, 6, 8, 11, 13, 16, 18, 26, 28, 36, 38, 47, 48, 53, 57, 62, 69, 72, 77, 82, 87, 97, 99, 102, 106, 114, 126, 131, 138, 145, 148, 155, 175, 177, 180, 182, 189, 197, 206, 209, 219, 221, 236, 238, 241, 243, 253, 258, 260, 273, 282, ... (sequence A002858 in the OEIS).

The first Ulam numbers that are also prime numbers are

2, 3, 11, 13, 47, 53, 97, 131, 197, 241, 409, 431, 607, 673, 739, 751, 983, 991, 1103, 1433, 1489, 1531, 1553, 1709, 1721, 2371, 2393, 2447, 2633, 2789, 2833, 2897, ... (sequence A068820 in the OEIS).

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: U_{n − 1} + U_n is uniquely represented as a sum of two of the first n numbers, and there may be other smaller numbers that are also uniquely represented in this way, so the next element can be chosen as the smallest of these uniquely representable numbers.^[2]

Ulam is said to have conjectured that the numbers have zero density,^[3] but they seem to have a density of approximately 0.07398.^[4]

Hidden structure

It has been observed^[5] that the first 10 million Ulam numbers satisfy ${\displaystyle \cos {(2.5714474995a_{n})}<0}$ except for the 4 elements ${\displaystyle \left\{2,3,47,69\right\}}$ (this has now been verified up to ${\displaystyle n=10^{9}}$). 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).

Generalizations

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.^[6]

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.^[7]

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.^[8]

Notes

1. Ulam (1964a, 1964b).
2. Recaman (1973) gives a similar argument, phrased as a proof by contradiction. He states that, if there were finitely many Ulam numbers, then the sum of the last two would also be an Ulam number – a contradiction. However, although the sum of the last two numbers would in this case have a unique representation as a sum of two Ulam numbers, it would not necessarily be the smallest number with a unique representation.
3. The statement that Ulam made this conjecture is in OEIS  A002858, but Ulam does not address the density of this sequence in Ulam (1964a), and in Ulam (1964b) he poses the question of determining its density without conjecturing a value for it. Recaman (1973) repeats the question from Ulam (1964b) of the density of this sequence, again without conjecturing a value for it.
4. OEIS  A002858
5. Steinerberger (2015)
6. Queneau (1972) first observed the regularity of the sequences for u = 2 and v = 7 and v = 9. Finch (1992) conjectured the extension of this result to all odd v greater than three, and this conjecture was proven by Schmerl & Spiegel (1994). The regularity of the (4, v)-Ulam numbers was proven by Cassaigne & Finch (1995).
7. Queneau (1972).
8. Finch (1992).

References

• Cassaigne, Julien; Finch, Steven R. (1995), "A class of 1-additive sequences and quadratic recurrences", Experimental Mathematics, 4 (1): 49–60, doi:10.1080/10586458.1995.10504307, MR 1359417
• Finch, Steven R. (1992), "On the regularity of certain 1-additive sequences", Journal of Combinatorial Theory, Series A, 60 (1): 123–130, doi:10.1016/0097-3165(92)90042-S, MR 1156652
• Guy, Richard (2004), Unsolved Problems in Number Theory (3rd ed.), Springer-Verlag, pp. 166–167, ISBN 0-387-20860-7
• Queneau, Raymond (1972), "Sur les suites s-additives", Journal of Combinatorial Theory, Series A (in French), 12 (1): 31–71, doi:10.1016/0097-3165(72)90083-0, MR 0302597
• Recaman, Bernardo (1973), "Questions on a sequence of Ulam", American Mathematical Monthly, 80 (8): 919–920, doi:10.2307/2319404, JSTOR 2319404, MR 1537172
• Schmerl, James; Spiegel, Eugene (1994), "The regularity of some 1-additive sequences", Journal of Combinatorial Theory, Series A, 66 (1): 172–175, doi:10.1016/0097-3165(94)90058-2, MR 1273299
• Ulam, Stanislaw (1964a), "Combinatorial analysis in infinite sets and some physical theories", SIAM Review, 6: 343–355, doi:10.1137/1006090, JSTOR 2027963, MR 0170832
• Ulam, Stanislaw (1964b), Problems in Modern Mathematics, New York: John Wiley & Sons, Inc, p. xi, MR 0280310
• Steinerberger, Stefan (2015), A Hidden Signal in the Ulam sequence, Experimental Mathematics, arXiv:1507.00267

External links

• Ulam Sequence from MathWorld
• Fast computation of the Ulam sequence by Philip Gibbs
• Description of Algorithm by Donald Knuth
• The github page of Daniel Ross