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()

Introduction

Yet another blog on number theory? Better yet, yet another blog on number theory with no substance to it? Well... yes. This is mostly for my own amusement. I am in the process of acquainting myself with the topic. This is purely in the hobby realm. I am not a student. I am not a mathematician, and what little training I have had on the subject is many years old at this point, and mostly forgotten. I will be using a number of books supplemented by various websites to explore this topic. 

Where does that leave us? Well, that means that I will mostly be rehashing pretty elementary topics that you can probably find coverage on in any number of other places. It also means, that little of what I write here will be novel. And really, in the unlikely event that I come up with the latest proof of Fermat's Last Theorem... well I will post it here after it has been published elsewhere. 

So join me on this journey. A journey that promises to be wandering, mundane, and uninsightful.