With the following initial conditions:

Ulam numbers is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
      u1 = 1 
      u2 = 2 

We define the   nth   Ulam number   un   as the smallest number that is greater than   un-1     and
is the unique sum of two different Ulam numbers   ui (<n)   and   uj (<n).


Task

Write a function to generate the   nth   Ulam number.


References



11l

Translation of: Python
F ulam(n)
   I n <= 2
      R n
   V mx = 1352000
   V lst = [1, 2] [+] [0] * mx
   V sums = [0] * (mx * 2 + 1)
   sums[3] = 1
   V size = 2
   Int query
   L size < n
      query = lst[size - 1] + 1
      L
         I sums[query] == 1
            L(i) 0 .< size
               V sum = query + lst[i]
               V t = sums[sum] + 1
               I t <= 2
                  sums[sum] = t
            (lst[size], size) = (query, size + 1)
            L.break
         query++
   R query

L(p) 5
   V n = 10 ^ p
   print(‘The #.#. Ulam number is #.’.format(n, I n != 1 {‘th’} E ‘st’, ulam(n)))
Output:
The 1st Ulam number is 1
The 10th Ulam number is 18
The 100th Ulam number is 690
The 1000th Ulam number is 12294
The 10000th Ulam number is 132788

360 Assembly

*        Ulam numbers 25/01/2021
ULAMNUM  CSECT
         USING  ULAMNUM,R13        base register
         B      72(R15)            skip savearea
         DC     17F'0'             savearea
         SAVE   (14,12)            save previous context
         ST     R13,4(R15)         link backward
         ST     R15,8(R13)         link forward
         LR     R13,R15            set addressability
         LA     R1,1               1
         ST     R1,ULAM            ulam(1)=1
         LA     R1,2               2
         ST     R1,ULAM+4          ulam(2)=2
         LA     R9,2               k=2
         LA     R8,2               n=2
       DO  WHILE=(C,R9,LT,NN)      do while k<nn
         LA     R8,1(R8)             n=n+1
         XR     R10,R10              count=0       
         LR     R0,R9                k
         BCTR   R0,0                 -1
         LA     R6,1                 i=1
       DO  WHILE=(CR,R6,LE,R0)       do i=1 to k-1
         LR     R7,R6                  i
         LA     R7,1(R7)               j=i+1
       DO  WHILE=(CR,R7,LE,R9)         do j=i+1 to k
         LR     R1,R6                    i
         SLA    R1,2                     ~
         L      R2,ULAM-4(R1)            ulam(i)
         LR     R1,R7                    j
         SLA    R1,2                     ~
         L      R3,ULAM-4(R1)            ulam(j)
         AR     R2,R3                    ulam(i)+ulam(j)
       IF    CR,R2,EQ,R8 THEN            if ulam(i)+ulam(j)=n then    
         LA     R10,1(R10)                 count=count+1
       ENDIF    ,                        endif
         LA     R7,1(R7)                 j++
       ENDDO    ,                      enddo j
         LA     R6,1(R6)               i++
       ENDDO    ,                    enddo i
       IF     C,R10,EQ,=F'1' THEN    if count=1 then    
         LA     R9,1(R9)               k=k+1
         LR     R1,R9                  k
         SLA    R1,2                   ~
         ST     R8,ULAM-4(R1)          ulam(k)=n
         LR     R4,R9                  k
         SRDA   R4,32                  ~
         D      R4,=F'50'              k/50  
       IF   LTR,R4,Z,R4 THEN           if mod(k,50)=0 then
         XDECO  R9,PG                    k
         XDECO  R8,PG+12                 n
         XPRNT  PG,L'PG                  print buffer
       ENDIF    ,                      endif
       ENDIF    ,                    endif
       ENDDO    ,                  enddo n
         L      R13,4(0,R13)       restore previous savearea pointer
         RETURN (14,12),RC=0       restore registers from calling save
U        EQU    500                u : max value
NN       DC     A(U)               nn
ULAM     DS     (U)F               ulam(u)
PG       DC     CL80' '            buffer
         REGEQU 
         END    ULAMNUM
Output:
          50         253
         100         690
         150        1257
         200        1792
         250        2484
         300        3068
         350        3632
         400        4326
         450        4996
         500        5685

Action!

Calculations on a real Atari 8-bit computer take quite long time. It is recommended to use an emulator capable with increasing speed of Atari CPU.

PROC Main()
  DEFINE MAX="1000"
  INT ARRAY ulam(MAX)
  INT uCount,n,count,x,y
  BYTE flag

  ulam(0)=1 ulam(1)=2 uCount=2
  PrintI(ulam(0)) Put(32) PrintI(ulam(1))
  n=3
  WHILE uCount<MAX
  DO
    flag=0 count=0
    FOR x=0 TO uCount-2
    DO
      FOR y=x+1 TO uCount-1
      DO
        IF ulam(x)+ulam(y)=n THEN
          flag=1 count==+1
        FI
      OD
    OD
    IF flag=1 AND count=1 THEN
      ulam(uCount)=n uCount==+1
      Put(32) PrintI(n)
    FI
    n==+1
  OD
RETURN
Output:

Screenshot from Atari 8-bit computer

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 102 106 114 126 131 138 145 148 155 175 ...


Ada

Translation of: C
pragma Ada_2022;                    --  enables Ada 2022 features

--  Ada has a lot of safety checks that are turned on by default.
--  It is possible to turn them off, especially when you know they aren't needed,
--  but this should be done only when you've done your homework.
--  Turning this one off makes the program nearly 30x slower on my machine;
--  you may want to see how it works differently on yours.
pragma Suppress (All_Checks);
--  pragma Suppress (Tampering_Check);

with Ada.Containers.Vectors;

with Ada.Real_Time;
use all type Ada.Real_Time.Time_Span;  --  makes Time_Span's operators public

with Ada.Text_IO;

procedure Ulam_Numbers is

   package IO renames Ada.Text_IO;

   package IntVecs is new Ada.Containers.Vectors
     (Index_Type => Positive, Element_Type => Natural);
   subtype IntVec is IntVecs.Vector;

   Something_Went_Wrong : exception;

   function Ulam (Nth : Positive) return Positive is
      Numbers, Sieve : IntVec;
      Ith            : Positive := 2;
   begin
      --  initialize
      Numbers.Append (1);
      Numbers.Append (2);
      Sieve.Append (1);
      Sieve.Append (1);

      --  main loop
      while Positive (Numbers.Length) < Nth loop

         declare
            Old_Length : constant Positive := Positive (Sieve.Length) + 1;
            Extend_To  : constant Positive :=
              Ith + Numbers (Numbers.Last_Index);
         begin

            --  extend sieve
            Sieve.Set_Length (Ada.Containers.Count_Type (Extend_To));
            for Jth in Old_Length .. Extend_To loop
               Sieve (Jth) := 0;
            end loop;

            for Number of Numbers loop
               Sieve (Ith + Number) := Sieve (Ith + Number) + 1;
            end loop;
            Sieve (Ith + Numbers.Last_Element) :=
              Sieve (Ith + Numbers.Last_Element) - 1;

            Ith := Sieve.Find_Index (1, Ith + 1);
            if Ith > Positive (Sieve.Length) then
               raise Something_Went_Wrong with "Iteration" & Ith'Image;
            end if;
            Numbers.Append (Ith);

         end;

      end loop;

      return Numbers.Last_Element;

   end Ulam;

   Start, Stop : Ada.Real_Time.Time;
   Total_Time  : Ada.Real_Time.Time_Span := Ada.Real_Time.Time_Span_Zero;

   Entries_To_Compute : constant array (Positive range <>) of Integer :=
     [10, 100, 1_000, 10_000, 100_000];

begin

   Start := Ada.Real_Time.Clock;

   for Ith of Entries_To_Compute loop
      IO.Put_Line ("The" & Ith'Image & "th Ulam number is" & Ulam (Ith)'Image);
   end loop;

   Stop       := Ada.Real_Time.Clock;
   Total_Time := (@ + Stop) - Start;
   IO.Put_Line ("Elapsed time: " & Total_Time'Image);

end Ulam_Numbers;
Output:
The 10th Ulam number is 18
The 100th Ulam number is 690
The 1000th Ulam number is 12294
The 10000th Ulam number is 132788
The 100000th Ulam number is 1351223
Elapsed time:  20.473358675

ALGOL 68

Basically, the same algotithm as XPL0.

BEGIN # find some Ulam numbers, U(n) = the smallest number > U(n-1) that is  #
      # the uniue sum of U(i) and U(j), i, j < n, i =/= j, U(1)=1, U(2) = 2  #
    INT max ulam  = 10 000;                    # maximum ulam number to find #
    [ 1 : max ulam ]INT u;                              # ulam numbers found #
    FOR i TO UPB u DO u[ i ] := 0 OD;
    INT ulam size = 20 000;         # initial size of the ulam number buffer #
    CHAR unused = "0", one = "1", multiple = "2";   # states of ulam numbers #
    FLEX[ 1 : ulam size ]CHAR ulam;FOR i TO UPB ulam DO ulam[ i ] := unused OD;
    ulam[ 3 ] := ulam[ 2 ] := ulam[ 1 ] := one; u[ 1 ] := 1; u[ 2 ] := 2;
    print( ( " 1 2" ) );
    INT u count      :=   2;                  # numer of ulam numbers found  #
    INT power of ten := 100;       # next "power of ten" ulam number to show #
    FOR i FROM 3 WHILE u count < max ulam DO
        IF ulam[ i ] = one THEN
            # can use this number                                            #
            u[ u count +:= 1 ] := i;
            IF u count < 21 THEN
                print( ( " ", whole( i, 0 ) ) );
                IF u count = 20 THEN print( ( "..." ) ) FI
            ELIF u count = power of ten THEN
                print( ( newline, "The ", whole( power of ten, -6 ) ) );
                print( ( "th Ulam number is: ", whole( i, 0 ) ) );
                power of ten *:= 10
            FI;
            FOR p TO u count - 1 DO
                INT upi = u[ p ] + i;
                IF upi > UPB ulam THEN
                    # need a bigger ulam buffer                              # 
                    [ 1 : UPB ulam + ulam size ]CHAR new ulam;
                    new ulam[ 1 : UPB ulam ] := ulam;
                    FOR u pos FROM UPB ulam + 1 TO UPB new ulam DO new ulam[ u pos ] := unused OD;
                    ulam := new ulam
                FI;
                CHAR upic = ulam[ upi ];
                IF   upic = unused
                THEN ulam[ upi ] := one         # u[ p ] + i is unique so far #
                ELIF upic = one
                THEN ulam[ upi ] := multiple    # u[ p ] + i isn't unique     #
                FI
            OD
        FI
    OD;
    print( ( newline ) )
END
Output:
 1 2 3 4 6 8 11 13 16 18 26 28 36 38 47 48 53 57 62 69...
The    100th Ulam number is: 690
The   1000th Ulam number is: 12294
The  10000th Ulam number is: 132788

AWK

# syntax: GAWK -f ULAM_NUMBERS.AWK
BEGIN {
    u = split("1,2",ulam,",")
    for (n=3; ; n++) {
      count = 0
      for (x=1; x<=u-1; x++) {
        for (y=x+1; y<=u; y++) {
          if (ulam[x] + ulam[y] == n) {
            count++
          }
        }
      }
      if (count == 1) {
        ulam[++u] = n
        if (u ~ /^(10|50|100|500|1000)$/) {
          printf("%6d %6d\n",u,n)
          if (++shown >= 5) { break }
        }
      }
    }
    exit(0)
}
Output:
    10     18
    50    253
   100    690
   500   5685
  1000  12294

C

Translation of: Phix
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

void fatal(const char* message) {
    fprintf(stderr, "%s\n", message);
    exit(1);
}

void* xmalloc(size_t n) {
    void* ptr = malloc(n);
    if (ptr == NULL)
        fatal("Out of memory");
    return ptr;
}

void* xrealloc(void* p, size_t n) {
    void* ptr = realloc(p, n);
    if (ptr == NULL)
        fatal("Out of memory");
    return ptr;
}

int* extend(int* array, int min_length, int* capacity) {
    int new_capacity = *capacity;
    if (new_capacity >= min_length)
        return array;
    while (new_capacity < min_length)
        new_capacity *= 2;
    array = xrealloc(array, new_capacity * sizeof(int));
    memset(array + *capacity, 0, (new_capacity - *capacity) * sizeof(int));
    *capacity = new_capacity;
    return array;
}

int ulam(int n) {
    int* ulams = xmalloc((n < 2 ? 2 : n) * sizeof(int));
    ulams[0] = 1;
    ulams[1] = 2;
    int sieve_length = 2;
    int sieve_capacity = 2;
    int* sieve = xmalloc(sieve_capacity * sizeof(int));
    sieve[0] = sieve[1] = 1;
    for (int u = 2, ulen = 2; ulen < n; ) {
        sieve_length = u + ulams[ulen - 2];
        sieve = extend(sieve, sieve_length, &sieve_capacity);
        for (int i = 0; i < ulen - 1; ++i)
            ++sieve[u + ulams[i] - 1];
        for (int i = u; i < sieve_length; ++i) {
            if (sieve[i] == 1) {
                u = i + 1;
                ulams[ulen++] = u;
                break;
            }
        }
    }
    int result = ulams[n - 1];
    free(ulams);
    free(sieve);
    return result;
}

int main() {
    clock_t start = clock();
    for (int n = 1; n <= 100000; n *= 10)
        printf("Ulam(%d) = %d\n", n, ulam(n));
    clock_t finish = clock();
    printf("Elapsed time: %.3f seconds\n", (finish - start + 0.0)/CLOCKS_PER_SEC);
    return 0;
}
Output:
Ulam(1) = 1
Ulam(10) = 18
Ulam(100) = 690
Ulam(1000) = 12294
Ulam(10000) = 132788
Ulam(100000) = 1351223
Elapsed time: 8.630 seconds

C++

Translation of: Phix
#include <algorithm>
#include <chrono>
#include <iostream>
#include <vector>

int ulam(int n) {
    std::vector<int> ulams{1, 2};
    std::vector<int> sieve{1, 1};
    for (int u = 2; ulams.size() < n; ) {
        sieve.resize(u + ulams[ulams.size() - 2], 0);
        for (int i = 0; i < ulams.size() - 1; ++i)
            ++sieve[u + ulams[i] - 1];
        auto it = std::find(sieve.begin() + u, sieve.end(), 1);
        if (it == sieve.end())
            return -1;
        u = (it - sieve.begin()) + 1;
        ulams.push_back(u);
    }
    return ulams[n - 1];
}

int main() {
    auto start = std::chrono::high_resolution_clock::now();
    for (int n = 1; n <= 100000; n *= 10)
        std::cout << "Ulam(" << n << ") = " << ulam(n) << '\n';
    auto end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> duration(end - start);
    std::cout << "Elapsed time: " << duration.count() << " seconds\n";
}
Output:
Ulam(1) = 1
Ulam(10) = 18
Ulam(100) = 690
Ulam(1000) = 12294
Ulam(10000) = 132788
Ulam(100000) = 1351223
Elapsed time: 9.09242 seconds

Delphi

Translation of: Phix
Works with: Delphi version 6.0


function GetUlamNumber(N: integer): integer;
var Ulams: array of integer;
var U,ULen,I: integer;
var Sieve: array of integer;
begin
SetLength(Ulams,Max(N,2));
Ulams[0]:= 1;
Ulams[1]:= 2;
SetLength(Sieve, 2);
Sieve[0]:=1;
Sieve[1]:= 1;
U:=2; ULen:=2;
while Ulen < N do
	begin
	SetLength(Sieve,U + Ulams[Ulen - 2]);
	for I:= 0 to ulen - 2 do
	Sieve[u + Ulams[I] - 1]:=Sieve[u + Ulams[i] - 1]+1;
	for I:=U to High(Sieve) do
	 if Sieve[I] = 1 then
		begin
		U:=I + 1;
		Ulams[Ulen]:=U;
		Inc(ULen);
		break;
		end;
	end;
Result:=ULams[N - 1];
end;



procedure ShowUlamNumbers(Memo: TMemo);
var N: integer;
var S: string;
begin
N:=1;
while N<=100000 do
	begin
	S:=Format('Ulam(%d)',[N]);
	Memo.Lines.Add(Format('%-12S = %8d', [S, GetUlamNumber(N)]));
	N:=N * 10
	end;
end;
Output:
Ulam(1)      =        1
Ulam(10)     =       18
Ulam(100)    =      690
Ulam(1000)   =    12294
Ulam(10000)  =   132788
Ulam(100000) =  1351223

Elapsed Time: 17.685 Sec.


EasyLang

Translation of: Ring
func getulam n .
   ulam[] = [ 1 2 ]
   i = 3
   repeat
      cnt = 0
      for x = 1 to len ulam[] - 1
         ux = ulam[x]
         for y = x + 1 to len ulam[]
            if ux + ulam[y] >= i
               if ux + ulam[y] > i
                  break 1
               .
               cnt += 1
               if cnt > 1
                  break 2
               .
            .
         .
      .
      if cnt = 1
         ulam[] &= i
      .
      until len ulam[] = n
      i += 1
   .
   return i
.
print getulam 100
Output:
690

FreeBASIC

redim as uinteger ulam(1 to 2)
ulam(1) = 1 : ulam(2) = 2

function get_ulam( n as uinteger, ulam() as uinteger ) as uinteger
    dim as uinteger nu = ubound(ulam), c, r, s, t, i, usr
    if n <= nu then return ulam(n) 'if we have already calculated this one, just return it
    'otherwise, calculate it and all intermediate terms
    redim preserve ulam(1 to n)
    for t = nu+1 to n
        i = ulam(t-1)
        while true
            i += 1 : c = 0
            for r = 1 to t-2
                for s = r+1 to t-1
                    usr = ulam(s)+ulam(r)
                    if usr > i then exit for  'efficiency
                    if usr = i then
                        if c = 1 then continue while
                        c += 1
                    end if
                next s
            next r
            if c = 0 then continue while 'I'm not 100% sure this is even possible...
            ulam(t) = i
            exit while
        wend
    next t
    return ulam(n)
end function


for i as uinteger = 1 to 4
    print 10^i, get_ulam(10^i, ulam())
next i
Output:
 10          18
 100          690
 1000        12294
 10000        132788

Go

Version 1

Translation of: Wren
package main

import "fmt"

func ulam(n int) int {
    ulams := []int{1, 2}
    set := map[int]bool{1: true, 2: true}
    i := 3
    for {
        count := 0
        for j := 0; j < len(ulams); j++ {
            _, ok := set[i-ulams[j]]
            if ok && ulams[j] != (i-ulams[j]) {
                count++
                if count > 2 {
                    break
                }
            }
        }
        if count == 2 {
            ulams = append(ulams, i)
            set[i] = true
            if len(ulams) == n {
                break
            }
        }
        i++
    }
    return ulams[n-1]
}

func main() {
    for n := 10; n <= 10000; n *= 10 {
        fmt.Println("The", n, "\bth Ulam number is", ulam(n))
    }
}
Output:
The 10th Ulam number is 18
The 100th Ulam number is 690
The 1000th Ulam number is 12294
The 10000th Ulam number is 132788

Version 2

Translation of: Phix

The above version is reasonably efficient and runs in about 2.9 seconds on my machine (Intel Core i7-8565U). The following version, which builds up a sieve as it goes along, is (astonishingly) about 40 times faster!

Although not shown here, the 100,000th Ulam number (1,351,223) is computed in about 13.5 seconds.

package main

import (
    "fmt"
    "time"
)

func ulam(n int) int {
    ulams := []int{1, 2}
    sieve := []int{1, 1}
    u := 2
    for len(ulams) < n {
        s := u + ulams[len(ulams)-2]
        t := s - len(sieve)
        for i := 0; i < t; i++ {
            sieve = append(sieve, 0)
        }
        for i := 1; i <= len(ulams)-1; i++ {
            v := u + ulams[i-1] - 1
            sieve[v]++
        }
        index := -1
        for i, e := range sieve[u:] {
            if e == 1 {
                index = u + i
                break
            }
        }
        u = index + 1
        ulams = append(ulams, u)
    }
    return ulams[n-1]
}

func commatize(n int) string {
    s := fmt.Sprintf("%d", n)
    if n < 0 {
        s = s[1:]
    }
    le := len(s)
    for i := le - 3; i >= 1; i -= 3 {
        s = s[0:i] + "," + s[i:]
    }
    if n >= 0 {
        return s
    }
    return "-" + s
}

func main() {
    start := time.Now()
    for n := 1; n <= 10000; n *= 10 {
        s := "th"
        if n == 1 {
            s = "st"
        }
        fmt.Println("The", commatize(n), "\b"+s+" Ulam number is", commatize(ulam(n)))
    }
    fmt.Println("\nTook", time.Since(start))
}
Output:
The 1st Ulam number is 1
The 10th Ulam number is 18
The 100th Ulam number is 690
The 1,000th Ulam number is 12,294
The 10,000th Ulam number is 132,788

Took 74.45373ms

Version 3

Translation of: XPL0

This version is even quicker than Version 2 and reduces the time needed to calculate the 10,000th and 100,000th Ulam numbers to about 40 milliseconds and 3.25 seconds respectively.

As mentioned in the Wren version 3 example, you need to know how much memory to allocate in advance.

package main

import (
    "fmt"
    "time"
)

func ulam(n int) int {
    if n <= 2 {
        return n
    }
    const MAX = 1_352_000
    list := make([]int, MAX+1)
    list[0], list[1] = 1, 2
    sums := make([]byte, 2*MAX+1)
    sums[3] = 1
    size := 2
    var query int
    for {
        query = list[size-1] + 1
        for {
            if sums[query] == 1 {
                for i := 0; i < size; i++ {
                    sum := query + list[i]
                    t := sums[sum] + 1
                    if t <= 2 {
                        sums[sum] = t
                    }
                }
                list[size] = query
                size++
                break
            }
            query++
        }
        if size >= n {
            break
        }
    }
    return query
}

func commatize(n int) string {
    s := fmt.Sprintf("%d", n)
    if n < 0 {
        s = s[1:]
    }
    le := len(s)
    for i := le - 3; i >= 1; i -= 3 {
        s = s[0:i] + "," + s[i:]
    }
    if n >= 0 {
        return s
    }
    return "-" + s
}

func main() {
    start := time.Now()
    for n := 10; n <= 100000; n *= 10 {
        fmt.Println("The", commatize(n), "\bth Ulam number is", commatize(ulam(n)))
    }
    fmt.Println("\nTook", time.Since(start))
}
Output:
The 10th Ulam number is 18
The 100th Ulam number is 690
The 1,000th Ulam number is 12,294
The 10,000th Ulam number is 132,788
The 100,000th Ulam number is 1,351,223

Took 3.226255944s

Haskell

Lazy List

import Data.List

ulam 
  :: Integral i =>
     Int -> i
ulam 1 = 1
ulam 2 = 2
ulam n
  | n > 2 = ulams !! (n-1)

ulams
  :: Integral n =>
     [n]
ulams = 1:2:(nexts [2,1])
nexts us = u: (nexts (u:us))
  where
    n = length us
    [u] = head . filter isSingleton . group . sort  $ 
            [v | i <- [0 .. n-2], j <- [i+1 .. n-1] 
               , let s = us !! i
               , let t = us !! j
               , let v = s+t
               , v > head us
               ]

isSingleton :: [a] -> Bool
isSingleton as
  | length as == 1 = True
  | otherwise      = False

J

Implementation:

require'stats'
nextulam=: , {{<./(#~ ({:y)<])(~. #~ 1 = #/.~) +/"1 y{~2 comb #y}}
ulam=: <: { (nextulam^:(<:@(>./)`(1 2"_)))

This could be optimized, for example: caching could help.

Examples:

   ulam 1
1
   ulam 10
18
   ulam 100
690
   ulam 1000
12294
   ulam 10000
132788
   ulam 20 30 40 50 60
69 126 189 253 341

Java

Translation of: Phix
public class UlamNumbers {
    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        for (int n = 1; n <= 100000; n *= 10) {
            System.out.printf("Ulam(%d) = %d\n", n, ulam(n));
        }
        long finish = System.currentTimeMillis();
        System.out.printf("Elapsed time: %.3f seconds\n", (finish - start)/1000.0);
    }

    private static int ulam(int n) {
        int[] ulams = new int[Math.max(n, 2)];
        ulams[0] = 1;
        ulams[1] = 2;
        int sieveLength = 2;
        int[] sieve = new int[sieveLength];
        sieve[0] = sieve[1] = 1;
        for (int u = 2, ulen = 2; ulen < n; ) {
            sieveLength = u + ulams[ulen - 2];
            sieve = extend(sieve, sieveLength);
            for (int i = 0; i < ulen - 1; ++i)
                ++sieve[u + ulams[i] - 1];
            for (int i = u; i < sieveLength; ++i) {
                if (sieve[i] == 1) {
                    u = i + 1;
                    ulams[ulen++] = u;
                    break;
                }
            }
        }
        return ulams[n - 1];
    }

    private static int[] extend(int[] array, int minLength) {
        if (minLength <= array.length)
            return array;
        int newLength = 2 * array.length;
        while (newLength < minLength)
            newLength *= 2;
        int[] newArray = new int[newLength];
        System.arraycopy(array, 0, newArray, 0, array.length);
        return newArray;
    }
}
Output:
Ulam(1) = 1
Ulam(10) = 18
Ulam(100) = 690
Ulam(1000) = 12294
Ulam(10000) = 132788
Ulam(100000) = 1351223
Elapsed time: 9.098 seconds

jq

Adaptation of awk solution

# Input: the target number of Ulam numbers to generate
# Output: an array of Ulam numbers
def ulams:
  . as $target
  | label $done
  | {ulam: [1, 2],
     nulams: 2}
  | foreach range(3; infinite) as $n (.;
      .count = 0
      | .x = 0
      | until( .x == .nulams or .count > 1;
          .y = .x+1
	  | until( .y >= .nulams or .count > 1;
              if (.ulam[.x] + .ulam[.y] == $n) then .count += 1 else . end
	      | .y += 1)
	   | .x += 1)

       | if .count == 1 then .nulams += 1 | .ulam[.nulams-1] = $n else . end;
       select(.nulams >= $target) | .ulam, break $done);

def nth_ulam: ulams[.-1];

Illustration

(5 | nth_ulam) | "5 => \(.)",
"",
([5, 10, 100] as $in
 | (100|ulams) as $u
 | $in[]
 | "\(.) => \($u[. - 1])" )
Output:
5 => 6

5 => 6
10 => 18
100 => 690

Julia

Translation of: Wren
function nthUlam(n)
    ulams = [1, 2]
    memoized = Set([1, 2])
    i = 3
    while true
        count = 0
        for j in 1:length(ulams)
            if i - ulams[j] in memoized && ulams[j] != i - ulams[j]
                (count += 1) > 2 && break
            end
        end
        if count == 2
            push!(ulams, i)
            push!(memoized, i)
            length(ulams) == n && break
        end
        i += 1
    end
    return ulams[n]
end

nthUlam(5)

for n in [10, 100, 1000, 10000]
    @time println("The ", n, "th Ulam number is: ", nthUlam(n))
end
Output:
The 10th Ulam number is: 18
  0.000657 seconds (27 allocations: 1.422 KiB)
The 100th Ulam number is: 690
  0.000959 seconds (39 allocations: 7.094 KiB)
The 1000th Ulam number is: 12294
  0.027564 seconds (52 allocations: 72.188 KiB)
The 10000th Ulam number is: 132788
  3.076024 seconds (63 allocations: 473.125 KiB)

Lua

Implemented from scratch, but algorithmically equivalent to other solutions where a running count of number-of-ways-to-reach-sum is maintained in order to sieve candidate values.

function ulam(n)
  local ulams, nways, i = { 1,2 }, { 0,0,1 }, 3
  repeat
    if nways[i] == 1 then
      for j = 1, #ulams do
        local sum = i + ulams[j]
        nways[sum] = (nways[sum] or 0) + 1
      end
      ulams[#ulams+1] = i
    end
    i = i + 1
  until #ulams == n
  return ulams[#ulams]
end

for _,n in ipairs({10,100,1000,10000,100000}) do
  local s, u, e = os.clock(), ulam(n), os.clock()
  print(string.format("%dth is %d (%f seconds elapsed)", n, u, e-s))
end
Output:

Times are Lua 5.4 on i7-2600@3.4GHz

10th is 18 (0.000000 seconds elapsed)
100th is 690 (0.000000 seconds elapsed)
1000th is 12294 (0.020000 seconds elapsed)
10000th is 132788 (1.724000 seconds elapsed)
100000th is 1351223 (277.824000 seconds elapsed)

Nim

Phix algorithm

Translation of: Wren

This is a translation of Wren second solution which uses Phix algorithm.

It has been compiled with option -d:release which means that all runtime checks are done but debugging data is limited.

import strformat, times

func ulam(n: Positive): int =
  var
    ulams = @[1, 2]
    sieve = @[1, 1]
    u = 2
  while ulams.len < n:
    let s = u + ulams[^2]
    sieve.setLen(s)
    for i in 0..<ulams.high:
      let v = u + ulams[i] - 1
      inc sieve[v]
    for i in u..sieve.high:
      if sieve[i] == 1:
        u = i + 1
        break
    ulams.add u
  result = ulams[^1]

let t0 = cpuTime()
var n = 1
for _ in 0..4:
  let suffix = if n == 1: "st" else: "th"
  echo &"The {n}{suffix} Ulam number is {ulam(n)}."
  n *= 10
echo &"\nTook {cpuTime() - t0:.3f} s."
Output:

The program runs in about 150 ms on my laptop (i5-8250U with 8GB of RAM and running Linux Manjaro). It allows to get the 100_000th Ulam number in about 30 seconds.

The 1st Ulam number is 2.
The 10th Ulam number is 18.
The 100th Ulam number is 690.
The 1000th Ulam number is 12294.
The 10000th Ulam number is 132788.

Took 0.148 s.

XPL0 algorithm

Translation of: Wren

This is a translation of Wren third solution which uses XPL0 algorithm.

It has been compiled with the same option as the other version.

 import strformat, times

func ulam(n: Positive): int =
  if n <= 2: return n
  const Max = 1352000
  var list = newSeq[int](Max)
  list[0] = 1
  list[1] = 2
  var sums = newSeq[byte](2 * Max + 1)
  sums[3] = 1
  var size = 2
  var query: int
  while size < n:
    query = list[size-1] + 1
    while true:
      if sums[query] == 1:
        for i in 0..<size:
          let sum = query + list[i]
          let t = sums[sum] + 1
          if t <= 2: sums[sum] = t
        list[size] = query
        inc size
        break
      inc query
  result = query

let t0 = cpuTime()
var n = 10
while n <= 100_000:
  echo &"The {n}th Ulam number is {ulam(n)}."
  n *= 10
echo &"\nTook {cpuTime() - t0:.3f} s."
Output:

In a first translation, we got the result in about 24 seconds which is the time obtained by the XPL0 version on a less powerful machine. We found that declaring "sums" as a sequence of bytes (8 bits) instead of a sequence of integers (64 bits) makes a big difference. We then got the result in 5 seconds. Note than there are also some ways to improve the other algorithm by using 32 bits integers rather than 64 bits integers, but it will still remain at least 50 % less efficient.

The 10th Ulam number is 18.
The 10th Ulam number is 18.
The 100th Ulam number is 690.
The 1000th Ulam number is 12294.
The 10000th Ulam number is 132788.
The 100000th Ulam number is 1351223.

Took 4.986 s.

Pascal

Works with: Free Pascal

like GO,PHIX who was first

program UlamNumbers;
{$IFDEF FPC}
  {$MODE DELPHI}
  {$Optimization On,All}
{$ENDIF}
uses
  sysutils;
const
  maxUlam = 100000;
  Limit = 1351223+4000;
type
  tCheck  =  Uint16;
  tpCheck = pUint16;
var
  Ulams : array of Uint32;
  Check0 : array of tCheck;
  Ulam_idx :NativeInt;

procedure init;
begin
  setlength(Ulams,maxUlam);
  Ulams[0] := 1;
  Ulams[1] := 2;
  Ulam_idx := 1;
  setlength(check0,Limit);

  check0[1]:=1;
  check0[2]:=1;
end;

procedure OutData(idx,num:NativeInt);
Begin
  writeln(' Ulam(',idx+1,')',#9#9,num:10);
end;

function findNext(i:nativeInt;pCh0:tpCheck):NativeInt;
begin
  result := i;
  repeat
    if pCh0[result] = 1 then
      break;
    inc(result);
  until false;
end;

procedure SumOne(idx:NativeUint;pCh:tpCheck;pUlams:pUint32);
//seperated speeds up a lot by reducing register pressure in main
Begin
  For idx := idx downto 0 do
    pCh[pUlams[idx]] +=1;
end;

var
  pCh0,pCh : tpCheck;
  pUlams   : pUint32;
  ul,idx,lmtidx :nativeInt;
Begin

  Init;
  lmtidx := 9;
  pCh0:= @Check0[0];
  pUlams := @Ulams[0];
  OutData(0,pUlams[0]);
  ul := pUlams[Ulam_idx];
  pCh:= @pCh0[ul];
  repeat
    SumOne(Ulam_idx-1,pCh,pUlams);
    ul := findNext(ul+1,pCh0);
    inc(Ulam_idx);
    pUlams[Ulam_idx] := ul;
    pCh:= @pCh0[ul];
    IF ul>Limit DIV 2 then
      break;
    if Ulam_idx=lmtIdx then
    Begin
      OutData(Ulam_idx,ul);
      lmtidx := lmtidx*10+9;
    end;
  until Ulam_idx >= maxUlam-1;

  idx := Ulam_idx-1;
  //now reducing then the highest used summing idx
  while Ulam_idx< maxUlam-1 do
  begin
    while ul+pUlams[idx] > limit do
      dec(idx);
    SumOne(idx,pCh,pUlams);
    ul := findNext(ul+1,pCh0);
    inc(Ulam_idx);
    pUlams[Ulam_idx] := ul;
    pCh:= @pCh0[ul];
  end;
  OutData(Ulam_idx,ul);
  setlength(check0,0);
  setlength(Ulams,0);
end.
Output:
 Ulam(1)                 1
 Ulam(10)               18
 Ulam(100)             690
 Ulam(1000)          12294
 Ulam(10000)        132788
 Ulam(100000)      1351223

// real  0m4,731s AMD 2200G
//TIO.RUN
Free Pascal Compiler version 3.0.4 [2018/07/13] for x86_64
Copyright (c) 1993-2017 by Florian Klaempfl and others
Target OS: Linux for x86-64
Compiling .code.tio.pp
Linking .bin.tio
/usr/bin/ld: warning: link.res contains output sections; did you forget -T?
92 lines compiled, 0.2 sec

Real time: 3.025 s

Perl

Translation of: Julia
use strict;
use warnings;
use feature <say state>;

sub ulam {
    my($n) = @_;
    state %u     = (1 => 1, 2 => 1);
    state @ulams = <0 1 2>; # 0 a placeholder to shift indexing up one

    return $ulams[$n] if $ulams[$n];

    $n++;
    my $i = 3;

    while () {
        my $count = 0;
 
            $u{ $i - $ulams[$_] }
        and $ulams[$_] != $i - $ulams[$_]
        and $count++ > 2
        and last
            for 0..$#ulams;

            $count == 2
        and push(@ulams,$i)
        and $u{$i} = 1
        and @ulams == $n
        and last;

        $i++;
    }
    $ulams[$n-1];
}

printf "The %dth Ulam number is: %d\n", 10**$_, ulam(10**$_) for 1..4;
Output:
The 10th Ulam number is: 18
The 100th Ulam number is: 690
The 1000th Ulam number is: 12294
The 10000th Ulam number is: 132788
The 10000th Ulam number is: 132788

Phix

with javascript_semantics
function ulam(integer n)
    sequence ulams = {1, 2},
             sieve = {1, 1}
    integer u := 2
    while length(ulams)<n do
        integer s = u+ulams[$-1], t
        sieve &= repeat(0,s-length(sieve))
        for i=1 to length(ulams)-1 do
            s = u+ulams[i]
            t = sieve[s]+1
            if t<=2 then
                sieve[s] = t
            end if
        end for
        u = find(1,sieve,u+1)
        ulams &= u
    end while
    return ulams[n]
end function
 
atom t0 = time()
for p=0 to 4 do
    integer n = power(10,p)
    printf(1,"The %,d%s Ulam number is %,d\n",{n,ord(n),ulam(n)})
end for
?elapsed(time()-t0)
Output:
The 1st Ulam number is 1
The 10th Ulam number is 18
The 100th Ulam number is 690
The 1,000th Ulam number is 12,294
The 10,000th Ulam number is 132,788
"1.0s"

For comparison, Julia took 4.5s (9.3s on repl.it), Go took 4.9s, Wren (on tio) 27s, Ring timed out (>60s) on tio before getting the 1,000th number, REXX (also on tio) got to the 1,000th number in 12.3s but timed out before getting the 10,000th, Raku (on repl.it) 9mins 50s, FreeBASIC 17mins 44s, and I cancelled XPL0 (on EXPL32) after 53 minutes. The Haskell entry does not compile for me on either tio or repl.it (The above timings all predate any {{trans|Phix}})

The above algorithm can also yield "The 100,000th Ulam number is 1,351,223" in 1 minute and 40s, for me. (I fully expect translations of this better algorithm to run even faster, btw)

Python

Translation of: XPL0
import time

def ulam(n):
    if n <= 2:
        return n
    mx = 1352000
    lst = [1, 2] + [0] * mx
    sums = [0] * (mx * 2 + 1)
    sums[3] = 1
    size = 2
    while size < n:
        query = lst[size-1] + 1
        while True:
            if sums[query] == 1:
                for i in range(size):
                    sum = query + lst[i]
                    t = sums[sum] + 1
                    if t <= 2:
                        sums[sum] = t
                lst[size], size = query, size + 1
                break
            query += 1
    return query
 
t0 = time.time()
for p in range(5):
    n = 10**p
    print(f"The {n}{'th' if n!=1 else 'st'} Ulam number is {ulam(n)}")

print("\nElapsed time:", time.time() - t0)
Output:
The 1st Ulam number is 1
The 10th Ulam number is 18
The 100th Ulam number is 690
The 1_000th Ulam number is 12_294
The 10_000th Ulam number is 132_788

(Elapsed time: 11.470759391784668 seconds)
Extra
In [1]: %time ulam(100_000)
Wall time: 23min 58s
Out[1]: 1351223

In [37]: 

Raku

my @ulams = 1, 2, &next-ulam … *;

sub next-ulam {
    state $i = 1;
    state @sums = 0,1,1;
    my $last = @ulams[$i];
    (^$i).map: { @sums[@ulams[$_] + $last]++ };
    ++$i;
    quietly ($last ^.. *).first: { @sums[$_] == 1 };
}

for 1 .. 4 {
    say "The {10**$_}th Ulam number is: ", @ulams[10**$_ - 1]
}
Output:
The 10th Ulam number is: 18
The 100th Ulam number is: 690
The 1000th Ulam number is: 12294
The 10000th Ulam number is: 132788

REXX

Translation of: Wren

This REXX version has several speed improvements.

/*REXX program finds & displays the Nth Ulam number (or any number of specified values).*/
parse arg $                                      /*obtain optional argument from the CL.*/
if $='' | $=","  then $= 10 100 1000 10000       /*Not specified? Then use the defaults.*/

        do k=1  for words($)                     /*process each of the specified values.*/
        x= Ulam( word($, k) )                    /*invoke Ulam to find a  Ulam  number. */
        say 'the '        commas(#)th(#)       ' Ulam number is: '           commas(x)
        end   /*k*/
exit 0                                           /*stick a fork in it,  we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
commas: parse arg _;  do jc=length(_)-3  to 1  by -3; _= insert(',', _, jc); end; return _
th:     parse arg th; return word('th st nd rd', 1 + (th//10)*(th//100%10\==1)*(th//10<4))
/*──────────────────────────────────────────────────────────────────────────────────────*/
Ulam: parse arg n;    @.1= 1;   @.2= 2;   #= 2   /*1st two terms;  #:  sequence length. */
                      !.= 0;    !.1= 1;   !.2= 1 /*semaphore for each term in sequence. */
      z= 3                                       /*value of next possible term in seq.  */
                 do until #==n
                 cnt= 0
                        do j=1  for #;        _= z - @.j    /*_:   short circuit value. */
                        if !._  then if @.j\==_  then do;   cnt= cnt + 1
                                                            if cnt>2  then leave
                                                      end
                        end   /*j*/

                 if cnt==2  then do;  #= # + 1              /*bump the number of terms. */
                                      @.#= z                /*add  Z  to the sequence.  */
                                      !.z= 1                /*set the semaphore for  Z. */
                                 end
                 z= z + 1                                   /*bump next possible term.  */
                 end   /*until*/
      return @.#
output   when using the default input of:     10   100   1000   10000
the  10th  Ulam number is:  18
the  100th  Ulam number is:  690
the  1,000th  Ulam number is:  12,294
the  10,000th  Ulam number is:  132,788
output   (courtesy of Paul Kislanko's PC)   when using the input of:     100000
the  100,000th  Ulam number is:  1,351,223

Ring

load "stdlib.ring"

limit = 12500
Ulam = []
add(Ulam,1)
add(Ulam,2)

for n = 3 to limit
    flag = 0
    count = 0
    len = len(Ulam)
    for x = 1 to len-1
        for y = x+1 to len   
            if Ulam[x] + Ulam[y] = n
               flag = 1
               count = count + 1
            ok
        next
     next
     if flag = 1 and count = 1
        add(Ulam,n)
        ln = len(Ulam)
        if ln = 10
           see "The 10th Ulam number is: " + n + nl
        ok
        if ln = 100
           see "The 100th Ulam number is: " + n + nl
        ok
        if ln = 1000
           see "The 1000th Ulam number is: " + n + nl
        ok
        if ln = 10000
           see "The 10000th Ulam number is: " + n + nl
        ok
     ok
next

Output:

The 10th Ulam number is: 18
The 100th Ulam number is: 690
The 1000th Ulam number is: 12294
The 10000th Ulam number is: 132788

Rust

Translation of: Phix
fn ulam(n: usize) -> usize {
    let mut ulams = vec![1, 2];
    let mut sieve = vec![1, 1];
    let mut u = 2;
    while ulams.len() < n {
        sieve.resize(u + ulams[ulams.len() - 2], 0);
        for i in 0..ulams.len() - 1 {
            sieve[u + ulams[i] - 1] += 1;
        }
        for i in u..sieve.len() {
            if sieve[i] == 1 {
                u = i + 1;
                ulams.push(u);
                break;
            }
        }
    }
    ulams[n - 1]
}

fn main() {
    use std::time::Instant;
    let start = Instant::now();
    let mut n = 1;
    while n <= 100000 {
        println!("Ulam({}) = {}", n, ulam(n));
        n *= 10;
    }
    println!("Elapsed time: {:.2?}", start.elapsed());
}
Output:
Ulam(1) = 1
Ulam(10) = 18
Ulam(100) = 690
Ulam(1000) = 12294
Ulam(10000) = 132788
Ulam(100000) = 1351223
Elapsed time: 10.68s

Sidef

Translation of: Perl
func ulam(n) {

    static u     = Set(1,2)
    static ulams = [0, 1, 2]

    return ulams[n] if (ulams.end >= n)

    ++n

    for(var i = 3; true; ++i) {
        var count = 0

        ulams.each {|v|
            if (u.has(i - v) && (v != i-v)) {
                break if (count++ > 2)
            }
        }

        if (count == 2) {
            ulams << i
            u << i
            break if (ulams.len == n)
        }
    }

    ulams.tail
}

for k in (1..3) {
    say "The 10^#{k}-th Ulam number is: #{ulam(10**k)}"
}
Output:
The 10^1-th Ulam number is: 18
The 10^2-th Ulam number is: 690
The 10^3-th Ulam number is: 12294

V (Vlang)

Version 1

Translation of: Go
import time
fn ulam(n int) int {
    mut ulams := [1, 2]
    mut set := {1: true, 2: true}
    mut i := 3
    for {
        mut count := 0
        for j := 0; j < ulams.len; j++ {
            ok := set[i-ulams[j]]
            if ok && ulams[j] != (i-ulams[j]) {
                count++
                if count > 2 {
                    break
                }
            }
        }
        if count == 2 {
            ulams << i
            set[i] = true
            if ulams.len == n {
                break
            }
        }
        i++
    }
    return ulams[n-1]
}
 
fn main() {
    start := time.now()
    for n := 10; n <= 10000; n *= 10 {
        println("The ${n}th Ulam number is ${ulam(n)}")
    }
    println("\nTook ${time.since(start)}")
}
Output:
The 10th Ulam number is 18
The 100th Ulam number is 690
The 1000th Ulam number is 12294
The 10000th Ulam number is 132788

Took 9.611s

Version 2

Translation of: Go

The following version, which builds up a sieve as it goes along, is (astonishingly) about 40 times faster!

import time
fn ulam(n int) int {
    mut ulams := [1, 2]
    mut sieve := [1, 1]
    mut u := 2
    for ulams.len < n {
        s := u + ulams[ulams.len-2]
        t := s - sieve.len
        for i := 0; i < t; i++ {
            sieve << 0
        }
        for i := 1; i <= ulams.len-1; i++ {
            v := u + ulams[i-1] - 1
            sieve[v]++
        }
        mut index := -1
        for i, e in sieve[u..] {
            if e == 1 {
                index = u + i
                break
            }
        }
        u = index + 1
        ulams << u
    }
    return ulams[n-1]
}
 
fn commatize(n int) string {
    mut s := '$n'
    if n < 0 {
        s = s[1..]
    }
    le := s.len
    for i := le - 3; i >= 1; i -= 3 {
        s = '${s[0..i]},${s[i..]}'
    }
    if n >= 0 {
        return s
    }
    return "-$s"
}
 
fn main() {
    start := time.now()
    for n := 1; n <= 10000; n *= 10 {
        mut s := "th"
        if n == 1 {
            s = "st"
        }
        println("The ${commatize(n)}$s Ulam number is ${commatize(ulam(n))}")
    }
    println("\nTook ${time.since(start)}")
}
Output:
The 1st Ulam number is 1
The 10th Ulam number is 18
The 100th Ulam number is 690
The 1,000th Ulam number is 12,294
The 10,000th Ulam number is 132,788

Took 415.000ms

Version 3

Translation of: Go

This version is even quicker than Version 2 and reduces the time needed to calculate the 10,000th and 100,000th Ulam numbers to about 40 milliseconds and 3.25 seconds respectively.

As mentioned in the Wren version 3 example, you need to know how much memory to allocate in advance.

import time
fn ulam(n int) int {
    if n <= 2 {
        return n
    }
    max := 1_352_000
    mut list := []int{len:max+1}
    list[0], list[1] = 1, 2
    mut sums := []byte{len:2*max+1}
    sums[3] = 1
    mut size := 2
    mut query := 0
    for {
        query = list[size-1] + 1
        for {
            if sums[query] == 1 {
                for i in 0..size {
                    sum := query + list[i]
                    t := sums[sum] + 1
                    if t <= 2 {
                        sums[sum] = t
                    }
                }
                list[size] = query
                size++
                break
            }
            query++
        }
        if size >= n {
            break
        }
    }
    return query
}
 
fn commatize(n int) string {
    mut s := '$n'
    if n < 0 {
        s = s[1..]
    }
    le := s.len
    for i := le - 3; i >= 1; i -= 3 {
        s = '${s[0..i]},${s[i..]}'
    }
    if n >= 0 {
        return s
    }
    return "-$s"
}
 
fn main() {
    start := time.now()
    for n := 1; n <= 100000; n *= 10 {
        mut s := "th"
        if n == 1 {
            s = "st"
        }
        println("The ${commatize(n)}$s Ulam number is ${commatize(ulam(n))}")
    }
    println("\nTook ${time.since(start)}")
}
Output:
The 1st Ulam number is 1
The 10th Ulam number is 18
The 100th Ulam number is 690
The 1,000th Ulam number is 12,294
The 10,000th Ulam number is 132,788
The 100,000th Ulam number is 1,351,223

Took 42.912s

Wren

Version 1

Library: Wren-set
import "./set" for Set

var ulam = Fn.new() { |n|
    var ulams = [1, 2]
    var set = Set.new(ulams)
    var i = 3
    while (true) {
        var count = 0
        for (j in 0...ulams.count) {
            if (set.contains(i - ulams[j]) && ulams[j] != (i - ulams[j])) {
                count = count + 1
                if (count > 2) break
            }
        }
        if (count == 2) {
            ulams.add(i)
            set.add(i)
            if (ulams.count == n) break
        }
        i = i + 1
    }
    return ulams[-1]
}

var n = 1
while (true) {
    n = n * 10
    System.print("The %(n)th Ulam number is %(ulam.call(n))")
    if (n == 10000) break
}
Output:
The 10th Ulam number is 18
The 100th Ulam number is 690
The 1000th Ulam number is 12294
The 10000th Ulam number is 132788

Version 2

Translation of: Phix
Library: Wren-seq
Library: Wren-fmt

The above version is reasonably efficient and runs in about 21.6 seconds on my machine (Intel Core i7-8565U). The following version, which builds up a sieve as it goes along, is more than 3 times faster.

import "./seq" for Lst
import "./fmt" for Fmt

var ulam = Fn.new { |n|
    var ulams = [1, 2]
    var sieve = [1, 1]
    var u = 2
    while (ulams.count < n) {
        var s = u + ulams[-2]
        sieve = sieve + ([0] * (s - sieve.count))
        for (i in 1..ulams.count - 1) {
            var v = u + ulams[i-1] - 1
            sieve[v] = sieve[v] + 1
        }
        u = Lst.indexOf(sieve, 1, u) + 1
        ulams.add(u)
    }
    return ulams[n-1]
}

var start = System.clock
for (p in 0..4) {
    var n = 10.pow(p)
    Fmt.print("The $,r Ulam number is $,d", n, ulam.call(n))
}
System.print("\nTook %(System.clock - start) seconds.")
Output:
The 1st Ulam number is 1
The 10th Ulam number is 18
The 100th Ulam number is 690
The 1,000th Ulam number is 12,294
The 10,000th Ulam number is 132,788

Took 6.366709 seconds.

Version 3

Translation of: XPL0

This version is even quicker than Version 2 and reduces the time needed to calculate the 10,000th Ulam number to about 3.65 seconds. It also makes the 100,000th Ulam number a viable proposition for the Wren interpreter coming in at about 6 minutes 50 seconds.

The only downside with this version is that you need to know how much memory to allocate in advance.

import "./fmt" for Fmt

var ulam = Fn.new { |n|
    if (n <= 2) return n
    var max = 1352000
    var list = List.filled(max+1, 0)
    list[0] = 1
    list[1] = 2
    var sums = List.filled(max*2+1, 0)
    sums[3] = 1
    var size = 2
    var query
    while (true) {
        query = list[size-1] + 1
        while (true) {
            if (sums[query] == 1) {
                for (i in 0..size-1) {
                    var sum = query + list[i]
                    var t = sums[sum] + 1
                    if (t <= 2) sums[sum] = t
                }
                list[size] = query
                size = size + 1
                break
            }
            query = query + 1
        }
        if (size >= n) break
    }
    return query
}

var start = System.clock
var n = 10
while (true) {
    Fmt.print("The $,r Ulam number is $,d", n, ulam.call(n))
    n = n * 10
    if (n > 100000) break
}
System.print("\nTook %(System.clock - start) seconds.")
Output:
The 10th Ulam number is 18
The 100th Ulam number is 690
The 1,000th Ulam number is 12,294
The 10,000th Ulam number is 132,788
The 100,000th Ulam number is 1,351,223

Took 409.990502 seconds.

XPL0

Seeing "set" in the Go version and "sieve" in Phix, etc. lit a little light bulb. This version exploits those ideas and finds the 100,000th Ulam number in 24.7 seconds on a Pi4.

func    Ulam(N);                \Return Nth Ulam number
int     N;
def     Max = 1_352_000;        \enough for 100_000th Ulam number
int     List(Max);              \array of Ulam numbers
char    Sums(Max*2);            \array: 0, 1, or more ways to sum Ulams
int     I, Size, Query, Sum, T;
[if N <= 2 then return N;
for I:= 0 to Max*2 do Sums(I):= 0;
List(0):= 1;  List(1):= 2;
Sums(3):= 1;                    \only one way to sum Ulams: 1+2 = 3
Size:= 2;                       \start after first 2 Ulams
repeat  Query:= List(Size-1)+1;                 \possible next Ulam no.
        loop    [if Sums(Query) = 1 then        \sums 1 way so it's next
                    [for I:= 0 to Size-1 do     \update Sums array with
                        [Sum:= Query + List(I); \ all combos of sums
                        T:= Sums(Sum)+1;        \ but limit max count
                        if T <= 2 then Sums(Sum):= T;
                        ];
                    List(Size):= Query;         \add Query to List
                    Size:= Size+1;
                    quit;
                    ];
                Query:= Query+1;                \possible next Ulam no.
                ];
until   Size >= N;
return Query;
];

int  N;
[N:= 10;
repeat  Text(0, "The ");  IntOut(0, N);  
        Text(0, "th Ulam number is ");
        IntOut(0, Ulam(N));  CrLf(0);
        N:= N*10;
until   N > 100_000;
]
Output:
The 10th Ulam number is 18
The 100th Ulam number is 690
The 1000th Ulam number is 12294
The 10000th Ulam number is 132788
The 100000th Ulam number is 1351223