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

• ``````# Представление натурального числа
# в виде суммы квадратов
# натуральных чисел.

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.

• 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)
``````

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2