Presentation of the natural number as squares of natural chips, too slow code

[briley]

# Представление натурального числа
# в виде суммы квадратов
# натуральных чисел. 
 
k=int(input())
for i in range(1, k+1):
    if k==i**2:
        print(i)
for i in range(1, k+1):
    for j in range(i, k+1):
        if k==i**2+j**2:
            print(i, j)
for i in range(1, k+1):
    for j in range(i, k+1):
        for l in range(j, k+1):
            if k==i**2+j**2+l**2:
                print(i, j, l) 
for i in range(1, k+1):
    for j in range(i, k+1):
        for l in range(j, k+1):
            for m in range(l, k+1):
                if k==i**2+j**2+l**2+m**2:
                    print(i, j, l, m)

Of course, such an unsatisfactory code is being implemented very slowly, for example, on my home computer, when the number of 2021 came in, the program worked for about a minute, while Wolfram Alpha does the same thing in a second.

Please tell me how to change the code so as to radically speed up the calculation.

[Demir]

Well, in the first approach, you can make this code in your forehead:

def alg(value, data):
    if len(data) > 1:
        return
    for i in range(1, int(value**0.5) + 1):
        res = value - i * i
        if res > 0:
            alg(res, data + [i])
        elif res == 0:
            print(' + '.join(f'{j} * {j}' for j in data + [i]), '=', sum(j * j for j in data + [i]))
alg(int(input('введите число')), [])

The algorithm shall be allocated up to 2 squares, if more necessary, and this number shall be increased:

if len(data) > 1:

If the condition is removed, all possible amounts will be sought, but then, 5 = 1 + 1 + 1 + 1 + 1

Insufficient algorithm, he's looking for all combinations and 5 = 1 + 4 and 5 = 4 + 1♪ The idea is to get rid of these things (e.g., that they're only supposed to be smaller to larger)

That's a better algorithm that doesn't give duplicates.

def alg(value, last = 1, data = []):

if len(data) > 2:

return

for i in range(last, int(value**0.5) + 1):

res = value - i * i

if res > 0:

alg(res, i, data + [i])

elif res == 0:

print(' + '.join(f'{j} * {j}' for j in data + [i]), '=', sum(j * j for j in data + [i]))

alg(1256)

Insufficient algorithm - if you remove the bulb verification at all, the python starts to fight for the refilling of the track (more depth of the function)

But if, as a condition to demand that the layouts be unique, then this condition can be removed and the code will be:

def alg(value, last = 1, data = []):

for i in range(last + 1, int(value**0.5) + 1):

res = value - i * i

if res > 0:

alg(res, i, data + [i])

elif res == 0:

print(' + '.join(f'{j} * {j}' for j in data + [i]), '=', sum(j * j for j in data + [i]))

alg(1256)