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?

Source: codewars | Difficulty: MEDIUM_HARD
Tags: Mathematics

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]


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