This the second part part of the kata:

https://www.codewars.com/kata/the-sum-and-the-rest-of-certain-pairs-of-numbers-have-to-be-perfect-squares

In this part we will have to create a faster algorithm because the tests will be more challenging.

The function ```n_closestPairs_tonum()```, (Javascript: ```nClosestPairsToNum()```), will accept two arguments, ```upper_limit``` and ```k```.

The function should return the ```k``` largest pair of numbers [m, n] and the closest to ```upper_limit```. Expressing it in code:

```python
n_closestPairs_tonum(upper_limit, k) #-> [[m1, n1], [m2, n2], ...., [mk, nk]]
```
Such that:
```
upper_limit >= m1 >= m2 >= ....>= mk > 0
```
Examples:
```python
upper_limit = 1000; k = 4
n_closestPairs_tonum(upper_limit, k) == [[997, 372], [986, 950], [986, 310], [985, 864]]

upper_limit = 10000; k = 8
n_closestPairs_tonum(upper_limit, k) == [[9997, 8772], [9997, 2772], [9992, 6392], [9986, 5890], [9985, 7176], [9985, 4656], [9981, 9900], [9973, 9348]]
```
Features of the tests:
```
1000 ≤ upper_limit ≤ 200000
2 ≤ k ≤ 20
```

Enjoy it!

Difficulty: introductory

Starter code:

def n_closestPairs_tonum(num, k):
	

Solutions:
def n_closestPairs_tonum(upper_lim, k):
    square_lim = int((2 * upper_lim) ** .5) + 1
    squares = [n*n for n in range(1, square_lim)]
    p, s = [], set(squares)
    for m in range(upper_lim - 1, 1, -1):
        for b in squares:
            if b >= m: break
            if 2*m - b in s:
                p.append([m, m - b])
                if len(p) == k: return p

def n_closestPairs_tonum(n, k):
    found = []
    for number in range(n-1, 1, -1):
        i, limit = 1, int(number ** .5)
        while i <= limit and len(found) < k:
            sq = i * i
            diff = number - sq
            sq1 = (number + diff) ** .5
            if sq1.is_integer() and diff:
                found.append([number, diff])
            i += 1
        if len(found) == k : break
    return found

from itertools import combinations
from operator import itemgetter
from bisect import bisect_left

# 600 is too low but 700 works, so let's use this
squares = [i*i for i in range(1, 666)]
build = sorted([(x+y)>>1, (x-y)>>1] for y,x in combinations(squares, 2) if x&1 == y&1)
search = list(map(itemgetter(0), build))

# Down to about 7sec total
def n_closestPairs_tonum(num, k):
    n = bisect_left(search, num) - 1
    return build[n:n-k:-1]

def n_closestPairs_tonum(n, k):
    a = [i**2 for i in range(1, int((2*n)**0.5)+1)]
    res = [[(s1+s2)/2, (s2-s1)/2] for i, s1 in enumerate(a) for s2 in a[i+1:] if s1+s2<2*n and (s1+s2)%2==0]
    return sorted(res, key=lambda sl: (-sl[0], -sl[1]))[:k]

def n_closestPairs_tonum(upper_lim, k):
    solution = []
    count = 0
    for i in range(upper_lim - 1, 1, -1):
        second_num = i
        square_num = 1
        while True:
            second_num = i - (square_num ** 2)
            if second_num <= 0:
                break
            elif ((second_num + i) ** 0.5).is_integer():
                solution.append([i, second_num])
                count += 1
                if count ==k:
                    return solution
            square_num += 1


def n_closestPairs_tonum(num, k):
    #m+n=p**2
    #m-n=q**2 => n=m-q**2
    result = []
    for m in range(num-1,1,-1):
        for q in range(1,int(m**.5)):
            n=m-q**2
            if int((m+n)**.5)**2 == m+n:
                result.append([m, n])
                if len(result)==k:
                    return result
    return result

def n_closestPairs_tonum(num, k):
    r = []
    for a in range(int((2 * num - 2) ** 0.5), 1, -1):
        for b in range(min(int((a * a - 1) ** 0.5), int((2 * num - 2 - a * a) ** 0.5)), 0, -1):
            if a % 2 == b % 2:
                r.append([a ** 2 + b ** 2 >> 1, a ** 2 - b ** 2 >> 1])
    return sorted(r, reverse=True)[:k]

from math import sqrt

def n_closestPairs_tonum(num, k):
    # m+n = A^2 , m-n = B^2 ,then m = (A^2+B^2)/2 , n =(A^2-B^2)/2
    # A <= int(sqrt(num*2-1))
    bound = int(sqrt(num*2-1))
    odd_sol = []
    even_sol = []
    if bound % 2 ==1:
        A_square_odd = [i*i for i in list(range(1,bound+1,2))[::-1] ]
        A_square_even = [i*i for i in list(range(2,bound,2))[::-1] ] 
    else:
        A_square_odd = [i*i for i in list(range(1,bound,2))[::-1] ]
        A_square_even = [i*i for i in list(range(2,bound+1,2))[::-1] ] 
    for A_square in A_square_odd:
        for B_square in A_square_odd:
            if len(odd_sol)==num//2:
                break
            if (A_square+B_square)//2<num and (A_square-B_square)//2>0:
                odd_sol.append([(A_square+B_square)//2,(A_square-B_square)//2])
        if len(odd_sol)==num//2:
            break
    for A_square in A_square_even:
        for B_square in A_square_even:
            if len(even_sol)==num//2:
                break
            if (A_square+B_square)//2<num and (A_square-B_square)//2>0:
                even_sol.append([(A_square+B_square)//2,(A_square-B_square)//2])
        if len(even_sol)==num//2:
            break

    ans_li = odd_sol + even_sol
    ans_li.sort(reverse=True)
    return ans_li[:k]

def n_closestPairs_tonum(num, k):
    r=[]
    m=2
    while(m*m<num):
        for n in range(1,m):
            if (m*m+n*n>=num):
                break
            r.append([m*m+n*n,2*m*n])
        m+=1
    return sorted(r,reverse=True)[:k]

def n_closestPairs_tonum(num, k):
    result = []
    squares = []
    for i in range(1, (int)((2 * num) ** 0.5) + 2):
        squares.append(i ** 2)
    squares.reverse()
    for i in range(1, num):
        m = num - i
        np = []
        for s in squares:
            if s > m:
                np.append(s - m)
            else:
                break
        for n in np:
            if (m - n) in squares:
                result.append([m, n])
                if len(result) == k:
                    return result