Given an integer n
(where n < 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 > 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.
n
we have to handle? \$\endgroup\$ – Dennis Sep 8 '14 at 2:06