This kata is based on a [variation](https://www.codewars.com/kata/happy-numbers-5) of *Happy Numbers* by TySlothrop. It is advisable to complete it first to grasp the idea and then move on to this one.

___

Hello, my dear friend, and welcome to another *Happy Numbers* kata! What? You're not interested in them anymore? They are all the same? But what if I say that this one is a *performance version*...  

___

# Your task:

Write a function `performant_numbers` which takes a number `n` as an argument and returns a list of all *happy numbers* from `1` to `n` inclusive. For example:

```
performant_numbers(10)   =>  [1, 7, 10]
performant_numbers(50)   =>  [1, 7, 10, 13, 19, 23, 28, 31, 32, 44, 49]
performant_numbers(100)  =>  [1, 7, 10, 13, 19, 23, 28, 31, 32, 44, 49, 68, 70, 79, 82, 86, 91, 94, 97, 100]
```

# Test suite:

* `5000` tests with number `n` being up to `300000`
* The reference solution takes around `4.9` seconds to calculate the result
* you are not allowed to hardcode the sequence: you'll have to compute it (max length of the code: 1700 characters)

___

Will you take up the challenge?

Source: codewars | Difficulty: EASY

Starter code: def performant_numbers(n, happy_list=sorted(happy_set)):
	

Solutions:
sum_dig = lambda n, D={str(d): d * d for d in range(10)}: sum(map(D.get, str(n)))
is_happy = lambda n: n > 4 and is_happy(sum_dig(n)) or n == 1
happy_set = set(filter(is_happy, range(100)))
for n in range(100, 3 * 10 ** 5):
	if sum_dig(n) in happy_set:
		happy_set.add(n)
from bisect import bisect

def performant_numbers(n, happy_list=sorted(happy_set)):
	return happy_list[:bisect(happy_list, n)]


def is_happy(n):
	while n > 4:
		n = sum(((d - 48) ** 2 for d in str(n).encode()))
	return n == 1
happy = list(filter(is_happy, range(3 * 10 ** 5)))
from bisect import bisect_right

def performant_numbers(n):
	return happy[:bisect_right(happy, n)]


F = [2, 4, 16, 37, 58, 89, 145, 42, 20]
from bisect import bisect

def f(n):
	for i in range(50):
		n = sum((int(i) ** 2 for i in str(n)))
		if n in F:
			return False
		if n == 1:
			return True
H = [i for i in range(1, 300000) if f(i)]

def performant_numbers(n):
	return H[:bisect(H, n)]


LIMIT = 300000
(HAPPY, SAD) = (set(), set())
for n in range(1, LIMIT + 1):
	seen = set()
	while True:
		seen.add(n)
		n = sum((d * d for d in map(int, str(n))))
		if n == 1 or n in HAPPY:
			HAPPY |= seen
			break
		elif n in seen or n in SAD:
			SAD |= seen
			break
HAPPY = sorted(HAPPY)
from bisect import bisect

def performant_numbers(n):
	return HAPPY[:bisect(HAPPY, n)]


b = [False]
a = []
a2 = [None]

def f(n):

	def is_happy(n):
		s = {n}
		while n != 1:
			nn = 0
			while n > 0:
				nn += (n % 10) ** 2
				n //= 10
			n = nn
			if n < len(b):
				return b[n]
			if n in s:
				return False
			s.add(n)
		return True
	for k in range(1, n + 1):
		b.append(is_happy(k))
		if b[k]:
			a.append(k)
		a2.append(len(a))
f(300000)

def performant_numbers(n):
	return a[:a2[n]]


from bisect import bisect
LIMIT = 1 + 300000
happySieve = [None] * LIMIT
happySieve[1] = 1

def happyOnes(n):
	seen = set()
	while 1:
		if happySieve[n] is not None:
			return (happySieve[n], seen)
		if n in seen or n == 1:
			return (n == 1, seen)
		seen.add(n)
		n = sum((int(d) ** 2 for d in str(n)))
for n in range(1, LIMIT):
	(isH, seen) = happyOnes(n)
	for x in seen:
		happySieve[x] = isH
HAPPY = [i for i in range(1, LIMIT) if happySieve[i]]

def performant_numbers(n):
	return HAPPY[:bisect(HAPPY, n)]


from bisect import bisect

def happy_numbers(n):
	happy_list = []
	happy = {1}
	unhappy = set()
	for k in range(1, n + 1):
		i = k
		seen = set()
		while True:
			if i in happy:
				happy_list.append(k)
				happy |= seen
				break
			elif i in unhappy or i in seen:
				unhappy |= seen
				break
			seen.add(i)
			i = sum((int(d) ** 2 for d in str(i)))
	return happy_list
happy_list = happy_numbers(300000)

def performant_numbers(n):
	i = bisect(happy_list, n)
	return happy_list[:i]


from bisect import bisect
sieve = [None] * 300001

def is_happy(n):
	seen = set()
	while True:
		if sieve[n] is not None:
			return (sieve[n], seen)
		if n == 1:
			break
		elif n < 7:
			return (False, seen)
		seen.add(n)
		n = sum((int(x) ** 2 for x in str(n)))
	return (True, seen)
for i in range(1, 300000 + 1):
	(state, seen) = is_happy(i)
	for x in seen:
		sieve[x] = state
FINAL = [1] + [idx for idx in range(1, 300001) if sieve[idx]]

def performant_numbers(n):
	first = 0
	last = len(FINAL) - 1
	idx = float('inf')
	while first <= last:
		mid = (first + last) // 2
		if n == FINAL[mid]:
			idx = mid + 1
			break
		elif n < FINAL[mid]:
			idx = mid
			last = mid - 1
		else:
			first = mid + 1
	return FINAL[:idx]