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!

Source: codewars | Difficulty: EASY
Tags: Data structures

Mathematics

Starter code: def n_closestPairs_tonum(num, k):
	

Solutions:
def n_closestPairs_tonum(upper_lim, k):
	square_lim = int((2 * upper_lim) ** 0.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 ** 0.5))
		while i <= limit and len(found) < k:
			sq = i * i
			diff = number - sq
			sq1 = (number + diff) ** 0.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
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))

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):
	result = []
	for m in range(num - 1, 1, -1):
		for q in range(1, int(m ** 0.5)):
			n = m - q ** 2
			if int((m + n) ** 0.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):
	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