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?

Difficulty: introductory

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)]

# generate happy numbers up to LIMIT
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]