Ulam Sequence

Almost everyone is familiar with Fibonacci sequence. I remember first learning about this in high school math and science classes. Later, I would explore it more, albeit tangentially, in computer science as I coded it over and over again to demonstrate recursion and iteration. However, I only recently learned of a somewhat similar sequence, the Ulam sequence. Today I will explore the basics of this sequence and provide a simple (and very inefficient) program to calculate the sequence. Overall, I am intrigued by this topic, so it may become a recurring topic as I explore it more.

First, let's discuss what the Ulam Sequence is. The official definition is: "The Ulam sequence  is defined by , , with the general term  for  given by the least integer expressible uniquely as the sum of two distinct earlier terms." (Wolfram) What this means is that if you have a number greater than 2, it is a Ulam number if and only if, it is the unique sum of two other Ulam numbers.

The normal example is that the series starts with 1, 2, 3, 4, 6, 8, 11. 3 is the unique sum of 1 and 2. 4 is the unique sum of 3 and 1; while it is also the sum of 2 and 2, you can only use the same number once. 5 is not a Ulam number. It is the sum of 4 and 1 and 3 and 2. Once you get past these initial numbers, you can also ignore the sum of non-Ulam numbers in making the final determination. For example, 8 is the unique sum of 6 and 2. It is also the sum of 7 and 1, but since 7 is not a Ulam number, it does not invalidate 8. 

Additional resources and references:

In addition to the links above, Donald Knuth notes that a bitwise algorithm can be used to speed up the calculation of the series through 1,000,000. 

Richard Guy list several of the open questions regarding the series in his book Unsolved Problems in Number Theory.

And the Online Encyclopedia of Integer Sequences lists the currently known members of the series.

Finally, below is the simple program that I created while working through this. I make no claim to it being efficient, or even accurate, but it does match the listed sequence for U100 and below. It starts to bog down around 26,000. 

def ulam_count():

    i = 3400

    j = 3

    u = [1,2]

    while(j <= i):

        c = 0

        for a in u:

            for b in u:

                if( a >= b): 

                    pass

                elif((a + b) == j):

                    c = c + 1

                else:

                    pass

        if(c == 1):

            u.append(j)

        j = j +1

        u.sort()

   print(u)

ulam_count()