This is the performance edition of [this kata](https://www.codewars.com/kata/ulam-sequences). If you didn't do it yet, you should begin there.

---

The Ulam sequence U is defined by `u0=u`, `u1=v`, with the general term `u_n` 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.

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

* Here, the first term after the initial `1, 2` is obviously `3` since `3=1+2`.
* The next term is `4=1+3` (we don't have to worry about `4=2+2` since it is a sum of a single term instead of two distinct terms)
* `5` is not a member of the sequence since it is representable in two ways: `5=1+4=2+3`, but `6=2+4` is a member (since `3+3` isn't a valid calculation).

You'll have to write a code that creates an Ulam Sequence starting with `u0`, `u1` and containing `n` terms.

---

# ___The pitfall...___

While the passing solutions of the first version could have a time complexity of O(N^(3)) (or even O(N^(4))!!), with 20 tests up to 100 terms only, here you'll have to manage generation of sequences up to 1500 terms before time out.

___Inputs:___

* `u0` and `u1`: integers, greater than or equal to 1
* `n`: integer greater than 1, length of the returned list

___Configuration of the tests:___

```if:python
* 6 small fixed tests
* 20 random tests on small sequences (10 to 30 terms)
* 13 large random tests (1500 terms)
```
```if:ruby
* 6 small fixed tests
* 20 random tests on small sequences (10 to 30 terms)
* 16 large random tests (1500 terms)
```
```if:javascript,go
* 6 small fixed tests
* 40 random tests on small sequences (10 to 30 terms)
* 30 large random tests (2450 terms)
```

---

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

Source: codewars | Difficulty: EASY

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

Solutions:
def ulam_sequence(u, v, n):
	(lst, seq, ex, q) = ([], 1, 1, 1 << v | 1 << u)
	for _ in range(n):
		w = q & -q
		l = w.bit_length() - 1
		s = seq << l
		seq |= w
		lst.append(l)
		ex |= s & q
		q |= s
		q &= ~ex
	return lst


def ulam_sequence(u0, u1, n):
	seq = [u0, u1]
	candidates = (u0 + u1) * n * [0]
	candidates[u0 + u1] = 1
	num = u1 + 1
	for _ in range(n - 2):
		while candidates[num] != 1:
			num += 1
		if len(candidates) < num * 2:
			candidates.extend([0] * (num * 2 - len(candidates)))
		for x in seq:
			candidates[num + x] += 1
		seq.append(num)
		num += 1
	return seq


from collections import defaultdict
from heapq import heappop, heappush

def ulam_sequence(u0, u1, n):
	(q, seen, lst) = ([u1], defaultdict(int), [u0])
	seen[u1] = 1
	while len(lst) < n:
		while 1:
			last = heappop(q)
			if seen[last] == 1:
				break
		for v in lst:
			x = v + last
			if x not in seen:
				heappush(q, x)
			seen[x] += 1
		lst.append(last)
	return lst


import heapq

def ulam_sequence(u0, u1, n):
	(seq, h, s) = ([u0, u1], [u0 + u1], set())
	while len(seq) < n:
		v = heapq.heappop(h)
		h = set(h)
		for u in seq:
			if u + v not in s:
				s.add(u + v)
				h.add(u + v)
			elif u + v in h:
				h.remove(u + v)
		seq.append(v)
		h = list(h)
		heapq.heapify(h)
	return seq


def ulam_sequence(u0, u1, n):
	sequence = [u0, u1]
	good = {u0 + u1}
	bad = set()
	while len(sequence) < n:
		k = min(good)
		good.remove(k)
		for h in sequence:
			s = k + h
			if s in good:
				good.remove(s)
				bad.add(s)
			elif s not in bad:
				good.add(s)
		sequence.append(k)
	return sequence


def ulam_sequence(u0, u1, n):
	S0 = {u0 + u1}
	S1 = set()
	a = [u0, u1]
	c = a.append
	for k in range(2, n):
		m = min(S0)
		c(m)
		S0.discard(m)
		T = {a[i] + a[k] for i in range(k)}
		(S0, S1) = (S0 ^ T - S1, S1 | S0 & T)
	return a


def ulam_sequence(u0, u1, n):
	print(u0, u1, n)
	(ans, curr, seto) = ([u0, u1], u1 + 1, {u0, u1})
	while len(ans) < n:
		(temp, ways) = (0, 0)
		for mo in ans:
			if curr - mo in seto and mo != curr - mo:
				temp = curr
				ways += 1
				if ways > 2:
					break
		if ways == 2:
			ans.append(temp)
			seto.add(temp)
		curr += 1
	return ans


def ulam_sequence(u0, u1, n):
	sequence = [u0, u1]
	sums = {u0 + u1}
	unique_sums = {u0 + u1}
	for i in range(n - 3):
		next_num = min(unique_sums)
		for ulam in sequence:
			n = ulam + next_num
			if n not in sums:
				sums.add(n)
				unique_sums.add(n)
			elif n in unique_sums:
				unique_sums.remove(n)
		unique_sums.remove(next_num)
		sequence.append(next_num)
	sequence.append(min(unique_sums))
	return sequence


import time
from heapq import heappush, heappop, heapify

def ulam_sequence(u, v, numTerms):
	terms = [u, v]
	sumsDict = dict([(u, 1), (v, 1), (u + v, 1)])
	sumsHeap = [u, v, u + v]
	heapify(sumsHeap)
	deletedDict = dict()
	while True:
		while True:
			numtoBeAppended = heappop(sumsHeap)
			if numtoBeAppended > terms[-1] and numtoBeAppended in sumsDict:
				break
		terms.append(numtoBeAppended)
		if len(terms) >= numTerms:
			break
		for term in terms[:-1]:
			entry = term + numtoBeAppended
			if entry in sumsDict:
				del sumsDict[entry]
				deletedDict[entry] = True
			elif entry not in deletedDict:
				heappush(sumsHeap, entry)
				sumsDict[entry] = 1
	return terms


def ulam_sequence(u0, u1, n):
	seq = [u0, u1]
	sums = {u0 + u1}
	unique_sums = {u0 + u1}
	for i in range(n - 3):
		next_num = min(unique_sums)
		for num in seq:
			n = num + next_num
			if n not in sums:
				sums.add(n)
				unique_sums.add(n)
			elif n in unique_sums:
				unique_sums.remove(n)
		unique_sums.remove(next_num)
		seq.append(next_num)
	seq.append(min(unique_sums))
	return seq