Problem:
Problem B: Lagrange's Four-Square Theorem The fact that any positive integer has a representation as the sum of at most four positive
squares (i.e. squares of positive integers) is known as Lagrange’s Four-Square Theorem. The
first published proof of the theorem was given by Joseph-Louis Lagrange in 1770. Your mission
however is not to explain the original proof nor to discover a new proof but to show that the
theorem holds for some specific numbers by counting how many such possible representations
there are. For a given positive integer n, you should report the number of all representations of n as the
sum of at most four positive squares. The order of addition does not matter, e.g. you should
consider 4 2 + 3 2 and 3 2 + 4 2 are the same representation. For example, let’s check the case of 25. This integer has just three representations 1 2 +2 2 +2 2 +4 2 ,
3 2 + 4 2 , and 5 2 . Thus you should report 3 in this case. Be careful not to count 4 2 + 3 2 and
3 2 + 4 2 separately. Input The input is composed of at most 255 lines, each containing a single positive integer less than
2 15 , followed by a line containing a single zero. The last line is not a part of the input data. Output The output should be composed of lines, each containing a single integer. No other characters
should appear in the output. The output integer corresponding to the input integer n is the number of all representations
of n as the sum of at most four positive squares. Sample Input 1
25
2003
211
20007
0 Output for the Sample Input 1
3
48
7
738

Solution (Python):
from math import sqrt
MAX = 2**15-1
ub = int(sqrt(MAX))
square_sum = [[0 for i in range(MAX)] for j in range(4)]
for k in range(1,ub+1):
	square_k = k**2
	square_sum[0][square_k-1] = 1 
	for j in range(3):
		for i in range(1,MAX - square_k + 1):
			if square_sum[j][i-1] >= 1:
				square_sum[j+1][i-1+square_k] += square_sum[j][i-1]
while 1:
	n = int(raw_input())
	if n == 0:
		break
	print sum(square_sum[i][n-1] for i in range(4))

Solution (Python):
a=[[0]*5 for _ in [0]*(1<<15)]
for i in range(int((1<<15)**.5)+1):
    a[i*i][1]+=1
    for j in range(i*i+1,min(4*i*i+1,1<<15)):
        for k in range(2,5):
            a[j][k]+=a[j-i*i][k-1]
while 1:
    n=int(input())
    if n==0:break
    print(sum(a[n]))

Solution (Python):
MAXN = 2**15
MAXRT = int(MAXN**0.5)
MAXTERM = 4

dp = [[0 for n in range(MAXN+1)] for t in range(MAXTERM+1)]
dp[0][0] = 1
for r in range(MAXRT,0,-1):
    for t in range(MAXTERM):
        for n in range(MAXN+1 - r*r):
            if dp[t][n] == 0: continue
            dp[t+1][n + r*r] += dp[t][n]

while True:
    N = int(input())
    if N == 0: break
    print(sum(map(lambda x:x[N],dp)))

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    m = 2**15
    a = [[0]*(m+1) for _ in range(5)]
    a[0][0] = 1
    for i in range(1,m):
        ii = i**2
        if ii > m:
            break
        for k in range(4):
            for j in range(ii,m+1):
                a[k+1][j] += a[k][j-ii]

    def f(n):
        r = 0
        for i in range(5):
            r += a[i][n]
        return r

    while True:
        n = I()
        if n == 0:
            break
        rr.append(f(n))

    return '\n'.join(map(str, rr))


print(main())

Solution (Python):
R = 2**15+1
dp = [[0]*R for i in range(5)]
dp[0][0] = dp[1][0] = dp[2][0] = dp[3][0] = 1
for i in range(1,182):
	for k in range(1,5):
		for j in range(i*i,R):
			dp[k][j] += dp[k-1][j-i*i]

while 1:
	n = input()
	if n == 0: break
	print dp[4][n]

Solution (Python):
R = 2**15+1
r = 182
s = [i*i for i in range(r)]
L = [0]*R
for i in range(r):
	for j in range(i,r):
		for k in range(j,r):
			for l in range(k,r):
				if s[i]+s[j]+s[k]+s[l] < R:
					L[s[i]+s[j]+s[k]+s[l]] += 1

while 1:
	n = input()
	if n == 0: break
	print L[n]

Solution (Python):
def initSquaresArray():
    arr = []
    n = 1
    while True:
        if n * n >= 32768:
            break
        arr.append(n * n)
        n += 1
    return arr

def get2Squares(num):
    global squares
    global memo2

    if num in memo2:
        return memo2[num]

    squareSums = set()
    for square in squares:
        if square >= num:
            break
        if num - square in squares:
            squareSums.add( (min(square, num - square), max(square, num - square)) )
    
    memo2[num] = squareSums
    return memo2[num]

def get3Squares(num):
    global squares
    global memo3

    if num in memo3:
        return memo3[num]

    squareSums = set()
    for square in squares:
        if square >= num:
            break
        other = get2Squares(num - square)
        for o in other:
            a = square
            b = o[0]
            c = o[1]
            tpl = tuple(sorted([ a, b, c ]))
            squareSums.add(tpl)

    memo3[num] = squareSums
    return memo3[num]

def get4Squares(num):
    global squares
    global memo4

    if num in memo4:
        return memo4[num]

    squareSums = set()
    for square in squares:
        if square >= num:
            break
        other = get3Squares(num - square)
        for o in other:
            a = square
            b = o[0]
            c = o[1]
            d = o[2]
            tpl = tuple(sorted([ a, b, c, d ]))
            squareSums.add(tpl)

    memo4[num] = squareSums
    return memo4[num]

if __name__ == '__main__':
    memo2 = {}
    memo3 = {}
    memo4 = {}
    squares = initSquaresArray()
    
    while True:
        num = int(input())
        if num == 0:
            break

        s2 = get2Squares(num)
        s3 = get3Squares(num)
        s4 = get4Squares(num)

        count = 1 if num in squares else 0
        count += len(s2)
        count += len(s3)
        count += len(s4)

        print(count)