The Ulam sequence `U` is defined by `u0 = u`, `u1 = v`, with the general term `uN` for `N > 2` given by the least integer expressible uniquely as the sum of two distinct earlier terms. In other words, the next number is always the smallest, unique sum of any two previous terms.

Complete the function that creates an Ulam Sequence starting with the given `u0` and `u1`, and contains `n` terms.

## Example

The first 10 terms of the sequence `U(u0=1, u1=2)` are: 1, 2, 3, 4, 6, 8, 11, 13, 16, 18.

Let's see it in details:
* The first term after the initial 1, 2 is obviously 3, because 1 + 2 = 3
* The next term is 1 + 3 = 4 (we don't have to worry about 4 = 2 + 2 since it is a sum of a *single term* instead of *distinct terms*)
* 5 is not a member of the sequence since it is representable in two ways: 1 + 4 and 2 + 3
* 6 is a memeber, as 2 + 4 = 6
* etc.


Description Reference: http://mathworld.wolfram.com/UlamSequence.html

---

Performance version: https://www.codewars.com/kata/ulam-sequences-performance-edition

Source: codewars | Difficulty: EASY
Tags: Number theory

Mathematics

Starter code: def ulam_sequence(u0, u1, n):
	

Solutions:
from itertools import combinations
from collections import defaultdict

def ulam_sequence(u0, u1, n):
	seq = [u0, u1, u0 + u1]
	while len(seq) < n:
		candidates = defaultdict(int)
		for (a, b) in combinations(seq, 2):
			candidates[a + b] += 1
		for (num, pairs) in sorted(candidates.items()):
			if num > seq[-1] and pairs == 1:
				seq.append(num)
				break
	return seq


import collections

def ulam_sequence(u0, u1, n):
	possible_sums = {}
	sequence = [u0, u1]
	for _ in range(0, n - 2):
		for term in sequence[:-1]:
			if term + sequence[-1] in possible_sums.keys():
				possible_sums[term + sequence[-1]] += 1
			else:
				possible_sums[term + sequence[-1]] = 1
		possible_sums = collections.OrderedDict(sorted(possible_sums.items()))
		next_term = min([sum for sum in possible_sums.keys() if possible_sums[sum] == 1 and sum not in sequence])
		sequence.append(next_term)
	return sequence


def ulam_sequence(u0, u1, n):
	seq = [u0, u1]
	for _ in range(n - 2):
		sums = sorted([seq[i] + seq[j] for i in range(len(seq)) for j in range(i, len(seq)) if i != j])
		seq.append(next((s for s in sums if sums.count(s) == 1 and s not in seq)))
	return seq


from collections import Counter
from itertools import combinations

def ulam_sequence(u0, u1, n):
	seq = [u0, u1]
	for i in range(n - 2):
		c = Counter((a + b for (a, b) in combinations(seq, 2)))
		x = min((key for key in c if key > seq[-1] and c[key] == 1))
		seq.append(x)
	return seq


import itertools

def ulam_sequence(u0, u1, n):
	arr = [u0, u1]
	temp = u0 + u1
	control = list(map(sum, list(itertools.combinations(arr, 2))))
	while len(arr) != n:
		if control.count(temp) == 1:
			arr.append(temp)
			control = list(map(sum, list(itertools.combinations(arr, 2))))
		temp += 1
	return arr


from collections import Counter

def ulam_sequence(u0, u1, n):
	(seen, lst) = ({u0, u1}, [u0, u1])
	while len(lst) < n:
		c = Counter((v + w for (i, v) in enumerate(lst) for w in lst[i + 1:] if v + w not in seen))
		cnd = min(filter(lambda kv: kv[1] == 1, c.items()), key=lambda kv: kv[0])[0]
		lst.append(cnd)
		seen.add(cnd)
	return lst


def ulam_sequence(u0, u1, n):
	U = [u0, u1]
	next_num = u1 + 1
	while len(U) < n:
		count = 0
		index = 0
		for number in U:
			if next_num - number in U and number != next_num / 2:
				count += 1
			if count >= 3:
				break
		if count < 3 and count > 0:
			U.append(next_num)
		next_num += 1
	return U


ulam_sequence = f = lambda u, v, n, l=set(): v and (l.clear() or l.update({u, v})) or (len(l) >= n and sorted(l)) or l.add(next((y for y in range(max(l) + 1, 2 * max(l)) if sum((2 * x < y and y - x in l for x in l)) == 1))) or f(0, 0, n, l)


def isCandidate(x, seq):
	count = 0
	left_pointer = 0
	right_pointer = len(seq) - 1
	while left_pointer < right_pointer:
		left = seq[left_pointer]
		right = seq[right_pointer]
		if left + right == x:
			count += 1
			if count == 2:
				return False
		if left + right > x:
			right_pointer -= 1
			left_pointer = 0
			continue
		left_pointer += 1
	return count == 1

def ulam_sequence(u0, u1, n):
	seq = [u0, u1]
	x = u0 + u1
	while len(seq) < n:
		if isCandidate(x, seq):
			seq.append(x)
		x += 1
	return seq


def ulam_sequence(U, V, Q):
	R = [U, V]
	S = [U + V]
	while len(R) < Q:
		while 1 < len(S) and S[-1] == S[-2]:
			T = S.pop()
			while T == S[-1]:
				S.pop()
		T = S.pop()
		S.extend((T + V for V in R))
		R.append(T)
		S.sort(reverse=True)
	return R