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

Difficulty: introductory

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  # Put u and v into queue
    for _ in range(n):                           # Repeat n times
        w = q & -q                               # Take the smallest candidate
        l = w.bit_length() - 1                   # and its value
        s = seq << l                             # Generate its sums with all previous values
        seq |= w                                 # Append it afterwards to the sequence
        lst.append(l)                            # and to the list
        ex |= s & q                              # Update excluded values if any is already in queue
        q |= s                                   # Put previous sums into queue
        q &= ~ex                                 # Remove excluded values from queue
    return lst                                   # Return sequence list

def ulam_sequence(u0, u1, n):
    # set up variables
    seq = [u0, u1]
    candidates = (u0+u1) * n * [0]
    candidates[u0 + u1] = 1
    num = u1 + 1
    
    for _ in range(n-2):
        # find smallest candidate
        while candidates[num] != 1:
            num += 1
        # adjust list if needed
        if len(candidates) < num * 2:
            candidates.extend([0] * (num * 2 - len(candidates)))
        # calculate new candidates
        for x in seq:
            candidates[num + x] += 1
        # update sequence
        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:                                 # Extract next Ulam number
            last = heappop(q)
            if seen[last] == 1: break
        
        for v in lst:                            # Generate all possible new Ulam numbers, using the last found
            x = v+last
            if x not in seen: heappush(q,x)      # candidate found
            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)
            else:
                if 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] # This is the sequence we are producing.
    sumsDict = dict([(u, 1), (v,1), (u+v, 1)]) # This is a dict of sums so far.  So e.g. 5:2 means there are 2 ways to get 2 terms in the sequence to add to 5.
    sumsHeap = [u, v, u+v] # Sorted list of those sums.
    heapify(sumsHeap) 
    deletedDict = dict() # This is a list of sums that have already reached a value of 2 or more.  No point looking at these again.

    # The idea is to go through the sorted list of sums (previous terms in sequence added together)
    # and find the minimum of those and add that to the sequence.
    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:
                # If it's already in the heap then there are more than one ways to sum to 
                # this value, so remove it, it will never be part of the sequence
                del sumsDict[entry]
                deletedDict[entry] = True
            else:
                # If we haven't already marked it as being seen before (and so, deleted) add it to our heap
                if 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)
            else:
                if n in unique_sums:
                    unique_sums.remove(n)
        unique_sums.remove(next_num)
        seq.append(next_num)
    seq.append(min(unique_sums))
    return seq