PY
py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Minimal sum of squares
# Gives the decompositions of n in a minimal number of squares
# Based on Lagrange theorem any integer is a sum of max 4 squares. Thks to Louis for the set idea
# vcc 2018
m=lambda n:(lambda q:min((q[u]*(u>0)+q[n-u] for u in q if n-u in q),key=len))({x*x+y*y:[x]*(x> 0)+[y] for x in range(int(n**.5),-1,-1) for y in range(x,int(n**.5)+1)})
# Legendre : n=3 squares if n != (8k-1)*4**a
for n in [16,15,191,339,384,704,(4**3)*(8*200 -1),12345]:
print(n,m(n))
# Some tricks used here:
# [x]*(x>0)+[y]
#It is a trick to put perfect squares in the set (not just couples) so that i can catch sums of 1,2,3 or 4 squares in one unique loop.
# [x]*n = [x,x,...x] n times.
# (x>0) equals True or 1 if x is positive and False or 0 otherwise
# So [x]*(x>0)+[y] is [x,y] if x!=0 else [y]
# Other trick is building the set in the reverse order so that we have for example 25:[5] replacing 25:[4,3] to ensure we use the smallest option
Enter to Rename, Shift+Enter to Preview
OUTPUT
Run