Generate Ulam Numbers Given an integer n (where n &lt; 10001) as input, write a program that will output the first n Ulam numbers. An Ulam number is defined as follows:


U1 = 1, U2 = 2.  
For n &gt; 2, Un is the smallest integer which is greater than Un-1 that is the sum of two distinct earlier terms in exactly one way.


For example, U3 is 3 (2+1), U4 is 4 (3+1) (note that (2+2) does not count as the terms are not distinct), and U5 is 6, (U5 is not 5 because 5 can be represented as either 2+3 or 4+1). Here are the first few Ulam numbers:


  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


This is code golf, so the shortest entry wins.
CJam, 47 41 37 bytes

li4,1${__m*{_~&lt;\:+*}%$2/z:^$2=+}*1&gt;&lt;`


Try it online.

Example run

$ cjam &lt;(echo 'li4,1${__m*{_~&lt;\:+*}%$2/z:^$2=+}*1&gt;&lt;`') &lt;&lt;&lt; 26
[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]


How it works

This basic idea is the following:


Start with the array A := [ 0 U₁ U₂ ... Uₖ ].
Compute S, the array of all sums x + y such that x,y ∊ A and x &lt; y.
Discard all non-unique sums from S. Since every Ulam number greater than 2 is both the sum of two smaller ones and the sum of zero and itself, this discards the Ulam numbers U₃, U₄, ... Uₖ.
The remaining array is [ U₁ U₂ Uₖ₊₁ ... ], so the next Ulam number is the third smallest element. Append it to A and go back to step 1.




li                                    " Read one integer (I) from STDIN.                  ";
  4,                                  " Push the array A = [ 0 1 2 3 ].                   ";
    1${                        }*     " Do the following I times:                         ";
       __m*                           " Push the Cartesian product A × A.                 ";
           {       }%                 " For each pair (x,y) in A × A:                     ";
            _~&lt;\:+*                   " Compute (x + y) * (x &lt; y).                        ";
                     $2               " Sort the resulting array.                         ";
                       /              " Split it into chunks of length 2.                 ";
                        z             " Transpose the resulting two-dimensional array.    ";
                         :^           " Compute the symmetric difference of its rows.     ";
                           $          " Sort the resulting array.                         ";
                            2=        " Extract its third element.                        ";
                              +       " Push it on the array A.                           ";
                                 1&gt;   " Discard the first element of A (0).               ";
                                   &lt;  " Discard all but the first I elements of A.        ";
                                    ` " Push a string representation of A.                ";