Task — Ulam sequence

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

The standard Ulam sequence (the (1, 2)-Ulam sequence) starts with U1 = 1 and U2 = 2. 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.

For more information about Ulam Sequence, please checkout Wikipedia.

Examples

Example 1
Input: $u = 1, $v = 2
Output: 1, 2, 3, 4, 6, 8, 11, 13, 16, 18

Example 2
Input: $u = 2, $v = 3
Output: 2, 3, 5, 7, 8, 9, 13, 14, 18, 19

Example 3
Input: $u = 2, $v = 5
Output: 2, 5, 7, 9, 11, 12, 13, 15, 19, 23

Analysis

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

My 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 @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.

Try it 

Script

#!/usr/bin/perl

# Peter Campbell Smith - 2021-12-20
# PWC 144 task 2

use v5.20;
use warnings;
use strict;

my (@tests, $test, $max_terms, @times, $t, @ulam, $j, $k, $try, $next, $last, $ulam_j, $line);

#          u  v  max
@tests = ([1, 2, 10], [2, 3, 10], [2, 5, 100], [123, 456, 200]);

for $test (@tests) {
    ($ulam[1], $ulam[2], $max_terms) = @$test;
    say qq[\n$max_terms terms of the Ulam sequence starting with $ulam[1], $ulam[2]:];
    $line = '';

    # loop over terms
    for $t (3 .. $max_terms) {
        
        # try all the preceding pairs
        @times = ();
        $last = $ulam[$t - 1];
        for $j (1 .. $t - 2) {
            $ulam_j = $ulam[$j];   # to optimise the inner loop
            for $k ($j + 1 .. $t - 1) {
                $times[$ulam_j + $ulam[$k]] ++;   # no of times that $try has been found
            }
        }
        
        # now find the smallest $try where $times[$try] == 1 (which will always exist, 
        # because ulam[$t - 1] + $ulam[$t - 2] must be a unique sum)
        for $try ($last + 1 .. $last + $ulam[$t - 2]) {
            next unless defined $times[$try];
            if ($times[$try] == 1) {   # got it!
                $ulam[$t] = $try;
                last;
            }
        }       
    }
    
    # and show the answer
    for $j (1 .. $max_terms) {
        if (length($line) + length($ulam[$j]) > 56) {
            say $line;
            $line = '';
        }
        $line .= qq[$ulam[$j] ];
    }
    say $line;
}
    

Output

10 terms of the Ulam sequence starting with 1, 2:
1 2 3 4 6 8 11 13 16 18

10 terms of the Ulam sequence starting with 2, 3:
2 3 5 7 8 9 13 14 18 19

100 terms of the Ulam sequence starting with 2, 5:
2 5 7 9 11 12 13 15 19 23 27 29 35 37 41 43 45 49 51 55
61 67 69 71 79 83 85 87 89 95 99 107 109 119 131 133 135
137 139 141 145 149 153 155 161 163 167 169 171 175 177
181 187 193 195 197 205 209 211 213 215 221 225 233 235
245 257 259 261 263 265 267 271 275 279 281 287 289 293
295 297 301 303 307 313 319 321 323 331 335 337 339 341
347 351 359 361 371 383 385

200 terms of the Ulam sequence starting with 123, 456:
123 456 579 702 825 948 1035 1071 1194 1317 1440 1491
1563 1686 1737 1809 1932 1947 1983 2055 2178 2229 2301
2403 2424 2475 2547 2649 2670 2721 2793 2859 2895 2916
2967 3039 3141 3162 3213 3285 3315 3387 3408 3459 3531
3561 3633 3654 3705 3771 3777 3807 3879 3900 3951 4023
4053 4125 4146 4197 4227 4269 4299 4371 4392 4443 4473
4515 4545 4617 4638 4683 4689 4719 4761 4791 4863 4884
4935 4965 5007 5037 5109 5130 5139 5181 5211 5253 5283
5355 5376 5385 5427 5457 5499 5529 5595 5601 5622 5631
5673 5703 5745 5775 5847 5868 5877 5919 5949 5991 6021
6051 6093 6114 6123 6165 6195 6237 6267 6297 6339 6360
6369 6411 6441 6483 6507 6513 6543 6585 6606 6615 6657
6687 6729 6759 6789 6831 6852 6861 6903 6933 6963 6975
7005 7035 7077 7098 7107 7149 7179 7209 7221 7251 7281
7323 7344 7353 7395 7419 7425 7455 7467 7497 7527 7569
7590 7599 7641 7671 7701 7713 7743 7773 7815 7836 7845
7875 7887 7917 7947 7959 7989 8019 8061 8082 8091 8121
8133 8163 8193 8205 8235 8265 8307 8328 8331 8337 8367
8379