Illuminating the Ulam

Perl Weekly Challenge 144, task 2 states:

The challenge

Write a script to generate Ulam Sequence having at least 10 Ulam numbers where $u and $v are the first 2 Ulam numbers.

The first two numbers in an Ulam sequence are the lesser (U1) and the greater (U2) of $u and $v.

Then for n > 2, Un 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.

The solution

So how do we go about this?  If we know U1 to Un, how do we calculate Un+1?

The initial thought is that we need to find the sums of all possible pairs, Uj and Uk, chosen from U1 to Un. Clearly, there are n(n - 1) such pairs, and we are looking for the one that:

- exceeds Un,
- is unique (ie the sum is not the same as any of the other sums),
- is the lowest such number.

We can cut the number of pairs to consider by half by insisting that Uj is less than Uk.  So our nested loops look some thing like:

for j = 1 to n - 1 {
    for k = j + 1 to n {
        consider Uj + Uk
    }
}

Note that we have also eliminated the cases where j = k, as required.  But what does 'consider' need to do?

The easy first step is to discard any Uj + Uk that is less than Un.  We can then can consider whether this Uj + Uk is unique, so we need to keep a tally of the times that sum has come up, and I think the easiest way to do that is simply to use an array, say 'times', and to increment times[Uj + Uk] for each pair of values. 

By the end of our nested loops, then, we have a sparse array 'times', with the populated elements being the number of times we have made that index from a pair of the values of U1 to Un.  So if 10 has come up twice - say 6 + 4 and 3 + 7, times[10] will be 2, and if 11 has come up only once, say 5 + 6, then times[11]  will be 1.

Now all we have to do is to search up from times[Un + 1] for the first element with the value 1, and assign that to U[n + 1]. 

The time to do this increases exponentially with the number of elements. On my (quite slow) Raspberry Pi computer I can do 100 elements in milliseconds, but 500 takes 4 seconds and 1000 takes 37 seconds.