This kata generalizes [Twice Linear](https://www.codewars.com/kata/5672682212c8ecf83e000050). You may want to attempt that kata first.

## Sequence

Consider an integer sequence `U(m)` defined as:

1. `m` is a given non-empty set of positive integers.
2. `U(m)[0] = 1`, the first number is always 1.
3. For each `x` in `U(m)`, and each `y` in `m`, `x * y + 1` must also be in `U(m)`.
4. No other numbers are in `U(m)`.
5. `U(m)` is sorted, with no duplicates.

### Sequence Examples

#### `U(2, 3) = [1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, ...]`

1 produces 3 and 4, since `1 * 2 + 1 = 3`, and `1 * 3 + 1 = 4`.

3 produces 7 and 10, since `3 * 2 + 1 = 7`, and `3 * 3 + 1 = 10`.

#### `U(5, 7, 8) = [1, 6, 8, 9, 31, 41, 43, 46, 49, 57, 64, 65, 73, 156, 206, ...]`

1 produces 6, 8, and 9.

6 produces 31, 43, and 49.

## Task:

Implement `n_linear` or `nLinear`: given a set of postive integers `m`, and an index `n`, find `U(m)[n]`, the `n`th value in the `U(m)` sequence.

### Tips

* Tests use large n values. Slow algorithms may time-out.
* Tests use large values in the m set. Algorithms which multiply further than neccessary may overflow.
* Linear run time and memory usage is possible.
* How can you build the sequence iteratively, without growing extra data structures?

Difficulty: interview

Starter code:

def n_linear(m,n):
	

Solutions:
from heapq import *

def n_linear(ms, n):
    lst = [1] * (n+1)
    q   = [(1+v,v,1) for v in ms]
    heapify(q)
    for i in range(1,n+1):
        v,x,j  = heappop(q)
        lst[i] = v
        heappush(q, (lst[j]*x+1, x, j+1) )
        while q[0][0]==lst[i]:
            v,x,j = heappop(q)
            heappush(q, (lst[j]*x+1, x, j+1) )
    return lst[n]

from heapq import heappush, heappop

def n_linear(m, n):
    h = [1]
    x = 0
    for _ in range(n+1):
        x = heappop(h)
        while h and h[0] == x:
            heappop(h)
        for y in m:
            a = y * x + 1
            heappush(h, a)
    return x

from collections import deque
from heapq import heappush, heappop


def n_linear(m, n):
    y, h, q = 1, [], {}
    for x in m:
        h.append((y, x))
        q[x] = deque([x * y + 1])
    while n:
        z, w = heappop(h)
        if y != z:
            y = z
            for x in m: q[x].append(x * y + 1)
            n -= 1
        heappush(h, (q[w].popleft(), w))
    return y


from heapq import *

def n_linear(m,n):
    k = [1]
    queue = []
    while len(k) <= n:
        for x in m:
            heappush(queue, x*k[-1]+1)
        k.append(heappop(queue))

        while queue[0] == k[-1]:
            heappop(queue)
    
    return k[-1]

from heapq import *

def n_linear(ms, n):
    lst = [1] * (n+1)
    q   = [(1+v,v,1) for v in ms]
    heapify(q)
    for i in range(1,n+1):
        v,x,j  = heappop(q)
        lst[i] = v
        heappush(q, (lst[j]*x+1, x, j+1) )
        while q[0][0]==lst[i]:
            v,x,j = heappop(q)
            heappush(q, (lst[j]*x+1, x, j+1) )
    print(ms,n)
    return lst[n]

def n_linear(m, n): 
    indxs = {i:0 for i in m}
    u = [1]
    
    while len(u) <= n:
        tmp = [ [k*u[v] + 1, k] for k, v in indxs.items()]
        nxt = min(tmp, key = lambda x: x[0])
        u.append(nxt[0])     
        for i in tmp:
            if i[0] == nxt[0]:
                indxs[i[1]] += 1
    return u[n]

def n_linear(m,n):
    arr = [1]
    ms = list(m)
    idxs = [0] * len(ms)
    r = range(len(ms))
    
    for i in range(n):
        vals = [arr[idxs[j]]*ms[j]+1 for j in r]
        val = min(vals)
        arr.append(val)
        
        for j in r:
            idxs[j] += 1*(val==vals[j])
            
    return arr[n]

def n_linear(m,n):
    arr = [1]
    indices = [0] * len(m)
    r = range(len(m))
    count = 0
    while count < n:
        x = min([arr[indices[i]] * m[i] for i in r])
        for i in r:
            if x == arr[indices[i]] * m[i]:
                indices[i] += 1
        arr.append(x + 1)
        count += 1
        
    return arr[-1]

import heapq

def n_linear_generator(m):
    u = [1]
    s = set(u)

    while True:
        x = heapq.heappop(u)
        yield x
        s.remove(x)

        for y in m:
            z = x * y + 1
            if z not in s:
                heapq.heappush(u, z)
                s.add(z)

memos = {}

def n_linear(m, n):
    m = tuple(m)
    if m not in memos:
        memos[m] = ([], n_linear_generator(m))
        
    past, gen = memos[m]
    past.extend(next(gen) for _ in range(len(past), n + 1))
    return past[n]

def n_linear(m,n):
    if n==0: return 1
    init,dicto=[1],{}.fromkeys(m,0)
    for i in range(n):
        dd = min(k*init[dicto[k]]+1 for k in dicto)
        init.append(dd)
        for k in dicto:
            dicto[k] += init[dicto[k]]*k+1==dd
    return dd