Question

A positive integer m can be expresseed as the sum of three squares if it is of the form p + q + r where p, q, r ≥ 0, and p, q, r are all perfect squares. For instance, 2 can be written as 0+1+1 but 7 cannot be expressed as the sum of three squares. The first numbers that cannot be expressed as the sum of three squares are 7, 15, 23, 28, 31, 39, 47, 55, 60, 63, 71, … (see Legendre's three-square theorem).

Write a Python function threesquares(m) that takes an integer m as input and returns True if m can be expressed as the sum of three squares and False otherwise. (If m is not positive, your function should return False.)

Answer 1

Answer:def threesquares(n):

list1=[]

flag=False

for i in range(0,100):

for j in range(0,100):

tempVar=(4^i)*(8*j)

list1.append(tempVar)

if n not in list1 and n > 0:

flag = True

else:

flag = False

return(flag)

Explanation:

Answer 2

A Python function threesquares(m) that takes an integer m as input and returns True if m can be expressed as the sum of three squares and False otherwise (If m is not positive, your function should return False) is given below:

def threesquares(m):

   while m > 0 and m % 4 == 0:

       m /= 4

   return m % 8 != 7

for x in range(500):

   if threesquares(x):

       print(x, end=' ,  ')

print( )

• The Legendre's three-square theorem states that a number m is expressible as the sum of three squares if

       m != 4^a(8b+7).

• This python function gives a simple O(log(n)) complexity.