Ulam numbers

From Wikipedia, the free encyclopedia

A Ulam number is a member of an integer sequence which was devised by Stanislaw Ulam and published in SIAM Review in 1964. The standard Ulam sequence (the (1, 2)-Ulam sequence) starts with U₁=1 and U₂=2 being the first two Ulam numbers. 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 (Guy 2004:166-67). Ulam conjectured that the numbers have zero density, but they seem to have a density of approximately 0.07396.

1 Examples
2 Generalization
3 Sample code
4 References
5 External links

[edit] Examples

By the definition, 3=1+2 is an Ulam number; and 4=1+3 is an Ulam number (The sum 4=2+2 doesn't count 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 (sequence A002858 in 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 (A068820).

[edit] Generalization

The idea can be generalized as (u, v)-Ulam Numbers by selecting different starting values (u, v) and by requiring that the terms be a sum of "s" previous terms in a given number "t" of ways, referred as an (s, t)-Additive Sequence or as an s-Additive Sequence for the standard case t = 2.

[edit] Sample code

Here is some sample (non-optimized) Python code that generates all Ulam numbers less than 1000.

ulam_i = [1,2,3]
ulam_j = [1,2,3]
for cand in range(4,1000):
    res = []
    for i in ulam_i:
        for j in ulam_j:
            if i == j or j > i: pass
            else:
                res.append(i+j)
    if res.count(cand) == 1:
        ulam_i.append(cand)
        ulam_j.append(cand)
print ulam_i